Chapitre 2 — Arithmétique

Programme officiel — Maths expertes, thème arithmétique des entiers.

Mobilise : divisibilité, congruences, PGCD, théorèmes de Bezout et Gauss, applications cryptographiques.

Divisibilité dans $\mathbb{Z}$

Définition

$a$ divise $b$ (noté $a | b$) s'il existe $k \in \mathbb{Z}$ tel que $b = ka$.

Propriétés :

• $a | a$, $1 | a$, $a | 0$.
• Si $a | b$ et $b | c$, alors $a | c$ (transitivité).
• Si $a | b$ et $a | c$, alors $a | (\lambda b + \mu c)$ pour tous $\lambda, \mu \in \mathbb{Z}$ (linéarité).

Division euclidienne

Pour $a \in \mathbb{Z}$ et $b \in \mathbb{N}^*$, il existe un unique couple $(q, r)$ tel que : $a = bq + r \quad \text{avec} \quad 0 \leq r < b$

$q$ = quotient, $r$ = reste.

PGCD et algorithme d'Euclide

Définition

Le PGCD (plus grand commun diviseur) de $a$ et $b$ (entiers non tous nuls) est l'unique entier positif qui divise $a$ et $b$ et est divisible par tout diviseur commun.

Notation : $\text{PGCD}(a, b)$ ou $a \wedge b$.

Algorithme d'Euclide

Pour calculer $\text{PGCD}(a, b)$ avec $a \geq b > 0$ :

1. Division euclidienne : $a = bq + r$.
2. Si $r = 0$ : $\text{PGCD} = b$.
3. Sinon : $\text{PGCD}(a, b) = \text{PGCD}(b, r)$ — recommencer.

Exemple : $\text{PGCD}(252, 105)$.

• $252 = 105 \times 2 + 42$
• $105 = 42 \times 2 + 21$
• $42 = 21 \times 2 + 0$

Donc $\text{PGCD}(252, 105) = 21$.

Nombres premiers entre eux

$a$ et $b$ sont premiers entre eux si $\text{PGCD}(a, b) = 1$.

Théorèmes de Bezout et Gauss

Théorème de Bezout (identité de Bezout)

Pour tous $a, b \in \mathbb{Z}$ non tous nuls, il existe $u, v \in \mathbb{Z}$ tels que : $au + bv = \text{PGCD}(a, b)$

Corollaire : $a$ et $b$ premiers entre eux $\Leftrightarrow \exists u, v : au + bv = 1$.

Calcul de $(u, v)$ : algorithme d'Euclide étendu (remonter les divisions).

Théorème de Gauss

Si $a | bc$ et $\text{PGCD}(a, b) = 1$, alors $a | c$.

Application : pour résoudre $7x \equiv 3 \pmod{15}$ : comme $\text{PGCD}(7, 15) = 1$, par Bezout $7 \cdot 13 + 15 \cdot (-6) = 1$. Donc $7 \cdot 13 \equiv 1 \pmod{15}$. Donc $x \equiv 13 \cdot 3 = 39 \equiv 9 \pmod{15}$.

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.