Euclide Terminale Spé
Bonjour, mon exercice de Spé me laisse perplexe, je ne décolle pas d'un pouce.Pourriez vous m'aider s'il vous plait ? :
L'algorithme d'Euclide étendu
Soit deux entiers a et b premiers entre eux. On se propose de calculer un couple d'entiers (u;v) tels que ua + vb = 1, en utilisant la méthode classique de "remontée" dans les divisions de l'algorithme d'Euclide. A chaque étape de l'algorithme, on peut ainsi exprimer le reste rn en fonction de a et b :
rn = una + vnb
a. L'algorithme démarre par la division a = bq1 + r2
On pose r0 = a et r1 = b
En déduire les valeurs de u0, v0, u1, v1, u2 et v2.
b. On suppose qu'à la p-ième division de l'algorithme,
r p-1 = rpqp + rp+1
En déduire les formules :
up+2 = up - qp+1up+1
vp+2 = vp - qp+1vp+1
En vous remerciant,
Bonnes fêtes
-----
,