Comment calculer le reste d'une grande puissance, par exemple $3^{100}$ modulo 7 ?

On cherche une petite puissance congrue à 1 (ou à $-1$) : $3^2 = 9 \equiv 2$, $3^3 \equiv 6 \equiv -1$, donc $3^6 \equiv 1 \ [7]$ (on peut aussi l'obtenir directement par le petit théorème de Fermat). On divise l'exposant : $100 = 6 \times 16 + 4$, d'où $3^{100} = (3^6)^{16} \times 3^4 \equiv 3^4 = 81 \equiv 4 \ [7]$. On réduit à chaque étape pour ne jamais manipuler de grands nombres.

Comment résoudre $ax \equiv b \ [n]$ ?

Si $a$ et $n$ sont premiers entre eux, $a$ admet un inverse $a'$ modulo $n$ (tel que $aa' \equiv 1 \ [n]$), obtenu par Bézout ou par essais ; on multiplie par $a'$ : $x \equiv a'b \ [n]$, solution unique modulo $n$. Exemple : $3x \equiv 2 \ [7]$ ; l'inverse de 3 est 5 car $15 \equiv 1$, donc $x \equiv 10 \equiv 3 \ [7]$. Si $d = \text{PGCD}(a, n) > 1$, il faut que $d$ divise $b$ (sinon aucune solution) et on divise tout, y compris le modulo, par $d$.

Pourquoi peut-on additionner et multiplier des congruences, mais pas les diviser ?

Si $a \equiv b$ et $c \equiv d \ [n]$, alors $n$ divise $a - b$ et $c - d$, donc divise $(a + c) - (b + d)$ et $ac - bd = a(c - d) + d(a - b)$ : la compatibilité est démontrée. En revanche $2 \times 3 \equiv 2 \times 0 \ [6]$ sans que $3 \equiv 0 \ [6]$ : on ne peut simplifier par $c$ que si $c$ est premier avec $n$ (théorème de Gauss).

Congruences — BgMaths

Définitions

Définition 1 — congruence modulo $n$ . Soit $n \in \mathbb{N}^*$ et $a, b \in \mathbb{Z}$ . On dit que $a$ est congru à $b$ modulo $n$ , et on note $a \equiv b \ [n]$ (ou $a \equiv b \pmod n$ ), si $n$ divise $a - b$ . Exemples : $17 \equiv 2 \ [5]$ , $-17 \equiv 3 \ [5]$ , $-3 \equiv 2 \ [5]$ , $12 \equiv 2 \ [5]$ . La relation est réflexive ( $a \equiv a$ ), symétrique ( $a \equiv b \Rightarrow b \equiv a$ ) et transitive ( $a \equiv b$ et $b \equiv c \Rightarrow a \equiv c$ ).

Définition 2 — inverse modulo $n$ . Un entier $a$ est inversible modulo $n$ s’il existe un entier $a'$ tel que $aa' \equiv 1 \ [n]$ ; $a'$ est un inverse de $a$ modulo $n$ . Exemple : modulo 7, $3 \times 5 = 15 \equiv 1$ , donc $3^{-1} \equiv 5$ et $5^{-1} \equiv 3$ .

Théorèmes et propriétés

Théorème 1 (congruence et restes). (démonstration exigible) $a \equiv b \ [n]$ si et seulement si $a$ et $b$ ont le même reste dans la division euclidienne par $n$ . En particulier, tout entier $a$ est congru modulo $n$ à un unique entier de $\{0, 1, \ldots, n - 1\}$ : son reste ; et $a \equiv 0 \ [n] \iff n \mid a$ .

