On propose le programme suivant, décrit en langage naturel :
| R, a et b sont trois nombres Entrer la valeur de a Entrer la valeur de b R vaut 1. Tant que – R prend la valeur a − b × (partie entière de a /b) – b prend la valeur R Afficher le message “Le PGCD cherché vaut” Afficher la valeur de a |
1. Pourquoi est-il indispensable d'initialiser la valeur de R ( par exemple, ici :
R = 1) ?
2. Expliquer pourquoi on a la formule R = a − b × 
| Cette formule permet de réaliser le programme, même sur des logiciels ou des calculatrices qui ne proposent pas la fonction “reste de la division euclidienne”. |
3. Expliquer en détail ce qui se passe lors de la première boucle si a b.
4. Pourquoi fait-on afficher la valeur de a comme étant le PGCD, et non pas R ?
5. Réaliser ce programme sur votre calculatrice, et déterminer :
a. le PGCD de 12 et de 9
b. le PGCD de 68 et de 48
c. le PGCD de 347 et de 222.
1. Afin que l'algorithme ne s'arrête pas, il faut initialiser la valeur de R pour être sûr que 
soit non nul au démarrage de la boucle.
2. La division euclidienne de a par b s'écrit : il existe un unique couple d'entiers q et R, avec 
tel que 
soit
. De plus, q est le quotient de a par b, c'est-à-dire le plus grand entier inférieur ou égal à 
, donc q est la partie entière de 
. Finalement 
.
3. Si
, 
donc 
. D'où 
à la première étape de la boucle. Puis on remplace a par b, et b par
, ce qui a pour effet d'échanger a et b. Et comme
, la boucle reprend ensuite, avec cette fois 
.
4. Le programme s'arrête lorsque 
, ce qui n'est pas le PGCD, donc il faut rechercher le dernier reste non nul.
Au tour de boucle précédent, R prend la valeur 
c'est à partir de là que R vaut 0. a prend la valeur b b prend la valeur R, c'est-à-dire 0.
Il faut regarder le tour encore précédent :
R prend la valeur 
c'est le dernier reste non nul cherché a prend la valeur b b prend la valeur R, c'est le PGCD.
Ainsi, lorsqu'au dernier tour, a prend la valeur b, c'est bien le PGCD.
5. a. Le PGCD de 12 et de 9 vaut 3. b. Le PGCD de 68 et de 48 vaut 4 . c. Le PGCD de 347 et de 222 vaut 1.