📏 La question d'Euclide
Tu as une grille rectangulaire de a sur b cases (par exemple 252 × 105). Question : quel est le plus grand carré qui peut paver entièrement ce rectangle, sans laisser de trou ?
Ce problème, posé par Euclide vers 300 av. J.-C. dans le Livre VII des Éléments, est géométriquement équivalent au calcul du plus grand commun diviseur (PGCD) de a et b. Et la méthode pour le résoudre est l'algorithme le plus vieux du monde encore utilisé tel quel.
🎛️ La méthode géométrique en action
L'idée d'Euclide est simple : dans un rectangle a × b (avec a > b), découpe un carré de côté b. Il te reste un rectangle plus petit. Recommence. Quand tu peux remplir exactement le dernier rectangle avec des carrés sans reste, ce carré a le côté qui est le PGCD.
🎛️ Découpe géométrique du rectangle
Change a et b. Regarde le rectangle se faire dévorer par des carrés successifs.
Résultat
PGCD(252, 105) = 21
📐 La version arithmétique (celle que tu apprends au BAC)
Géométriquement, on découpe des carrés. Arithmétiquement, on fait des divisions euclidiennes successives. La règle clé :
PGCD(a, b) = PGCD(b, a mod b)
jusqu'à ce que le reste soit 0.
Exemple : PGCD(252, 105)
- 252 = 2 × 105 + 42
- 105 = 2 × 42 + 21
- 42 = 2 × 21 + 0 ← le reste est nul
- PGCD = 21 (le dernier reste non nul)
⚡ Pourquoi cet algo est si rapide
La beauté de l'algorithme d'Euclide est qu'il diminue exponentiellement les nombres manipulés. À chaque étape, le reste est au moins divisé par 2 (théorème de Lamé, 1844).
Conséquence : pour calculer le PGCD de deux entiers de n chiffres, l'algorithme prend environ 5n divisions. Pour deux nombres à 600 chiffres (utilisés en cryptographie), c'est environ 3 000 opérations — quelques millisecondes sur ton téléphone.
À titre de comparaison, calculer un PGCD en factorisant les deux nombres en facteurs premiers prendrait l'âge de l'univers pour les mêmes tailles.
🔐 L'algorithme d'Euclide étendu (Bezout)
Une variante puissante : l'algorithme d'Euclide étendu ne calcule pas seulement le PGCD, mais aussi les coefficients de Bezout u et v tels que :
au + bv = PGCD(a, b)
Pour 252 et 105 : on trouve 252 × 2 + 105 × (−5) = 504 − 525 = −21… non, en réalité 252 × (−2) + 105 × 5 = −504 + 525 = 21. 21 = PGCD. ∎
Cette identité de Bezout est au cœur de la cryptographie RSA : elle permet de calculer l'inverse modulaire d'un nombre, étape critique pour générer la clé privée.
🎓 L'algo d'Euclide au BAC SM
L'algorithme d'Euclide est au programme officiel du 2BAC SM, dans le chapitre Arithmétique. Tu y verras :
- Calcul du PGCD par divisions successives
- Théorème de Bezout : a ∧ b = d ⟺ ∃ u, v entiers : au + bv = d
- Lemme d'Euclide : si p est premier et p divise ab, alors p divise a ou p divise b
- Équations diophantiennes ax + by = c (résolution via Euclide étendu)
- Inverse modulaire : trouver x tel que ax ≡ 1 [n]
🌍 2 300 ans d'utilité ininterrompue
L'algorithme d'Euclide a un statut particulier dans l'histoire des sciences : c'est le seul algorithme inventé pendant l'Antiquité qui est encore utilisé tel quel aujourd'hui, dans la même forme, avec la même justification, dans tous les ordinateurs du monde.
🧠 Réflexion finale
L'algorithme d'Euclide est un exemple parfait d'une vérité paradoxale : en sciences, ce qui est le plus ancien n'est pas forcément le plus dépassé. Au contraire, ce qui survit 2 000 ans est généralement ce qui touche à quelque chose d'essentiel.
Quand tu apprendras Euclide en cours d'arithmétique, ne le vois pas comme une curiosité historique. Vois-le comme la brique de base qu'utilise toute la sécurité informatique mondiale. C'est probablement la chose la plus pratique qu'un mathématicien grec t'aura jamais transmise.
Vérifie ta compréhension
3 questions courtes pour valider tes acquis. Tu peux réessayer.