# Division Algorithm question

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

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

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

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

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

Is this alright?

N.B.
The case where $r=\frac{b}{2}$ works similarly. You end up with $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