Euclid's division lemma states that for any positive integers a and b, there exist unique integers q and r such that a = bq + r, where r must satisfy

(a) 1 < r < b (b) $0 < r \leq b$ (c) $0 \leq r < b$ (d) 0 < r < b

Open in App

Solution

Here we need to argue that q and r are no unique
Let us assume q and r are not unique i.e. let there exists another pair $q_{0}$ and $r_{0}$ i.e. a = $b \times q_{0}$ + $r_{0}$ , where 0 ≤ $r_{0}$ < b

=> $b \times q$ + r = $b \times q_{0}$ + $r_{0}$
=> $b \times (q - q_{0})$ = $r_{0}$ - r ................ (I)

Since $0 \leq r < b$ and $0 \leq r_{0} < b$ , thus $0 \leq (r_{0}$ - r)< b ........ (II)

The above eq (I) tells that b divides $r_{0}$ - r and $r_{0}$ - r is an integer less than b. This means $r_{0}$ - r must be 0.
=> $r_{0}$ - r = 0
=> r = $r_{0}$
Eq (I) will be, $b \times (q - q_{0})$ = 0
Since b > 0, => $(q - q_{0})$ = 0
=> q = $q_{0}$

Since r = $r_{0}$ and q = $q_{0}$ , Therefore q and r are unique.

hence
(c) $0 \leq r < b$ is correct option

Suggest Corrections

Similar questions

a = b q + r

The solution is blank in this question "

Euclid's division lemma states that for any positive integers a and b, there exist unique integers q and r such that a = bq + r, where r must satisfy

(a) 1 < r < b (b) 0<r≤b (c) 0≤r<b (d) 0 < r < b

Please sort this for me

Join BYJU'S Learning Program