Euclide spé

[Tangui]

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

[Tangui]

Excusez moi fausse manoeuvre. u(a) = u indice a


Bonjour, mon exercice de Spé me laisse perplexe, je ne décolle pas d'un pouce.Pourriez vous m'aider s'il vous plait ? :hein: :

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 :
r(n) = u(n)a + v(n)b

a. L'algorithme démarre par la division a = bq(1) + r(2)
On pose r(0) = a et r(1) = b
En déduire les valeurs de u(0), v(0), u(1), v(1), u(2) et v(2).

b. On suppose qu'à la p-ième division de l'algorithme,
r (p-1) = r(p)q(p) + r(p+1)
En déduire les formules :
u(p+2) = u(p)-q(p+1)u(p+1)
v(p+2) = v(p)-q(p+1)v(p+1)

En vous remerciant,
Bonnes fêtes