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

Identit´e de B´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´ e de B´ 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 = P GCD(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 = P GCD(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 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 = 0 faire
A mod B->R
E(A/B)->Q
//R=A-B*Q
U-W*Q->S
V-X*Q->T