Démonstration : si $a = nq + r$ et $b = nq' + r'$ avec $0 \leq r, r' < n$ , alors $a - b = n(q - q') + (r - r')$ avec $-n < r - r' < n$ . Donc $n \mid a - b \iff n \mid r - r' \iff r = r'$ .

Théorème 2 (compatibilité avec les opérations). (démonstration exigible) Si $a \equiv b \ [n]$ et $c \equiv d \ [n]$ , alors :

$a + c \equiv b + d \ [n] \qquad a - c \equiv b - d \ [n] \qquad ac \equiv bd \ [n] \qquad a^k \equiv b^k \ [n] \ (k \in \mathbb{N})$

Démonstration : $n \mid a - b$ et $n \mid c - d$ donnent $n \mid (a + c) - (b + d) = (a - b) + (c - d)$ et $n \mid ac - bd = a(c - d) + d(a - b)$ (combinaisons linéaires). Les puissances s’obtiennent par récurrence à partir du produit : si $a^k \equiv b^k$ , alors $a^{k+1} = a^k \cdot a \equiv b^k \cdot b = b^{k+1}$ .

Attention : pas de division. $2 \times 3 \equiv 2 \times 0 \ [6]$ mais $3 \not\equiv 0 \ [6]$ . On ne peut simplifier $ac \equiv bc \ [n]$ par $c$ que si $\text{PGCD}(c, n) = 1$ : en effet $n \mid c(a - b)$ et $n$ premier avec $c$ donnent $n \mid a - b$ par le théorème de Gauss (chapitre PGCD).

Théorème 3 (tests de divisibilité). Soit $N$ un entier d’écriture décimale $\overline{c_k \ldots c_1 c_0}$ , c’est-à-dire $N = \sum_{i=0}^{k} c_i 10^i$ .

Par 9 et par 3 : $10 \equiv 1 \ [9]$ , donc $N \equiv c_0 + c_1 + \cdots + c_k \ [9]$ (et de même modulo 3) : $N$ est divisible par 9 (resp. 3) si et seulement si la somme de ses chiffres l’est.
Par 11 : $10 \equiv -1 \ [11]$ , donc $N \equiv c_0 - c_1 + c_2 - \cdots \ [11]$ (somme alternée des chiffres).
Par 4 et par 25 : $100 \equiv 0 \ [4]$ , donc $N \equiv \overline{c_1 c_0} \ [4]$ (les deux derniers chiffres suffisent) ; par 8 : les trois derniers.
Par 2 et par 5 : $10 \equiv 0$ , donc $N \equiv c_0$ .

Exemples : $123456 \equiv 1 + 2 + 3 + 4 + 5 + 6 = 21 \equiv 3 \ [9]$ ; $918082 \equiv 2 - 8 + 0 - 8 + 1 - 9 = -22 \equiv 0 \ [11]$ ; $2024 \equiv 24 \equiv 0 \ [4]$ . En base 7, $7 \equiv 1 \ [6]$ : un nombre écrit en base 7 est divisible par 6 si et seulement si la somme de ses chiffres l’est.

Théorème 4 (inversibilité modulo $n$ ). $a$ est inversible modulo $n$ si et seulement si $\text{PGCD}(a, n) = 1$ . L’inverse est alors unique modulo $n$ .

Démonstration : si $aa' \equiv 1 \ [n]$ , alors $aa' - 1 = nk$ , soit $aa' + n(-k) = 1$ : par le théorème de Bézout, $a$ et $n$ sont premiers entre eux. Réciproquement, si $\text{PGCD}(a, n) = 1$ , Bézout donne $au + nv = 1$ , d’où $au \equiv 1 \ [n]$ : $u$ est un inverse. Unicité : si $aa' \equiv aa'' \equiv 1$ , alors $a' \equiv a'(aa'') = (a'a)a'' \equiv a'' \ [n]$ .

Exemples : modulo 26, $5 \times 21 = 105 = 4 \times 26 + 1$ , donc $5^{-1} \equiv 21$ . Le nombre 4 n’est pas inversible modulo 10 car $\text{PGCD}(4, 10) = 2$ .

Théorème 5 (petit théorème de Fermat) (admis ici ; la démonstration figure au chapitre Nombres premiers). Soit $p$ un nombre premier.

Si $a$ est un entier non divisible par $p$ , alors $a^{p-1} \equiv 1 \ [p]$ .
Pour tout entier $a$ , $a^p \equiv a \ [p]$ .

Les deux énoncés sont équivalents : le second s’obtient en multipliant le premier par $a$ (et il est évident si $p \mid a$ ) ; réciproquement, si $p \nmid a$ , on simplifie $a^p \equiv a$ par $a$ , premier avec $p$ .

Attention. L’hypothèse $p$ premier est essentielle : $2^3 = 8 \equiv 0 \not\equiv 1 \ [4]$ . La réciproque est fausse : $2^{340} \equiv 1 \ [341]$ alors que $341 = 11 \times 31$ .

Exemple : $n^7 - n$ est divisible par 7 pour tout entier $n$ ; on peut montrer qu’il est aussi divisible par 2 et 3, donc par 42.

Méthodes

Méthode 1 — calculer modulo $n$ en réduisant à chaque étape.

Remplacer chaque nombre par son reste modulo $n$ , ou par un représentant commode comme $-1$ (Théorème 1).
Effectuer les opérations sur ces petits représentants (Théorème 2).
Réduire le résultat dans $\{0, \ldots, n - 1\}$ pour donner le reste.

Exemple : $2023 \times 2024 + 2025^2 \equiv 0 \times 1 + 2^2 = 4 \ [7]$ car $2023 = 7 \times 289$ , $2024 \equiv 1$ et $2025 \equiv 2 \ [7]$ .

Méthode 2 — raisonner par disjonction de cas.

Modulo $n$ , il n’y a que $n$ cas : $x \equiv 0, 1, \ldots, n - 1$ .
Calculer l’expression étudiée dans chaque cas (Théorème 2).
Conclure sur les valeurs possibles.

Exemple : restes de $n^2$ modulo 4 : si $n \equiv 0, 1, 2, 3$ , alors $n^2 \equiv 0, 1, 0, 1 \ [4]$ : un carré est congru à 0 ou 1 modulo 4. Conséquence : un entier de la forme $4k + 3$ n’est jamais somme de deux carrés. Autre exemple : $n^3 \equiv n \ [6]$ pour tout $n$ (on vérifie les six cas).

Méthode 3 — calculer une puissance $a^k$ modulo $n$ .

Chercher un exposant $m$ tel que $a^m \equiv 1$ (ou $-1$ ) $[n]$ : essais successifs, ou petit théorème de Fermat (Théorème 5) si $n$ est premier.
Écrire la division euclidienne de l’exposant : $k = mq + r$ .
Conclure : $a^k = (a^m)^q \times a^r \equiv a^r \ [n]$ (Théorème 2), puis réduire $a^r$ .

Exemple : $3^{100}$ modulo 7 : $3^6 \equiv 1 \ [7]$ et $100 = 6 \times 16 + 4$ , donc $3^{100} \equiv 3^4 = 81 \equiv 4 \ [7]$ . Chiffre des unités de $7^{222}$ : modulo 10, $7^2 \equiv -1$ donc $7^4 \equiv 1$ ; $222 = 4 \times 55 + 2$ , d’où $7^{222} \equiv 7^2 \equiv 9 \ [10]$ .

def puissance_mod(a, k, n):
    """Reste de a**k modulo n, en reduisant a chaque etape."""
    r = 1
    for _ in range(k):
        r = (r * a) % n
    return r

print(puissance_mod(3, 100, 7))   # 4
print(pow(3, 100, 7))             # fonction native de Python : 4

Méthode 4 — trouver un inverse modulo $n$ .

Vérifier que $\text{PGCD}(a, n) = 1$ (Théorème 4), sinon il n’y a pas d’inverse.
Pour un petit modulo : tester $a \times 1, a \times 2, \ldots$ jusqu’à trouver un produit congru à 1.
Sinon : écrire une relation de Bézout $au + nv = 1$ (algorithme d’Euclide étendu, chapitre PGCD) ; alors $a^{-1} \equiv u \ [n]$ .

Exemple : inverse de 5 modulo 26 : $5 \times 21 = 105 = 4 \times 26 + 1$ , donc $5^{-1} \equiv 21 \ [26]$ . Par Bézout : $5 \times 21 + 26 \times (-4) = 1$ .

Méthode 5 — résoudre $ax \equiv b \ [n]$ .

Calculer $d = \text{PGCD}(a, n)$ .
Si $d = 1$ : multiplier par l’inverse $a'$ de $a$ (Méthode 4) : $x \equiv a'b \ [n]$ , unique solution modulo $n$ (Théorème 4).
Si $d > 1$ : si $d \nmid b$ , aucune solution ; si $d \mid b$ , diviser $a$ , $b$ et $n$ par $d$ , résoudre comme en 2, puis remonter modulo $n$ : il y a $d$ solutions modulo $n$ .

Exemple : $3x \equiv 2 \ [7]$ : $x \equiv 5 \times 2 = 10 \equiv 3 \ [7]$ . $4x \equiv 6 \ [10]$ : $d = 2 \mid 6$ , donc $2x \equiv 3 \ [5]$ , $x \equiv 3 \times 3 \equiv 4 \ [5]$ , soit $x \equiv 4$ ou $9 \ [10]$ . $6x \equiv 5 \ [9]$ : $\text{PGCD}(6, 9) = 3 \nmid 5$ , aucune solution.

Méthode 6 — coder et décoder par chiffrement affine.

Numéroter les lettres de 0 (A) à 25 (Z) ; choisir une clé $(a, b)$ avec $\text{PGCD}(a, 26) = 1$ (condition qui garantit que deux lettres différentes ont des codes différents, Théorème 4). Coder : $y \equiv ax + b \ [26]$ .
Pour décoder : calculer l’inverse $a'$ de $a$ modulo 26 (Méthode 4), puis $x \equiv a'(y - b) \ [26]$ .
Réduire chaque résultat dans $\{0, \ldots, 25\}$ et revenir aux lettres.

Exemple : clé $(5, 3)$ : la lettre E ( $x = 4$ ) devient $y \equiv 23$ , soit X. Comme $5 \times 21 \equiv 1 \ [26]$ , le déchiffrement est $x \equiv 21(y - 3) \ [26]$ : pour $y = 23$ , $x \equiv 21 \times 20 = 420 \equiv 4$ , on retrouve E. Le chiffrement de César est le cas $a = 1$ . Même principe pour les clés de contrôle : le numéro de sécurité sociale vérifie $N + c \equiv 0 \ [97]$ et le code ISBN-10 $\sum_{i=1}^{10} i\,c_i \equiv 0 \ [11]$ ; ces congruences détectent toute erreur sur un chiffre.

Définitions

Théorèmes et propriétés

Méthodes

Reste informé