Lycée Louis-Le-Grand, Paris Pour le 07/01/2016

MPSI 4 – Mathématiques
A. Troesch

DM no 10 : Groupes, arithmétique

Correction du problème 1 – Nombres de Carmichael

Partie I – Structure du groupe (Z/pZ)∗

1. Soit pour tout p ∈ P,

 
v (a)
p si vp (a) > vp (b) v (b) si v (a) < v (b)
p p p
αp = et βp =
0 sinon 0 sinon
Y Y
On pose a′ = pαp et b′ = pβp . On a alors a′ ∧ b′ = 1, a′ ÷ a et b′ |b . De plus :
p∈P p∈P

Y
a′ b ′ = pmax(vp (a),vp (b)) soit: a′ b ′ = a ∨ b .
p∈P

′ ′
On considère alors x′ = xa/a et y ′ = y b/b , qui sont bien d’ordre a′ et b′ respectivement.
′ ′ a′ ′ b′ ′
2. Comme G est abélien, on a (x′ y ′ )a b = (x′ )b (y ′ )a = 1. Ainsi, en notant c l’ordre de x′ y ′ , on a c|a′ b′ .
Par ailleurs, (x′ y ′ )c = 1, donc (x′ )c = (y ′ )−c ∈ hxi ∩ hyi. Notons H = hx′ i ∩ hy ′ i. Comme H est un sous-groupe
de hxi et de hyi, l’ordre de H divise a′ et b′ . Puisque a′ et b′ sont premiers entre eux, H = {1} ; Ainsi, (x′ )c = 1
et (y ′ )c = 1, de quoi on déduit que a′ |c et b′ |c. Comme a′ et b′ sont premiers entre eux, a′ b′ |c.
Ainsi, x′ y ′ est d’ordre a′ b′ = a ∨ b.
3. Soit ω(G) le ppcm des ordres de tous les éléments de G. En notant x1 , . . . , xn les éléments de G et a1 , . . . , an
leurs ordres, on montre sans problème par une récurrence immédiate basée sur la question précédente, que pour
tout k ∈ [[1, n]], il existe un élément d’ordre a1 ∨ · · · ∨ ak .
En particulier, pour k = n, il existe un élément g ∈ G d’ordre ω(G) .
Par définition, pour tout g ∈ G, l’ordre de g divise ω(G), donc g ω(G) = 1. Donc ω(G) > min{k ∈ N∗ | ∀g ∈
G, g k = 1, }.
De plus, l’existence de g d’ordre ω(G), assure que pour tout k ∈ [[1, ω(G) − 1]], g k 6= 1, donc ω(G) 6 min{k ∈
N∗ | ∀g ∈ G, g k = 1, }.
Les deux inégalités amènent : ω(G) = min{k ∈ N∗ | ∀g ∈ G, g k = 1, } .
4. Tout élément non nul de Z/pZ est inversible (car Fp est un corps). On rappelle que cela provient d’une relation
de Bézout entre k non divisible par p et p : on trouve un inverse de k en réduisant l’égalité uk + bp = 1 modulo
p.
Ainsi, (Z/pZ)∗ = Z/pZ \ {0}, donc son ordre est p − 1.
5. Soit P ∈ Fp [X] le polynôme à coefficients dans Fp défini par :

P (X) = X ω(G) − 1.

Pour tout ξ ∈ G, xξ = 1, par définition de l’exposant. Donc P (ξ) = 0. D’après le point admis plus haut P (X)
est divisible par X − ξ). Écrivons P (X) = (X − ξ)Q(X).
Soit ξ ′ 6= ξ. On a alors P (ξ ′ ) = 0, donc (ξ − ξ ′ )Q(ξ ′ ) = 0. Comme ξ − ξ ′ = 0 et que Fp est un corps (donc
intègre), on en déduit que Q(ξ ′ ) = 0, et donc qu’on peut factoriser Q par (X − ξ ′ ).
Y
En continuant de la sorte (par une récurrence immédiate), on en déduit que P est divisible par (X − ξ)
ξ∈G

1
 Y
6. L’examen des degrés nous assure alors, puisque P n’est pas le polynôme nul, que (X − ξ) 6 deg(P ), donc
ξ∈G

que p − 1 6 ω(G) .
Comme par ailleurs, pour tout x ∈ G, xp−1 = 1 (d’après Lagrange), on en déduit, d’après la question 3, que
ω(G) 6 p − 1.
Ainsi, p − 1 = ω(G).
7. On déduit alors de la question 3 qu’il existe un élément g d’ordre p − 1, ce qui équivaut à dire que G = hxi.
Ainsi, G est cyclique d’ordre p − 1.

