Algorithme d'Euclide

L'**algorithme d'Euclide** est une méthode rapide pour trouver le **plus grand commun diviseur (PGCD)** de deux nombres entiers, sans lister les diviseurs ni faire d'arbre de facteurs. Divise le plus grand nombre $a$ par le plus petit nombre $b$ et écris le résultat sous forme de **division euclidienne** : $$a = q \times b + r, \quad 0 \le r < b$$ Ici, $q$ est le **quotient** et $r$ est le **reste**. Ensuite, **remplace le couple $(a, b)$ par $(b, r)$** et divise à nouveau. Recommence jusqu'à obtenir un reste égal à $0$. Le **dernier reste non nul** (le diviseur de la dernière ligne) est le PGCD. **Exemple :** $\text{PGCD}(48, 18)$ - $48 = 2 \times 18 + 12$ - $18 = 1 \times 12 + 6$ - $12 = 2 \times 6 + 0$ Le reste vaut $0$, donc $\text{PGCD}(48, 18) = 6$. **Pourquoi ça marche :** si un nombre $d$ divise à la fois $a$ et $b$, il divise aussi $r = a - q \times b$. Et si $d$ divise à la fois $b$ et $r$, il divise aussi $a = q \times b + r$. Les couples $(a, b)$ et $(b, r)$ ont donc exactement les mêmes diviseurs communs, et donc le même PGCD : $$\text{PGCD}(a, b) = \text{PGCD}(b, r)$$ Les nombres diminuent à chaque étape, donc l'algorithme s'arrête toujours.

L'image géométrique : des carrés dans un rectangle de 48 sur 18

Un rectangle mesure $48$ sur $18$. Découpe à chaque fois les plus grands carrés possibles. Quel est le côté des carrés qui tombent juste à la fin ?

Découpe des carrés de côté 18 sur la longueur: Deux carrés $18 \times 18$ rentrent, il reste $12$ : $48 = 2 \times 18 + 12$ = Rectangle restant $18 \times 12$

Découpe des carrés de côté 12 dans le reste: Un carré $12 \times 12$ rentre, il reste $6$ : $18 = 1 \times 12 + 6$ = Rectangle restant $12 \times 6$

Découpe des carrés de côté 6: Deux carrés $6 \times 6$ rentrent exactement : $12 = 2 \times 6 + 0$ = Il ne reste rien

Pave tout le rectangle avec le dernier carré: $6$ divise $48$ et $18$ : $\frac{48}{6} \times \frac{18}{6} = 8 \times 3$ = $24$ carrés de côté $6$ le recouvrent

Answer: Les carrés de côté $6$ tombent juste, donc $\text{PGCD}(48, 18) = 6$. Chaque découpe correspond à une ligne de l'algorithme.

La méthode des soustractions successives

Calcule $\text{PGCD}(35, 14)$ uniquement avec des soustractions : soustrais toujours le plus petit nombre du plus grand.

Soustrais 14 de 35: $35 - 14 = 21$ = Nouveau couple $(21, 14)$

Soustrais encore 14: $21 - 14 = 7$ = Nouveau couple $(14, 7)$

Maintenant 7 est plus petit : soustrais 7: $14 - 7 = 7$ = Nouveau couple $(7, 7)$

Soustrais une dernière fois: $7 - 7 = 0$ = Les nombres s'arrêtent à $7$

Answer: $\text{PGCD}(35, 14) = 7$. Soustraire $14$ deux fois revient à une seule division : $35 = 2 \times 14 + 7$. La division n'est qu'un raccourci pour plusieurs soustractions.

Un classique : le PGCD de 1071 et 462

Calcule $\text{PGCD}(1071, 462)$ avec l'algorithme d'Euclide.

Divise 1071 par 462: $462 \times 2 = 924$ et $1071 - 924 = 147$ = $1071 = 2 \times 462 + 147$

Remplace le couple par (462, 147) et divise: $147 \times 3 = 441$ et $462 - 441 = 21$ = $462 = 3 \times 147 + 21$

Remplace le couple par (147, 21) et divise: $21 \times 7 = 147$, il ne reste rien = $147 = 7 \times 21 + 0$

Lis le dernier reste non nul: Le reste est devenu $0$ en divisant par $21$ = $\text{PGCD}(1071, 462) = 21$

