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

12 Chapitre 1 – Les Aplets
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
`
A l’aide des suites, on ´ecrit la suite des restes.
Avec la HP40G, on utilise l’Aplet Sequence (touche APLET puis on
s´electionne Sequence puis START du bandeau).
Si l’on veut d´
eterminer le PGCD(78,56), on d´efinit la suite :
U1(1) = 78
U1(2) = 56
U1(N) = U1(N
− 2) MOD U1(N − 1)
On tape sur NUM pour avoir la liste num´ erique des U1(N) c’est ` a
dire la liste des restes des divisions successives...
Le dernier reste non nul est 2 donc le PGCD(78,56)=2.
Remarque
On peut utiliser dans HOME les variables A et B pour stocker les deux
nombres et mettre alors U1(1)=A U1(2)=B.
Il faut aussi remarquer que A MOD 0 = A.
Le calcul des coefficients de l’identit´ e de B´ ezout
L’algorithme d’Euclide permet de trouver un couple U, V v´erifiant :
A
× U + B × V = P GCD(A, B)
Avec les suites :
On va d´efinir “la suites des restes” R
n
et deux suites U
n
et V
n
, de
fa¸con qu’` a chaque ´etape on ait :
R
n
= U
n
× A + V
n
× B.
Puisque on a : R
n
= R
n −2
− Q
n
× R
n −1 , U
n
et V
n
vont v´erifier
la mˆeme relation de recurrence (Q
n
=quotient entier de R
n −2
par
R
n −1 ).
On a au d´ebut :
R
1
= A R
2
= B
U
1
= 1 U
2
= 0 puisque A = 1
× A + 0 × B
V
1
= 0 V
2
= 1 puisque B = 0 × A + 1 × B
Avec la HP40G, grˆ ace ` a l’Aplet Sequence, on va d´efinir la suite
U1 des restes et les suites U2 et U3 qui seront telles que pour tout N
on ait : U1(N)=A*U2(N)+B*U3(N).
Pour cela on a besoin de la suite des quotients que l’on mettra
en U4.
Les suites U1, U2, U3 v´erifient la mˆeme relation de r´ecurrence :
U
n
= U
n −2
− Q
n
× U
n −1
avec
Q
n
= U4(N) = FLOOR(U1(N
− 2)/U1(N − 1))