Two ribbons of length 108 cm and 144 cm are to be cut into pieces of equal length, with nothing left over and each piece as long as possible. How many pieces are obtained altogether?

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