12 Chapitre 1 – Les Aplets
On a alors :
PGCD(A, B)=PGCD(B,R
1
)=....
PGCD(R
n−1
,R
n
)=PGCD(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 AMOD0=A.
Le calcul des coefficients de l’identit´edeB´ezout
L’algorithme d’Euclide permet de trouver un couple U, V v´erifiant :
A × U + B × V = PGCD(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
).
Onaaud´ebut :
R
1
= AR
2
= B
U
1
=1U
2
= 0 puisque A =1× A +0× B
V
1
=0V
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))
Comentarios a estos manuales