Q1: Compute the following using the improved version of Euclid’s algorithm. (i) (ii) (iii) (iv)
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 and , there exist unique integers and such that:
The Algorithm:
- Let be the larger number and be the smaller number.
- Divide by to get quotient and remainder .
- If , then .
- If , replace with and with , and repeat the process.
This process continues until the remainder becomes zero. The divisor at that stage is the GCD.
(i)PART I
ComputeStep 1 — IDENTIFY DIVIDEND AND DIVISOR
Let and . Since , we divide by .
Using Euclid's Division Lemma:
We find the quotient and remainder :
So,
Here, .
Step 2 — REPEAT WITH NEW DIVIDEND AND DIVISOR
Now, take the previous divisor as the new dividend and the previous remainder as the new divisor.
We find the quotient and remainder :
So,
Here, .
Step 3 — DETERMINE THE GCD
Since the remainder is now , 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 .
Therefore, .
ANSWER (I)
(ii)PART II
ComputeStep 1 — IDENTIFY DIVIDEND AND DIVISOR
Let and . Since , we divide by .
Using Euclid's Division Lemma:
We find the quotient and remainder :
So,
Here, .
Step 2 — REPEAT WITH NEW DIVIDEND AND DIVISOR
Now, take the previous divisor as the new dividend and the previous remainder as the new divisor.
We find the quotient and remainder :
So,
Here, .
Step 3 — REPEAT AGAIN
Now, take the previous divisor as the new dividend and the previous remainder as the new divisor.
We find the quotient and remainder :
So,
Here, .
Step 4 — REPEAT AGAIN
Now, take the previous divisor as the new dividend and the previous remainder as the new divisor.
We find the quotient and remainder :
So,
Here, .
Step 5 — REPEAT AGAIN
Now, take the previous divisor as the new dividend and the previous remainder as the new divisor.
We find the quotient and remainder :
So,
Here, .
Step 6 — DETERMINE THE GCD
Since the remainder is now , the process stops. The GCD is the divisor at the last step.
The divisor is .
Therefore, .