Coursd'arithm´etique Premi`erepartie

Description

• cours - matière potentielle : arithmetique ecrit pour les eleves pre
• cours - matière potentielle : arithmetique premiere partie

Cours d'arithmetique Premiere partie Pierre Bornsztein Xavier Caruso Pierre Nolin Mehdi Tibouchi Decembre 2004 Ce document est la premiere partie d'un cours d'arithmetique ecrit pour les eleves pre- parant les olympiades internationales de mathematiques. Le plan complet de ce cours est : 1. Premiers concepts 2. Division euclidienne et consequences 3. Congruences 4. Equations diophantiennes 5. Structure de Z/nZ 6. Sommes de carres 7. Polynomes a coefficients entiers 8.

• internationales de mathematiques sl
• etant par convention egal
• formule precedente
• symbole de sommation2∏ symbole de produit3
• inegalite
• coefficients entiers
• entière
• entiers
• entier
• exercice
• exercices

Sujets

• Caruso
• Symbole
• Exercice
• Coefficient
• Entier relatif
• Precedente
• Inégalité
• Mathématiques

Informations

• Publié par: zeap
• Nombre de lectures: 35
• 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.
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