**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.