Euclid's Division Lemma

For any two positive integers $a$ and $b$, there exist unique integers $q$ and $r$ such that:

$$a = bq + r, \quad 0 \leq r < b$$

where $q$ is the quotient and $r$ is the remainder.

Example: Finding HCF using Euclid's Algorithm

Find the HCF of $455$ and $42$.

Step 1: Apply the division lemma to $455$ and $42$:

$$455 = 42 \times 10 + 35$$

Step 2: Since $r = 35 \neq 0$, apply the lemma to $42$ and $35$:

$$42 = 35 \times 1 + 7$$

Step 3: Apply the lemma to $35$ and $7$:

$$35 = 7 \times 5 + 0$$

Since the remainder is now $0$, the HCF is $\boxed{7}$.