Partie II – Stucture des groupes (Z/pn Z)∗

1. Il s’agit encore d’une relation de Bézout : k est inversible modulo pn ssi il existe u ∈ Z tel que ku ≡ 1 [pn ],
ssi il existe u et v dans Z tels que ku + pn v = 1, ssi a et pn sont premiers entre eux, ssi p ne divise pas k .
2. Le nomrbe de diviseurs de p dans [[1, pn ]] est pn−1 , donc, d’après la question précédente, le nombre d’éléments
inversibles de Z/pn Z est pn − pn−1 , soit :

|(Z/pn Z)∗ | = ϕ(pn ) = pn−1 (p − 1) .

3. Soit a ∈ Z, et m ∈ N∗ . D’après la formule du binôme,

p  
m
X
p p mk k
(1 + p a) = p a .
k
k=0
 
p
Pour tout k > 2, mk > 3m > m + 2 (car m > 1). De plus, pour k = 2, est divisible par p (car k ∈ [[1, p − 1]]
  k
p p(p − 1)
puisque p > 3 par hypothèse ; plus simplement = , et p − 1 est pair), et 2m > m + 1. Ainsi, pour
  k 2
p mk
k = 2, p est divisible par pm+2 .
k
On en déduit que
 
p m
(1 + pm a)p ≡ 1 + p a ≡ 1 + apm+1 [pm+2 ] .
1

4. On raisonne par récurrence, en notant pour m ∈ N∗ , P(m) la propriété :

m
∀a ∈ Z, (1 + pa)p ≡ 1 + pm+1 a [pm+2 ].
0
• Initialisation : pour m = 0, c’est une évidence, puisque (1 + p)p = 1 + p.
• Hérédité : Soit m ∈ N. Supposons P(m). Nous avons alors :
m+1 m
(1 + pa)p = ((1 + pa)p )p .
m
Or, d’après l’hypothèse de récurrence, il existe b ∈ Z tel que (1 + pa)p = 1 + pm+1 a + pm+2 b. On a donc
m+1
(1 + pa)p = (1 + pm+1 (a + pb))p .

On applique la question précédente au rang m + 1 > 1 :

(1 + pm+1 (a + pb))p ≡ 1 + pm+2 (a + pb) [pm+3 ],

puis :
m+1
(1 + pa)p ≡ 1 + pm+2 a [pm+3 ].
Il s’agit là de P(m + 1).
• Ainsi, d’après le principe de récurrence, on peut conclure que :
m
∀m ∈ N∗ , ∀a ∈ Z, (1 + pa)p ≡ 1 + pm+1 a [pm+2 ] .

2
 5. On a, d’après la question précédente (qu’on peut appliquer pour n − 1 car n > 2),
n−1 n−1
(1 + p)p ≡ 1 + pn [pn+1 ] donc: (1 + p)p ≡ 1 [pn ].

On en déduit que l’ordre a de 1 + p divise pn−1 . Il existe donc α ∈ [[1, n − 1]] tel que a = pα (α ne peut pas être
nul car 1 + p 6= 1 dans Z/pn Z). Or, la question précédente amène aussi (au rang n − 2 > 0) :
n−2 n−1
(1 + p)p ≡ 1 + pn−1 [pn ] donc: (1 + p)p 6≡ 1 [pn ].

Ainsi, a ne divise pas pn−2 , donc α > n − 2. On a donc α = n − 1, et a = pn−1 .

Ainsi, 1 + p est d’ordre pn−1 dans (Z/pn Z)∗ .
6. Soit x ∈ Z tel que sa classe x modulo p soit une racine primitive modulo p. Ainsi, x est d’ordre p − 1 dans
(Z/pZ)∗ . Considérons x̃ la classe de x modulo pn . Comme x est premier avec p (car x est inversible), x est de
∗
même premier avec pn . Donc x̃ ∈ (Z/pn Z) . L’ordre de ce groupe étant pn (p − 1), l’ordre de x̃ divise pn (p − 1),
d’après le théorème de Lagrange. Soit a l’ordre de x̃. Il existe donc α ∈ [[0, n]] et m divisant p − 1 tel que
a = pα m. On a alors
α α
xp m ≡ 1 [pn ] donc: xp m ≡ 1 [p].

