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

Answer: Let n and n-1 be the 2 positive integers.

∴ product= n(n-1) =n

^{2}-n

**CASE 1 (when n is even):**

Let n = 2q

n

^{2}-n = (2q)

^{2 }- 2q

= 4q

^{2}-2q

= 2q (2q-1)

Hence the product n

^{2}-n is divisible by 2

**CASE 2(when n is odd)**

Let n be 2q+1

n

^{2}-n = (2q+1)

^{2}- (2q+1)

= 4q

^{2}+4q+1-2q-1

= 4q

^{2}+2q

= 2q(2q+1)

Hence the product n

^{2}-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

a

^{2}- 1= (4k+1)

^{2}- 1 or a

^{2}- 1 = (4k+3)

^{2}- 1 .

⇒ a

^{2}- 1= 16k

^{2}+ 8k + 1 or a

^{2}-1 = 16k

^{2}+ 24k + 8 .

⇒ a

^{2}- 1= 8k(2k + 1) or a

^{2}- 1 = 8 (2k

^{2}+ 3k + 1) .

∴ a

^{2}- 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.

**See Also:**

CH 1: Real Numbers (MCQ)

CH 1: Real Numbers (Study Points)

CH 1: Real Numbers (NCERT Ex 1.1)

20 questions for euclid division algorithm and 20 for euclid division lemna

ReplyDelete