Extra Questions For Class 10 Maths Chapter 1 Real Numbers Based On Euclid’s Division Algorithm

Extra Questions On Euclid’s Division Algorithm

Euclid’s division algorithm is a technique to compute the Highest Common Factor (HCF) of two given positive integers. Recall that the HCF of two positive integers a and b is the largest positive integer d that divides both a and b.

To obtain the HCF of two positive integers, say c and d, with c > d, follow the steps below:
Step 1 : Apply Euclid’s division lemma, to c and d. So, we find whole numbers, q and r such that c = dq + r, 0≤ r < b .
Step 2 : If r = 0, d is the HCF of c and d. If r≠0 apply the division lemma to d and r.
Step 3 : Continue the process till the remainder is zero. The divisor at this stage will be the required HCF.
This algorithm works because HCF (c, d) = HCF (d, r) where the symbol HCF (c, d) denotes the HCF of c and d, etc.

Question: Use Euclid’s division algorithm to find the HCF of 867 and 255
Solution: Since 867 > 255, we apply the division lemma to 867 and 255 to obtain
867 = 255 × 3 + 102
Since remainder 102 ≠ 0, we apply the division lemma to 255 and 102 to obtain
255 = 102 × 2 + 51
We consider the new divisor 102 and new remainder 51, and apply the division lemma to obtain
102 = 51 × 2 + 0
Since the remainder is zero, the process stops.
Since the divisor at this stage is 51,
Therefore, HCF of 867 and 255 is 51.

Q.1. Use Euclid’s algorithm to find the HCF of 4052 and 12576.

Q.2. Use Euclid’s division algorithm to find the HCF of 135 and 225.

Q.3. Use Euclid’s division algorithm to find the HCF of 196 and 38220.

Q.4. Use Euclid’s division algorithm to find the HCF of 455 and 42.

Q.5. Using Euclid’s division algorithm, find which of the following pairs of numbers are co-prime: (i) 231, 396 (ii) 847, 2160

Q.6. If the HCF of 65 and 117 is expressible in the form 65m – 117, then find the value of m.

Q.7. Find the HCF of 81 and 237 and express it as a linear combination of 81 and 237.

Q.8. Find the HCF of 65 and 117 and express it in the form 65m + 117n.

Q.9. If the HCF of 210 and 55 is expressible in the form of 210×5 + 55y, find y.

Q.10. If d is the HCF of 56 and 72, find x, y satisfying d = 56x + 72y. Also show that x and y are not unique.

Q.11. Express the HCF of 468 and 222 as 468x + 222y where x, y are integers in two different ways.

Q.12. Express the HCF of 210 and 55 as 210x + 55y where x, y are integers in two different ways.

Q.13. If the HCF of 408 and 1032 is expressible in the form of 1032m – 408×5, find m.

Frequently Asked Questions – FAQs

How does Euclid algorithm calculate HCF?

To obtain the HCF of two positive integers, say c and d, with c > d, follow the steps below:
Step 1 : Apply Euclid’s division lemma, to c and d. So, we find whole numbers, q and r such that c = dq + r, 0≤ r < b .
Step 2 : If r = 0, d is the HCF of c and d. If r≠0 apply the division lemma to d and r.
Step 3 : Continue the process till the remainder is zero. The divisor at this stage will be the required HCF.

What is the HCF of 196 and 38220?

Since 867 > 255, we apply the division lemma to 867 and 255 to obtain
38220 = 196 × 195 + 0
Therefore, the HCF of 196 and 38220 is 196.

Related Posts

Category Lists (All Posts)