Puisque x est d’ordre p − 1, on en déduit que p − 1 divise pα m, et étant premiers avec pα , il divise m. Par
conséquent m = p − 1.
α
Ainsi, x̃ est d’ordre pα (p − 1), donc tildexp est d’ordre p − 1.
Il existe donc un élément d’ordre p − 1 dans (Z/pn Z)∗ .
7. (Z/pn Z)∗ contient un élément d’ordre p − 1, et un élément d’ordre pn−1 . Par conséquent p − 1 et pn−1 étant
premiers entre eux, il découle de la question I-2 que (Z/pn Z)∗ contient un élément y d’ordre pn−1 (p−1). Comme
il s’agit là de l’ordre du groupe (Z/pn Z)∗ , on en déduit que y engendre (Z/pn Z)∗ .
Ainsi, (Z/pn Z)∗ est cyclique d’ordre pn−1 (p − 1) .

Partie III – Cas des (Z/2n Z)∗

1. On suppose n > 3. On note G = (Z/2n Z)∗ , H l’ensemble des classes modulo 2n des entiers k congrus à 1
modulo 4, et et K = ({−1, +1}, ×).
(a) On a H ⊂ G car les éléments de H sont représentés par des entiers k impairs, donc premiers avec 2n , donc
inversibles modulo 2n . De plus :
• 1 ≡ 1[4], donc 1 ∈ H : H contient le neutre de (Z/2n Z)∗ .
• Soit h et k dans H, représentés par des entiers x et y de Z. On a donc x ≡ 1 [H] et y ≡ 1 [4], donc
xy ≡ 1 [4], donc hk ∈ H.
• Soit h ∈ H représenté par x. Comme x est impair, donc premier avec 2n , x est inversible modulo 2n .
Soit y ∈ Z un inverse modulo 2n de x. On a alors xy ≡ 1[2n ] et comme n > 3, xy ≡ 1 [4]. Or, comme
x ≡ 1 [4], on a xy ≡ y [4], donc y ≡ 1 [4]. Ainsi, y ∈ H. H est donc stable par inversion.
On en déduit que H est un sous-groupe de G . Son ordre est clairement 2n−2 .
(b) Il n’est pas dur de vérifier que K est un groupe (version multiplicative de Z/2Z).
On définit ϕ de H × K dans G par :
ϕ(h, k) = hk.

• Comme h est inversible modulo 2n ainsi que k (égal à 1 ou −1), il en est de même de hk. Ainsi, ϕ est
bien à valeurs dans G.
• Soit (h, k) et (h′ , k ′ ) des éléments de H × K. On a alors

ϕ((h, k) · (h′ , k ′ )) = ϕ(hh′ , kk ′ ) = hh′ kk ′ = hkh′ k ′ = ϕ(h, k)ϕ(h′ , k ′ ),

puisque G est abélien. Ainsi, ϕ est un morphisme.

3
 • Soit (h, k) ∈ Ker(ϕ). On a donc hk = 1 dans Z/2n Z. Comme k = 1 ou k = −1, on en déduit que
