Identit´edeB´ezout 127
Vous entrez par exemple :
E1 = S1
2
− 1 et E2 = S1
2
− 2 ∗ S1 + 1 pour trouver le PGCD ´egal `a
2*S1-2.
7.2 Identit´edeB´ezout
Dans ce paragraphe la fonction Bezout(A,B) renvoie la liste :
{U, V, P GCD(A, B)} o`u U et V v´erifient :
A × U + B × V = PGCD(A, B).
7.2.1 Version it´erative sans les listes
L’algorithme d’Euclide permet de trouver un couple U et V v´erifiant :
A × U + B × V = PGCD(A, B)
En effet, si on note A
0
etB
0
les valeurs de A et de B du d´ebut on a :
A = A
0
× U + B
0
× V avec U =1 et V =0
B = A
0
× W + B
0
× X avec W =0 et X =1
Puis on fait ´evoluer A, B, U, V, W, X de fa¸con que les deux relations
ci-dessus soient toujours v´erifi´ees.
Si :
A = B × Q + R 0
6 R<B (R = A mod B et Q = E(A/B))
On ´ecrit alors :
R = A − B × Q = A
0
× (U − W × Q)+B
0
× (V − X × Q)=
A
0
× S + B
0
× T avec S = U − W × Q et T = V − X × Q
Il reste alors `a recommencer avec :
B dans le rˆole de A (B->A W->U X->V) et,
R dans le rˆole de B (R->B S->W T->X )
d’o`u l’algorithme :
fonction Bezout (A,B)
local U,V,W,X,S,T,Q,R
1->U 0->V 0->W 1->X
tant que B 6= 0 faire
A mod B->R
E(A/B)->Q
//R=A-B*Q
U-W*Q->S
V-X*Q->T
Comentários a estes Manuais