Cours d’arithm´etique - Bienvenue sur le site de la ...

1 Cours d'arithme tique Premie re partie Pierre Bornsztein Xavier Caruso Pierre Nolin Mehdi Tibouchi De cembre 2004. Ce document est la premie re partie d'un Cours d'arithme tique e crit pour les e le ves pre - parant les olympiades internationales de mathe matiques. Le plan complet de ce Cours est : 1. Premiers concepts 2. Division euclidienne et conse quences 3. Congruences 4. E quations diophantiennes 5. Structure de Z/nZ. 6. Sommes de carre s 7. Polyno mes a coefficients entiers 8. Fractions continues Cette premie re partie traite les quatre premiers chapitres. Les quatre derniers chapitres forment quant a eux la deuxie me partie de ce Cours . Contrairement a la seconde partie, cette premie re partie se veut le plus e le mentaire possible. Les notions abstraites, souvent plus difficiles a assimiler, mais qui clarifient les ide es lorsqu'elles sont comprises, ne sont e voque es que dans la seconde partie.

2 Nous conseillons au lecteur de bien ma triser ce premier tome avant de passer a la lecture du second. Les notions et les the ore mes introduits ici sont ge ne ralement tout a fait suffisants pour traiter les exercices propose es aux olympiades internationales de mathe matiques. Vous trouverez a la fin de chaque chapitre une se rie d' exercices de difficulte variable mais indique e par des e toiles1 . Toutes les solutions sont rassemble es a la fin du document. Nous vous souhaitons bon apprentissage et bonne lecture. 1. Plus nous avons juge l'exercice difficile, plus le nombre d'e toiles est important. 1. Liste des abbre vations : AMM American Mathematical Monthly APMO The Asian Pacific Mathematics Olympiad CG Concours ge ne ral OIM Olympiades Internationales de Mathe matiques SL Short List TDV Tournoi Des Villes Liste des notations : ensemble vide N ensemble des entiers naturels (positifs ou nuls).

3 N? ensemble des entiers naturels strictement positifs Z ensemble des entiers relatifs Q ensemble des nombres rationnels R ensemble des nombres re els P. Q symbo le de sommation2. symbo le de produit3. a|b a divise b [x] partie entie re de x {x} partie de cimale de x pgcd plus grand commun diviseur a b pgcd (a, b). ppcm plus petit commun multiple a b ppcm (a, b). a b (mod N ) a est congru a b modulo N. p un nombre premier vp (n) valuation p-adique de n d(n) nombre de diviseurs positifs de n (n) somme des diviseurs positifs de n fonction indicatrice d'Euler sb (n) somme des chiffres de n en base b (n) nombre de nombres premiers infe rieurs ou e gaux a n an .. a 0 b e criture en base b n! factorielle de n : n! = 1 2 n Ckn coefficient binomial : Ckn = k!(n k)! n! un v n les suites (un ) et (vn ) sont e quivalentes 2. Une somme indexe e par l'ensemble vide est e gale a 0. 3. Un produit indexe par l'ensemble vide est e gale a 1.

4 2. Table des matie res 1 Premiers concepts 4. Divisibilite .. 4. Nombres premiers .. 9. Valuation p-adique .. 12. Quelques fonctions arithme tiques .. 14. Nombres rationnels .. 15. exercices .. 17. 2 Division euclidienne et conse quences 24. Division euclidienne et de composition en base b .. 24. Algorithme d'Euclide .. 27. Algorithme d'Euclide e tendu et the ore me de Be zout .. 28. Lemme de Gauss et conse quences .. 29. exercices .. 32. 3 Congruences 37. De finition, premie res proprie te s .. 37. Crite res de divisibilite .. 38. Ordre d'un e le ment .. 39. The ore me chinois .. 40. Congruences modulo p .. 43. Congruences modulo pn .. 45. Coefficients binomiaux .. 47. exercices .. 51. 4 E quations diophantiennes 56. Quelques re flexes .. 56. Utilisation des congruences .. 59. Descente infinie .. 62. E quations de degre 2 .. 65. E quations de degre 3 .. 68. exercices .. 70.

