Cours d'arithmétique

Sujets

• maths
• exercice
• cours
• exercices
• exercice de

Informations

• Publié par: Chiwyir
• Nombre de lectures: 450
• Langue: Français

Extrait

Cours d’arithm´etique Premi`ere partie Pierre Bornsztein Xavier Caruso Pierre Nolin Mehdi Tibouchi D´ecembre 2004 Ce document est la premi`ere partie d’un cours d’arithm´etique ´ecrit pour les ´el`eves pr´e- parant les olympiades internationales de math´ematiques. Le plan complet de ce cours est : 1. Premiers concepts 2. Division euclidienne et cons´equences 3. Congruences ´4. Equations diophantiennes 5. Structure de Z/nZ 6. Sommes de carr´es 7. Polynˆomes `a coefficients entiers 8. Fractions continues Cette premi`ere partie traite les quatre premiers chapitres. Les quatre derniers chapitres forment quant a` eux la deuxi`eme partie de ce cours. Contrairement `a la seconde partie, cette premi`ere partie se veut le plus ´el´ementaire possible.Lesnotionsabstraites,souventplusdifficiles`aassimiler,maisquiclarifientlesid´ees lorsqu’elles sont comprises, ne sont ´evoqu´ees que dans la seconde partie. Nous conseillons au lecteur de bien maˆıtriser ce premier tome avant de passer a` la lecture du second. Les notions et les th´eor`emes introduits ici sont g´en´eralement tout `a fait suffisants pour traiter les exercices propos´ees aux olympiades internationales de math´ematiques. Voustrouverez`alafindechaquechapitreunes´eried’exercicesdedifficult´evariablemais 1indiqu´ee par des ´etoiles . Toutes les solutions sont rassembl´ees `a la fin du document. Nous vous souhaitons bon apprentissage et bonne lecture. 1Plus nous avons jug´e l’exercice difficile, plus le nombre d’´etoiles est important. 1Liste des abbr´evations : AMM American Mathematical Monthly APMO The Asian Pacific Mathematics Olympiad CG Concours g´en´eral OIM Olympiades Internationales de Math´ematiques SL Short List TDV Tournoi Des Villes Liste des notations : ? ensemble vide N ensemble des entiers naturels (positifs ou nuls) ?N ensemble des entiers naturels strictement positifs Z ensemble des entiers relatifs Q ensemble des nombres rationnels R ensemble des nombres r´eels P 2symbˆole de sommationQ 3symbˆole de produit a|b a divise b [x] partie enti`ere de x {x} partie d´ecimale 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 v (n) valuation p-adique de np d(n) nombre de diviseurs positifs de n σ(n) somme des diviseurs positifs de n ϕ fonction indicatrice d’Euler s (n) somme des chiffres de n en base bb π(n) nombre de nombres premiers inf´erieurs ou ´egaux `a n ba ...a ´ecriture en base bn 0 n! factorielle de n : n!=1×2×···×n k k n!C coefficient binomial : C =n n k!(n−k)! u ∼v les suites (u ) et (v ) sont ´equivalentesn n n n 2Une somme index´ee par l’ensemble vide est ´egale `a 0. 3Un produit index´e par l’ensemble vide est ´egale `a 1. 2Table des mati`eres 1 Premiers concepts 4 1.1 Divisibilit´e . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4 1.2 Nombres premiers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9 1.3 Valuation p-adique . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12 1.4 Quelques fonctions arithm´etiques . . . . . . . . . . . . . . . . . . . . . . . . 14 1.5 Nombres rationnels . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15 1.6 Exercices. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17 2 Division euclidienne et cons´equences 24 2.1 Division euclidienne et d´ecomposition en base b . . . . . . . . . . . . . . . . 24 2.2 Algorithme d’Euclide . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27 2.3 Algorithme d’Euclide ´etendu et th´eor`eme de B´ezout . . . . . . . . . . . . . . 28 2.4 Lemme de Gauss et cons´equences . . . . . . . . . . . . . . . . . . . . . . . . 29 2.5 Exercices. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32 3 Congruences 37 3.1 D´efinition, premi`eres propri´et´es . . . . . . . . . . . . . . . . . . . . . . . . . 37 3.2 Crit`eres de divisibilit´e . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38 3.3 Ordre d’un ´el´ement . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39 3.4 Th´eor`eme chinois . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40 3.5 Congruences modulo p . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43 n3.6 Congruences modulo p . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45 3.7 Coefficients binomiaux . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47 3.8 Exercices. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51 ´4 Equations diophantiennes 56 4.1 Quelques r´eflexes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 56 4.2 Utilisation des congruences . . . . . . . . . . . . . . . . . . . . . . . . . . . . 59 4.3 Descente infinie . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 62 ´4.4 Equations de degr´e 2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 65 ´4.5 Equations de degr´e 3 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 68 4.6 Exercices. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 70 5 Corrig´e des exercices 75 5.1 Exercices de «Premiers concepts » . . . . . . . . . . . . . . . . . . . . . . . 75 5.2 Exercices de «Division euclidienne et cons´equences » . . . . . . . . . . . . . 103 5.3 Exercices de «Congruences » . . . . . . . . . . . . . . . . . . . . . . . . . . 118 ´5.4 Exercices de «Equations diophantiennes » . . . . . . . . . . . . . . . . . . . 143 3+ + + + + 6 6 + + + 1 Premiers concepts Cette section, comme son nom l’indique, pr´esente le concept de base de l’arithm´etique, a` savoir la divisibilit´e. On introduit ensuite les nombres premiers ce qui permet d’´enoncer le th´eor`emefondamentaldel’arithm´etique(c’est-a`-direlad´ecompositionenfacteurspremiers) dans lequel les nombres premiers jouent le rˆole de briques ´el´ementaires pour la fabrication des nombres. 1.1 Divisibilit´e D´efinition 1.1.1 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. Propri´et´es aSi a et b sont deux entiers avec b=0, b divise a si et seulement si la fraction est unb entier. 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. Sia|b ,b ,...,b ,alorsa|b c +b c +...+b c ,quelsquesoientlesentiersc ,c ,...,c .1 2 n 1 1 2 2 n n 1 2 n Si a divise b et b=0, alors|a|6|b|. Si a divise b et b divise a, alors a=±b. n nSi a et b sont deux entiers tels que a |b pour un entier n>1, alors a|b. Touteslespropri´et´eslist´eespr´ec´edemmentsontimm´ediates,`al’exceptiondeladerni`eredont la d´emonstration n’est pas triviale sans bagage arithm´etique. Une preuve possible consiste a` utiliser la caract´erisation de la divisibilit´e par les valuations p-adiques (voir paragraphe 1.3). Voyons imm´ediatement deux exercices qui montrent comment on peut manipuler la no- tion de divisibilit´e : Exercice : Soient x et y des entiers. Montrer que 2x+3y est divisible par 7 si et seulement si 5x+4y l’est. Solution : Supposons que 7 divise 2x+3y, alors il divise 6(2x+3y)−7(x+2y)=5x+4y.√ R´eciproquement si 7 divise 5x+4y, il divise 6(5x+4y)−7(4x+3y)=2x+3y. 2Exercice : Pour quels entiers n strictement positifs, le nombre n +1 divise-t-il n+1? 2 2Solution : Si n +1 divise n+1, comme tout est positif, on doit avoir n +16n+1, ce qui√ n’est v´erifi´e que pour n=1. On v´erifie ensuite que n=1 est bien solution. 4+ + + + + + Parties enti`eres D´efinition 1.1.2 Si x est un r´eel, on appelle partie enti`ere de x, et on note [x], le plus grand entier inf´erieur ou ´egal `a x. Ainsi, on a [x]6x<[x]+1. Remarque. On d´efinit aussi la partie d´ecimale de x, comme la diff´erence x−[x]. La partie d´ecimale de x est souvent not´ee{x}. Cette notion est moins utilis´ee que la notion de partie enti`ere et les conventions de notations sont moins usuelles `a ce propos : lors d’un exercice, oud’unexpos´e,ilesttoujoursdebongouˆtdecommencerparpr´eciserlesnotationsquivont ˆetre employ´ees par la suite. Notonsqu’ilfautˆetreprudentaveclesnombresn´egatifs:autantpourlesnombrespositifs, la partie enti`ere correspond au nombre auquel on retire ses chiffres apr`es la virgule, autant ce n’est pas le cas pour les nombres n´egatifs. En effet, si on suit la d´efinition, on voit par exemple que [−3,5]=−4. Les parties enti`eres et parties d´ecimales ob´eissent a` quelques propri´et´es´el´ementaires que nous listons ci-dessous : Propri´et´es ´el´ementaires On a toujours x=[x]+{x}. Pour tout r´eel x, on a x−1<[x]6x Si x est entier, [x] = x et {x} = 0. Et r´eciproquement si l’une des deux ´egalit´es est v´erifi´ee, alors x est entier. [−x]=−[x]−1 sauf si x est entier, auquel cas [−x]=−[x]. Si x et y sont deux r´eels, [x]+[y]6[x+y]6[x]+[y]+1. xSi m > 0 est un entier, alors il y a exactement [ ] multiples de m compris entre 1 etm x. La d´emonstration des propri´et´es consiste en de simples manipulations de la d´efinition et principalement de l’in´egalit´e [x]6 x < [x]+1. Elle est laiss´ee au lecteur. On remarquera que tr`es souvent les questions faisant intervenir des parties enti`eres se r´esument `a de la manipulation d’in´egalit´es comme le montre par exemple l’exercice suivant : Exercice : On suppose que 4n+2 n’est pas le carr´e 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’in´egalit´e : √ √√ n+ n+1< 4n+2 √ √ 2 2En effet, en ´elevant au carr´e, on a a` comparer 2n+1+2 n +n et 4n+2, soit 2 n +n et 2n+1 et l’in´egalit´e devient ´evidente apr`es une nouvelle ´el´evation au carr´e. Il reste `a prouver qu’il n’existe aucun entier k tel que : √ √√ n+ n+1