NEWAll India NCERT Mock Test Series is now live!Take Free Test
| Exercise end-of-chapter

Q1: Compute the following using the improved version of Euclid’s algorithm. (i) gcd⁡(375,825)\gcd(375, 825) (ii) gcd⁡(51000,81000)\gcd(51000, 81000) (iii) gcd⁡(1789287,237656)\gcd(1789287, 237656) (iv) gcd⁡(2587392,157656)\gcd(2587392, 157656)

UNDERSTAND THE QUESTION

The question asks to compute the Greatest Common Divisor (GCD) of four pairs of numbers using the improved version of Euclid's algorithm.

Core Concept (Class 9 NCERT - Chapter 11: Number Systems / Euclid's Division Lemma):
Euclid's Division Lemma states that for any two positive integers aa and bb, there exist unique integers qq and rr such that:
a=bq+r,0≤r<ba = bq + r, \quad 0 \le r < b

The Algorithm:

  1. Let aa be the larger number and bb be the smaller number.
  2. Divide aa by bb to get quotient qq and remainder rr.
  3. If r=0r = 0, then gcd⁡(a,b)=b\gcd(a, b) = b.
  4. If r≠0r \neq 0, replace aa with bb and bb with rr, and repeat the process.

This process continues until the remainder becomes zero. The divisor at that stage is the GCD.

(i)PART I

Compute gcd⁡(375,825)\gcd(375, 825)

Step 1 — IDENTIFY DIVIDEND AND DIVISOR

Let a=825a = 825 and b=375b = 375. Since 825>375825 > 375, we divide 825825 by 375375.

Using Euclid's Division Lemma:
825=375×q+r825 = 375 \times q + r

We find the quotient qq and remainder rr:
825÷375=2 with a remainder of 75825 \div 375 = 2 \text{ with a remainder of } 75

So,
825=375×2+75825 = 375 \times 2 + 75
Here, r=75≠0r = 75 \neq 0.

Step 2 — REPEAT WITH NEW DIVIDEND AND DIVISOR

Now, take the previous divisor 375375 as the new dividend and the previous remainder 7575 as the new divisor.

375=75×q+r375 = 75 \times q + r

We find the quotient qq and remainder rr:
375÷75=5 with a remainder of 0375 \div 75 = 5 \text{ with a remainder of } 0

So,
375=75×5+0375 = 75 \times 5 + 0
Here, r=0r = 0.

Step 3 — DETERMINE THE GCD

Since the remainder is now 00, the process stops. According to Euclid's algorithm, the GCD is the divisor at the last step where the remainder became zero.

The divisor is 7575.

Therefore, gcd⁡(375,825)=75\gcd(375, 825) = 75.

ANSWER (I)

gcd⁡(375,825)=75\gcd(375, 825) = 75

(ii)PART II

Compute gcd⁡(51000,81000)\gcd(51000, 81000)

Step 1 — IDENTIFY DIVIDEND AND DIVISOR

Let a=81000a = 81000 and b=51000b = 51000. Since 81000>5100081000 > 51000, we divide 8100081000 by 5100051000.

Using Euclid's Division Lemma:
81000=51000×q+r81000 = 51000 \times q + r

We find the quotient qq and remainder rr:
81000÷51000=1 with a remainder of 3000081000 \div 51000 = 1 \text{ with a remainder of } 30000

So,
81000=51000×1+3000081000 = 51000 \times 1 + 30000
Here, r=30000≠0r = 30000 \neq 0.

Step 2 — REPEAT WITH NEW DIVIDEND AND DIVISOR

Now, take the previous divisor 5100051000 as the new dividend and the previous remainder 3000030000 as the new divisor.

51000=30000×q+r51000 = 30000 \times q + r

We find the quotient qq and remainder rr:
51000÷30000=1 with a remainder of 2100051000 \div 30000 = 1 \text{ with a remainder of } 21000

So,
51000=30000×1+2100051000 = 30000 \times 1 + 21000
Here, r=21000≠0r = 21000 \neq 0.

Step 3 — REPEAT AGAIN

Now, take the previous divisor 3000030000 as the new dividend and the previous remainder 2100021000 as the new divisor.

30000=21000×q+r30000 = 21000 \times q + r

We find the quotient qq and remainder rr:
30000÷21000=1 with a remainder of 900030000 \div 21000 = 1 \text{ with a remainder of } 9000

So,
30000=21000×1+900030000 = 21000 \times 1 + 9000
Here, r=9000≠0r = 9000 \neq 0.

Step 4 — REPEAT AGAIN

Now, take the previous divisor 2100021000 as the new dividend and the previous remainder 90009000 as the new divisor.

21000=9000×q+r21000 = 9000 \times q + r

We find the quotient qq and remainder rr:
21000÷9000=2 with a remainder of 300021000 \div 9000 = 2 \text{ with a remainder of } 3000

So,
21000=9000×2+300021000 = 9000 \times 2 + 3000
Here, r=3000≠0r = 3000 \neq 0.

Step 5 — REPEAT AGAIN

Now, take the previous divisor 90009000 as the new dividend and the previous remainder 30003000 as the new divisor.

9000=3000×q+r9000 = 3000 \times q + r

We find the quotient qq and remainder rr:
9000÷3000=3 with a remainder of 09000 \div 3000 = 3 \text{ with a remainder of } 0

So,
9000=3000×3+09000 = 3000 \times 3 + 0
Here, r=0r = 0.

Step 6 — DETERMINE THE GCD

Since the remainder is now 00, the process stops. The GCD is the divisor at the last step.

The divisor is 30003000.

Therefore, gcd⁡(51000,81000)=3000\gcd(51000, 81000) = 3000.

ANSWER (II)

gcd⁡(51000,81000)=3000\gcd(51000, 81000) = 3000

Was this solution helpful?