Let n and d be integers where d 1 The Division Algorithm st

Let n and d be integers, where d > 1. The Division Algorithm states that there are integers q and r such that n = dq + r. where 0 lessthanorequalto r lessthanorequalto d - 1. Prove that the integers q and r are unique.

Solution

We prove by contradiction

Assume there are two integers q\' and r\' such that

n=dq\'+r\'

0<=r\'<=d-1

q not equal to q\'

r not equal to r\'

So,

dq+r=dq\'+r\'

d(q-q\')=r-r\'

Without loss of generality we can assume: r>r\'

Now 0<r-r\'<d

But, d(q-q\')=r-r\' implies d|r-r\' which is a contradiction

Hence, r=r\', q=q\'