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 PGCD.
L’algorithme d’Euclide est bas´e sur la d´efinition r´ecursive du PGCD :
PGCD(A, 0) = A
PGCD(A, B)=PGCD(B, A mod B) si B 6=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 6 R
1
<B
B = R
1
× Q
2
+ R
2
0 6 R
2
<R
1
R
1
= R
2
× Q
3
+ R
3
0 6 R
3
<R
2
.......
Apr`es un nombre fini d’´etapes, il existe un entier n tel que : R
n
=0.
on a alors :
PGCD(A, B)=PGCD(B, R
1
)=...
PGCD(R
n−1
,R
n
)=PGCD(R
n−1
, 0) = R
n−1
123
Kommentare zu diesen Handbüchern