Christophe Bertault — Mathématiques en MPSI ARITHMÉTIQUE DES ENTIERS
DIVISIBILITÉ, DIVISION EUCLIDIENNE ————————————–
ET CONGRUENCES Montrer que pour tous n ∈ N∗ et a, b ∈ Z :
7
a ≡ b [n] =⇒ a n ≡ b n n2 .
Vrai ou faux ? Justifier. Soient d, m, n, a ∈ Z.
1
1) 2m 3n possède mn diviseurs positifs. ————————————–
2) ¹1, 1000º contient 140 entiers divisibles par 7.
3) Si a et b divisent d, alors a b aussi. Soit (un )n∈N une suite réelle sous-additive, i.e. pour
8
4) d divise a b ¦si et seulement si ©d divise a ou b. laquelle um+n ¶ um + un pour tous m, n ∈ N. Montrer le
un uk
5) L’ensemble p − q | p, q ∈ P contient 19. lemme sous-additif de Fekete : −−−−−→ inf∗ ,
n n → +∞ k∈N k
6) d divise n2 si et seulement si d divise n. où la borne inférieure est calculée dans R.
7) a2 ≡ 1 [n] si et seulement si a ≡ ±1 [n].
8) Si 4a ≡ 4b [13], alors a ≡ b [13]. ————————————–
9) Si 4a ≡ 4b [6], alors a ≡ b [6].
10) Si a ≡ b [n], alors d a ≡ d b [n].
11) Si a ≡ b [6], alors 2a ≡ 2 b [9].
NOMBRES PREMIERS
12) Si tout diviseur premier de n est congru à ±1 mo- ET VALUATIONS p-ADIQUES
dulo 8, alors n ≡ ±1 [8]. Et la réciproque ?
————————————– Pour tout n ∈ N∗ , on note pn le nème nombre pre-
9
mier. Montrer que pour tout n ¾ 2 : pn+1 < p1 . . . pn .
2 ————————————–
1) Montrer que 2123 + 3121 est divisible par 11.
2) Calculer le reste de la division euclidienne :
a) de 32189 par 25. b) de 4990021 par 13. 10
1) Soient a ¾ 2 et n ¾ 2.
a) Montrer que si a n − 1 premier, alors a = 2 et n
————————————–
est premier.
Soit n ∈ N. On note a0 , . . . , a r les chiffres de la b) Montrer que si a n + 1 est premier, alors a est
3 pair et n est une puissance de 2.
décomposition de n en base 10.
Par exemple, (a0 , a1 , a2 ) = (6, 5, 1) pour n = 156. Les nombres premiers de la forme 2 p −1 avec p ∈ P
1) Montrer que n est divisible par 4 si et seulement sont dit de Mersenne. On ignore s’il en existe une
si l’entier obtenu en ne conservant que les chiffres infinité, mais on conjecture que oui.
n
a0 et a1 l’est. 2) Pour tout n ∈ N, Fn = 22 + 1 est appelé le nème
2) Montrer que n est divisible par 3 (resp. 9) si et nombre de Fermat. On conjecture que parmi ces en-
seulement si la somme a0 + . . . + a r l’est. tiers, seul F0 , . . . , F4 sont premiers.
3) Déterminer une condition nécessaire et suffisante a) Montrer que Fn+1 = F0 . . . Fn +2 pour tout n ∈ N.
sur a0 , . . . , a r pour que n soit divisible par 11. b) En déduire que Fm ∧ Fn = 1 pour tous m, n ∈ N
distincts.
————————————–
————————————–
4
1) Montrer que n(n + 2)(7n − 5) est divisible par 11
6 pour tout n ∈ Z. 1) a) Montrer que tout entier naturel congru à 3 mo-
2) Déterminer tous les entiers n ∈ Z pour lesquels dulo 4 possède au moins un diviseur premier
n + 1 divise n + 7. congru à 3 modulo 4.
3) Déterminer tous les entiers n ∈ Z pour lesquels b) Montrer qu’il existe une infinité de nombres
n2 + (n + 1)2 + (n + 3)2 est divisible par 10. premiers congrus à 3 modulo 4.
4) Déterminer tous les nombres premiers p pour 2) Montrer qu’il existe une infinité de nombres pre-
lesquels 3p + 4 est un carré parfait. miers congrus à 5 modulo 6.
5) Déterminer tous les entiers n ∈ N pour les-
————————————–
quels n(n + 2) est une puissance de 2. Et si n ∈ Z ?
————————————– Soient a, b ∈ Z et n ∈ N∗ . Montrer que si a n divise
12 n
b , alors a divise b.
Soient x, y, z ∈ Z.
5 ————————————–
1) Montrer que x 2 + y 2 est divisible par 7 si et seule-
ment si x et y le sont. Soit n ∈ N. Montrer que si n est à la fois un
2) Montrer que si x 3 + y 3 + z 3 est divisible par 7, l’un 13
carré parfait et un cube parfait, alors il est la puissance
des entiers x, y ou z l’est aussi. sixième d’un entier.
————————————– ————————————–
Montrer que p2 ≡ 1 [24] pour tout p ∈ P supérieur Montrer que (a ∧ b)n = a n ∧ b n pour tous a, b ∈ Z
6 14
ou égal à 5. et n ∈ N.
1
Christophe Bertault — Mathématiques en MPSI ARITHMÉTIQUE DES ENTIERS
————————————– 3) Montrer que si a ∧ n = 1, alors :
(a b) ∧ n = b ∧ n.
15
1) Montrer que pour tous p ∈ P et n ∈ N : 4) Montrer que :
+∞X n n4 + 3n2 − n + 2 ∧ n2 + n + 1 = (n − 2) ∧ 7.
vp n! = (formule de Legendre),
k=1
pk 5) Simplifier (a + b) ∧ (a ∨ b).
n 6) Montrer que si a et b sont strictement positifs
où la somme est faussement infinie car k
=0
∗ k p et premiers entre eux, l’application (x, y) 7−→ x y
pour tout k ∈ N pour lequel p > n.
2) Par combien de zéros l’entier 1000! s’achève-t-il ? est bijective de div+ (a) × div+ (b) sur div+ (a b), où
div+ (k) est l’ensemble des diviseurs positifs de k
————————————– pour tout k ∈ N∗ .
————————————–
16 ∗
1) Montrer que pour tout n ∈ N , n divise (n − 1)! si
et seulement si n n’est ni égal à 4, ni premier. Soient a, b ∈ N∗ . À quelle condition nécessaire
24
2) Soit p ∈ P supérieur à 7. Montrer que (p − 1)! + 1 et suffisante existe-t-il deux entiers x, y ∈ N∗ pour les-
n’est pas une puissance de p. quels x ∨ y = a et x y = b ?
————————————–
————————————–
X
n
1 25
Montrer que pour tout n ¾ 2, n’est pas 1) Soient x ∈ Z et n ∈ N∗ premiers entre eux.
17 k
k=1 un entier. a) Pourquoi l’application qui associe à tout entier
k ∈ ¹0, nº le reste de la division euclidienne
————————————– de x k par n n’est-elle pas injective ? En déduire
que pour un certain N ∈ ¹1, nº : x N ≡ 1 [n].
Déterminer tous les entiers n ∈ N∗ pour lesquels
18 b) Montrer qu’on peut choisir N inférieur à l’en-
2 divise 3n − 1.
n
¦ ©
tier ϕ(n) = k ∈ ¹0, n − 1º | k ∧ n = 1 .
————————————–
La fonction ϕ est appelée l’indicatrice d’Euler.
2) Soit p ∈ P.
p
PGCD, PPCM a) Montrer que p divise
k
pour tout k ∈ ¹1, p−1º.
ET NOMBRES PREMIERS ENTRE EUX b) En déduire que (x + y) p ≡ x p + y p [p] pour
tous x, y ∈ Z.
Déterminer tous les couples (x, y) ∈ Z2 d’entiers c) En déduire que pour tout x ∈ Z :
19
premiers entre eux pour lesquels x y = 150. x p ≡ x [p] (petit théorème de Fermat),
————————————– puis que si x ∧ p = 1, alors x p−1 ≡ 1 [p].
d) Montrer que pour tous y ∈ Z et k ∈ N :
20 y ≡ 1 pk =⇒ y p ≡ 1 p k+1 .
1) Montrer que n + 1 et 2n + 1 sont premiers entre
eux pour tout n ∈ N. e) En déduire que pour tous x ∈
Z premier à p et
k−1
2n + 1 2n k ∈ N∗ : x p (p−1) ≡ 1 p k .
2) En déduire, grâce à , que est divi- Y
n+1 n 3) Soit n ∈ N∗ . On pose Nn = p vp (n)−1 (p − 1)
sible par n + 1 pour tout n ∈ N.
p|n
où l’indice p est un nombre premier. Montrer que
————————————–
pour tous x ∈ Z premier à n : x Nn ≡ 1 [n]
Soit p ∈ P. (théorème d’Euler). Nous montrerons au chapitre
21 p « Groupes et anneaux » qu’en réalité, Nn = ϕ(n).
1) Montrer que p divise pour tout k ∈ ¹1, p − 1º.
k 4) Soit p ∈ P.
2) En déduire que pour tout k ∈ ¹0, p − 1º : a) Montrer que pour tous A, B ∈ Mn (Z) :
p−1
≡ (−1)k [p]. tr (A + B) p ≡ tr Ap + tr B p [p].
k
b) En déduire que pour tout A ∈ Mn (Z) :
————————————–
tr Ap ≡ tr(A) [p].
Montrer que Ua ∩ U b = Ua∧b pour tous a, b ∈ N∗ .
22 ————————————–
————————————–
Déterminer toutes les parties non vides E de N∗
Soient a, b, n ∈ Z. 26 x+y
23 pour lesquelles ∈ E pour tous x, y ∈ E.
1) Montrer que n3 + 3n2 − 5 ∧ (n + 2) = 1. x∧y
21n − 3 15n + 2 ————————————–
2) Montrer que et ne sont pas
4 4
tous les deux entiers.
2
Christophe Bertault — Mathématiques en MPSI ARITHMÉTIQUE DES ENTIERS
ÉQUATIONS DIOPHANTIENNES
Résoudre
§ les équations d’inconnue (x, y) ∈ N2 :
27
x∧ y =3
1) 2) x ∨ y = x + y − 1.
x + y = 18.
3) (x ∧ y) + (x ∨ y) = 2x + 3 y.
————————————–
Résoudre les équations d’inconnue (x, y) ∈ N2 sui-
28
vantes :
1) x 2 − y 2 = 7. 2) 9x 2 − y 2 = 32.
2 2
3) x − 2 y = 3 en raisonnant modulo 8.
4) 15x 2 − 7 y 2 = 9 en raisonnant modulo 3.
————————————–
Montrer que l’équation 2n + 1 = m3 d’inconnue
29
(m, n) ∈ N2 n’a pas de solution.
————————————–
Soient a, b, c ∈ Z avec (a, b) 6= (0, 0). On s’intéresse
30
à l’équation Æ a x + b y = c d’inconnue (x, y) ∈ Z2 .
1) Montrer qu’Æ n’a pas de solution si c n’est pas un
multiple de a ∧ b.
2) On suppose que a ∧ b = 1.
a) Montrer qu’Æ possède au moins une solution.
b) En déduire toutes les solutions d’Æ et interpré-
ter le résultat géométriquement.
3) Résoudre les équations d’inconnue (x, y) ∈ Z2 :
a) 7x − 12 y = 3. b) 20x − 53 y = 3.
————————————–
Résoudre l’équation x 2 + y 2 = 3z 2 d’inconnue
31
(x, y, z) ∈ N3 , notamment en raisonnant modulo 3.
————————————–
32 3
1) Soit (x, y, z) ∈ N∗ . On suppose que :
x 2 + y 2 = z2 et x ∧ y = 1.
a) Montrer que y ∧ z = 1.
b) Montrer que x ou y est pair. Quitte à les per-
muter, on suppose désormais y pair.
c) Montrer que y + z et z − y sont premiers entre
eux, puis que y + z = a2 et z − y = b2 pour cer-
tains a, b ∈ N∗ impairs et premiers entre eux.
d) En déduire la forme du triplet (x, y, z).
2) Résoudre finalement l’équation x 2 + y 2 = z 2 d’in-
3
connue (x, y, z) ∈ N∗ .
————————————–
2
Résoudre l’équation x y = y x d’inconnue (x, y) ∈ N∗ .
33
————————————–
Résoudre pour tout p ∈ P l’équation x 2 + px = y 2
34
d’inconnue (x, y) ∈ N2 .
————————————–