Answer: $\text{PGCD}(1071, 462) = 21$. Vérification : $1071 = 21 \times 51$ et $462 = 21 \times 22$.

Simplifier une fraction difficile

Rends la fraction $\frac{391}{667}$ irréductible.

Divise 667 par 391: $667 = 1 \times 391 + 276$ = Reste $276$

Divise 391 par 276: $391 = 1 \times 276 + 115$ = Reste $115$

Divise 276 par 115: $276 = 2 \times 115 + 46$ = Reste $46$

Divise 115 par 46, puis 46 par 23: $115 = 2 \times 46 + 23$ et $46 = 2 \times 23 + 0$ = $\text{PGCD}(391, 667) = 23$

Divise le numérateur et le dénominateur par 23: $\frac{391 \div 23}{667 \div 23} = \frac{17}{29}$ = $\frac{17}{29}$

Answer: $\frac{391}{667} = \frac{17}{29}$. Comme $17$ et $29$ sont tous deux premiers, la fraction est irréductible.

Le PPCM à partir du PGCD

Calcule $\text{PPCM}(84, 120)$ avec l'algorithme d'Euclide.

Divise 120 par 84: $120 = 1 \times 84 + 36$ = Reste $36$

Divise 84 par 36: $84 = 2 \times 36 + 12$ = Reste $12$

Divise 36 par 12: $36 = 3 \times 12 + 0$ = $\text{PGCD}(84, 120) = 12$

Utilise PPCM = a × b ÷ PGCD: $\frac{84 \times 120}{12} = \frac{10080}{12}$ = $840$

Vérifie: $840 \div 84 = 10$ et $840 \div 120 = 7$ = Les deux divisent $840$

Answer: $\text{PPCM}(84, 120) = 840$.

