A hall floor 420 cm × 360 cm is to be covered with identical square tiles of the largest possible size, with no cutting. One tile is shown. How many tiles are needed?

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