Euclid's Division Algorithm for HCF

• Use Euclid's division algorithm to find HCF of two positive integers.
• Apply the lemma: for integers a, b (b ≠ 0), a = bq + r with 0 ≤ r < b.
• Repeat division until remainder is 0; the last non-zero remainder is the HCF.

1. Euclid's division lemma — a = bq + r, 0 ≤ r < b.
2. Algorithm — divide larger by smaller; replace numbers with (divisor, remainder); repeat.
3. HCF — last non-zero remainder (also called gcd).
4. Example chain — 455 = 42×10 + 35; 42 = 35×1 + 7; 35 = 7×5 + 0 → HCF = 7.
5. NCERT link — Chapter 1 Real Numbers; used to show √2, √3 are irrational.

Find HCF(867, 255) using Euclid's algorithm

867 = 255 × 3 + 102
255 = 102 × 2 + 51
102 = 51 × 2 + 0
Last non-zero remainder = 51
HCF(867, 255) = 51

• Stopping before remainder 0 and taking the wrong remainder as HCF.
• Swapping order incorrectly — always divide larger by smaller at each step.
• Confusing HCF with LCM (HCF × LCM = product of numbers for two integers).

• State Euclid's division lemma in symbols.
• Find HCF(26, 91) stepwise.
• Why must the remainder satisfy 0 ≤ r < b?

Open the Practice tab for graded questions on Euclid's Division Algorithm for HCF.