Algorithme d'Euclide
Pour calculer le PGCD (plus grand diviseur commun) de a et b, on suit les étapes suivantes :
1. On effectue la division euclidienne de a par b.
2. On divise le diviseur de la division précédente par son reste.
3. On recommence cette procédure jusqu'à obtenir un reste nul.
Le PGCD de a et b est le dernier reste non nul.
Exemple
Quel est le PGCD de 720 et de 192 ?
720=192*3+144
192=144*1+48 PGCD(720,192)=48
144=48*3+0
Le dernier reste non nul est 48 donc le PGCD de 720 et 192 est 48.
/https%3A%2F%2Fassets.over-blog.com%2Ft%2Fcedistic%2Fcamera.png)
/https%3A%2F%2Fekladata.com%2FEOn6FphXxB5cf96pNCLZThk8dmI%40500x250.png)
/https%3A%2F%2Fekladata.com%2FhtAuBoPthMbbrBLVykHCAbKjisE%40500x352.png)