Soient et deux entiers naturels avec non nul.
Effectuer la division euclidienne de par , c’est déterminer le couple d’entiers naturels tel que :
a=b×q+retr
Le couple est unique.
Un diviseur commun à deux entiers naturels et est un entier naturel qui divise les deux à la fois. Le plus grand entier qui divise à la fois et est appelé le Plus Grand Commun Diviseur de et , et est noté .
Calculs de PGCD avec l'algorithme d'Euclide (divisions successives)
C’est un algorithme itératif qui consiste à faire des divisions euclidiennes successives. Il repose sur la propriété suivante :
Soient et deux entiers naturels non nuls avec et est le reste de la division euclidienne de par . On a :
Algorithme
Dans la 1ère division, on divise (le plus grand) par (le plus petit) et dans la 2ème division, on prend le diviseur de la 1ère, comme dividende et le reste de la 1ère division comme diviseur et ainsi de suite jusqu’à obtenir un reste nul. Le dernier reste non nul est .