5 5 Corrige des exercices 75. exercices de Premiers concepts .. 75. exercices de Division euclidienne et conse quences .. 103. exercices de Congruences .. 118. exercices de E quations diophantiennes .. 143. 3. 1 Premiers concepts Cette section, comme son nom l'indique, pre sente le concept de base de l'arithme tique, a savoir la divisibilite . On introduit ensuite les nombres premiers ce qui permet d'e noncer le the ore me fondamental de l'arithme tique (c'est-a -dire la de composition en facteurs premiers). dans lequel les nombres premiers jouent le ro le de briques e le mentaires pour la fabrication des nombres. Divisibilite . De finition Si a et b sont deux entiers, on dit que a divise b, ou que b est divisible par a, s'il existe un entier q tel que b = aq. On dit encore que a est un diviseur de b, ou que b est un multiple de a. On le note a|b. Proprie te s a Si a et b sont deux entiers avec b 6= 0, b divise a si et seulement si la fraction b est un entier.

6 Tous les entiers divisent 0, et sont divisibles par 1. Un entier n est toujours divisible par 1, 1, n et n. Si a|b, et b|c, alors a|c. Si a|b1 , b2 , .. , bn , alors a|b1 c1 +b2 c2 +..+bn cn , quels que soient les entiers c1 , c2 , .. , cn . Si a divise b et b 6= 0, alors |a| 6 |b|. Si a divise b et b divise a, alors a = b. Si a et b sont deux entiers tels que an |bn pour un entier n > 1, alors a|b. Toutes les proprie te s liste es pre ce demment sont imme diates, a l'exception de la dernie re dont la de monstration n'est pas triviale sans bagage arithme tique. Une preuve possible consiste a utiliser la caracte risation de la divisibilite par les valuations p-adiques (voir paragraphe ). Voyons imme diatement deux exercices qui montrent comment on peut manipuler la no- tion de divisibilite : Exercice : Soient x et y des entiers. Montrer que 2x + 3y est divisible par 7 si et seulement si 5x + 4y l'est.

7 Solution : Supposons que 7 divise 2x + 3y, alors il divise 6 (2x + 3y) 7 (x + 2y) = 5x + 4y.. Re ciproquement si 7 divise 5x + 4y, il divise 6 (5x + 4y) 7 (4x + 3y) = 2x + 3y. Exercice : Pour quels entiers n strictement positifs, le nombre n2 + 1 divise-t-il n + 1 ? Solution : Si n2 + 1 divise n + 1, comme tout est positif, on doit avoir n2 + 1 6 n + 1, ce qui . n'est ve rifie que pour n = 1. On ve rifie ensuite que n = 1 est bien solution. 4. Parties entie res De finition Si x est un re el, on appelle partie entie re de x, et on note [x], le plus grand entier infe rieur ou e gal a x. Ainsi, on a [x] 6 x < [x] + 1. Remarque. On de finit aussi la partie de cimale de x, comme la diffe rence x [x]. La partie de cimale de x est souvent note e {x}. Cette notion est moins utilise e que la notion de partie entie re et les conventions de notations sont moins usuelles a ce propos : lors d'un exercice, ou d'un expose , il est toujours de bon gou t de commencer par pre ciser les notations qui vont e tre employe es par la suite.

8 Notons qu'il faut e tre prudent avec les nombres ne gatifs : autant pour les nombres positifs, la partie entie re correspond au nombre auquel on retire ses chiffres apre s la virgule, autant ce n'est pas le cas pour les nombres ne gatifs. En effet, si on suit la de finition, on voit par exemple que [ 3, 5] = 4. Les parties entie res et parties de cimales obe issent a quelques proprie te s e le mentaires que nous listons ci-dessous : Proprie te s e le mentaires On a toujours x = [x] + {x}. Pour tout re el x, on a x 1 < [x] 6 x Si x est entier, [x] = x et {x} = 0. Et re ciproquement si l'une des deux e galite s est ve rifie e, alors x est entier. [ x] = [x] 1 sauf si x est entier, auquel cas [ x] = [x]. Si x et y sont deux re els, [x] + [y] 6 [x + y] 6 [x] + [y] + 1. x Si m > 0 est un entier, alors il y a exactement [ m ] multiples de m compris entre 1 et x. La de monstration des proprie te s consiste en de simples manipulations de la de finition et principalement de l'ine galite [x] 6 x < [x] + 1.

9 Elle est laisse e au lecteur. On remarquera que tre s souvent les questions faisant intervenir des parties entie res se re sument a de la manipulation d'ine galite s comme le montre par exemple l'exercice suivant : Exercice : On suppose que 4n + 2 n'est pas le carre d'un nombre entier. Montrer que pour n > 0, on a : h i h i . n+ n+1 = 4n + 2. Solution : Remarquons tout d'abord que l'on a toujours l'ine galite : . n + n + 1 < 4n + 2.. En effet, en e levant au carre , on a a comparer 2n + 1 + 2 n2 + n et 4n + 2, soit 2 n2 + n et 2n + 1 et l'ine galite devient e vidente apre s une nouvelle e le vation au carre . Il reste a prouver qu'il n'existe aucun entier k tel que : . n + n + 1 < k 6 4n + 2. 5. soit, encore en e levant au carre qu'il n'existe aucun entier k tel que : . 2n + 1 + 2 n2 + n < k 2 6 4n + 2.. Mais il est clair que 4n + 1 < 2n + 1 + 2 n2 + n et un tel entier k ve rifirait a fortiori 4n + 1 < k 2 6 4n + 2.

10 Comme k est entier, il vient force ment k 2 = 4n + 2, mais cela n'est . pas possible puisque l'on a suppose que 4n + 2 n'e tait pas le carre d'un entier. Remarque. En fait, 4n + 2 n'est jamais le carre d'un entier. En effet, le nombre 4n + 2 est pair, et s'il e tait le carre d'un entier, il serait le carre d'un entier pair. Mais alors 4n + 2. devrait e tre un multiple de 4, ce qui n'est, a l'e vidence, pas le cas. L'e galite pre ce dente de parties entie res est donc valable pour tout entier n > 1, sans hypothe se supple mentaire. Une proprie te amusante des parties entie res qui montre e galement que parfois (souvent). les manipulations d'ine galite s ne sont pas faciles est le the ore me de Beatty que voici : The ore me (Beatty) Soient et deux re els strictements positifs. On note S . (resp. S ) l'ensemble des entiers strictement positifs qui s'e crivent sous la forme [n ] (resp.)