Maths Olympiad Prep

Library / /435 of 520

Number theory Difficulty 6.8 National olympiad Prove it

Lemma 4 If a,ba, b are two integers, b0b \neq 0, then there exist and are unique two integers q,rq, r such that
a=bq+r,0r<ba=b q+r, \quad 0 \leqslant r<|b|

holds.

Solution

If b>0b>0, then the multiples of bb when listed from negative to positive, in ascending order, are
,4b,3b,2b,b,0,b,2b,3b,4b,\cdots,-4 b,-3 b,-2 b,-b, 0, b, 2 b, 3 b, 4 b, \cdots

If b>0b>0, there exists an integer qq such that qba<(q+1)bq b \leqslant a<(q+1) b. And when b<0b<0, there exists an integer qq such that qba<(q1)bq b \leqslant a<(q-1) b. Therefore, we have a=bq+ra=b q+r, and 0r<b0 \leqslant r<|b|.

Now we need to prove that there is a unique pair of q,rq, r such that a=bq+r,0r<ba=b q+r, 0 \leqslant r<|b| holds. Suppose there is another pair q1,r1q_{1}, r_{1}, such that
a=bq1+r1,0r1<ba=b q_{1}+r_{1}, \quad 0 \leqslant r_{1}<|b|

holds, then subtracting the two equations, we get
0=b(qq1)+(rr1)0=b\left(q-q_{1}\right)+\left(r-r_{1}\right)

which means b(qq1)=rr1-b\left(q-q_{1}\right)=r-r_{1}. So by definition 1, b(rr1)b \mid\left(r-r_{1}\right). According to lemma 1, brr1|b||| r-r_{1} \mid. Since 0r<b,0r1<b0 \leqslant r<|b|, 0 \leqslant r_{1}<|b|, we have
rr1={rr1r<b, when rr1,r1rr1<b, when r<r1.\left|r-r_{1}\right|=\left\{\begin{array}{ll} r-r_{1} \leqslant r<|b|, & \text { when } r \geqslant r_{1}, \\ r_{1}-r \leqslant r_{1}<|b|, & \text { when } r<r_{1}. \end{array}\right.

From rr1<b,brr1\left|r-r_{1}\right|<|b|,|b||| r-r_{1} \mid and lemma 3, we get rr1=0r-r_{1}=0, which means r=r1r=r_{1}. By b0b \neq 0 and b(qq1)=r1r=0b\left(q-q_{1}\right)=r_{1}-r=0, we get qq1=0q-q_{1}=0, which means q=q1q=q_{1}.

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: NuminaMath-1.5, licensed Apache-2.0. Statement and solution reproduced as published; topic and difficulty added by this site.