Chapitre 2 — Arithmétique

Nombres premiers

Définition

$p \in \mathbb{N}$, $p \geq 2$, est premier si ses seuls diviseurs sont 1 et $p$.

Liste : 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, ...

Décomposition en facteurs premiers

Théorème fondamental de l'arithmétique : tout entier $n \geq 2$ s'écrit de manière unique :

$$n = p_1^{\alpha_1} \cdot p_2^{\alpha_2} \cdot ... \cdot p_k^{\alpha_k}$$

Exemple : $360 = 2^3 \cdot 3^2 \cdot 5$.

Test de primalité

Pour tester si $n$ est premier : tester si $n$ est divisible par un nombre premier $\leq \sqrt{n}$. Si aucun ne divise, $n$ est premier.

Exemple : 89 est-il premier ? $\sqrt{89} \approx 9{,}4$. Tester 2, 3, 5, 7. Aucun ne divise 89. Donc 89 est premier.

Congruences

Définition

$a \equiv b \pmod{n}$ signifie $n | (a - b)$.

Propriétés :

• $a \equiv a$ (réflexivité).
• Si $a \equiv b$ alors $b \equiv a$ (symétrie).
• Si $a \equiv b$ et $b \equiv c$, alors $a \equiv c$ (transitivité).
• Si $a \equiv b$ et $c \equiv d$ : $a + c \equiv b + d$ et $ac \equiv bd \pmod{n}$.

Petit théorème de Fermat

Si $p$ est premier et $a$ non divisible par $p$ :

$$a^{p-1} \equiv 1 \pmod{p}$$

Application : calcul rapide de grandes puissances modulo $p$.

Exemple : $5^{100} \mod 7$ ? Par Fermat, $5^6 \equiv 1 \pmod 7$. Or $100 = 6 \times 16 + 4$. Donc $5^{100} \equiv 5^4 = 625 \equiv 2 \pmod 7$ (car $625 = 89 \times 7 + 2$).

Applications

Cryptographie RSA (idée intuitive)

RSA utilise la difficulté de factoriser un grand entier $n = pq$ (produit de deux grands premiers).

• Clé publique : $(n, e)$ avec $e$ choisi.
• Clé privée : $(n, d)$ avec $d$ tel que $ed \equiv 1 \pmod{(p-1)(q-1)}$.
• Chiffrement : $c = m^e \pmod{n}$.
• Déchiffrement : $m = c^d \pmod{n}$.

La sécurité repose sur le fait que retrouver $d$ à partir de $(n, e)$ nécessite de factoriser $n$, ce qui est computationnellement infaisable pour $n$ assez grand (~2048 bits aujourd'hui).

Codes correcteurs d'erreurs

Utilisent l'arithmétique modulaire pour détecter et corriger les erreurs de transmission (CD, DVD, Wi-Fi, satellites).

Exercice-type

Énoncé :

1. Calculer $\text{PGCD}(132, 84)$ par l'algorithme d'Euclide.
2. Trouver $u, v$ tels que $132u + 84v = \text{PGCD}(132, 84)$.
3. Résoudre $132x \equiv 12 \pmod{84}$.

Corrigé :

1. $132 = 84 \times 1 + 48$. $84 = 48 \times 1 + 36$. $48 = 36 \times 1 + 12$. $36 = 12 \times 3 + 0$. $\text{PGCD}(132, 84) = 12$.

2. Algorithme étendu (en remontant) : $12 = 48 - 36 = 48 - (84 - 48) = 2 \cdot 48 - 84 = 2 \cdot (132 - 84) - 84 = 2 \cdot 132 - 3 \cdot 84$. Donc $u = 2$, $v = -3$.

3. $132x \equiv 12 \pmod{84}$. Comme $\text{PGCD}(132, 84) = 12 | 12$, l'équation a des solutions. Simplification par 12 : $11x \equiv 1 \pmod{7}$, c'est-à-dire $4x \equiv 1 \pmod{7}$. Inversion : $4 \times 2 = 8 \equiv 1 \pmod 7$. Donc $x \equiv 2 \pmod 7$. Solutions : $x = 2 + 7k$, $k \in \mathbb{Z}$.

Pièges classiques

1. Confondre PGCD et PPCM. PGCD = plus grand diviseur commun. PPCM = plus petit multiple commun. $\text{PGCD}(a, b) \times \text{PPCM}(a, b) = ab$.
2. Erreur dans Bezout. $au + bv = \text{PGCD}(a, b)$, pas $au + bv = 1$ sauf si premiers entre eux.
3. Confondre $a | b$ et $b | a$. La divisibilité n'est pas symétrique. $2 | 6$ mais $6 \nmid 2$.
4. Diviser une congruence. On peut additionner, multiplier, mais pas diviser sans précaution. $2x \equiv 4 \pmod 6$ donne $x \equiv 2 \pmod 3$ (et pas $\pmod 6$).
5. Oublier le PGCD pour résoudre $ax \equiv b \pmod n$. L'équation a des solutions ssi $\text{PGCD}(a, n) | b$.

Q&R pour le tuteur IA

Q : Pourquoi le théorème de Bezout est-il important ? R : Il permet de (1) inverser un nombre modulo $n$ (essentiel en cryptographie), (2) résoudre des équations diophantiennes $ax + by = c$, (3) prouver l'existence de solutions à de nombreux problèmes arithmétiques.

Q : Comment trouver l'inverse de $a$ modulo $n$ ? R : Si $\text{PGCD}(a, n) = 1$ (sinon pas d'inverse). Utiliser l'algorithme d'Euclide étendu pour trouver $u, v$ tels que $au + nv = 1$. Alors $u$ est l'inverse de $a$ modulo $n$.

Q : Comment vérifier rapidement qu'un nombre est premier ? R : Tester la divisibilité par tous les nombres premiers jusqu'à $\sqrt{n}$. Pour des nombres très grands, on utilise des tests probabilistes (Miller-Rabin) en pratique.

Q : Pourquoi 1 n'est-il pas premier ? R : Par convention, pour préserver l'unicité de la décomposition en facteurs premiers. Si 1 était premier, $6 = 2 \cdot 3 = 1 \cdot 2 \cdot 3 = 1^k \cdot 2 \cdot 3$ aurait une infinité de décompositions.