Comment calculer le PGCD avec l’algorithme d’Euclide ?

Tu ne sais pas comment calculer le PGCD de deux nombres facilement ? Euclide, un grand mathématicien de la Grèce Antique, a trouvé une méthode imparable. Dans ce cours, apprends à calculer le PGCD avec l’algorithme d’Euclide.

Et pour résoudre le casse-tête du PGCD comme un pro, inscris-toi à des cours de maths en ligne personnalisés où tu pourras explorer en profondeur l’antique méthode d’Euclide. 🧩

Théorème : Théorème d’Euclide

Soient deux entiers relatifs et . On suppose . On note et le quotient et le reste de la division de par . Alors :

   

Démonstration :

Par définition de et , on a : . On note l’ensemble des diviseurs communs de et et l’ensemble des diviseurs communs de et . Montrons que par double inclusion. Soit , comme et que divise et , on en déduit que divise aussi et donc , d’où l’inclusion . Soit , comme et que divise et , on en déduit que divise aussi et donc , d’où l’inclusion . En conclusion, Ces deux ensembles ont donc le même plus grand élément, soit : .

Corollaire : L’algorithme d’Euclide

Voici un algorithme qui permet de déterminer le PGCD de deux entiers non nuls et . Pour cela, on définit une suite :

On pose et ;

Tant que , on effectue la division euclidienne de par et on note le nouveau reste obtenu.

Le PGCD de et est le dernier terme de la suite non nul.

Remarque :

Si on note le premier entier naturel tel que , le théorème d’Euclide nous permet d’écrire que :

   

Or, .

Exemple :

Déterminons le PGCD de 2020 et 150 en utilisant l’algorithme d’Euclide :

Le dernier reste non nul est , donc 2020 150 = 10