MathQuest — Maths pour l'ingénieur

💡

Pourquoi apprendre ça ?

Le PGCD (Plus Grand Commun Diviseur) de deux entiers est le plus grand entier qui divise les deux. Il mesure le "facteur commun maximal". L'algorithme d'Euclide permet de le calculer en quelques étapes, sans factoriser — une des plus anciennes et plus efficaces techniques mathématiques.

🎯

Analogie

Tu veux couper deux planches de 48 cm et 36 cm en morceaux égaux les plus grands possibles, sans gaspillage. La longueur idéale est le PGCD(48, 36) = 12 cm. L'algorithme d'Euclide trouve cette valeur en effectuant des divisions successives, comme peser avec une balance en retirant itérativement la plus petite quantité de la plus grande.

📐

Théorie

Un entier $a$ divise $b$ (noté $a \mid b$ ) si $\exists k \in \mathbb{Z},\ b = ka$ .

Le Plus Grand Commun Diviseur (PGCD) de $a, b \in \mathbb{Z}$ (non tous nuls) :

$\gcd(a, b) = \max\{d \in \mathbb{N}^* \mid d \mid a \text{ et } d \mid b\}$

Propriétés :

$\gcd(a, 0) = |a|$
$\gcd(a, b) = \gcd(b, a)$
$\gcd(a, b) = \gcd(-a, b) = \gcd(|a|, |b|)$
$\gcd(a, b) = \gcd(a - b, b)$ — clé de l'algorithme d'Euclide
$\gcd(a, b) \mid a$ et $\gcd(a, b) \mid b$

$a$ et $b$ sont premiers entre eux (copremiers) si $\gcd(a, b) = 1$ .

📝

Calcul direct du PGCD

$\gcd(12, 18)$ : diviseurs de 12 = $\{1,2,3,4,6,12\}$ , diviseurs de 18 = $\{1,2,3,6,9,18\}$ .

Diviseurs communs : $\{1, 2, 3, 6\}$ . Le plus grand : $\gcd(12, 18) = 6$ .

Cette méthode est inefficace pour de grands nombres — l'algorithme d'Euclide est bien plus rapide.

📐

Théorie

Algorithme des divisions successives (Euclide) :

Basé sur la propriété : $\gcd(a, b) = \gcd(b, a \bmod b)$

Euclide(a, b):
  tant que b ≠ 0 :
    r ← a mod b
    a ← b
    b ← r
  retourner a

Convergence : à chaque étape, $b$ diminue strictement. L'algorithme s'arrête quand $b = 0$ .

Complexité : $O(\log(\min(a,b)))$ étapes — très efficace même pour de très grands entiers.

📝

Trace de l'algorithme d'Euclide pour gcd(252, 105)

| Étape | $a$ | $b$ | $r = a \bmod b$ | |-------|-----|-----|----------------| | 1 | 252 | 105 | $252 = 2 \times 105 + 42$ → $r = 42$ | | 2 | 105 | 42 | $105 = 2 \times 42 + 21$ → $r = 21$ | | 3 | 42 | 21 | $42 = 2 \times 21 + 0$ → $r = 0$ | | Fin | 21 | 0 | retourner $a = 21$ |

$\gcd(252, 105) = 21$ . Vérification : $252 = 12 \times 21$ et $105 = 5 \times 21$ . ✓

🧩

Checkpoint

Quel est gcd(48, 18) calculé par l'algorithme d'Euclide ?

📐

Théorie

Théorème de Bézout : Pour tous $a, b \in \mathbb{Z}$ (non tous nuls), il existe $u, v \in \mathbb{Z}$ tels que :

$au + bv = \gcd(a, b)$

$(u, v)$ sont appelés coefficients de Bézout. Ils se calculent par l'algorithme d'Euclide étendu (remontée des divisions).

Conséquences :

$\gcd(a, b) = 1$ ⟺ $\exists u,v \in \mathbb{Z},\ au + bv = 1$
Si $a \mid bc$ et $\gcd(a, b) = 1$ , alors $a \mid c$ (lemme de Gauss)
Les solutions de $ax \equiv c \pmod{b}$ existent ⟺ $\gcd(a,b) \mid c$

