FANDOM



''''L'algorithme d'Euclide, consiste à effectuer une suite de divisions euclidiennes: ''''

''''- On effectue la division euclidienne de a par b et on note r le reste.''''

''''- Ensuite, b devient a et r devient b comme sur le tableau ci-dessous; et on recommence: on effectue la division euclidienne de a par b et on note r le reste''''

''''- Et on continue ainsi de suite jusqu'à ce qu'une division donne un reste égal à 0''''

''''Dans cette méthode le PGCD est le dernier reste non nul. ''''

''''''' a désigne le plus grand nombre et b désigne le plus petit. '''''''


a

b

r

Le plus grand nombre

Le plus petit nombre

Le RESTE de la division euclidienne de a par b

10

8

2

8

2

0

''''Exemple du tableau : Déterminer le PGCD de 10 et de 8''''

''''10:8 = 1 reste 2''''


10

2

8

1

''''8:2 = 4 reste 0''''


8

0

2

4

''''Le reste est 0, on en déduit que 2 est le PGCD de 10 et de 8.''''

''''Il peut arriver qu'à un moment le reste soit 1 : dans ce cas, le PGCD est 1 (le reste suivant sera forcément zéro !)''''

''''Exemple : Déterminer le PGCD de 7 et de 4.''''


a

b

r

Le plus grand nombre

Le plus petit nombre

Le RESTE de la division euclidienne de a par b

7

4

3

4

3

1

''''7:4 = 1 reste 3
4:3 = 1 reste 1
Le résultat est 1, le PGCD de 7 et de 4 est donc 1.''''