09. Euclid Algorithm (HCF Fast Method)

Euclid Algorithm se HCF (GCD) fast nikalna: concept, steps, a mod b method, why it works (simple), examples, SSC CGL practice questions with answers.

---

1) Euclid Algorithm kya hai? (Simple)

Euclid Algorithm HCF/GCD nikalne ka sabse fast aur clean method hai. Idea simple: remainder ko use karke problem ko repeatedly smaller banate jao.

2) Core rule (one line)

Agar a = bq + r (where 0 ≤ r < b), then: HCF(a, b) = HCF(b, r).

Matlab: a ko b se divide karo, remainder nikalo, phir HCF(b, remainder) nikal do. Repeat until remainder 0.

3) Steps (algorithm)

1. Assume a > b (agar nahi to swap).
2. a ÷ b karo, remainder r nikalo.
3. Now set (a, b) = (b, r).
4. Repeat until r = 0.
5. Last non-zero remainder = HCF.

4) Why it works? (Exam-friendly reason)

a = bq + r me a aur b ka common divisor d hoga to d, bq ko bhi divide karega. Isliye d, (a − bq) = r ko bhi divide karega. So common divisors of (a,b) and (b,r) same hote hain ⇒ HCF same.

5) Example 1 (classic)

Find HCF(252, 105)

• 252 = 105×2 + 42
• 105 = 42×2 + 21
• 42 = 21×2 + 0

HCF = 21

6) Example 2 (bigger numbers)

Find HCF(1190, 544)

• 1190 = 544×2 + 102
• 544 = 102×5 + 34
• 102 = 34×3 + 0

HCF = 34

7) Quick tips (SSC)

• Mod form ya division form dono same: HCF(a,b) = HCF(b, a mod b).
• Numbers bade ho to prime factorization slow hota; Euclid fast hota.
• 3 numbers ka HCF: HCF(a,b,c) = HCF(HCF(a,b), c).

8) Common traps

• “Last remainder” bolke 0 le lena — HCF last non-zero remainder hota hai.
• a > b ensure karo (warna swap).

---

9) Practice (SSC CGL) + Answers

1. Find HCF(270, 192) using Euclid method.
2. Find HCF(1015, 455).
3. Find HCF of 3 numbers: 84, 126, 210.
4. If a = 864 and b = 315, find HCF(a,b).
5. True/False: HCF(a,b) = HCF(a, a−b).

Show Answers

1. 270=192×1+78; 192=78×2+36; 78=36×2+6; 36=6×6+0 ⇒ HCF=6
2. 1015=455×2+105; 455=105×4+35; 105=35×3+0 ⇒ HCF=35
3. HCF(84,126)=42; then HCF(42,210)=42 ⇒ answer 42
4. 864=315×2+234; 315=234×1+81; 234=81×2+72; 81=72×1+9; 72=9×8+0 ⇒ HCF=9
5. True (since HCF(a,b)=HCF(a, a−b) also works; repeated subtraction is same idea)