0
$\begingroup$

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$?

$\endgroup$

1 Answer 1

Reset to default
2
$\begingroup$

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$.

$\endgroup$
10
  • $\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, 2014 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, 2014 at 12:54
  • $\begingroup$ Yeah, I made a typo. $\endgroup$
    – user103816
    Nov 20, 2014 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, 2014 at 16:55
  • 1
    $\begingroup$ Who said $d$ is always equal to 1? I think you must have misunderstood something. $\endgroup$
    – Ojas
    Nov 20, 2014 at 16:56

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .