Theorem (Division Algorithm);

 

Statement:-

If a and b are integers (b>0 ) , there exist integers q and r , uniquely determined by a, b, such that   a=bq+r,   0≤r<b.

Proof:-

Let consider a sequence of multiple of b are,

…..-ab,(-a+1)b,…-bq,….0,b,2b,3b,4b,…bq,……(a-1)b,ab………

In this situation a=bq+r......eq(1)

 two different cases arise,

(1)          a is multiple of b.

Or

(2)          a is not a not a multiple of b.

For case (1),

If a is a multiple of b

Therefore, a=bq  for some q€Z 

But a=bq+r , hence r=0.

 

For case (2),

If a is not a multiple of b

Then obviously a should lie between two consecutive multiples of b,

That is,    bq < a < b(q+1)

Then    bq < a < bq + b

        =  0 < a-bq < b………………………eq(2)

From the given format of a= bq+r from eq(1)

 r=a-bq

by replacing a-bq in eq(2) {0 < a-bq < b} by the value of r=a-bq.

Therefore ,

Eq (2) becomes,

0< r < b

The combine result of case1 and case2

For case1,    r=0

And for case2,   0< r < b

Therefore,

  0≤ r < b.

Now the proof of uniqueness of q and r by the method of contradiction.

Suppose there exist another integer for a =bq + r,…………..eq(3)

That is  a= bx + y  ……………….eq(4)

Equating eq(3) and eq(4)

I can write,   bq+r = bx+y

ð   b(q-x) = y-r………………………..eq(5)

ð By divisibility rule I can say that b divide (y-r) or b|y-r

By condition r<b also y<b

But here it shows that b divide (y-r)

It happens only if y-r becomes zero.

That is,        y-r=0……………………eq(6)

Therefore,   y=r

And by putting the value of y-r=0  in eq (5)

That is,     b(q-x) = 0

Here b can’t be zero, because it is given that b>0

Therefore (q-x) =0………………….eq(7)

And hence q=x

From eq(6) and eq(7) ,  r=y  and  q=x , Proves the uniqueness of q and r.