In class, we've studied Bezout's identity but I think I didn't write the proof correctly. I'd like to know if what I've tried doing is okay. These are my notes:
Bezout's identity:
If $a, \in \mathbb{Z}, b \neq 0$ there exists $u,v \in \mathbb{Z}$ such that $ua+vb=d$ where $d=\gcd (a,b)$ \
My attempt at proving it:
Since $\gcd(a,b) = gcd (|a|,|b|)$, we can assume that $a,b \in \mathbb{N} $. We carry on an induction on r.
If $r=0$ then $a=qb$ and we take $u=0, v=1$
Now, for the induction step, we assume it's true for smaller r_1 than the given one.
By the division algorithm there are $q,r\in \mathbb{Z}$ with $a = q_1b + r_1$ and $0 \leq r_1 < b$. Applying it again $\exists q_2, r_2$ such that $b=q_2r_1+r_2$ with $0 \leq r_2 < r_1$. Then $d = \gcd (a, b) = \gcd (b, r)= \gcd (r_1,r_2)$
But, since $r_2<r_1$ , by our induction hypothesis $\exists u_0,v_0 \in \mathbb{Z}$ such that $u_0r_1 + v_0r_2 = d$, hence
$$\begin{align}
d&=u_0r_1 + v_0(b-r_1q_2)\\
& = v_0b + (u_0-v_0q_2)r_1\\
&=v_0b + (u_0-v_0q_2)(a-q_1b)\\
&=(u_0-v_0q_1)a+(v_0+q_1q_2v_0+u_0q_1)b
\end{align}$$
so it suffices to take $u = u_0-v_0q_1$ and $v = v_0+q_1q_2v_0+u_0q_1$ to obtain the induction step.
Is this correct?
Best Answer
Seems fine to me. I think you should write at the beginning you are performing the Euclidean division as otherwise that $r=0 $ seems to be got out of nowhere. The induction works just fine, although I think there may be a slight mistake at the end. You wrote (correctly): $$d=v_0b+(u_0-v_0q_2)(a-q_1b)$$ but then when rearranging the sum there seems to be a change of index: $$d=v_0b+u_0a-v_0q_2a-u_0q_1b+v_0q_2q_1b$$ by this point by distribution law, you should find $(u_0-v_0q_2)a$ whereas you wrote $(u_0-v_0q_1)a$, but apart from this slight inaccuracy everything works fine.
I suppose that the identity $d=gcd(a,b)=gcd(r_1,r_2)$ has been proven in a previous lecture, as it is clearly true, but a proof is still needed.