# Division Algorithm question

• Oct 26th 2010, 11:16 AM
I-Think
Division Algorithm question
The division algorithm states
$\displaystyle b=aq+r$where $\displaystyle 0<r<a$ and $\displaystyle b,a,q,r\in{Z}$
Prove $\displaystyle r<\frac{b}{2}$

I shall attempt a proof by contradiction
Assuming $\displaystyle r>\frac{b}{2}$
Let $\displaystyle r=\frac{mb}{n}$ where $\displaystyle m<n<2m$

So
$\displaystyle b=aq+\frac{mb}{n}$
$\displaystyle b-\frac{mb}{n}=b(1-\frac{mb}{n})=b(\frac{n-m}{n})=aq$
$\displaystyle b=\frac{aqn}{n-m}$

Placing it into the original equation
$\displaystyle \frac{aqn}{n-m}=aq+r$
$\displaystyle aqn=aqn-aqm+(n-m)r$
$\displaystyle aq\frac{m}{n-m}=r$

And as $\displaystyle \frac{m}{n}>\frac{1}{2}$ and $\displaystyle m<n$, then $\displaystyle m>n-m$
So $\displaystyle r>aq$, but this is a contradiction to the division algorithm
So $\displaystyle r<\frac{b}{2}$

Is this alright?

N.B.
The case where $\displaystyle r=\frac{b}{2}$ works similarly. You end up with $\displaystyle r=aq$, which is also a contradiction
• Oct 26th 2010, 01:49 PM
emakarov
The problem statement does not say that b >= a. If a > b, then q = 0 and r = b.

Quote:

Let r=\frac{mb}{n} where m<n<2m
Are m and n integer? Why do they exist?

I have not read your proof to the end, but I think there is an easier direct proof. Suppose b >= a. If a <= b/2, then r < a <= b/2. If a > b/2, then q = 1 and r = b - a < b/2.
• Oct 26th 2010, 05:42 PM
I-Think
Sorry about that omission, but it is true that b>a>0 for this question.

Yes, m and n are integers, they exist because any integer can be expressed as the fraction of another integer, and I chose to represent r as a fraction of b.

But I understand your proof, it is easier.
Thanks