Suppose a divides b, where a and b are positive integers with a < b. Then HCF(a, b) and LCM(a, b) are, respectively:

**Lemma**: For positive integers a, $b$ (with $b>0$), there exist UNIQUE $q,r$ with $a=bq+r$ and 0 ≤ $r<b$.

This is just formal long division — $q$ is the quotient, $r$ is the remainder.

**Algorithm to find HCF(a, b)** with $a>b$:
1. Apply lemma: $a=bq+r$.
2. If $r=0$, HCF = $b$.
3. If $r$ ≠ 0, replace (a, b) with $(b$, r) and repeat.

**Example**: HCF(420, 130)$.-420=130\times 3+30-130=30\times 4+10-30=10\times 3+0$
→ HCF = 10.