Coursd'arithm´etique Premi`erepartie

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.
1Liste 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.
2Table 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 un
b
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