#Arithmétique modulaireCopier le lien

L'arithmétique modulaire est un système de calcul où les nombres « bouclent » après avoir atteint une certaine valeur, appelée le module: 25 heures après midi, il est 1 heure, on calcule dans Z/13Z sans le dire. Elle est fondamentale en cryptographie, en théorie des nombres et partout où l'info manipule des cycles, des empreintes ou des tailles bornées.

Prérequis: division euclidienne (dividende, diviseur, quotient, reste), un peu d'algèbre ensembliste, notion de PGCD.

Objectifs d'apprentissage:

• Calculer avec les congruences et justifier chaque égalité par la propriété utilisée.
• Appliquer l'algorithme d'Euclide et sa version étendue (identité de Bézout) pour trouver un inverse modulaire.
• Utiliser le petit théorème de Fermat pour réduire une grande puissance avant de la calculer.
• Résoudre un système de congruences par le théorème des restes chinois.

#CongruencesCopier le lien

Deux entiers a et b sont congrus modulo n si leur différence est un multiple de n :

1a ≡ b (mod n)  ⟺  n divise (a - b)

#PropriétésCopier le lien

• Réflexivité : a ≡ a (mod n)
• Symétrie : a ≡ b (mod n) ⟹ b ≡ a (mod n)
• Transitivité : a ≡ b (mod n) et b ≡ c (mod n) ⟹ a ≡ c (mod n)

#OpérationsCopier le lien

• Addition : (a + b) mod n = ((a mod n) + (b mod n)) mod n
• Multiplication : (a × b) mod n = ((a mod n) × (b mod n)) mod n
• Soustraction : (a - b) mod n = ((a mod n) - (b mod n)) mod n

#PGCD (Plus Grand Commun Diviseur)Copier le lien

Le PGCD de deux entiers est le plus grand entier qui les divise tous les deux.

#Algorithme d'EuclideCopier le lien

1def pgcd(a, b):2    while b:3        a, b = b, a % b4    return a

#PropriétésCopier le lien

• Commutatif : pgcd(a, b) = pgcd(b, a)
• Associatif : pgcd(a, pgcd(b, c)) = pgcd(pgcd(a, b), c)
• Identité : pgcd(a, 0) = |a|

