2
$\begingroup$

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?

$\endgroup$
6
  • $\begingroup$ Add "proof-verification" tag! This question was asked many times, it risks being closed as a duplicate, otherwise. $\endgroup$ Commented Apr 10, 2021 at 10:01
  • 1
    $\begingroup$ Okay, thanks! I just added it! $\endgroup$ Commented Apr 10, 2021 at 10:05
  • $\begingroup$ @Max, please take note of the TeX edits I made for future reference. (There's a bit of a learning curve when it comes to TeX, but it's a learning curve well worth climbing.) $\endgroup$ Commented Apr 10, 2021 at 10:21
  • $\begingroup$ Okay, noted! @BarryCipra $\endgroup$ Commented Apr 10, 2021 at 10:24
  • 1
    $\begingroup$ Incidentally, there are some typos and a small lacuna regarding your $r$'s which I would have you fix before accepting your proof (if I were your teacher), but the basic idea looks fine. (The lacuna is what Davide Trono mentions in his answer: the variable $r$ initially appears with no connection to $a$ or $b$. It's not hard to infer you mean for $r$ to denote the remainder when dividing $a$ by $b$, but that really ought to be made clear.) $\endgroup$ Commented Apr 10, 2021 at 10:28

1 Answer 1

Reset to default
1
$\begingroup$

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.

$\endgroup$
1
  • 1
    $\begingroup$ I'll add I'm performing the euclidean division and you're right, it is $q_2$, I misspelt that. Thank you! $\endgroup$ Commented Apr 10, 2021 at 10:41

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.