📝

Coefficients de Bézout pour gcd(252, 105) = 21

Remontée des divisions :

Étape 3 : $42 = 2 \times 21 \Rightarrow 21 = 42 - 2 \times 21$ ... non, plutôt :

$21 = 105 - 2 \times 42$ (de l'étape 2)

$42 = 252 - 2 \times 105$ (de l'étape 1)

Substitution : $21 = 105 - 2 \times (252 - 2 \times 105) = 105 - 2 \times 252 + 4 \times 105 = 5 \times 105 - 2 \times 252$

Donc : $252 \times (-2) + 105 \times 5 = 21 = \gcd(252, 105)$

Vérification : $-504 + 525 = 21$ ✓. Les coefficients de Bézout sont $u = -2,\ v = 5$ .

📐

Théorie

Le Plus Petit Commun Multiple (PPCM) de $a, b \in \mathbb{N}^*$ :

$\text{ppcm}(a, b) = \min\{m \in \mathbb{N}^* \mid a \mid m \text{ et } b \mid m\}$

Relation fondamentale :

$\gcd(a, b) \times \text{ppcm}(a, b) = |a \times b|$

Donc : $\text{ppcm}(a, b) = \dfrac{|ab|}{\gcd(a,b)}$

Cette formule permet de calculer le PPCM une fois le PGCD connu.

Application aux fractions : réduire $\frac{a}{b}$ → diviser par $\gcd(a,b)$ . Additionner $\frac{p}{a} + \frac{q}{b}$ → dénominateur commun = $\text{ppcm}(a, b)$ .

📝

PPCM via le PGCD

$\text{ppcm}(12, 18)$ :

$\gcd(12, 18) = 6$ (calculé plus haut)

$\text{ppcm}(12, 18) = \dfrac{12 \times 18}{6} = \dfrac{216}{6} = 36$

Vérification : $36 = 3 \times 12 = 2 \times 18$ ✓

Application : $\dfrac{5}{12} + \dfrac{7}{18} = \dfrac{5 \times 3}{36} + \dfrac{7 \times 2}{36} = \dfrac{15 + 14}{36} = \dfrac{29}{36}$

⚠️

Piège : ppcm(a,b) ≠ a×b en général

Le PPCM n'est égal au produit que lorsque $\gcd(a,b) = 1$ (entiers premiers entre eux). Sinon, le produit surestime le PPCM. Exemple : $\text{ppcm}(4, 6) = 12 \neq 24 = 4 \times 6$ . Toujours diviser par le PGCD.

🧩

Checkpoint

Si gcd(a, b) = 4 et a×b = 96, quel est ppcm(a, b) ?

📐

Théorie

L'algorithme d'Euclide étendu calcule simultanément le PGCD et les coefficients de Bézout $(u, v)$ tels que $au + bv = \gcd(a, b)$ .

On maintient deux suites de coefficients $(s_i, t_i)$ satisfaisant à chaque étape $r_i = a \cdot s_i + b \cdot t_i$ :

| Étape | $r_i$ | $s_i$ | $t_i$ | Quotient | |-------|--------|--------|--------|----------| | 0 | $a$ | $1$ | $0$ | — | | 1 | $b$ | $0$ | $1$ | — | | $k$ | $r_{k-2} - q_{k-1}\, r_{k-1}$ | $s_{k-2} - q_{k-1}\, s_{k-1}$ | $t_{k-2} - q_{k-1}\, t_{k-1}$ | $q_{k-1}$ |

où $q_{k-1} = \lfloor r_{k-2}/r_{k-1} \rfloor$ est le quotient euclidien.

Application — inverse modulaire : si $\gcd(a, m) = 1$ , il existe $a^{-1} \pmod{m}$ tel que $a \cdot a^{-1} \equiv 1 \pmod{m}$ . C'est le coefficient $u$ de Bézout pour $(a, m)$ .

📝

Euclide étendu : gcd(35, 15) et inverse de 3 modulo 7

Euclide étendu pour $\gcd(35, 15)$ :

| Étape | $r$ | $s$ | $t$ | Quotient | |-------|-----|-----|-----|----------| | 0 | 35 | 1 | 0 | — | | 1 | 15 | 0 | 1 | — | | 2 | $35 - 2 \times 15 = 5$ | $1 - 2 \times 0 = 1$ | $0 - 2 \times 1 = -2$ | 2 | | 3 | $15 - 3 \times 5 = 0$ | — | — | 3 |

$\gcd(35, 15) = 5$ . Vérification : $35 \times 1 + 15 \times (-2) = 35 - 30 = 5$ ✓

Inverse de 3 modulo 7 : $\gcd(3, 7) = 1$ , l'inverse existe.

On cherche $u, v$ tels que $3u + 7v = 1$ : par Euclide étendu, $u = -2,\ v = 1$ .

$-2 \equiv 5 \pmod{7}$ , donc $3^{-1} \equiv 5 \pmod{7}$ . Vérification : $3 \times 5 = 15 = 2 \times 7 + 1 \equiv 1 \pmod{7}$ ✓

📐

Théorie

Lien PGCD — RSA :

Choisir deux grands premiers $p, q$ . Poser $n = pq$ .
Calculer $\phi(n) = (p-1)(q-1)$ (indicatrice d'Euler).
Choisir $e$ tel que $\gcd(e, \phi(n)) = 1$ .
Calculer $d = e^{-1} \pmod{\phi(n)}$ via l'algorithme d'Euclide étendu.
Clé publique : $(e, n)$ . Clé privée : $(d, n)$ .
Chiffrement : $c \equiv m^e \pmod{n}$ . Déchiffrement : $m \equiv c^d \pmod{n}$ .

L'inverse modulaire (étape 4) repose entièrement sur l'algorithme d'Euclide étendu.

Condition d'existence de l'inverse : $a^{-1} \pmod{m}$ existe $\iff \gcd(a, m) = 1$ .

Lien PGCD–PPCM rappel : $\gcd(a,b) \times \text{ppcm}(a,b) = |ab|$ , ce qui permet de calculer le PPCM dès que le PGCD est connu.

📝

Mini-RSA avec de petits nombres

$p = 5,\ q = 11 \Rightarrow n = 55,\ \phi(n) = 40$ .

Choisissons $e = 3$ : $\gcd(3, 40) = 1$ ✓.

Euclide étendu : $3 \times (-13) + 40 \times 1 = 1$ , donc $d \equiv -13 \equiv 27 \pmod{40}$ .

Chiffrement de $m = 2$ : $c \equiv 2^3 = 8 \pmod{55}$ .

Déchiffrement : $8^{27} \pmod{55} = 2$ ✓ (par exponentiation rapide).

🧩

Checkpoint

Quel est l'inverse de 5 modulo 7 (c'est-à-dire x tel que 5x ≡ 1 mod 7) ?

🧩

Checkpoint

Si gcd(12, 30) = 6, quel est ppcm(12, 30) ?

⭐

À retenir

PGCD : plus grand commun diviseur — $\gcd(a,b) = \gcd(b, a \bmod b)$
Algorithme d'Euclide : divisions successives, $O(\log \min(a,b))$ étapes
Théorème de Bézout : $\exists u,v \in \mathbb{Z},\ au + bv = \gcd(a,b)$
Euclide étendu : calcule simultanément PGCD et coefficients de Bézout $(u, v)$
Inverse modulaire : $a^{-1} \pmod{m}$ existe $\iff \gcd(a,m)=1$ — clé de RSA
PPCM : $\text{ppcm}(a,b) = |ab|/\gcd(a,b)$
$a, b$ premiers entre eux $\iff \gcd(a,b) = 1 \iff \exists u,v,\ au + bv = 1$

PGCD, PPCM et Euclide

Divisibilité et PGCD

Algorithme d'Euclide

Identité de Bézout

PPCM et lien avec le PGCD

Algorithme d'Euclide étendu

PGCD et cryptographie RSA