I am reading this proof of Bézout's identity. It starts as:

For given nonzero integers $a$ and $b$ there is a nonzero integer $ax + by$, $x$ and $y$ are also integers. The minimum absolute value of $ax+by$ is supposed to be $as+bt=d$($d$ can be made positive by changing the signs of $s$ and $t$). Then they say that dividing $a$ or $b$ with $d$ gives the reminder which is of the form $ax+by$.

By Euclid division we have:

$a=q_1d+r_1\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ $ and $\ \ \ \ \ \ b=q_2d+r_2$
$a=q_1(as+bt)+r_1\ \ \ \ \ \ \ \ \ \ \ $ and $\ \ \ \ \ \ b=q_2(as+bt)+r_2$
$a(1-q_1s)+b(-q_1t)=r_1\ \ $ and $\ \ \ \ \ a(-q_2s)+b(1-q_2s)=r_2$

So, $r_1$ and $r_2$ are of form $ax+by$. Then they say $r_1$ and $r_2$ must be less than $d$, acc. to Euclid's division. Upto now everything is clear to me but not the next step. In the next step they say that the only way $r_1$ and $r_2$ can be smaller that $d$ is that they become $0$. How?

Why $r_1$ and $r_2$ have to be $0$?


In the proof, it is stated that $d$ is the minimum absolute value of the form $as + bt$. And, as the remainder of division of $a$ by $d$ must be less than $d$, and also must be of the form $ax+by$ (because $d$ and $a$ are both of the same form), hence the only option which remains for the remainder to be is $0$ (because $d$ is the smallest positive value, hence there cant be any other positive number of the same form less than $d$). Thus, $r_1$ is 0. Similar argument for $r_2$.

  • $\begingroup$ Ok, we are using the fact that $b$ is non-negative. So for any number of form $ax+by$ to become less than $b$, it has to become 0. $\endgroup$ – user103816 Nov 20 '14 at 12:48
  • $\begingroup$ We are not assuming $b$ to be non-negative. We are assuming $d$ to be non-negative(it is the smallest positive integer of the form $as+bt$). And as the remainder $r_1$should be also of the same form($ax+by$) and $0 \le r_1 \le (d-1)$, it is not possible unless it is 0(not a positive integer but can be written as $a0+b0$ ). $\endgroup$ – Ojas Nov 20 '14 at 12:54
  • $\begingroup$ Yeah, I made a typo. $\endgroup$ – user103816 Nov 20 '14 at 12:59
  • 1
    $\begingroup$ Yes you are right. I didn't notice the way you had expressed $r_1$ and $r_2$. Although, the rest of the argument is correct. (0 can still be written as $ax+by$. e.g. : $ab+b(-a)$ ) $\endgroup$ – Ojas Nov 20 '14 at 16:55
  • 1
    $\begingroup$ Who said $d$ is always equal to 1? I think you must have misunderstood something. $\endgroup$ – Ojas Nov 20 '14 at 16:56

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.