Accueil | Outils
Arithmétique
Déterminer le PGCD de deux entiers naturels non nuls
Méthode
A l'aide de la décomposition en nombres premiers

Soit et deux entiers naturels non nuls.

et .

sont des nombres premiers distincts.

et sont des entiers naturels éventuellement nuls.

pour tout indice vérifiant : .

Exemple

Déterminer .

et donc .

Définition
A l'aide de l'algorithme d'Euclide

Soit et sont deux entiers naturels non nuls.

La suite des divisions euclidiennes :

de par , |  | avec
de par (si ), |  | avec
de par (si ), |  | avec
de par (si ), |  | avec

permet de définir une suite strictement décroissante d'entiers positifs.

Le dernier reste non nul est alors le de et (si , alors c'est ).

Exemple

Déterminer le

Donc .

Précédent Suivant
Equipe Académique Mathématiques, Rectorat de l'Académie de Bordeaux, France, 2003 |