Number Systems • Topic 1 of 4

Euclid’s Division Lemma

What is Euclid's Division Lemma? Euclid's Division Lemma states that for any two positive integers a (dividend) and b (divisor), there exist unique integers q (quotient) and r (remainder) such that:

$a = bq + r$, where $0 \le r < b$.

This means: when you divide $a$ by $b$, you always get a quotient and a remainder that is smaller than the divisor. "Lemma" simply means a proven statement used to prove other statements.

Real-life example: If you have 23 candies ($a = 23$) and want to share them equally among 5 friends ($b = 5$), each friend gets 4 candies ($q = 4$) and 3 candies are left over ($r = 3$). Check: $23 = 5 \times 4 + 3$. Here $0 \le 3 < 5$, so the lemma holds.

Key properties:

  • $q$ is the floor value of $a \div b$ (the greatest integer not exceeding $a/b$)
  • $r$ is always a non-negative integer that is strictly less than $b$
  • For every pair $(a, b)$ the pair $(q, r)$ is unique — no other pair works
  • If $r = 0$, then $b$ divides $a$ exactly (we write $b \mid a$, and $a$ is a multiple of $b$)

Euclid's Division Algorithm (to find the HCF). The lemma is the engine behind a fast method for the Highest Common Factor (HCF) of two positive integers $c$ and $d$ with $c > d$:

  • Step 1. Apply the lemma: $c = dq + r$.
  • Step 2. If $r = 0$, the HCF is $d$. Stop.
  • Step 3. If $r \ne 0$, replace $(c, d)$ by $(d, r)$ and repeat Step 1.

This works because of a key fact: $\mathrm{HCF}(c, d) = \mathrm{HCF}(d, r)$. Every common divisor of $c$ and $d$ also divides $r = c - dq$, and every common divisor of $d$ and $r$ divides $c = dq + r$. So the set of common divisors never changes, and the remainders keep shrinking until one of them is $0$ — the last non-zero divisor is the HCF.

Using the lemma to prove properties of integers. Taking $b = 2$ shows every integer is $2q$ (even) or $2q+1$ (odd). Taking $b = 4$ shows every odd integer is of the form $4q+1$ or $4q+3$. Taking $b = 6$ shows every positive odd integer is of the form $6q+1$, $6q+3$, or $6q+5$. With $b = 3$ one proves that the square of any positive integer is of the form $3m$ or $3m+1$ (never $3m+2$), because squaring $3k$, $3k+1$, $3k+2$ gives remainders $0$, $1$, $1$ respectively.

Common mistakes to avoid:

  • Writing a remainder equal to or larger than the divisor (e.g. $17 = 5\times 2 + 7$). The remainder must satisfy $0 \le r < b$, so the correct form is $17 = 5\times 3 + 2$.
  • Allowing a negative remainder — $r$ is never negative.
  • In the algorithm, forgetting to shift down: the new divisor becomes the old remainder. The HCF is the last non-zero remainder's divisor, i.e. the divisor at the step where the remainder becomes $0$.
  • Confusing HCF (largest common factor) with LCM (smallest common multiple).
Euclid’s division lemma a = bq + r shown as a number line with 23 = 5×4 + 3Euclid’s Division Lemma: a = bq + r, 0 ≤ r < b23 = 5 × 4 + 3    (b = 5 groups of 5, then r = 3 left over)55553q = 4 groups of b = 5 → 5 × 4 = 20r = 3(r < b)023The remainder r is always smaller than the divisor b, and the pair (q, r) is unique.Euclid’s division algorithm finding HCF(60, 48) by repeated division until remainder zeroDivision Algorithm → HCF(60, 48)60 = 48 × 1 + 1248 = 12 × 4 + 0divisor 48, remainder 12shift down: (60,48) → (48,12)HCF = 12remainder 0 → last divisor is the HCFKeep dividing; when r = 0 the divisor at that step is HCF(60, 48) = 12.
Solved Examples
1
Worked Example
Apply Euclid’s Division Lemma to find $q$ and $r$ when $a = 47$ and $b = 6$.
Solution
  1. Step 1: Divide 47 by 6: $6 \times 7 = 42$, and $47 - 42 = 5$.
  2. Step 2: Write in the form $a = bq + r$: $47 = 6 \times 7 + 5$.
  3. Step 3: Check the remainder condition: $0 \le 5 < 6$, which holds.

