## Euclid's Division Lemma

### Important Questions asked in Examination... Euclid (4th BC) credits: wikipedia

Q1: State Euclid's Division Lemma.

Answer: Given positive integers a and b ( b ≠ 0 ), there exists unique integer numbers q and r satisfying a = bq + r, 0 ≤ r < |b|. where
a is called dividend
b is called divisor
q is called quotient
r is called remainder.

e.g. 17 = 5 × 3 + 2

Q2: Prove Euclid's Division Lemma.

Answer: According to Euclid's Division lemma, for a positive pair of integers there exists unique integers q and r, such that
a = bq + r, where 0 ≤ r < b

Let us assume q and r are not unique i.e. let there exists another pair q0 and r0 i.e. a = bq0 + r0, where 0 ≤ r0 < b

⇒ bq + r = bq0 + r0
⇒ b(q - q0) = r - r0                                          ................ (I)

Since 0 ≤ r < b and 0 ≤ r0 < b, thus 0 ≤ r - r0 < b ......... (II)

The above eq (I) tells that b divides (r - r0) and (r - r0) is an integer less than b. This means (r - r0) must be 0.
⇒ r - r0 = 0 ⇒ r = r0

Eq (I) will be, b(q - q0) = 0
Since b ≠ 0, ⇒ (q - q0) = 0 ⇒ q = q0

Since r = r0 and q = q0, ∴ q and r are unique.

Q3: Prove that the product of two consecutive positive integers is divisible by 2?

Answer: Let n and n-1 be the 2 positive integers.
∴ product= n(n-1) =n2-n
CASE 1 (when n is even):
Let n = 2q
n2-n = (2q)- 2q
= 4q2-2q
= 2q (2q-1)
Hence the product n2-n is divisible by 2

CASE 2(when n is odd)
Let n be 2q+1
n2-n = (2q+1)2- (2q+1)
= 4q2+4q+1-2q-1
= 4q2+2q
= 2q(2q+1)
Hence the product n2-n is divisible by 2
Thus we conclude that the product of two consecutive positive integers is always divisible by 2.

Q4: Let a,b,c are positive integers. If c ≠ 0 and ac divides bc. Prove that a also divides b.

Answer: Since ac divides bc, according to Euclid's Division Lemma there exists an integer k such that, bc = ack.

⇒ ack - bc = 0
⇒ c(ak - b) = 0

Since c ≠ 0, ⇒ ak - b = 0
⇒ ak = b ⇒ b/a = k
⇒ b divides a.

Q5: Prove that square of an odd integer decreased by 1 is a multiple of 8.

Answer: According to Euclid's division Lemma, for a positive pair of integers (say a and b) there exists unique integers q and r, such that
a = bq + r, where 0 ≤ r < b
Here b = 4,
∴  a = 4q + r, 0 ≤ r < 4
Hence r = 0 or 1 or 2 or 3.

For r = 0 or 2, then a = 4q or a = 4q + 2 = 2(2q + 1) is even.
Since it is given, a is odd.
∴ r = 1 or 3 ⇒ a = 4q + 1 or a = 4q +3
∴ Every odd integer is of the form of 4q + 1 or 4q + 3, (q E Z)

Square of an odd integer decreased by 1 can be written as

a2 - 1= (4k+1)2 - 1        or    a2 - 1 = (4k+3)2 - 1 .
⇒  a2 - 1= 16k2 + 8k + 1   or    a2 -1  = 16k2 + 24k + 8 .
⇒  a2 - 1= 8k(2k + 1)         or   a2 - 1 = 8 (2k2 + 3k + 1) .
∴ a2 - 1 is a multiple of 8.

Q6(mcq): Euclid's division lemma states that for two 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

Answer: (d) 0 ≤ r < b

Q7(mcq)For some integer m, every even integer is of the form

(a) m
(b) m + 1
(c) 2m
(d) 2m + 1

Answer: (c) 2m (even no.s are divisible by 2)

Q8: Write if every positive integer can be of the form 4q + 2 where q is an integer. Justify your answer.

Answer: No, because every positive integer may have other forms 4q, 4q + 1 etc.