HP Calculatrice graphique HP 39g - Manuel (Page 123)

Chapitre 7
Programmes
d’arithm´
etique
7.1 Le PGCD et l’algorithme d’Euclide
Soient A et B deux entiers positifs dont on cherche le P GCD.
L’algorithme d’Euclide est bas´e sur la d´efinition r´ecursive du P GCD :
P GCD(A, 0) = A
P GCD(A, B) = P GCD(B, A mod B) si B = 0
o` u A mod B d´esigne le reste de la division euclidienne de A par B.
Voici la description de cet algorithme :
on effectue des divisions euclidiennes successives :
A = B
× Q
1
+ R
1
0 R
1
< B
B = R
1
× Q
2
+ R
2
0 R
2
< R
1
R
1
= R
2
× Q
3
+ R
3
0 R
3
< R
2
.......
Apr`es un nombre fini d’´ etapes, il existe un entier n tel que : R
n
= 0.
on a alors :
P GCD(A, B) = P GCD(B, R
1
) = ...
P GCD(R
n −1 , R
n
) = P GCD(R
n −1 , 0) = R
n −1
123