Answer: $q = 7,\ r = 5$

2
Worked Example
A teacher has 125 notebooks to pack into boxes holding 12 each. Find the number of full boxes and the notebooks left over.
Solution
  1. Step 1: Here $a = 125$ (total) and $b = 12$ (box capacity).
  2. Step 2: $12 \times 10 = 120$, and $125 - 120 = 5$.
  3. Step 3: So $125 = 12 \times 10 + 5$ with $0 \le 5 < 12$.

Answer: 10 full boxes, 5 notebooks left over

3
Worked Example
Find the value of $a$ for which Euclid’s Division Lemma gives $b = 7$, $q = 8$, $r = 3$, and verify uniqueness.
Solution
  1. Step 1: Use $a = bq + r = 7 \times 8 + 3$.
  2. Step 2: Compute: $7 \times 8 = 56$, then $56 + 3 = 59$.
  3. Step 3: Verify: $59 \div 7$ gives quotient 8, remainder 3 since $59 - 56 = 3$.
  4. Step 4: No other valid pair exists: $q = 7$ forces $r = 10 \ge 7$ (invalid) and $q = 9$ forces $r = -4 < 0$ (invalid).

Answer: $a = 59$; the pair $(q, r)$ is unique

4
Worked Example
Use Euclid’s Division Algorithm to find $\mathrm{HCF}(60, 48)$.
Solution
  1. Step 1: $60 = 48 \times 1 + 12$ (remainder 12).
  2. Step 2: Shift down: now divide 48 by 12. $48 = 12 \times 4 + 0$.
  3. Step 3: The remainder is 0, so the divisor at this step, 12, is the HCF.

Answer: $\mathrm{HCF}(60, 48) = 12$

5
Worked Example
Find $\mathrm{HCF}(867, 255)$ using Euclid’s Division Algorithm.
Solution
  1. Step 1: $867 = 255 \times 3 + 102$.
  2. Step 2: $255 = 102 \times 2 + 51$.
  3. Step 3: $102 = 51 \times 2 + 0$.
  4. Step 4: Remainder is 0, so the HCF is the last divisor, 51.

Answer: $\mathrm{HCF}(867, 255) = 51$

6
Worked Example
Find $\mathrm{HCF}(135, 225)$ by Euclid’s algorithm.
Solution
  1. Step 1: Take the larger first: $225 = 135 \times 1 + 90$.
  2. Step 2: $135 = 90 \times 1 + 45$.
  3. Step 3: $90 = 45 \times 2 + 0$.
  4. Step 4: Remainder is 0, so the HCF is 45.

Answer: $\mathrm{HCF}(135, 225) = 45$

7
Worked Example
Use Euclid’s algorithm to find $\mathrm{HCF}(196, 38220)$.
Solution
  1. Step 1: Divide the larger by the smaller: $38220 = 196 \times 195 + 0$ (since $196 \times 195 = 38220$).
  2. Step 2: The remainder is 0 in one step.
  3. Step 3: Hence the divisor 196 is the HCF.

Answer: $\mathrm{HCF}(196, 38220) = 196$

8
Worked Example
Show that any positive odd integer is of the form $4q + 1$ or $4q + 3$, where $q$ is some integer.
Solution
  1. Step 1: Let $a$ be any positive integer and take $b = 4$ in the lemma: $a = 4q + r$ with $0 \le r < 4$.
  2. Step 2: So $r$ can be $0, 1, 2,$ or $3$, giving $a = 4q,\ 4q+1,\ 4q+2,\ 4q+3$.
  3. Step 3: The forms $4q$ and $4q+2 = 2(2q+1)$ are even.
  4. Step 4: The remaining forms $4q+1$ and $4q+3$ are odd, so every odd integer is one of these.

Answer: Every positive odd integer is $4q + 1$ or $4q + 3$

