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

**Select Category**

All categories of this website are listed below with number of posts in each category for better navigation. Visitors can click on a particular category to see all posts related to that category.

- Biography of Scientists (1)
- Biology (65)
- Blog Posts (31)
- Career Guidance (1)
- CBSE Class 10 Maths (86)
- Assertion Reason Questions for Class 10 Maths (14)
- Case Study Questions for Class 10 Maths (14)
- Extra Questions for Class 10 Maths (12)
- Maths Formulas for Class 10 (1)
- MCQ Questions for Class 10 Maths (9)
- NCERT Solutions for Class 10 Maths (8)
- Quick Revision Notes for Class 10 Maths (14)
- RS Aggarwal Solutions for Class 10 Maths (12)

- CBSE Class 10 Science (185)
- Assertion Reason Questions for Class 10 Science (16)
- Case Study Questions for Class 10 Science (14)
- Evergreen Science Book Solutions for Class 10 (17)
- Extra Questions for Class 10 Science (21)
- HOTS for Class 10 Science (17)
- Important Questions for Class 10 Science (10)
- Lakhmir Singh Class 10 Biology Solutions (4)
- Lakhmir Singh Class 10 Chemistry Solutions (5)
- Lakhmir Singh Class 10 Physics Solutions (5)
- MCQ Questions for Class 10 Science (20)
- NCERT Exemplar Solutions for Class 10 Science (16)
- NCERT Solutions for Class 10 Science (15)
- Quick Revision Notes for Class 10 Science (4)
- Study Notes for Class 10 Science (17)

- CBSE CLASS 11 (1)
- CBSE Class 11 Chemistry (52)
- CBSE Class 11 Maths (26)
- CBSE Class 11 Physics (115)
- Assertion Reason Questions for Class 11 Physics (15)
- Case Study Questions for Class 11 Physics (12)
- Class 11 Physics Study Notes (5)
- Conceptual Questions for Class 11 Physics (9)
- Extra Questions for Class 11 Physics (9)
- MCQ Questions for Class 11 Physics (7)
- Physics Formulas for Class 11 (7)
- Revision Notes for Class 11 Physics (11)
- Very Short Answer Questions for Class 11 Physics (11)

- CBSE CLASS 12 (8)
- CBSE Class 12 Biology (27)
- CBSE Class 12 Business Studies (10)
- CBSE Class 12 Chemistry (81)
- Assertion Reason Questions for Class 12 Chemistry (15)
- Case Study Based Questions for Class 12 Chemistry (14)
- Extra Questions for Class 12 Chemistry (4)
- Important Questions for Class 12 Chemistry (15)
- MCQ Questions for Class 12 Chemistry (8)
- NCERT Solutions for Class 12 Chemistry (16)
- Revision Notes for Class 12 Chemistry (7)

- CBSE Class 12 Maths (42)
- CBSE Class 12 Physics (107)
- Assertion Reason Questions for Class 12 Physics (16)
- Case Study Based Questions for Class 12 Physics (14)
- Class 12 Physics Conceptual Questions (15)
- Class 12 Physics Discussion Questions (1)
- Class 12 Physics Latest Updates (1)
- Derivations for Class 12 Physics (5)
- Extra Questions for Class 12 Physics (4)
- Important Questions for Class 12 Physics (8)
- MCQ Questions for Class 12 Physics (14)
- NCERT Solutions for Class 12 Physics (18)
- Numerical Problems Based on Class 12 Physics (3)
- Revision Notes for Class 12 Physics (7)

- CBSE Class 7 (80)
- CBSE Class 9 Maths (55)
- CBSE Class 9 Science (107)
- Assertion Reason Questions for Class 9 Science (16)
- Case Study Questions for Class 9 Science (14)
- Extra Questions for Class 9 Science (18)
- MCQ Questions for Class 9 Science (11)
- NCERT Solutions for Class 9 Science (15)
- Revision Notes for Class 9 Science (1)
- Study Notes for Class 9 Science (15)
- Topic wise MCQ Questions for Class 9 Science (2)
- Topicwise Questions and Answers for Class 9 Science (15)

- CHEMISTRY (8)
- Chemistry Articles (1)
- Daily Practice Problems (DPP) (3)
- H. C. Verma (Concepts of Physics) (18)
- ICSE Class 10 Biology (14)
- ICSE Class 10 Chemistry (5)
- ICSE Class 10 Maths (16)
- ICSE Class 10 Physics (12)
- IIT Foundation Mathematics (4)
- JEE Advanced Physics (3)
- JEE Chemistry (7)
- JEE Main Mock Test Series (1)
- JEE Mock Test Physics (1)
- JEE Study Material (1)
- JEE/NEET Physics (6)
- Maths Articles (1)
- NCERT Books (3)
- NEET Chemistry (13)
- NEET Physics (55)
- NTSE (1)
- Physics (1)
- Physics Articles (12)
- Physics for JEE Main (19)
- Previous Years Question Paper (3)
- Products (50)
- Products for CBSE Class 10 (8)
- Products for CBSE Class 11 (9)
- Products for CBSE Class 12 (6)
- Products for CBSE Class 7 (3)
- Products for CBSE Class 8 (1)
- Products for CBSE Class 9 (3)
- Products for Commerce (3)
- Products for Foundation Courses (2)
- Products for JEE Main & Advanced (10)
- Products for NEET (6)

- Question Answer (3)
- Topic Wise Study Notes (Physics) (2)
- Topicwise MCQs (2)
- Uncategorized (138)

**Test Series (Engineering, Medical and School Level Exams)**

Test series for students preparing for Engineering & Medical Entrance Exams are available. We also provide test series for School Level Exams. Tests for students studying in CBSE, ICSE or any state board are available here. Just click on the link and start test.