Calculateur de PGCD par l'algorithme d'Euclide

Entrez le calcul

Valeur 1

Valeur 2

Résultats

https://example.com

Plus grand commun diviseur

4

PGCD (« GCF » ou « GCD » en anglais)

Solution — Euclid's Algorithm

Step 1: 2260 ÷ 816 = 2 R 628   (2260 = 2 × 816 + 628)
Step 2: 816 ÷ 628 = 1 R 188   (816 = 1 × 628 + 188)
Step 3: 628 ÷ 188 = 3 R 64   (628 = 3 × 188 + 64)
Step 4: 188 ÷ 64 = 2 R 60   (188 = 2 × 64 + 60)
Step 5: 64 ÷ 60 = 1 R 4   (64 = 1 × 60 + 4)
Step 6: 60 ÷ 4 = 15 R 0   (60 = 15 × 4 + 0)

Qu'est-ce que l'algorithme d'Euclide ?

Le plus grand commun diviseur (PGCD) est le plus grand nombre entier qui divise exactement deux entiers. En anglais, on le désigne par les sigles GCF (greatest common factor) et GCD (greatest common divisor) : il s'agit toujours de la même notion. L'algorithme d'Euclide est une méthode ancienne et remarquablement efficace pour le déterminer, fondée sur des divisions successives avec reste. Ce calculateur renvoie le PGCD de deux entiers quelconques et affiche chaque division afin que vous puissiez suivre tout le raisonnement.

L'algorithme d'Euclide pave un rectangle avec les plus grands carrés égaux possibles — le côté de ce carré est le PGCD.

Comment l'utiliser

Saisissez deux entiers dans les champs Valeur 1 et Valeur 2. L'outil prend le plus grand comme dividende et le plus petit comme diviseur, puis effectue des divisions successives jusqu'à obtenir un reste nul. Le dernier diviseur non nul est le PGCD. L'ordre des nombres n'a aucune importance et les signes négatifs sont ignorés, car le PGCD ne dépend que de la valeur absolue.

La formule expliquée

À chaque étape, on calcule un quotient et un reste : \(a = c \times b + R\), où \(c = \text{partie entière de } (a / b)\) et \(R = a \bmod b\). On remplace ensuite a par b et b par R, puis on recommence. Comme chaque reste est strictement inférieur au diviseur précédent, le processus se termine toujours. Lorsque \(R = 0\), le diviseur en cours est la réponse. Sous forme récursive : $$\gcd\!\left(\text{Valeur 1},\ \text{Valeur 2}\right) = \gcd\!\left(b,\ a \bmod b\right),\quad \gcd(a, 0) = a$$

Publicité

Exemple résolu

Cherchons PGCD(816, 2260). Posons a = 2260, b = 816.

$$2260 = 2 \times 816 + 628$$ $$816 = 1 \times 628 + 188$$ $$628 = 3 \times 188 + 64$$ $$188 = 2 \times 64 + 60$$ $$64 = 1 \times 60 + 4$$ $$60 = 15 \times 4 + 0$$ Le reste atteint zéro avec le diviseur 4 : ainsi PGCD(816, 2260) = 4.

Chaque étape remplace (a, b) par (b, a mod b) jusqu'à ce que le reste soit 0 ; le dernier diviseur non nul est le PGCD.

Questions fréquentes

« GCF » et « GCD » désignent-ils la même chose ? Oui. En anglais, « greatest common factor » et « greatest common divisor » sont synonymes et correspondent tous deux au PGCD en français ; cet outil répond donc indifféremment aux deux.

Que se passe-t-il si l'une des valeurs vaut 0 ? \(\gcd(a, 0) = a\), car tout nombre divise 0. Si les deux valeurs sont nulles, le PGCD n'est pas défini.

Peut-on calculer le PGCD de trois nombres ? Il suffit d'appliquer l'outil deux à deux : \(\gcd(x, y, z) = \gcd(\gcd(x, y), z)\).