9
Worked Example
Show that every positive odd integer is of the form $6q + 1$, $6q + 3$, or $6q + 5$.
Solution
  1. Step 1: Take $b = 6$: any integer $a = 6q + r$ with $r \in \{0,1,2,3,4,5\}$.
  2. Step 2: The forms $6q,\ 6q+2,\ 6q+4$ are all even (each has a factor of 2).
  3. Step 3: The forms $6q+1,\ 6q+3,\ 6q+5$ are odd.
  4. Step 4: Hence any positive odd integer must be of the form $6q+1$, $6q+3$, or $6q+5$.

Answer: Odd integers are $6q+1$, $6q+3$, or $6q+5$

10
Worked Example
Show that the square of any positive integer is of the form $3m$ or $3m + 1$ for some integer $m$.
Solution
  1. Step 1: Take $b = 3$: any integer $a = 3k + r$ with $r \in \{0, 1, 2\}$.
  2. Step 2: If $a = 3k$: $a^2 = 9k^2 = 3(3k^2) = 3m$.
  3. Step 3: If $a = 3k+1$: $a^2 = 9k^2 + 6k + 1 = 3(3k^2 + 2k) + 1 = 3m + 1$.
  4. Step 4: If $a = 3k+2$: $a^2 = 9k^2 + 12k + 4 = 3(3k^2 + 4k + 1) + 1 = 3m + 1$.
  5. Step 5: In every case $a^2$ is $3m$ or $3m+1$ — never $3m + 2$.

Answer: Any square is of the form $3m$ or $3m+1$

11
Worked Example
Find the largest number that divides 70 and 125, leaving remainders 5 and 8 respectively.
Solution
  1. Step 1: If the number leaves remainder 5 on dividing 70, it divides $70 - 5 = 65$ exactly.
  2. Step 2: If it leaves remainder 8 on dividing 125, it divides $125 - 8 = 117$ exactly.
  3. Step 3: So the number is $\mathrm{HCF}(65, 117)$.
  4. Step 4: $117 = 65 \times 1 + 52$, then $65 = 52 \times 1 + 13$, then $52 = 13 \times 4 + 0$, giving HCF 13.
  5. Step 5: Check $13 > 8$, so both remainders are valid.

Answer: The required number is 13

12
Worked Example
Find the largest number which divides 2053 and 967 leaving remainders 5 and 7 respectively.
Solution
  1. Step 1: It must divide $2053 - 5 = 2048$ exactly.
  2. Step 2: It must divide $967 - 7 = 960$ exactly.
  3. Step 3: So the number is $\mathrm{HCF}(2048, 960)$.
  4. Step 4: $2048 = 960 \times 2 + 128$, then $960 = 128 \times 7 + 64$, then $128 = 64 \times 2 + 0$, giving HCF 64.
  5. Step 5: Since $64 > 7$, both remainders are valid.

Answer: The required number is 64

Key Points

  • Euclid’s Division Lemma: $a = bq + r$, where $0 \le r < b$ for positive integers $a$ and $b$
  • $q$ is the quotient (floor of $a \div b$), $r$ is the remainder
  • The remainder is always less than the divisor $b$ and never negative
  • When $r = 0$, $b$ divides $a$ exactly — this drives the division algorithm
  • The pair $(q, r)$ is unique for given $a$ and $b$
  • Euclid’s Division Algorithm finds HCF by repeated division; the HCF is the last non-zero remainder’s divisor
  • The lemma proves integer forms: every odd integer is $4q+1$/$4q+3$ or $6q+1$/$6q+3$/$6q+5$; every square is $3m$ or $3m+1$
Quick Check — 4 MCQs
Tap an option to check your answer0 / 4
Q1.Euclid's division lemma states $a=bq+r$ where:
Explanation: The remainder satisfies $0\le r
Q2.The HCF of $8$ and $12$ is:
Explanation: Greatest common divisor is $4$.
Q3.Using Euclid's algorithm, HCF$(60,48)=$
Explanation: $60=48\cdot1+12,\ 48=12\cdot4$.
Q4.The HCF of two coprime numbers is:
Explanation: Coprime numbers share only the factor $1$.
Practice more MCQs → 📝 Assignment · 35 marks