##
**Euclid's Division Lemma**

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

credits: wikipedia

credits: wikipedia

**Q1: State Euclid's Division Lemma.**

Answer: Given positive integers

**and**

*a***( b ≠ 0 ), there exists unique integer numbers q and r satisfying a = bq + r, 0 ≤ r < |b|. where**

*b***is called**

*a***dividend**

**is called**

*b***divisor**

**is called**

*q***quotient**

**is called**

*r***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?**