Université Chouaïb Doukkali - Faculté des Sciences Module :Algèbre 1
Département de Mathématiques Responsable du cours : A. Haïly
Filière SMIA - Semestre 1 Année Universitaire : 17-18
Corrigé de l'Examen du Module Algèbre 1
Problème 1. Soient a, b deux entiers naturels non nuls. On considère l'application :
f : Z × Z −→ Z
(x, y) 7−→ ax + by
1. Montrer que f n'est pas injective.
2. Montrer que f (Z × Z) = dZ, où d = a ∧ b est le PGCD de a et b.
3. Déduire de la question 2, que f est surjective, si et seulement si, a et b sont premiers entre eux.
4. On prend a = 17 et b = 13.
4.1. Véri er que a et b sont premiers entre eux.
4.2. Déterminer l'ensemble f −1 ({1}).
4.3. Quel est l'inverse de 13 modulo 17 ?
4.4. Montrer que 3 est un élément primitif modulo 17.
4.5. Déterminer les entiers relatifs x tels que x6 ≡ 2, modulo 17.
Corrigé du Problème 1
1. On a f (0, 0) = 0 = f (b, −a), donc f n'est pas injective.
2. D'après le cours, il existe u, v ∈ Z, tels que ua + vb = d. Donc f (u, v) = d.
Soit n ∈ dZ, ∃α ∈ Z : n = αd = αua + αvb, donc n = f (αu, αb). Par conséquent, n ∈ f (Z × Z). i.e.
dZ ⊂ f (Z × Z).
Réciproquement, soit n ∈ f (Z × Z), alors n = f (x, y) = ax + by . Or d | ax + by , donc d | n. D'où n ∈ dZ.
En conclusion on a dZ ⊂ f (Z × Z) et f (Z × Z) ⊂ dZ, par conséquent f (Z × Z) = dZ.
3 - f est surjective, si et seulement si, f (Z × Z) = Z. Or d'après la question 2, f (Z × Z) = dZ. Donc, f
est surjective, si et seulement si, dZ = Z. i.e. d = 1.
4-
4.1. Les nmbres 17 et 13 sont des nombres premiers distincts, donc ils sont premiers entre eux.
4.2. f −1 ({1}) = {(x, y) ∈ Z × Z : 17x + 13y = 1}, c'est donc l'ensemble des solutions de l'équation
17x + 13y = 1. On commence par chercher une solution particulière. En utilisant l'algorithme d'Euclide
ou tout autre méthode valable, on a la relation : 17 × (−3) + 13 × 4 = 1. Donc (−3, 4) est une solution
particulière. Par conséquent, (x, y) ∈ f −1 ({1}) ⇔ 17x + 13y = 17 × (−3) + 13 × 4 ⇔ 17(x + 3) = 13(4 − y).
En utilisant les résultats du cours, on obtient x = −3+13k, y = 4−17k, où k ∈ Z est un entier quelconque.
Finalement, f −1 ({1}) = {(−3 + 13k, 4 − 17k) ∈ Z × Z : k ∈ Z}.
4.3. On a 4 × 13 = 1 + (3 × 17). Donc 4 × 13 ≡ 1 (modulo 17). Il en résulte que l'inverse de 13 modulo
17 est égal à 4.
4.4. Comme p = 17 est un nombre premier, on sait d'après le cours qu'il existe a ∈ N dont l'ordre
multiplicatif est égal à p − 1 = 17 − 1 = 16. Un tel élément est dit primitif modulo p. Montrons que 3
est un élément primitif modulo 17. Pour cela, on cherche l'ordre multiplicatif de 3 modulo 17. i.e. le plus
1
Université Chouaïb Doukkali - Faculté des Sciences Module :Algèbre 1
Département de Mathématiques Responsable du cours : A. Haïly
Filière SMIA - Semestre 1 Année Universitaire : 17-18
petit entier naturel non nul n tel que 3n ≡ 1 (modulo 17).
Les calculs modulo 17 donnent : 30 = 1, 31 = 3, 32 = 9, 33 = 27 ≡ 10, 34 ≡ 30 ≡ 13, 35 ≡ 39 ≡ 5,
36 ≡ 15, 37 ≡ 45 ≡ 11, 38 ≡ 33 ≡ −1.
Si n est l'ordre multiplicatif, on sait d'après le cours que n | 17 − 1 = 16. Or n > 8, donc n = 16. Par
conséquent, 3 est un élément primitif modulo 17.
4.5. On peut résoudre cette équation en utilise le fait que 3 est un élément primitif modulo 17, car ∀x ∈ Z,
non divisible par 17, ∃k ∈ {0, 1, . . . , 15} tel que x ≡ 3k (modulo 17).
Dans l'équation x6 ≡ 2 (mod 17), on pose x ≡ 3k . Par ailleurs, cherchons m tel que 2 ≡ 3m . On a
2 ≡ −15 ≡ −36 ≡ 38 36 ≡ 314 . Donc 2 ≡ 314 (mod 17).
Posons x ≡ 2k (modulo 17). On a alors x6 ≡ 2 (mod 17), si et seulement si, (3k )6 ≡ 314 , si et seulement
si, 36k ≡ 314 ⇔ 36k−14 ≡ 1 ⇔ 16 | 6k − 14 ⇔ 8 | 3k − 7 ⇔ k ∈ {5, 13}.
Donc les solutions de l'équation sont x ≡ 35 ≡ 5 et x ≡ 313 ≡ 12 (modulo 17).
Problème 2.
1. Calculer l'ordre multiplicatif de 2 modulo 7.
2. Soit n ∈ N. On note r le reste de la division euclidienne de 2n par 7.
Montrer que r ∈ {1, 2, 4}.
3. Déduire de la question 2 que, ∀n ∈ N, 2n + 1 n'est pas divisible par 7.
4. Soit n ∈ N. On pose un = 2n + 3n + 4n + 5n. Montrer que 7 | un ⇔ n est impair.
5. Déterminer, suivant les valeurs de l'entier naturel n le reste de la division euclidienne de 4n −2n par 7.
Corrigé du Problème 2.
1. 20 = 1, 21 = 2, 22 = 4, 23 = 8 ≡ 1 (modulo 7). Donc l'ordre multiplicatif de 2 modulo 7 est égal à 3.
2. On pose n = 3k + s, s ∈ {0, 1, 2}, alors 2n = (23 )k 2s ≡ 2s (modulo 7). Donc r = 2s ∈ {1, 2, 4}.
3. ∀n ∈ N, on a 2n + 1 ≡ r + 1 ∈ {2, 3, 5} 6≡ 0. Donc 7 - 2n + 1.
4. Remarquons d'abord que 5 ≡ −2 et 4 ≡ −3 modulo 7. On a alors un = 2n + 32 + (−3)n + (−2)n .
Supposons que n est impair, n = 2k + 1, alors un ≡ 22k+1 + 32k+1 + (−3)2k+1 + (−2)2k+1 ≡ 0 (mod 7).
Supposons que n est pair, n = 2k + 1, alors un ≡ 22k + 32k + (−3)2k + (−2)2k ≡ 22k + 9k + 9k + 22k .
or 9 ≡ 2 (modulo 7), donc un ≡ 22k + 2k + 2k + 22k ≡ 22k+1 + 2k+1 ≡ 2k+1 (2k + 1).
on a 7 - 2k+1 et d'après la question 3, 7 - 2k + 1. Donc 7 - un , si n est pair.
5 - On a 4n − 2n = 22n − 2n = 2n (2n − 1). Comme l'ordre multiplicatif de 2 modulo 7 est égal à 3, on
pose n = 3k + s, où s ∈ {0, 1, 2}. On a alors 4n − 2n = 2n (2n − 1) ≡ 2s (2s − 1) (modulo 7).
Si n ≡ 0 (modulo 3), 4n − 2n ≡ 0 (modulo 7).
Si n ≡ 1 (modulo 3), 4n − 2n ≡ 2 (modulo 7).
Si n ≡ 2 (modulo 3), 4n − 2n ≡ 5 (modulo 7).