L'algorithme d'Euclide a plus de 2300 ans (Euclide l'a décrit vers 300 av. J.-C.) et il reste l'un des algorithmes les plus utilisés au monde : - **Grands nombres** : décomposer $1071$ ou $391$ en facteurs premiers est long, mais trois ou quatre divisions donnent le PGCD tout de suite. Pour des nombres de plusieurs centaines de chiffres, la décomposition est pratiquement impossible, alors que l'algorithme d'Euclide se termine en quelques milliers d'étapes rapides au plus. - **Fractions** : pour simplifier $\frac{391}{667}$, il faut $\text{PGCD}(391, 667) = 23$, difficile à voir en décomposant mais rapide avec l'algorithme. - **PPCM** : dès que tu connais le PGCD, $\text{PPCM}(a, b) = \frac{a \times b}{\text{PGCD}(a, b)}$. Un seul algorithme donne donc les deux. - **Carrelage, engrenages et écrans** : le plus grand carreau carré pour un sol, le moment où deux engrenages se retrouvent dans la même position et la raison pour laquelle un écran $1920 \times 1080$ est au format $16:9$ se ramènent tous au PGCD. - **Sécurité sur Internet** : des systèmes de chiffrement comme RSA utilisent une version étendue de cet algorithme chaque fois que tu ouvres un site sécurisé.

Mistake: Garder l'ancien grand nombre : après $48 = 2 \times 18 + 12$, continuer avec $48$ et $12$

Why: L'algorithme marche parce que $\text{PGCD}(a, b) = \text{PGCD}(b, r)$. Le nombre $a$ ne sert plus après la première division.

Correct: Le couple suivant est $(18, 12)$ : l'ancien diviseur et le reste. Donc $18 = 1 \times 12 + 6$.

Mistake: Donner $0$ ou le dernier quotient comme PGCD

Why: La dernière ligne a un reste égal à $0$, ce qui indique seulement qu'il faut s'arrêter. Le quotient compte combien de carrés rentrent, ce n'est pas un diviseur commun.

Correct: Le PGCD est le dernier reste non nul, c'est-à-dire le diviseur de la dernière ligne. Dans $12 = 2 \times 6 + 0$, c'est $6$.

Mistake: Écrire un reste trop grand, comme $1071 = 1 \times 462 + 609$

Why: L'égalité est vraie, mais $609 > 462$, donc $462$ rentre encore une fois. Le reste doit être plus petit que le diviseur.

Correct: Prends le plus grand quotient possible : $1071 = 2 \times 462 + 147$ avec $147 < 462$.

Mistake: Prendre $a \times b$ comme PPCM

Why: $a \times b$ est toujours un multiple commun, mais en général pas le plus petit : $84 \times 120 = 10080$ compte deux fois le diviseur commun $12$.

Correct: Divise par le PGCD : $\text{PPCM}(84, 120) = \frac{84 \times 120}{12} = 840$.

Carreler un sol avec les plus grands carreaux carrés

Un carreleur veut couvrir un sol rectangulaire avec des carreaux carrés identiques sans en couper aucun. Le plus grand côté possible est le PGCD des deux longueurs.

Un panneau de $48$ cm sur $18$ cm est recouvert exactement par des carrés de $6$ cm : $\text{PGCD}(48, 18) = 6$, soit $8 \times 3 = 24$ carreaux.

Engrenages et cycles qui se répètent

Quand deux roues dentées tournent ensemble, les mêmes deux dents se retrouvent après un nombre de dents égal au PPCM des nombres de dents. L'algorithme d'Euclide donne le PGCD, et le PPCM s'en déduit.

Des roues de $18$ et $48$ dents : $\text{PGCD} = 6$, donc les mêmes dents se retrouvent après $\frac{18 \times 48}{6} = 144$ dents.

Le format des écrans

Une définition d'écran comme $1920 \times 1080$ devient un format en divisant les deux nombres par leur PGCD.

$1280 \times 1024$ : $\text{PGCD}(1280, 1024) = 256$, donc le format est $5:4$.

Algorithme d'Euclide : divise $a$ par $b$ sous la forme $a = q \times b + r$ avec $0 \le r < b$, puis remplace $(a, b)$ par $(b, r)$ jusqu'à obtenir un reste nul

Le PGCD est le dernier reste non nul, c'est-à-dire le diviseur de la dernière ligne

Ça marche parce que $\text{PGCD}(a, b) = \text{PGCD}(b, r)$ : les deux couples ont les mêmes diviseurs communs

Géométriquement, on découpe un rectangle $a \times b$ en carrés les plus grands possibles ; le côté du dernier carré est le PGCD

La méthode des soustractions successives retire encore et encore le plus petit nombre ; la division en est le raccourci

On l'utilise pour rendre une fraction irréductible, pour calculer $\text{PPCM}(a, b) = \frac{a \times b}{\text{PGCD}(a, b)}$ et pour savoir si deux nombres sont premiers entre eux (PGCD $= 1$)

Q: Est-ce que l'ordre des nombres compte ?

A: Non. Si tu commences avec le plus petit nombre, la première ligne est du type $18 = 0 \times 48 + 18$, ce qui échange simplement les deux nombres. Commencer par le plus grand évite cette étape.

Q: L'algorithme d'Euclide est-il plus rapide que la décomposition en facteurs premiers ?

A: Pour de petits nombres comme $12$ et $18$, les deux méthodes sont rapides. Pour de grands nombres, oui, de très loin : tu n'as besoin de trouver aucun nombre premier. $\text{PGCD}(1071, 462)$ demande trois divisions, alors que la décomposition exige $1071 = 3^2 \times 7 \times 17$ et $462 = 2 \times 3 \times 7 \times 11$.

Q: Que signifie un PGCD égal à 1 à la fin ?

A: Les deux nombres sont alors **premiers entre eux** : ils n'ont aucun diviseur commun autre que $1$. Deux nombres de Fibonacci voisins comme $144$ et $89$ sont toujours premiers entre eux, et ce sont eux qui demandent le plus d'étapes pour leur taille.

Q: Puis-je l'utiliser pour trois nombres ?

A: Oui, deux par deux : $\text{PGCD}(a, b, c) = \text{PGCD}(\text{PGCD}(a, b), c)$. Par exemple, $\text{PGCD}(840, 1176) = 168$ et $\text{PGCD}(168, 1260) = 84$, donc le PGCD des trois nombres est $84$.

Quitter la présentation

Algorithme d'Euclide

1 / 14

Théorie des Nombres / Facteurs & Multiples

Algorithme d'Euclide

Trouve le PGCD de deux nombres par des divisions euclidiennes successives, puis utilise-le pour simplifier des fractions et calculer le PPCM.

Avancé25 min

Utilisez les touches fléchées ou la barre d'espace pour naviguer