Quiz — Congruences

Question 1 : Quel est le reste de la division euclidienne de $3^{100}$ par $7$ ?

• $1$
• $2$
• ✓ $4$
• $6$

Explication : On applique la **Méthode 3 — calculer une puissance modulo $n$** : $3^3 = 27 \equiv -1 \ [7]$, donc $3^6 \equiv 1 \ [7]$ (c'est aussi ce que donne directement le **Théorème 5 (petit théorème de Fermat)** avec $p = 7$). On divise l'exposant : $100 = 6 \times 16 + 4$, d'où, par le **Théorème 2 (compatibilité avec les opérations)**, $3^{100} = (3^6)^{16} \times 3^4 \equiv 1^{16} \times 81 = 81 = 11 \times 7 + 4 \equiv 4 \ [7]$ : option C.

Question 2 : Quel est l'inverse de $5$ modulo $7$ ?

• $2$
• ✓ $3$
• $5$
• $6$

Explication : D'après la **Définition 2 — inverse modulo $n$**, on cherche $x$ tel que $5x \equiv 1 \ [7]$. Par la **Méthode 4 — trouver un inverse modulo $n$** (essais successifs) : $5 \times 3 = 15 = 2 \times 7 + 1 \equiv 1 \ [7]$. L'inverse est $3$ : option B, et il est unique modulo 7 d'après le **Théorème 4 (inversibilité modulo $n$)** car $\text{PGCD}(5, 7) = 1$. La relation de Bézout $5 \times 3 + 7 \times (-2) = 1$ donne la même chose.

Question 3 : Quelle est la solution de $3x \equiv 2 \ [7]$ dans $\{0, 1, \ldots, 6\}$ ?

• ✓ $x = 3$
• $x = 5$
• $x = 2$
• $x = 6$

Explication : On applique la **Méthode 5 — résoudre $ax \equiv b \ [n]$** : $\text{PGCD}(3, 7) = 1$, donc le **Théorème 4 (inversibilité modulo $n$)** garantit une unique solution modulo 7. L'inverse de 3 est 5 car $3 \times 5 = 15 \equiv 1 \ [7]$ (**Méthode 4**). En multipliant par 5 : $x \equiv 5 \times 2 = 10 \equiv 3 \ [7]$ : option A. Vérification : $3 \times 3 = 9 \equiv 2 \ [7]$.

Question 4 : Quel est le reste de la division de $123456$ par $9$ ?

• $0$
• ✓ $3$
• $6$
• $21$

Explication : D'après le **Théorème 3 (tests de divisibilité)**, comme $10 \equiv 1 \ [9]$, tout entier est congru modulo 9 à la somme de ses chiffres : $123456 \equiv 1 + 2 + 3 + 4 + 5 + 6 = 21 \equiv 2 + 1 = 3 \ [9]$ : option B. Attention : 21 n'est pas un reste valable car $21 \geq 9$ ; d'après le **Théorème 1 (congruence et restes)**, le reste est l'unique représentant dans $\{0, \ldots, 8\}$.

Question 5 : Un chiffrement affine code la lettre de rang $x$ ($0 \leq x \leq 25$) par le rang $y \equiv 5x + 3 \ [26]$. Sachant que $5 \times 21 \equiv 1 \ [26]$, la fonction de déchiffrement est :

• $x \equiv 5(y - 3) \ [26]$
• $x \equiv \dfrac{y - 3}{5}$
• ✓ $x \equiv 21(y - 3) \ [26]$
• $x \equiv 21y + 3 \ [26]$

Explication : C'est la **Méthode 6 — coder et décoder par chiffrement affine** : de $y \equiv 5x + 3$ on tire $5x \equiv y - 3 \ [26]$, puis on multiplie par l'inverse 21 de 5 modulo 26 (**Définition 2** et **Méthode 4**) : $x \equiv 21(y - 3) \ [26]$ : option C. Il n'y a jamais de division dans les congruences : on multiplie par un inverse, qui existe ici car $\text{PGCD}(5, 26) = 1$ (**Théorème 4 (inversibilité modulo $n$)**).

Question 6 : Laquelle de ces implications est vraie pour tous entiers $a, b, c$ et tout $n \geq 2$ ?

• $a^2 \equiv b^2 \ [n] \Rightarrow a \equiv b \ [n]$
• $ac \equiv bc \ [n] \Rightarrow a \equiv b \ [n]$
• $a \equiv b \ [n] \Rightarrow a \equiv b \ [2n]$
• ✓ $a \equiv b \ [n] \Rightarrow a^2 \equiv b^2 \ [n]$

Explication : Le **Théorème 2 (compatibilité avec les opérations)** permet de multiplier deux congruences membre à membre : $a \equiv b \Rightarrow a \times a \equiv b \times b$, donc $a^2 \equiv b^2 \ [n]$ : option D. Les réciproques et les autres implications sont fausses : $1^2 \equiv 2^2 \ [3]$ mais $1 \not\equiv 2$ ; $2 \times 3 \equiv 2 \times 0 \ [6]$ mais $3 \not\equiv 0$ (pas de simplification sans $\text{PGCD}(c, n) = 1$) ; $1 \equiv 4 \ [3]$ mais $1 \not\equiv 4 \ [6]$.

Question 7 : Le tableau donne les restes de $2^k$ modulo $11$ pour $k = 1$ à $10$. Quel est le reste de $2^{2024}$ modulo $11$ ?

• $1$
• ✓ $5$
• $4$
• $2$

Explication : Le tableau montre $2^{10} \equiv 1 \ [11]$, conformément au **Théorème 5 (petit théorème de Fermat)** ($p = 11$ premier, $11 \nmid 2$). On applique la **Méthode 3 — calculer une puissance modulo $n$** : $2024 = 10 \times 202 + 4$, donc $2^{2024} = (2^{10})^{202} \times 2^4 \equiv 1^{202} \times 16 = 16 \equiv 5 \ [11]$ : option B.

Question 8 : Quel est l'ensemble des solutions de $4x \equiv 6 \ [10]$ dans $\{0, 1, \ldots, 9\}$ ?

• $\{4\}$
• $\{9\}$
• Aucune solution
• ✓ $\{4\,;9\}$

Explication : C'est le second cas de la **Méthode 5 — résoudre $ax \equiv b \ [n]$** : $d = \text{PGCD}(4, 10) = 2$ divise 6, donc on divise tout, **y compris le modulo**, par 2 : $2x \equiv 3 \ [5]$. L'inverse de 2 modulo 5 est 3 ($2 \times 3 = 6 \equiv 1$, **Méthode 4**), donc $x \equiv 9 \equiv 4 \ [5]$. Modulo 10, cela donne $d = 2$ solutions : $x = 4$ et $x = 9$ : option D. Vérification : $16 \equiv 6$ et $36 \equiv 6 \ [10]$.

Question 9 : Quel est le chiffre des unités de $7^{222}$ ?

• ✓ $9$
• $1$
• $3$
• $7$

Explication : Le chiffre des unités est le reste modulo 10 (**Théorème 3 (tests de divisibilité)** : $10 \equiv 0 \ [10]$ pour toutes les puissances supérieures). On applique la **Méthode 3 — calculer une puissance modulo $n$** : $7^2 = 49 \equiv -1 \ [10]$, donc $7^4 \equiv 1 \ [10]$. Comme $222 = 4 \times 55 + 2$, le **Théorème 2 (compatibilité)** donne $7^{222} = (7^4)^{55} \times 7^2 \equiv 7^2 \equiv 9 \ [10]$ : option A.

Question 10 : Question type bac. Quels sont les restes possibles de $n^2$ modulo $4$, pour $n$ entier ?

• ✓ $0$ ou $1$
• $0$, $1$, $2$ ou $3$
• $0$ seulement
• $1$ ou $3$

Explication : On applique la **Méthode 2 — raisonner par disjonction de cas** : modulo 4, $n \equiv 0, 1, 2$ ou $3$, et le **Théorème 2 (compatibilité avec les opérations)** donne $n^2 \equiv 0^2, 1^2, 2^2, 3^2$, soit $0, 1, 0, 1 \ [4]$. Donc $n^2 \equiv 0$ ou $1 \ [4]$ : option A (0 si $n$ pair, 1 si $n$ impair). Conséquence : un entier congru à 2 ou 3 modulo 4 n'est pas un carré, et un entier congru à 3 modulo 4 n'est pas somme de deux carrés.