I need to prove Bezout's Theorem and the recommended method is using the induction on the number of steps before the Euclidean algorithm terminates for a given input pair.$~~~~~~$
I am having hard time understanding what it means of the number of steps before the Euclidean algorithm terminates for a given input pair. Please help me!
Best Answer
You can use another induction, which is useful to understand the Extended Euclidean algorithm: it consists in proving that all successive remainders in the algorithm satisfy a Bézout's identity whatever the number of steps, by a finite induction or order $2$.
Initialisation is easy, as the first two remainders are $r_0=a$ and $r_1=b$, you have: $$a=1\cdot a+0\cdot b,\quad=0\cdot a+1\cdot b.$$
At the $i$-step, you have $r_{i-1}=q_ir_i+r_{i+1}$. By induction hypothesis, we have: $$r_{i-1}=u_{i-1}a+v_{i-1}b,\quad r_i=u_ia+v_ib $$ whence $$r_{i+-1}=r_{i-1}-q_ir_i=(u_{i-1}-q_iu_i)a+(v_{i-1}-q_iv_i)b.$$
Icing on the cake: you get the recurrence relations between the coefficients, ready for use in the Extended Euclidean algorithm.