TD d’arithmétique groupe C : ordre modulaire et petit théorème de
Fermat
Aline Cahuzac
samedi 6 janvier 2024
Exercice 1 Soit n ∈ N. Montrer que (n − 1)! ≡ −1[n] si et seulement si n est premier.
Solution de l’exercice 1 On distingue quatre cas possible pour la décomposition de n en facteurs premiers.
n = pq, avec p < q < n Dans ce cas
(n − 1)! = 1 · 2 . . . p . . . q . . . (n − 1)
est un multiple de n, donc pas congru à −1 modulo n.
2
n = p , p ⩾ 3 Dans ce cas,
(n − 1)! = 1 · 2 . . . p . . . 2p . . . (n − 1)
est un multiple de 2n donc en particulier de n, donc n’est pas congru à −1 modulo n.
n = 4 On calcule directement
(n − 1)! = 3! = 6 ̸≡ −1[n = 4]
n premier Dans ce cas on regroupe les éléments de Z/nZ, notés {1, . . . , n − 1}, par paires de la forme {a, a−1 }.
Le seul élement qui est son propre inverse st n − 1 ≡ −1 (en exercice pour le lecteur : vérifier ce point), donc
on a bien
(n − 1)! ≡ 1 · 1 . . . 1 · (n − 1) ≡ −1[n]
Exercice 2 A quelle condition un entier n ∈ N possède-t-il un multiple qui ne s’écrit qu’avec des 1 ?
Solution de l’exercice 2
analyse supposons que n vérifie la propriété de l’énoncé et écrivons donc
10k − 1
m · n = 11 . . . 11 =
9
pour des entiers k, m. On voit immédiatement que n ne peut pas être un multiple de 2 ou de 5, donc n est
premier avec 10.
synthèse soit donc n premier avec 10. 10 est inversible modulo 9n, donc avec
k = ω9n (10)
10k −1
on obtient 9n | 10k − 1, de sorte que 9 soit un multiple de n qui ne s’écrit qu’avec des 1.
Exercice 3 Soit p un nombre premier et d un diviseur de p − 1. Calculer, modulo p, le produit des éléments
de Z/pZ dont l’ordre est exactement égal à d.
Solution de l’exercice 3 Remarquons que ωp (a) = ωp (a−1 ) : autrement dit, un élement et son inverse ont
toujours le même ordre. Alors on distingue deux cas :
d ̸= 2 Dans ce cas, tous les élements vérifiant ωp (a) = d vérifient aussi a ̸= a−1 . Les éléments vont par paire élément-
inverse dans le produit : Y
= 1 · 1...1 = 1
ωp (a)=d
1
d = 2 Dans ce cas, les éléments vont tous par paire, sauf −1 et le produit devient :
Y
= 1 · 1 · · · − 1 = −1
ωp (a)=d
Exercice 4 Trouver les entiers (n, m) ∈ N tels que
m20 + 11n
soit un carré parfait.
Solution de l’exercice 4 On suppose l’énoncé vérifié et on écrit m20 + 11n = a2 , soit 11n = (a + m10 )(a − m10 )
pour a ∈ N. En faisant la différence des deux termes, on obtient qu’il existe des entiers α < β tels que α + β = n et
2m10 = 11α − 11β = 11β (11α−β − 1)
On distingue alors deux cas :
β = 0 Dans ce cas 2m10 = 11α − 1. Mais d’après le petit théorème de Fermat, m10 est congru à 0 ou 1 modulo 11.
Le seul cas possible est α = 0, ce qui donne n = 0. Il n’y a alors pas de solution (impossible de trouver deux
carrés consécutifs non nuls).
β > 0 Dans ce cas, on écrit m = 11u · ℓ pour u, ℓ ∈ N avec ℓ ∧ 11 = 1 (on met à part la puissance de 11 dans la
décomposition de m en facteurs premiers). Nécéssairement, β = 10u et 2ℓ1 0 = 11α−β − 1, mais toute puissance
de ℓ est congrue à 1 modulo 11 donc il n’y a pas de solution de cette forme hormis ℓ = 0 et α = β.
En conclusion, les solutions sont les couples (2n, 0) avec n ∈ N quelconque.
Exercice 5
Soit p premier. Montrer qu’on peut trouver un diviseur premier ℓ de pp − 1 tel que l ≡ 1[p].
Solution de l’exercice 5
On remarque que pp ≡ 1[ℓ] ⇒ ωℓ (p)|p. On distingue deux cas :
ωℓ (p) = p Dans ce cas p|φ(ℓ) = ℓ − 1 et ℓ ≡ 1[p] comme on veut.
ωℓ (p) = 1 Dans ce cas ℓ|p − 1. Or
pp − 1 = (p − 1)(pp−1 + · · · + 1) = (p − 1)K
pour un entier K ∈ N. Il reste à montrer que K a des diviseurs premiers qui ne divisent pas p − 1.
On écrit donc
p−1
X p−1
X
K= pk = 1 + (pk − 1) + (p − 1)
k=0 k=1
p−1
X k−1
X
=p+ (p − 1) pj
k=1 j=0
≡ p ≡ 1[p − 1]
En particulier, K ∧ (p − 1) = 1, donc on a même le résultat plus fort que tous les diviseurs premiers de K ne
divisent pas p − 1, et il suffit de prendre ℓ diviseur premier de K.
Exercice 6
Soit n1 , . . . , nk ∈ N∗ tels que ni+1 |2ni − 1 pour 1 ⩽ i ⩽ k (avec n0 = nk ). Montrer que n1 = · · · = nk = 1.
Solution de l’exercice 6 :
Si un des ni vaut 1, tous les autres aussi.
Sinon, on note pi le plus petit diviseur premier de ni . On a pi |2ni−1 − 1, donc ωpi (2)|(pi − 1) ∧ nn−1 . Si l’ordre
n’est pas 1 (cas impossible), alors il y a un facteur premier de ni−1 qui divise aussi pi − 1. En particulier :
p1 < p2 < · · · < pk < p1
C’est absurde.
