Exercices - Z/NZ : corrigé
Exercice 1 - Equations linéaires - L2/Math Spé - ?
1. On cherche d’abord l’inverse de 7 dans Z/37Z. Cela revient a résoudre l’équation de Bezout
7u + 37v = 1. En appliquant l’algorithme d’Euclide, on trouve qu’une solution particulière
est donnée par 16 × 7 − 3 × 37 = 1. Ainsi, 16 est inverse de 7 dans Z/37Z. Il vient
7y = 2 ⇐⇒ 16 × 7y = 16 × 2 ⇐⇒ y = 32.
2. On additionne la première et la deuxième ligne pour trouver 9x = 3. Or, 1 = 37 − 4 × 9
et donc −4 est un inverse de 9 dans Z/37Z. On trouve donc
9x = 3 ⇐⇒ x = −4 × 3 = −12 = 25.
Si on reporte dans la première équation, on obtient
3 × (−12) + 7y = 3 ⇐⇒ 7y = 39 = 2.
Le résultat de la question précédente nous donne y = 32.
Exercice 2 - Equation du second degré - Math Spé/L3 - ??
L’idée est de procéder comme pour la résolution habituelle d’une équation du second degré.
On applique donc la méthode qui conduit au discriminant, c’est-à-dire que l’on met le trinome
sous forme canonique.
1. On peut remarque pour cette question que 14 = 1. Ainsi,
x2 + x + 7 = 0 ⇐⇒ x2 + 14x + 7 = 0 ⇐⇒ (x + 7)2 − 42 = 0
2
soit encore (x + 7)2 = 3. On remarque alors que 4 = 3. Ainsi, l’équation est équivalente à
2
(x + 7)2 − 4 = 0 ⇐⇒ (x + 7 + 4)(x + 7 − 4) = 0.
Puisque Z/13Z est un corps, et donc en particulier est intègre, ceci est encore équivalent
à x + 11 = 0 ou x + 3 = 0. L’ensemble des solutions est donc {2, 10}.
2. On procède de la même façon. L’équation est équivalente à
(x − 2)2 − 1 = 0.
On peut bien sûr factoriser encore et obtenir que l’équation est équivalente à
(x − 2 − 1)(x − 2 + 1) = 0.
Mais cette fois, on ne peut pas aller plus loin car Z/12Z n’est pas un corps. Il faut
plutôt écrire (x − 2)2 = 1 et chercher les t dans Z/12Z avec t2 = 1. Pour cela on dresse le
tableau :
t 0̄ 1̄ 2̄ 3̄ 4̄ 5̄ 6̄
t2 0̄ 1̄ 4̄ −3̄ 4̄ 1̄ 0̄
(on a bien sûr (−t)2 = t2 ). Ainsi, l’équation est équivalente x − 2 ∈ {−5̄, −1̄, 1̄, 5̄}. L’en-
semble des solutions est donc {−5̄, −3̄, 1̄, 5̄}.
http://www.bibmath.net 1
Exercices - Z/NZ : corrigé
Exercice 3 - Test de primalité de Miller-Rabin - Math Spé/L3 - ??
1. On factorise x2 − 1 en (x − 1)(x + 1). Par intégrité de Z/pZ, l’équation (x − 1)(x + 1) = 0
entraine x = 1 ou x = −1.
s
2. On a bs = ad×2 = ap−1 . Le résultat est donc une conséquence immédiate du petit
théorème de Fermat.
3. Posons = sup{j ≥ 0; bj n’est pas congru à 1} modulo p. Un tel nombre existe car b0 n’est
pas congru à 1 modulo p (l’ensemble que l’on considère est non vide), et pour tout j ≥ s,
bj ≡ 1 [p] (l’ensemble est majoré par s, et même par s − 1). Ainsi, on a i ∈ {0, . . . , s − 1}.
D’autre part, b2i = bi+1 ≡ 1 [p]. D’après le résultat de la première question, bi ≡ 1 [p] ou
bi ≡ −1 [p]. La première possibilité est exclue par définition de i. Donc bi ≡ 1 [p].
4. Soit p un entier impair dont on souhaite tester s’il est premier. On le factorise sous la
forme p = d × 2s + 1. Pour différentes valeurs de a, on calcule la suite bi donnée par
l’énoncé. Si b0 6= 1 et pour tout i ∈ {1, . . . , s − 1}, bi n’est pas congru à −1 modulo p,
alors on est sûr que p n’est pas premier. C’est le test de (non-)primalité de Miller-Rabin.
Exercice 4 - Indicateur d’Euler - Math Spé/L2/L3 - ??
1. Tous les nombres compris entre 1 et p, sauf p lui-même, sont premiers avec p puisque p
est premier. Donc φ(p) = p − 1.
2. Le pgcd de k et de pα n’est pas égal à 1 si et seulement si k est un multiple de p. Il
suffit donc de compter le nombre de multiples de p qui sont inférieurs ou égaux à pα et
de retrancher ce nombre à pα . Un tel nombre s’écrit p × l avec p × l ≤ pα , soit l ≤ pα−1 .
On obtient donc
φ(pα ) = pα − pα−1 .
3. k est premier avec n si et seulement si sa classe est inversible dans l’anneau Z/nZ. Ainsi,
φ(n) désigne le nombre d’éléments inversibles de Z/nZ.
4. D’après le théorème chinois, les anneaux Z/nmZ et Z/nZ × Z/mZ sont isomorphes. Le
groupe de leurs éléments inversibles sont également isomorphes. D’autre part, pour deux
anneaux A et B, il est facile de prouver que (A × B)∗ = A∗ × B ∗ . Ainsi,
(Z/nmZ)∗ et (Z/nZ)∗ × (Z/mZ)∗
sont isomorphes et ont donc le même nombre d’éléments. En calculant ce nombre d’élé-
ments, on trouve :
φ(nm) = φ(n)φ(m).
5. On décompose n en produits de facteurs premiers n = pα1 1 . . . pαr r . On trouve
φ(n) = φ (pα1 1 ) . . . φ (pαr r )
= pα1 1 − pα1 1 −1 × · · · × pαr r − pαr r −1
1 1
= n 1− ... 1 − .
p1 pr
http://www.bibmath.net 2
Exercices - Z/NZ : corrigé
6. (a) Soit k ∈ Ad . Alors k s’écrit d × l, avec l ∧ n = 1 et 1 ≤ ld ≤ n ce qui entraîne
1 ≤ l ≤ nd (remarquons que nd est entier). Réciproquement, tout entier k s’écrivant
d × l avec 1 ≤ l ≤ nd est élément de Ad . On en déduit que
n
card(Ad ) = φ .
d
(b) Il est clair que les ensembles Ad , pour d|n, forment une partition de {1, . . . , n}. Ainsi,
on a
X X n X
n= card(Ad ) = φ = φ(d).
d|n d|n
d d|n
Pour obtenir la dernière inégalité, on a effectué le changement de variables d0 = n/d.
Exercice 5 - Carrés de Z/pZ - Math Spé/L3 - ??
1. Il s’agit simplement d’une application du petit théorème de Fermat qui dit que si a∧n = 1,
alors an−1 ≡ 1 [n]. On peut aussi utiliser le théorème de Lagrange et dire que l’ordre de
x divise l’ordre du groupe, ici p − 1.
2. On écrit k = l2 et on a k (p−1)/2 = lp−1 = 1.
3. Soit x0 un élément générateur de G. Il existe s tel que k = xs0 . Il suffit de montrer que s
est pair : en effet, écrivant s = 2t, on obtient k = (xt )2 . Or,
s(p−1)
k (p−1)/2 = x0 2
= 1.
Comme x0 est d’ordre p − 1 puisqu’il engendre G qui est de cardinal p − 1, p − 1 divise
s(p − 1)/2. Autrement dit, il existe u ∈ Z tel que s(p − 1)/2 = u(p − 1). Ceci prouve que
s = 2u, donc que s est pair.
4. Soit y = x(p−1)/2 . Alors y 2 = 1, et donc (y − 1)(y + 1) = 0. Puisque Z/pZ est un anneau
intègre, on en déduit y = 1 ou y = −1. On a donc x(p−1)/2 ∈ {−1, 1} (en prenant ces
représentants modulo p).
Exercice 6 - Ordre d’élements dans le groupe des inversibles de Z/nZ et divisibilité
- L2/L3/Math Spé - ??
1. Si 2|n, alors 2|2n − 1 et donc 2n − 1 est pair, ce qui n’est pas le cas.
2. (a) Puisque p est premier, (Z/pZ)∗ est un groupe de cardinal p − 1. D’après le théorème
de Lagrange, l’ordre de tout élément divise p − 1. Donc m|p − 1.
(b) Par hypothèse, 2n ≡ 1 [n] ce qui entraîne 2n ≡ 1 [p], ou encore 2n = 1 dans Z/pZ. n
est donc un multiple de l’ordre de 2, ou encore m|n.
(c) Puisque p est le plus petit facteur premier de n, on a n∧(p−1) = 0. Ainsi, m|pgcd(p−
1, n) = 1, et donc m = 1. C’est absurde puisque 2 6= 1 dans Z/pZ, p ≥ 3. Il est donc
impossible que n divise 2n − 1.
Exercice 7 - Théorème de Wilson - Math Spé/L3 - ???
http://www.bibmath.net 3
Exercices - Z/NZ : corrigé
1. L’équation x2 = 1 est équivalente à (x − 1)(x + 1) = 0, ce qui est équivalent à dire, puisque
Z/pZ est un corps, x = 1 ou x = −1.
2. Travaillons dans Z/pZ. Tout élément de {1̄, . . . , p − 1} est inversible et son inverse est
différent de lui-même, sauf pour 1̄ et −1 d’après la question précédente. Dans le produit
2̄ × · · · × p − 2, on peut donc regrouper chaque élément avec son inverse, et on trouve que
1̄ × · · · × p − 1 = 1̄ × p − 1 = −1
ce qui est le resultat attendu.
3. Soit a ∈ {1, . . . , n − 1}. Alors a est un facteur de (n − 1)! et donc il existe k tel que
(n − 1)! = ak. On en déduit a × (−k) ≡ 1 [n], et donc a est inversible dans Z/nZ. Par le
théorème de Bézout, ceci signifie que a est premier avec n, et ceci est vrai pour tout a de
{1, . . . , n − 1}. Autrement dit, n est premier.
Exercice 8 - Un groupe d’inversibles non cyclique - Math Spé/L2 - ???
1. On procède par récurrence sur n et on écrit a = 2k + 1. Pour n = 3, on a (2k + 1)2 =
4k 2 + 4k + 1 = 1 + 4k(k + 1). Or, k(k + 1) est un nombre pair car ou bien k, ou bien
k + 1 est pair. Ainsi, 4k(k + 1) est divisible par 8 et a2 ≡ 1 [8]. Supposons maintenant le
n−2
résultat établi au rang n, c’est-à-dire que a2 = 1 + u2n . On met tout au carré et on
trouve :
(n+1)−2
a2 = (1 + u2n )2
= 1 + 2u2n + u2 22n
= 1 + 2n+1 (u + u2 2n−1 )
ce qui prouve bien le résultat au rang n + 1.
∗
2. Soit G = Z/(2n Z) . Un élément x de Z/(2n Z) est élément de G si et seulement si
x ∧ 2n = 1, si et seulement si x ∧ 2 = 1. Ainsi, on peut décrire G comme
G = {x; 1 ≤ x ≤ 2n , x ∧ 2 = 1} .
Mais dans {1, . . . , 2n }, il y a exactement 2n−1 éléments impairs. Le cardinal de G est donc
égal à 2n−1 . Or, pour g = a ∈ G, la question précédente nous dit que
{g k ; k ≥ 0} = {g k ; 0 ≤ k < 2n−2 }.
Ce dernier ensemble comporte au plus 2n−2 éléments, et g n’est pas un élément cyclique
de G. G n’est donc pas cyclique.
Si vous trouvez une erreur, une faute de frappe, etc... dans ces exercices, merci de la signaler à
[email protected] Venez poursuivre le dialogue sur notre forum :
http://www.bibmath.net/forums
http://www.bibmath.net 4
