Day 1 · Euclid's Division Lemma

Euclid's Division Lemma: for any two positive integers a and b, there exist unique integers q and r such that a = bq + r, where 0 ≤ r < b.

258 divided by 8: 258 = 8×32 + 2 — the quotient (q) is 32 and the remainder (r) is 2.

We can apply this lemma repeatedly to find the HCF of two numbers — this is called "Euclid's Algorithm".

Activity: Use Euclid's Algorithm to find the HCF of 96 and 72.