h = 1 ou h = −1 dans Z/2n Z. Comme n > 2, on peut réduire modulo 4. Comme h soit être représenté
par un élément congru à 1 modulo 4, on en déduit qu’on a nécessairement h = 1, puis k = 1. Ainsi,
Ker(ϕ) = {(1, 1)}, donc ϕ est injective.
• G est de cardinal 2n−1 (représenté par les entiers impaires de [[2, 2n ]], ainsi que H × K. Ainsi, l’injectivité
et l’égalité des cardinaux finis amènent le fait que ϕ est bijective.
• On en déduit que ϕ est un isomorphisme .
(c) On montre par récurrence sur n > 3 la propriété
n−3
P(n) : 52 ≡ 1 + 2n−1 [2n ].

• Initialisation : Pour n = 3, c’est trivial : 5 ≡ 1 + 4 [8].

• Hérédité : Soit n > 3 tel que P(n) soit vrai. Il existe alors a tel que
n−3
52 = 1 + 2n−1 + a2n = 1 + 2n−1 (1 + 2a).

En élevant au carré et en développant le carré de droite, il vient :

n−2
52 = 1 + 2n (1 + 2a) + 22n−2 (1 + 2a)2 .

Or, n > 3, donc 2n − 2 > n + 1. On en déduit alors que

n−2
52 ≡ 1 + 2n [2n+1 ],

ce qui est exactement P(n + 1).

• On déduit du principe de récurrence que
n−3
∀n > 3, 52 ≡ 1 + 2n−1 [2n ] .

Comme H est d’ordre 2n−2 , le théorème de Lagrange nous affirme que l’ordre de 5 (ou plutôt de sa classe
n−3
dans H) est une puissance de 2, inférieure à 2n−2 . Comme 52 6≡ 1 [2n ] d’après la question précédente,
n−2
l’ordre de 5 ne peut alors qu’être 2 .
(d) On déduit de la question précédente que H est cyclique d’ordre 2n−2 , donc isomorphe à Z/2n−2 Z (remarquez
que cet isomorphisme nous fait passer d’une notation multiplicative à une notation additive). On a déjà
remarqué que K est isomorphe à Z/2Z.
Donc, d’après la question 1(b), (Z/2Z)∗ est isomorphe à (Z/2Z) × (Z/2n−2 Z)
Ce groupe n’est pas cyclique . En effet, pour tout x = (y, z) dans ce produit cartésien,

2n−2 x = (2n−2 y, 2n−2 z) = (0, 0),

donc il n’existe pas d’élément d’ordre 2n−1 (l’ordre maximal ne pouvant excéder 2n−2 , égal d’ailleurs à cette
valeur).
2. • Cas n = 1 : le seul élément inversible de Z/2Z est 1, donc (Z/2Z)∗ = {1} (groupe trivial)
• Cas n = 2 : les éléments inversibles de Z/4Z sont 1 et 3. Donc (Z/4Z)∗ est d’ordre 2, donc isomorphe à Z/2Z .

Partie IV – Nombres de Carmichael et indicateur de Carmichael

1. • Soit n > 2 ; Comme ϕ(n) est l’ordre de (Z/nZ)∗ (encore Bézout comme en II-1), l’ordre des éléments de
(ZZ/nZ)∗ divise ϕ(n) (théorème d’Euler), donc leur ppcm aussi.
Ainsi pour tout n > 2, λ(n) divise ϕ(n) .
• Si λ(n) = ϕ(n), alors d’après le rappel en début de partie, il existe un élément x d’ordre λ(n), donc d’ordre
ϕ(n) dans (Z/nZ)∗ . Pour des raisons de cardinalité, on a alors (Z/nZ)∗ = hxi, donc (Z/nZ)∗ est cyclique .
• Réciproquement, si (Z/nZ)∗ est cyclique, il existe un élément d’ordre ϕ(n), donc ϕ(n) divise λ(n) par
définition. Les deux divisibilités amènent l’égalité ϕ(n) = λ(n).

4
 • Ainsi, λ(n) = ϕ(n) si et seulement si (Z/nZ)∗ est cyclique.
2. • Si n est premier, alors λ(n) = ϕ(n) (car (Z/pZ)∗ est cyclique), et ϕ(n) = n − 1. Ainsi, λ(n) ne divise pas
strictement n − 1.
• Supposons alors que λ(n) divise strictement n − 1. La remarque qui précède permet déjà d’affirmer que n
n’est pas premier. De plus, pour tout x premier avec n, x est dans (Z/nZ)∗ , donc son ordre divise λ(n)
(définition de λ(n)), donc aussi n − 1, par hypothèse. Ainsi, xn−1 = 1, soit xn−1 ≡ 1 [n].
On en déduit que n est un nombre de Carmichael.
• Réciproquement, supposons que n est un nombre de Carmichael. Alors pour tout x premier avec n, xn−1 = 1,
donc l’ordre de x divise n−1. Ceci étant vrai pour tout élément de (Z/nZ)∗ , le ppcm des ordres des éléments
de ce groupe divise aussi n − 1, soit λ(n) divise n − 1.
De plus, on ne peut pas avoir égalité, car cela impliquerait que ϕ(n) > n − 1, puis ϕ(n) = n − 1, donc que
tout nombre de [[1, n − 1]] est premier avec n, donc que n est premier, ce qui est exclus par définition pour
un nombre de Carmichael.
• Ainsi, n est de Carmichael si et seulement si λ(n) divise strictement n − 1 .
k
Y
3. Soit n = pα
i , avec αi > 1 et k > 1.
i

i=1
• Le théorème chinois nous permet d’affirmer que

Z/nZ = Z/pα αk
1 Z × · · · × Z/pk Z.
1

On montre sans difficulté qu’on a alors :

(Z/nZ)∗ = (Z/pα ∗ αk ∗
1 Z) × · · · × (Z/pk Z) .
1

• Il existe dans (Z/pαi ∗ αi

i Z) un élément d’ordre λ(pi ) (question I-3), donc en itérant I-2, il existe dans (Z/nZ)
∗
α1 α2 αk
un élément d’ordre µ = λ(p1 ) ∨ λ(p2 ) ∨ · · · ∨ λ(pk ). Donc µ divise λ(n).
• Récirproquement, µ est un multiple de chaque Piαi , donc pour tout i ∈ [[1, k]], et tout x dans Z/pα
i Z, l’ordre
i

µ α1 αk
de x divise µ, donc x = 1. Ainsi, pour tout (x1 , . . . , xk dans (Z/p1 Z) × · · · × (Z/pk Z) , on a :
∗ ∗

(x1 , . . . , xk )µ = (xµ1 , . . . , xµk ) = (1, . . . , 1).

Donc l’ordre de tout élément de (Z/nZ)∗ divise µ, donc λ(n) divise µ.

• On en déduit que
αk
λ(n) = µ = λ(pα α2
1 ) ∨ λ(p2 ) ∨ · · · ∨ λ(pk ) .
1

4. Les parties précédentes nous apprennent que si p est un nombre premier impair, λ(pα ) = ϕ(pα ) = pα−1 (p − 1)
(car Z/pα Z est cyclique), et que pour p = 2, λ(2α ) = 2α−2 si α > 3, 2α−1 si α = 1 ou α = 2 (ce qui correspond
aussi à l’expression obtenue pour p > 2). Ainsi :
• si vp (2) 6 2 (donc si 8 ne divise pas n), on a :

λ(n) = (p1α1 −1 (p1 − 1)) ∨ (p2α2 −1 (p2 − 1) ∨ · · · ∨ (pα

k
k −1
(pk − 1)) .

• si vp (2) > 3 (donc si 8 divise n), en stipulant que p1 = 2, on a :

λ(n) = 2α1 −2 ∨ (pα

2
2 −1
(p2 − 1)) ∨ · · · ∨ (pα
k
k −1
(pk − 1)) .

5. • Si n est un nombre de Carmichael, il est composé par définition.

Par ailleurs, λ(n) divise n − 1, donc pour tout i ∈ [[1, p]], λi (pα αi
i ) divise n − 1, et l’expression de λi (pi )
i

montre que si αi > 1, alors pi divise n − 1 (y compris pour p = 2, en distinguant les cas α = 2 et a > 3).
Or, comme pi divise n, ceci n’est pas possible. Par conséquent, αi 6 1. Par conséquent, n n’a pas de facteur
multiple.
On a donc pour tout i ∈ [[1, k]], λ(pα αi
i ) = pi − 1 (y compris si pi = 2), et λ(pi ) divise n − 1, donc pi − 1
i

divise n − 1.

5
 • Réciproquement, si n est composé, sans facteur multiple et si pour tout p facteur premier de n, p − 1 divise
n, alors, en écrivant n = p1 · pk avec les pi premiers deux à deux distincts, on a

λ(n) = (p1 − 1) ∨ · ∨ (pk − 1).

Or chacun des pi − 1 divise n − 1, donc leur pgcd aussi. On en déduit que λ(n) divise n − 1. On a déjà
montré qu’on ne peut avoir l’égalité que si n est premier, ce qui est exclus ici. Ainsi, λ(n) divise strictement
n − 1.
Ainsi, n est de Carmichael ssi tout facteur premier p de n est simple et vérifie p − 1|n − 1 .
6. On a 561 = 3 × 11 × 17, donc il est composé, sans facteur multiple. De plus on vérifie facilement que 2, 10 et
16 divisent 560, donc n est de Carmichael.
7. La réciproque résulte du fait que si a est premier avec n, il est inversible modulo n, donc on peut simplifier
par a.
Dans le sens direct, si n est de Carmichael, l’égalité est trivialement vérifiée par définition pour les a premiers
avec n, et il faut l’obtenir pour les autres valeurs de a. C’est en fait une conséquence du théorème chinois.
On écrit n = p1 · · · pk (les pi étant deux à deux distincts car n est de Carmichael), et on considère a ∈ Z, et
i ∈ [[1, k]]
• Si a ∧ pi = 1, alors api −1 ≡ 1 [pi ] d’après Fermat, donc, comme pi − 1 divise n − 1, an−1 ≡ 1 [pi ], puis
an ≡ a [pi ].
• Si a ∧ pi 6= 1, alors pi |a, donc a ≡ 0 |p1 ], donc an ≡ a ≡ 0 [pi ].
Par conséquent, pour tout i ∈ [[1, k]], an ≡ a [pi ]. Les pi étant des premiers 2 à 2 distincts, ils sont 2 à 2 premiers
entre eux, et, sachant que n = p1 · · · pk , le théorème chinois permet de conclure que an ≡ a [n].