Dernière version du 21.04.2010 00h15
Sommaire
1 Les pré-requis
2 L'algorithme
3 Exemples
3.1 122 et 9
3.2 355 et 30
4 Implémentation en pseudo-code
Parfois quand on fait des maths, on a besoin de connaître le PGCD (
http://www.daskoo.org/61-le-pgcd.cours) de deux entiers naturels. C'est très simple à trouver grâce à l'algorithme d'Euclide.
[modifier ( modifier-181-section-1.cours)]Les pré-requis
Il faut savoir effectuer des divisions euclidiennes ( 187-la-division-euclidienne.cours) et connaître un peu le PGCD, ce qui normalement ne pose pas de problème.
Et accessoirement parler français 
.
[modifier ( modifier-181-section-2.cours)]L'algorithme
La méthode ou algorithme d'Euclide se base sur la division euclidienne qui, je vous le rappelle, peut s'écrire comme ceci :
est le dividende.
est le diviseur.
est le quotient.
est le reste, vérifiant
Voici l'énoncé de l'algorithme :
a et b étant deux entiers naturels, on calcule le reste de la division euclidienne de a par b. On recommence cette opération, le diviseur de l'étape précédente devenant le dividende de la nouvelle étape et le reste de l'étape précédente devenant le diviseur de la nouvelle étape. On effectue ces divisions euclidiennes jusqu'à l'obtention d'un reste nul. le PGCD de a et b est le dernier reste non-nul.
On voit bien que c'est une suite d'opérations qui s'enchaînent, c'est-à-dire un algorithme !
Qu'est-ce qui nous assure que l'algorithme se termine toujours?
La condition de la division euclidienne sur le reste (r<b) assure que le reste sera bien nul. L'algorithme se termine donc.
[modifier ( modifier-181-section-3.cours)]Exemples
[modifier ( modifier-181-section-4.cours)]122 et 9
On divise donc le premier nombre (le plus grand) par le plus petit, si on fait dans l'autre sens cela rajoute une étape.
Le dernier reste non-nul est 1. Le PGCD de 122 et 9 est 1. Donc 122 et 9 sont premiers entre eux.
Prenons un autre exemple, cette fois ci avec un PGCD plus grand.
[modifier ( modifier-181-section-5.cours)]355 et 30
Le dernier reste non-nul est 5, donc le PGCD de 355 et 30 est 5.
Bien sûr, on ne l'utilise pas tous les jours, mais il est très utile (et ça impressionne les profs quand on est au CM1 
).
[modifier ( modifier-181-section-6.cours)]Implémentation en pseudo-code
Ceci est peut être plus parlant qu'une méthode décrite ou des exemples.
(apercent_signeb désigne le reste de la division euclidienne de a par b, a/b le quotient de cette même division)
1 a un entier
2 b un entier
3 ou bien a>=b ou bien on échange les valeurs des deux variables
4 tant que apercent_signeb est différent de 0
5 faire
6 a prend la valeur de b
7 b prend la valeur de a/b
8 fin de tant que
9 rendre b