Trouver le PGCD sans poser une seule division

L’algorithme en 1 phrase

Le PGCD de deux nombres ne change pas si on remplace le plus grand par la différence avec le plus petit.

Exemple pas à pas : PGCD(84, 30)

Étape	Opération	Résultat
1	$84 - 30$	$(54, 30)$
2	$54 - 30$	$(24, 30)$
3	$30 - 24$	$(24, 6)$
4	$24 - 6$	$(18, 6)$
5	$18 - 6$	$(12, 6)$
6	$12 - 6$	$(6, 6)$ ✓

PGCD(84, 30) = 6.

Version « division » (plus rapide)

Au lieu de soustraire plusieurs fois, tu peux prendre le reste de la division :

• $84 = 2 \times 30 + 24$ → PGCD(30, 24)
• $30 = 1 \times 24 + 6$ → PGCD(24, 6)
• $24 = 4 \times 6 + 0$ → PGCD = 6.

C’est l’algorithme d’Euclide classique.

Le raccourci reconnaissable

Si les deux nombres finissent par le même chiffre pair, tente 2 en facteur. S’ils sont multiples de 3 (somme des chiffres), tente 3. Ça évite l’algorithme complet.

?À toi de jouer

Quel est le PGCD de 48 et 36 ?

A.6B.12C.18D.24

Valider