Christophe Bertault — Mathématiques en MPSI ARITHMÉTIQUE DES ENTIERS RELATIFS
Vrai ou faux ? Justifier. Soient d, n, a ∈ Z. ————————————–
1
1) 45 possède 12 diviseurs.
2) Si n ≡ 1 [35], alors n est impair. Montrer que p2 ≡ 1 [24] pour tout p ∈ P supé-
6
3) Si a et b divisent d, alors a b aussi. rieur ou égal à 5.
4) Si d divise a b, alors d divise a ou d divise b.
————————————–
5) L’intervalle d’entiers ¹1, 1000º contient 140 entiers
divisibles par 7. ∗
7 2 tous n ∈ N et a, b ∈ Z, si
Montrer que pour
6) Pour tous p, q ∈ P, si q − p = 11 : p = 2 et n n
a ≡ b [n] : a ≡ b n .
q = 13.
7) Si d divise n2 , alors d divise n. ————————————–
8) Si a2 ≡ 1 [n] : a ≡ ±1 [n]. n
Montrer que a2 ≡ 1 2n+1 pour tous a ∈ Z
9) Si 4a ≡ 4b [13] : a ≡ b [13]. 8
impair et n ∈ N.
10) Si 4a ≡ 4b [6] : a ≡ b [6].
11) Si tout diviseur premier de n est congru à ±1 mo- ————————————–
dulo 8 : n ≡ ±1 [8]. Et la réciproque ?
9
————————————– 1) Montrer que pour tout n ¾ 6 pair, n divise
(n − 1)!.
2) Soit p ∈ P supérieur ou égal à 7. Montrer
DIVISIBILITÉ, DIVISION EUCLIDIENNE que (p − 1)! + 1 n’est pas une puissance de p.
ET CONGRUENCES
————————————–
2 Soit (un )n∈N une suite réelle sous-additive, i.e.
1) Montrer que 2123 + 3121 est divisible par 11. 10
pour laquellenpour tous m, no∈ N : um+n ¶ um + un .
2) Calculer le reste de la division euclidienne : un
On pose A = n ∈ N∗ .
a) de 32189 par 25. b) de 4990021 par 13. n
1) On suppose A minoré et on pose a = inf A.
————————————– a) Soient n, N ∈ N∗ . La division euclidienne de n
par N s’écrit n = N q + r pour certains q ∈ N et
un uN u r
3 r ∈ ¹0, N − 1º. Montrer que : ¶ + .
1) Montrer que n(n + 2)(7n − 5) est divisible par un n N n
6 pour tout n ∈ Z. b) En déduire que lim = a.
n→+∞ n
2) Pour quels entiers n ∈ Z est-il vrai que n + 1 un
2) Montrer que lim = −∞ dans le cas où A
divise n + 7 ? n→+∞ n
3) Pour quelles valeurs de n ∈ Z l’entier : n’est pas minoré.u
n
n2 + (n + 1)2 + (n + 3)2 En résumé, la suite possède toujours une li-
n n∈N∗
mite (lemme sous-additif de Fekete).
est-il divisible par 10 ?
4) Trouver tous les nombres premiers p pour ————————————–
lesquels 3p + 4 est un carré parfait.
5) Pour quels n ∈ Z le produit n(n + 2) est-il
une puissance de 2 ? PGCD, PPCM
————————————–
ET NOMBRES PREMIERS ENTRE EUX
Soit n ∈ N. On note a0 , . . . , a r les chiffres de Déterminer tous les couples (x, y) ∈ Z2 d’entiers
4 11
la décomposition de n en base 10. Par exemple, pour premiers entre eux pour lesquels x y = 150.
n = 156 : a0 = 6, a1 = 5 et a2 = 1.
————————————–
1) Montrer que n est divisible par 4 si et seulement
si l’entier obtenu en ne conservant que les chiffres
a0 et a1 l’est. 12
1) Montrer que n + 1 et 2n + 1 sont premiers entre
2) Montrer que n est divisible par 3 (resp. 9) si et eux pour tout n ∈ N.
seulement si la somme a0 + . . . + a r l’est. 2n + 1 2n
3) Déterminer une condition nécessaire et suffisante 2) En déduire, grâce à , que est divi-
n+1 n
sur a0 , . . . , a r pour que n soit divisible par 11. sible par n + 1 pour tout n ∈ N.
————————————– ————————————–
Soient x, y, z ∈ Z. Soit p ∈ P.
5 13 p
1) Montrer que x 2 + y 2 est divisible par 7 si et seule- 1) Montrer que p divise pour tout k ∈ ¹1, p − 1º.
k
ment si x et y le sont. 2) En déduire que pour tout k ∈ ¹0, p − 1º :
2) Montrer que si x 3 + y 3 + z 3 est divisible par 7, l’un
p−1
des entiers x, y ou z l’est aussi. ≡ (−1)k [p].
k
1
Christophe Bertault — Mathématiques en MPSI ARITHMÉTIQUE DES ENTIERS RELATIFS
————————————– ————————————–
Montrer que pour tous a, b ¾ 2 premiers entre Montrer que (a ∧ b)n = a n ∧ b n pour tous a, b ∈ Z
14 23
ln a et n ∈ N.
eux, est irrationnel.
ln b ————————————–
————————————–
Le résultat de cet exercice est utile à la réso-
Soient a, b, n ∈ Z. 24
15 lution de bon nombre d’équations diophantiennes, no-
1) Montrer que n3 + 3n2 − 5 ∧ (n + 2) = 1. tamment de cette feuille d’exercices.
2) Montrer que si a∧n = 1 : (a b)∧n = b∧n. 1) Soient a, b ∈ N∗ et k ¾ 2 entier. Montrer que si a et
3) Montrer que : b sont premiers entre eux et si a b est la puissance
n + 3n2 − n + 2 ∧ n2 + n + 1 = (n − 2) ∧ 7.
4 kème d’un entier, alors a et b sont eux-mêmes des
puissances kèmes d’entiers.
4) Simplifier (a + b) ∧ (a ∨ b).
2) Le résultat de la question 1) est-il vrai pour des
————————————– entiers a, b ∈ Z ?
21n − 3 15n + 2 ————————————–
Soit n ∈ Z. Montrer que et ne
16 4 4
sont pas tous les deux entiers.
25
1) Montrer que pour tous p ∈ P et n ∈ N :
————————————–
+∞X n
Montrer que Ua ∩U b = Ua∧b pour tous a, b ∈ N∗ . vp n! = (formule de Legendre),
17 k=1
pk
n
————————————– où la somme est faussement infinie car =0
pk
pour tout k ∈ N∗ pour lequel p k > n.
Soient a, b ∈ N∗ premiers entre eux. 2) Par combien de zéros l’entier 100! s’achève-t-il ?
18
1) Pour tout k ∈ N, on note rk le reste de la divi-
sion euclidienne de a k par b. Pourquoi l’applica- ————————————–
tion k 7−→ rk n’est-elle pas injective sur N ?
2) En déduire que a n ≡ 1 [b] pour un certain n ∈ N∗ . Déterminer tous les entiers n ∈ N∗ pour les-
26
quels 2n divise 3n − 1.
————————————–
————————————–
∗
Soient a, b ∈ N premiers entre eux. Montrer
19
que l’application « produit » (x, y) 7−→ x y est bijective NOMBRES PREMIERS
de div+ (a)×div+ (b) sur div+ (a b), où l’on a noté div+ (n)
l’ensemble des diviseurs positifs de n pour tout n ∈ N∗ . Pour tout n ∈ N∗ , on note pn le nème nombre pre-
27
mier. Montrer que pour tout n ¾ 2 : pn+1 < p1 . . . pn .
————————————–
————————————–
On dira qu’une partie non vide E de N∗ est sympathique
20 x+y
si pour tous x, y ∈ E : ∈ E. Soient a ¾ 2 et n ¾ 2. On suppose a n −1 premier.
x∧y 28
1) Montrer que a = 2.
1) Montrer
que toute partie sympathique contient 2) Montrer que n est premier.
2 et que 2 est une partie sympathique. Pour tout p ¾ 2, l’entier M p = 2 p − 1 est appelé le
2) Déterminer toutes les parties sympathiques
pème nombre de Mersenne. Tous ne sont pas premiers,
qui contiennent 1.
par exemple M11 = 23 × 89.
3) Soit E une partie sympathique non ré-
duite à 2 et ne contenant pas 1. ————————————–
a) Montrer que le plus petit élément de E \ 2 est
impair. 29
1) Montrer que pour tout n ∈ N∗ , si 2n +1 est premier,
b) Montrer que E = N \ 0, 1 .
n est une puissance de 2.
n
————————————– Pour tout n ∈ N, Fn = 22 + 1 est appelé le nème nombre
de Fermat. Les nombres de Fermat F0 , F1 , F2 , F3 et F4
sont premiers et on conjecture que ce sont les seuls.
VALUATIONS p-ADIQUES 2) a) Montrer que Fn+1 = F0 . . . Fn +2 pour tout n ∈ N.
b) En déduire que Fm et Fn sont premiers entre
Soient a, b ∈ Z. Montrer que si a2 divise b2 , alors eux pour tous m, n ∈ N distincts.
21
a divise b.
————————————–
————————————–
30
Soit n ∈ N. Montrer que si n est à la fois un carré 1) a) Montrer que tout entier naturel congru à 3 mo-
22
parfait et un cube parfait, alors il est la puissance sixième dulo 4 possède au moins un diviseur premier
d’un entier. congru à 3 modulo 4.
2
Christophe Bertault — Mathématiques en MPSI ARITHMÉTIQUE DES ENTIERS RELATIFS
b) Montrer qu’il existe une infinité de nombres ————————————–
premiers congrus à 3 modulo 4.
2) Montrer qu’il existe une infinité de nombres pre- 38 3
miers congrus à 5 modulo 6. 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-
ÉQUATIONS DIOPHANTIENNES muter, on suppose désormais y pair.
c) Montrer que y + z et z − y sont premiers entre
Résoudre les équations d’inconnue (x, y) ∈ N2 : eux, puis que y + z = a2 et z − y = b2 pour cer-
31 §
x∧ y =3 tains a, b ∈ N∗ impairs et premiers entre eux.
1) d) En déduire la forme du triplet (x, y, z).
x + y = 21.
2) (x ∧ y) + (x ∨ y) = 2x + 3 y. 2) Résoudre finalement l’équation x 2 + y 2 = z 2 d’in-
3
3) x ∨ y = x + y − 1. connue (x, y, z) ∈ N∗ .
————————————– ————————————–
Résoudre les équations d’inconnue (x, y) ∈ N2 sui- Pour montrer que l’équation y 2 = x 3 + 7 d’in-
32 39
vantes : connue (x, y) ∈ Z2 n’a pas de solution, on suppose par
1) x 2 − y 2 = 7. 2) 9x 2 − y 2 = 32. l’absurde qu’elle en possède une (x, y).
2 2
3) x − 2 y = 3 en raisonnant modulo 8. 1) Montrer que x ≡ 1 [4].
4) 15x 2 − 7 y 2 = 9 en raisonnant modulo 3. 2) Montrer que x 3 + 8 possède un facteur premier p
congru à 3 modulo 4.
————————————–
3) Calculer y p−1 modulo p de deux manières diffé-
rentes, puis conclure.
33
1) Soient a, b, n ∈ Z pour lesquels a ∧ n = 1.
————————————–
a) Montrer que aa′ ≡ 1 [n] pour un certain a′ ∈ Z.
b) En déduire, en fonction de a′ , b et n, les so- On veut résoudre l’équation x y = y x d’incon-
lutions de l’équation a x ≡ b [n] d’inconnue 40
nue (x, y) ∈ N∗ .
x ∈ Z. 1) Soient x, y ∈ N∗ deux entiers pour lesquels x ¶ y
2) Résoudre les équations suivantes d’inconnue et x y = y x . Montrer que x divise y en étudiant
x ∈Z: a) 5x ≡ 3 [28]. b) 14x ≡ 6 [34]. leur PGCD.
3) Résoudre l’équation a x ≡ b [n] d’inconnue 2) Conclure.
x ∈ Z pour tous a, b, n ∈ Z.
————————————–
————————————–
Résoudre l’équation y 3 = x 2 + x d’inconnue
Soient a, b, c ∈ Z avec (a, b) 6= (0, 0). On s’in- 41 2
34 (x, y) ∈ Z .
téresse à l’équation : a x + b y = c Æ d’inconnue
(x, y) ∈ Z2 . ————————————–
1) Montrer que Æ n’a pas de solution si c n’est pas un
multiple de a ∧ b. Résoudre l’équation x 2 + px = y 2 d’inconnue
42
2) On suppose à présent que a ∧ b divise c. (x, y) ∈ N2 pour tout p ∈ P.
a) Montrer, grâce à une relation de Bézout de a et ————————————–
b, que Æ possède une solution (x 0 , y0 ).
b) Résoudre Æ et interpréter le résultat géométri-
quement.
3) Résoudre les équations d’inconnue (x, y) ∈ Z2 :
a) 7x − 12 y = 3. b) 20x − 53 y = 3.
————————————–
§
x ≡ 1 mod 5
Résoudre le système d’incon-
35 nue x ∈ Z. x ≡ 2 mod 11
————————————–
Résoudre l’équation x 2 + y 2 = 3z 2 d’inconnue
36
(x, y, z) ∈ N3 , notamment en raisonnant modulo 3.
————————————–
Montrer que l’équation 2n + 1 = m3 d’inconnue
37
(m, n) ∈ N2 n’a pas de solution.
