A 42 cm × 15 cm card is cut as shown: the largest possible squares first, then the largest squares from the strip left over, and so on until nothing is left. The side of the smallest squares (?) is HCF(42, 15). What is it?

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