Question

In Euclid's division lemma ,where a,b,q and r are integers prove that q and r are unique.

Answer 1

Theorem (Euclid’s Division Lemma):

For a pair of given positive integers ‘a’ and ‘b’, there exist unique integers ‘q’ and ‘r’ such that a=bq+r

PROOF-

Consider the set, S, of all numbers of the form a+nb, where n is an integer.

S = {a - nb : n is an integer}

S contains at least one nonnegative integer, because there is an integer, n, that ensures a-nb ≥ 0, namely

n = -|a|b makes a-nb = a+|a| b2 ≥ a+|a| ≥ 0.

Now, by the well-ordering principle, there is a least nonnegative element of S, which we will call r, where r=a-nb for some n.  Let q = (a-r)/b = (a-(a-nb))/b = n.  To show that r  <  |bI, suppose to the contrary that r ≥ |b|.  In that case, either r-|b|=a-m, where m=n+1 (if d is positive) or m=n-1 (if b is negative), and so r-|b| is an element of S that is nonnegative and smaller than r, a contradiction.  Thus r < |b|.

To show uniqueness, suppose there exist q,r,q',r' with 0 ≤ r,r' < |d| such that a = qb + r and a = q'b + r'.  Subtracting these equations gives b(q'-q) = r'-r, so b|r'-r.  Since 0 ≤ r,r' < |b|, the difference r'-r must also be smaller than b.  Since b is a divisor of this difference, it follows that the difference r'-r must be zero, i.e. r'=r, and so q'=q⇒q and r are unique