L'algorithme d'Euclide termine car le second argument décroît strictement (c'est a mod b, donc inférieur à b) tout en restant positif; il atteint donc 0. Sa correction repose sur l'invariant pgcd(a, b) = pgcd(b, a mod b), conséquence du fait que a et b ont exactement les mêmes diviseurs communs que b et a mod b.

#Inverse modulaireCopier le lien

L'inverse modulaire de a modulo m est un entier x tel que :

1(a × x) ≡ 1 (mod m)

Un inverse modulaire existe si et seulement si pgcd(a, m) = 1 (a et m sont copremiers).

#Pourquoi cette condition est nécessaire et suffisanteCopier le lien

L'identité de Bézout dit que l'ensemble des combinaisons au + mv, avec u et v entiers, est exactement l'ensemble des multiples de g = pgcd(a, m). Écrire au ≡ 1 (mod m) revient à dire qu'il existe v tel que au + mv = 1, donc que 1 est combinaison de a et m: cela n'arrive que si g divise 1, autrement dit g = 1. Si g > 1, aucun multiple de a n'est jamais congru à 1 modulo m. C'est aussi la raison profonde pour laquelle Z/nZ est un corps si et seulement si n est premier: tous les éléments non nuls y sont alors inversibles.

#Algorithme d'Euclide étenduCopier le lien

1def euclide_etendu(a, b):2    if b == 0:3        return a, 1, 04    else:5        d, x, y = euclide_etendu(b, a % b)6        return d, y, x - (a // b) * y7 8def inverse_modulaire(a, m):9    d, x, y = euclide_etendu(a, m)10    if d != 1:11        return None  # Pas d'inverse12    else:13        return x % m

La version étendue remonte les coefficients de Bézout en même temps qu'elle calcule le PGCD: elle renvoie d = pgcd(a, b) et des entiers x, y avec ax + by = d. Pour inverser a modulo m, on appelle euclide_etendu(a, m); si d = 1, le coefficient x vérifie ax ≡ 1 (mod m), et x mod m le met dans [0, m[.

Vérification systématique: si x = inverse_modulaire(a, m) est correct, alors (a * x) % m == 1. Ce test d'une ligne détecte les erreurs de signe dans les coefficients de Bézout, de loin les plus fréquentes.

#Explorer : résidus et opérationsCopier le lien

#Table mémoCopier le lien

#Réduire une puissance: Fermat puis exponentiation rapideCopier le lien

Le petit théorème de Fermat dit: si p est premier et a n'est pas un multiple de p, alors a^(p-1) ≡ 1 (mod p). On l'utilise pour ramener un exposant géant à un exposant petit avant tout calcul.

Exemple rédigé: calculer 7^120 mod 13.

1. Fermat donne 7^12 ≡ 1 (mod 13), car 13 est premier et 13 ne divise pas 7.
2. Division euclidienne de l'exposant par 12: 120 = 12 × 10, donc 7^120 = (7^12)^10 ≡ 1^10 = 1 (mod 13).

Autre exemple où un reste subsiste: 2^100 mod 7. Fermat donne 2^6 ≡ 1 (mod 7). Or 100 = 6 × 16 + 4, donc 2^100 = (2^6)^16 × 2^4 ≡ 1 × 16 ≡ 2 (mod 7). Vérification machine: pow(2, 100, 7) renvoie 2, et le test (a**e) % m == pow(a, e, m) sur de petits exposants confirme la méthode.

Pour la phase de calcul elle-même, l'exponentiation rapide (élévation au carré itérée) limite le coût à O(log e) multiplications modulaires: c'est le rôle du troisième argument de pow(a, e, m) en Python. Ne jamais écrire (a**e) % m sur de grands exposants: l'entier intermédiaire a^e est astronomique alors que le résultat final tient dans Z/mZ.

#Théorème des restes chinois: exemple completCopier le lien

Le CRT: si n1 et n2 sont premiers entre eux, le système x ≡ r1 (mod n1) et x ≡ r2 (mod n2) admet une solution unique modulo n1·n2. Construction pratique: poser g = n2 · inv(n2 mod n1, n1) et h = n1 · inv(n1 mod n2, n2); alors x = r1·g + r2·h est une solution (g vaut 1 modulo n1 et 0 modulo n2, h joue le rôle symétrique).

Résolvons x ≡ 2 (mod 3) et x ≡ 3 (mod 5):

1. inv(5, 3): 5 ≡ 2 (mod 3) et 2 × 2 = 4 ≡ 1 (mod 3), donc l'inverse vaut 2 et g = 5 × 2 = 10.
2. inv(3, 5): 3 × 2 = 6 ≡ 1 (mod 5), donc l'inverse vaut 2 et h = 3 × 2 = 6.
3. x = 2 × 10 + 3 × 6 = 38, et 38 mod 15 = 8.

Vérification: 8 mod 3 = 2 et 8 mod 5 = 3, les deux congruences sont satisfaites. La solution est unique modulo 15: les entiers 8, 23, 38, 53... sont la même classe dans Z/15Z. Retenez le geste de vérification: substituer la solution dans chacune des deux congruences de départ, systématiquement.

#Exercice : Implémentation d'opérations modulaires et chiffrement de CésarCopier le lien

Implémentez une bibliothèque d'arithmétique modulaire et utilisez-la pour créer un chiffrement de César.

#InstructionsCopier le lien

1. Implémentez les fonctions de base :
   • mod(a, n) : Calcul du modulo (toujours positif)
   • pgcd(a, b) : Calcul du PGCD
   • inverse_modulaire(a, m) : Calcul de l'inverse modulaire
2. Implémentez le chiffrement de César :
   • chiffrer_cesar(message, decalage) : Chiffre un message
   • dechiffrer_cesar(message_chiffre, decalage) : Déchiffre un message
3. Ajoutez une fonction pour casser le chiffre de César par force brute.

#Exemple de codeCopier le lien

1def mod(a, n):2    """Calcul du modulo toujours positif"""3    return a % n4 5def pgcd(a, b):6    """Calcul du PGCD par l'algorithme d'Euclide"""7    while b:8        a, b = b, a % b9    return abs(a)10 11def euclide_etendu(a, b):12    """Algorithme d'Euclide étendu"""13    if b == 0:14        return a, 1, 0

#Ordre d'un élément et théorème d'EulerCopier le lien

Le petit théorème de Fermat se généralise de deux façons utiles, qui portent sur le groupe multiplicatif $(\mathbb{Z}/n\mathbb{Z})^*$ des éléments inversibles modulo $n$.

Indicatrice d'Euler. On note $\varphi(n)$ le nombre d'entiers de $\{1, \ldots, n\}$ premiers avec $n$ ; c'est donc le cardinal de $(\mathbb{Z}/n\mathbb{Z})^*$. Propriétés à connaître :

• $\varphi(p) = p - 1$ pour $p$ premier ;
• $\varphi(p^k) = p^k - p^{k-1} = p^{k-1}(p-1)$ ;
• $\varphi$ est multiplicative : si $\gcd(m,n) = 1$, alors $\varphi(mn) = \varphi(m)\varphi(n)$.

On en déduit $\varphi(n) = n\prod_{p \mid n}\left(1 - \frac1p\right)$ pour la factorisation $n = \prod p_i^{\alpha_i}$.

Théorème d'Euler. Si $\gcd(a,n) = 1$, alors

$a^{\varphi(n)} \equiv 1 \pmod n.$

Preuve. La multiplication par $a$ induit une bijection de $(\mathbb{Z}/n\mathbb{Z})^*$ sur lui-même (c'est une permutation, car $a$ est inversible). Notons $u_1, \ldots, u_{\varphi(n)}$ les éléments de ce groupe. Alors les produits $au_1, \ldots, au_{\varphi(n)}$ sont exactement $u_1, \ldots, u_{\varphi(n)}$ dans un autre ordre, donc leurs produits sont égaux :

$\prod_{i} (au_i) \equiv \prod_i u_i \pmod n \implies a^{\varphi(n)} \prod_i u_i \equiv \prod_i u_i \pmod n.$

Comme $\prod_i u_i$ est inversible modulo $n$ (produit d'éléments inversibles), on peut le simplifier et obtenir $a^{\varphi(n)} \equiv 1$. ∎

Le petit théorème de Fermat est le cas particulier $n = p$ premier, où $\varphi(p) = p-1$.

Ordre d'un élément. Soit $a$ inversible modulo $n$. L'ordre de $a$ modulo $n$ est le plus petit entier $d \geq 1$ tel que $a^d \equiv 1 \pmod n$. Il divise toujours $\varphi(n)$ (théorème de Lagrange appliqué au sous-groupe engendré par $a$), ce qui donne un algorithme : pour trouver l'ordre, on teste les diviseurs de $\varphi(n)$, pas tous les entiers.

Exemple. Calculons l'ordre de $[3]_8$ dans $(\mathbb{Z}/8\mathbb{Z})^*$. On a $\gcd(3,8) = 1$, donc $[3]_8$ est inversible ; $\varphi(8) = 4$. Les puissances : $3^1 \equiv 3$, $3^2 = 9 \equiv 1 \pmod 8$. L'ordre vaut donc $2$, et le sous-groupe engendré est $\{[1]_8, [3]_8\}$. Comme $2 \mid 4 = \varphi(8)$, le théorème de Lagrange est bien vérifié.

#Théorème des restes chinoisCopier le lien

Énoncé (deux modules). Si $\gcd(n_1, n_2) = 1$, le système $x \equiv r_1 \pmod{n_1}$, $x \equiv r_2 \pmod{n_2}$ admet une solution, unique modulo $n_1n_2$.

Énoncé général. Si $n_1, \ldots, n_k$ sont deux à deux premiers entre eux, le système $x \equiv r_i \pmod{n_i}$ pour $i = 1, \ldots, k$ admet une solution unique modulo $N = n_1n_2\cdots n_k$.

Preuve de l'unicité. Si $x$ et $y$ sont deux solutions, alors $n_i \mid x - y$ pour tout $i$. Comme les $n_i$ sont deux à deux premiers entre eux, leur produit $N$ divise $x-y$ : donc $x \equiv y \pmod N$. ∎

Preuve de l'existence (version constructive). Pour chaque $i$, posons $N_i = N/n_i$ et $e_i = N_i \cdot \left(N_i^{-1} \bmod n_i\right)$. Alors $e_i \equiv 1 \pmod{n_i}$ et $e_i \equiv 0 \pmod{n_j}$ pour $j \neq i$ (car $n_j \mid N_i$). Une solution est donc

$x = \sum_{i=1}^{k} r_i\, e_i.$

Cette construction fournit aussi l'isomorphisme de groupes

$\mathbb{Z}/N\mathbb{Z} \;\cong\; \mathbb{Z}/n_1\mathbb{Z} \times \cdots \times \mathbb{Z}/n_k\mathbb{Z},$

qui est la véritable raison d'être du théorème : il découpe un calcul modulo un grand nombre composé en calculs indépendants modulo des nombres premiers entre eux. C'est exactement le mécanisme du RSA-CRT, qui accélère le déchiffrement d'un facteur 4 environ en travaillant modulo $p$ et $q$ séparément.

Quand les modules ne sont pas premiers entre eux. Le système $x \equiv r_1 \pmod{n_1}$, $x \equiv r_2 \pmod{n_2}$ admet une solution si et seulement si

$r_1 \equiv r_2 \pmod{\gcd(n_1, n_2)},$

et dans ce cas les solutions forment une classe modulo $\mathrm{lcm}(n_1, n_2)$. C'est le critère de compatibilité à connaître : sans lui, on peut chercher indéfiniment une solution qui n'existe pas.

#Structure de $\mathbb{Z}/n\mathbb{Z}$Copier le lien

L'anneau $\mathbb{Z}/n\mathbb{Z}$ est un corps si et seulement si $n$ est premier. C'est une conséquence directe de l'équivalence établie plus haut : $a$ est inversible modulo $n$ si et seulement si $\gcd(a,n) = 1$. Donc

• si $n = p$ premier, tous les éléments non nuls sont inversibles : $\mathbb{Z}/p\mathbb{Z}$ est un corps ;
• si $n$ est composé, $n = ab$ avec $1 < a,b < n$ donne $[a]_n \cdot [b]_n = [0]_n$ avec les deux facteurs non nuls : ce sont des diviseurs de zéro, et l'anneau n'est pas intègre, donc pas un corps.

Exemple. Dans $\mathbb{Z}/6\mathbb{Z}$, $[2]_6 \cdot [3]_6 = [6]_6 = [0]_6$ : l'anneau n'est pas intègre. Dans $\mathbb{Z}/7\mathbb{Z}$, tous les éléments non nuls ont un inverse ($2^{-1} = 4$ car $2 \cdot 4 = 8 \equiv 1$, $3^{-1} = 5$ car $15 \equiv 1$, $6^{-1} = 6$ car $36 \equiv 1$) : c'est un corps.

#ApplicationsCopier le lien

#HachageCopier le lien

• Tables de hachage : Utilisation de modulo pour distribuer les clés
• Fonctions de hachage : Calculs modulaires pour garantir des valeurs dans une plage

#CryptographieCopier le lien

• Chiffre de César : Chiffrement par décalage modulaire
• RSA : Opérations modulaires avec de grands nombres premiers
• Courbes elliptiques : Arithmétique sur des points modulo p

#Théorie des nombresCopier le lien

• Petit théorème de Fermat : a^(p-1) ≡ 1 (mod p) si p premier et p ne divise pas a
• Théorème des restes chinois : Résolution de systèmes de congruences
• Z/nZ est un corps si et seulement si n est premier (tous les non-nuls inversibles)

#Playground: inverse modulaire (Euclide étendu)Copier le lien

#Questions typesCopier le lien

• Démontrer qu'un inverse modulaire n'existe pas lorsque le PGCD est supérieur à 1.
• Résoudre un système de congruences par le théorème des restes chinois.
• Appliquer le petit théorème de Fermat pour simplifier une puissance (ex.: ).
• Montrer qu'une suite récurrente modulo 11 est périodique et déterminer la période.

#Check‑list modulaireCopier le lien

• Poser systématiquement le PGCD pour savoir si une équation est solvable.
• Savoir passer d'une congruence à une égalité en notant le reste.
• Être à l'aise avec le CRT pour combiner des systèmes de congruences.
• Vérifier ses solutions en les substituant dans l'énoncé.