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 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 exist 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: 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 exist 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?