The largest positive integer that divides both numbers exactly.
Prime-factorization rule for HCF?
Multiply each shared prime raised to the MINIMUM of its two exponents.
Prime-factorization rule for LCM?
Multiply every prime (from either number) to the MAXIMUM exponent.
Euclid's key lemma?
gcd(a,b)=gcd(b,r) where a=bq+r.
Why does Euclid's lemma hold?
Any d dividing a and b divides r=a−bq, and vice versa; same common divisors.
When does Euclid stop and what's the answer?
When remainder=0; answer is the last non-zero remainder.
Identity linking gcd and lcm?
gcd(a,b)·lcm(a,b)=a·b.
Bézout's identity?
There exist integers x,y with ax+by=gcd(a,b).
gcd(360,84)=?
12 (=2²·3).
gcd(a,0)=?
a.
Two numbers with gcd=1 are called?
Coprime (relatively prime).
Recall Feynman: explain to a 12-year-old
You have 12 red sweets and 18 blue sweets. You want to make identical goodie-bags using ALL the sweets, same red count and same blue count in every bag. The most bags you can make is the HCF = 6 (each bag: 2 red, 3 blue). To find it lazily: keep swapping "big number becomes what's left over after fitting the small number as many times as possible" until nothing is left over — the last leftover before zero is the answer. That trick is Euclid's algorithm.
HCF ya GCD ka matlab hai: do numbers ko sabse bada kaunsa number exactly divide kar deta hai. Jaise 12 aur 18 dono ko 6 exactly divide karta hai, aur 6 se bada koi common divisor nahi — to HCF = 6. Sochte hai tile-fitting jaisa: sabse badi tile jo dono floors ko perfectly cover kar de.
Do methods hai. Prime factorization mein dono numbers ko primes mein todo, phir har common prime ka minimum power lo. Yaad rakho: HCF = min power, LCM = max power. Log yahin galti karte hai — "highest" sun kar highest power le lete hai, jo actually LCM ho jata hai. HCF humble hota hai, chhote powers leta hai.
Dusra aur fast tarika hai Euclidean algorithm. Bade number ko chhote se divide karo, remainder nikalo, phir chhota number ban jata hai naya "bada" aur remainder ban jata hai naya "chhota" — yeh repeat karo jab tak remainder 0 na ho. Jo last non-zero remainder bacha, wahi HCF hai. Iska logic simple hai: agar koi number a aur b dono ko divide karta hai, to wo remainder r=a−bq ko bhi divide karega — isliye common divisors kabhi change nahi hote.
Yeh cheez fractions simplify karne, equal groups banane, aur cryptography (RSA) tak mein use hoti hai. Ek bonus identity: gcd×lcm=a×b — ek nikaalo to dusra turant mil jata hai.
