Euclids Division Algorithm

Imagine you have two ribbons, one 420 cm long and the other 130 cm long, and you must cut both into equal pieces of the greatest possible length with nothing wasted. That "greatest common length" is exactly the HCF of 420 and 130 — and around 300 BCE the Greek mathematician Euclid gave a remarkably clean, repeat-until-done recipe to find it that we still use today.

Definition: Euclid's Division Lemma states that for any two positive integers a and b, there exist unique whole numbers q (quotient) and r (remainder) such that a = bq + r, where 0 ≤ r < b.

Definition: Euclid's Division Algorithm is a repeated application of this lemma to compute the HCF (Highest Common Factor) of two positive integers: keep dividing the previous divisor by the previous remainder until the remainder becomes 0; the last non-zero remainder (the last divisor) is the HCF.

The lemma — division written as an equation

Euclid's Division Lemma is nothing but the ordinary division you have done since primary school, written in one tidy line. When you divide a by b, you get a quotient q and a remainder r, and the relation dividend = divisor × quotient + remainder becomes a = bq + r.

The single most important part is the condition 0 ≤ r < b. It says two things at once:

• The remainder is never negative (r ≥ 0).
• The remainder is always strictly less than the divisor (r < b). If your remainder ever came out equal to or bigger than b, you did not divide far enough.

The word "lemma" simply means a small proven statement used as a stepping-stone to a bigger result. The word "unique" is doing real work here: for a given a and b, there is exactly one pair (q, r) satisfying both a = bq + r and 0 ≤ r < b. You cannot find a second valid pair. For example, take a = 17, b = 5. Then 17 = 5 × 3 + 2, so q = 3 and r = 2, and indeed 0 ≤ 2 < 5. No other whole-number pair works.

Note the lemma is stated for positive integers a and b in the NCERT Class 10 syllabus, and q, r are whole numbers (so they can be 0).

The algorithm — using the lemma again and again to get HCF

To find the HCF of two positive integers using Euclid's Division Algorithm, follow these steps. Take the larger number as a and the smaller as b (so a > b).

1. Apply the lemma to a and b: write a = bq + r with 0 ≤ r < b.
2. If r = 0, then b is the HCF and you stop.
3. If r ≠ 0, apply the lemma again, this time to b and r (the old divisor becomes the new dividend, the old remainder becomes the new divisor).
4. Repeat step 3 — always divide the previous divisor by the previous remainder — until the remainder is exactly 0.
5. When the remainder finally becomes 0, the divisor at that last stage is HCF(a, b).

Why it works (intuition): at every step, HCF(a, b) = HCF(b, r). This is because any number that divides both a and b also divides r = a − bq, and any number that divides both b and r also divides a = bq + r. So the common divisors never change as we go down the ladder. The numbers keep shrinking (the remainder is strictly smaller each time), so the process must end with remainder 0 after finitely many steps — and the last divisor carries the same HCF as the original pair.

Let us find HCF(420, 130) to match the ribbon story:

• 420 = 130 × 3 + 30 (remainder 30, not 0 — continue)
• 130 = 30 × 4 + 10 (remainder 10, not 0 — continue)
• 30 = 10 × 3 + 0 (remainder 0 — stop)

The last divisor is 10, so HCF(420, 130) = 10. The greatest equal piece is 10 cm long: the 420 cm ribbon gives 42 pieces and the 130 cm ribbon gives 13 pieces, with none wasted.

Common forms: writing any integer in terms of a chosen divisor

A favourite exam use of the lemma is to classify integers. If you fix the divisor b, then by the lemma every integer a can be written as a = bq + r with r taking only the values 0, 1, 2, …, (b − 1).

Take b = 2. Then r is 0 or 1, so every positive integer is either 2q (even) or 2q + 1 (odd). This is the formal proof that every integer is even or odd.

Take b = 3. Then r is 0, 1 or 2, so every positive integer is of the form 3q, 3q + 1, or 3q + 2. This is the key to showing results like "the square of any positive integer is of the form 3m or 3m + 1".

Take b = 4. Then r is 0, 1, 2 or 3, so every positive integer is 4q, 4q + 1, 4q + 2, or 4q + 3. Since 4q and 4q + 2 are even, every odd integer must be 4q + 1 or 4q + 3.

The method is always the same: apply the lemma with the chosen b, list the finite possibilities for r, then reason case by case. The picture below shows how b = 3 sorts the number line into three tidy families.

Handling the details: uniqueness and the "last divisor" trap

Two points decide most marks on this topic.

Uniqueness of q and r. Suppose two pairs worked: a = bq₁ + r₁ and a = bq₂ + r₂, both with the remainder between 0 and b − 1. Subtracting gives b(q₁ − q₂) = r₂ − r₁. The right side is a difference of two numbers each in the range 0 to b − 1, so its size is less than b; but the left side is a multiple of b. The only multiple of b whose size is less than b is 0. Hence r₂ = r₁, and then q₁ = q₂. So the pair (q, r) is unique — exactly what the lemma claims.

The last-divisor trap. The HCF is the last divisor (equivalently, the last non-zero remainder), NOT the final remainder 0 and NOT the last quotient. In HCF(420, 130) above, the answer is the divisor 10 at the step "30 = 10 × 3 + 0". Students who write "0" or who stop at a non-zero remainder lose the mark. Always continue until the remainder is exactly 0, then look back one line for the divisor.

---

Work through these examples. They begin with a plain HCF computation and build to the twists CBSE boards enjoy — proofs by cases, word problems, and an assertion-reason trap. Keep the two tools ready: the lemma a = bq + r (0 ≤ r < b) and the algorithm (last divisor = HCF).

Example 1 — HCF by Euclid's algorithm (basic)

Q: Find the HCF of 867 and 255 using Euclid's division algorithm.
Given: a = 867, b = 255 (larger taken as a).
Solve:
867 = 255 × 3 + 102 (remainder 102 ≠ 0 — continue)
255 = 102 × 2 + 51 (remainder 51 ≠ 0 — continue)
102 = 51 × 2 + 0 (remainder 0 — stop)
The last divisor is 51.
Answer: HCF(867, 255) = 51. Check: 867 = 51 × 17, 255 = 51 × 5, and 17, 5 share no common factor except 1 ✓

Example 2 — HCF of a smaller pair

Q: Find the HCF of 96 and 404 by Euclid's algorithm.
Given: a = 404, b = 96.
Solve:
404 = 96 × 4 + 20 (remainder 20)
96 = 20 × 4 + 16 (remainder 16)
20 = 16 × 1 + 4 (remainder 4)
16 = 4 × 4 + 0 (remainder 0 — stop)
Last divisor = 4.
Answer: HCF(96, 404) = 4. Check: 404 = 4 × 101, 96 = 4 × 24 ✓

Example 3 — Apply the lemma once

Q: Using the division lemma, write 4032 in the form 12q + r with 0 ≤ r < 12.
Formula: a = bq + r, 0 ≤ r < b, with b = 12.
Solve: 4032 ÷ 12 = 336 exactly, so q = 336 and r = 0. Thus 4032 = 12 × 336 + 0.
Answer: q = 336, r = 0, so 4032 = 12 × 336. Since r = 0, 12 divides 4032 exactly ✓

Example 4 — Tricky: every positive odd integer is 4q + 1 or 4q + 3

Q: Show that every positive odd integer is of the form 4q + 1 or 4q + 3, where q is a whole number.
Solve: Let a be any positive integer and take b = 4 in the lemma. Then a = 4q + r with 0 ≤ r < 4, so r ∈ {0, 1, 2, 3}. Hence a is 4q, 4q + 1, 4q + 2, or 4q + 3. Now 4q = 2(2q) is even and 4q + 2 = 2(2q + 1) is even, so neither can be odd. The remaining forms 4q + 1 and 4q + 3 are each "even + 1", hence odd.
Answer: A positive odd integer cannot be 4q or 4q + 2, so it must be 4q + 1 or 4q + 3. Proved. Sanity check: 7 = 4×1 + 3 (odd) and 9 = 4×2 + 1 (odd) ✓

Example 5 — Tricky: square of any positive integer is 3m or 3m + 1

Q: Use Euclid's division lemma to show that the square of any positive integer is of the form 3m or 3m + 1 for some integer m.
Solve: Let a be a positive integer. With b = 3, a = 3q + r where r ∈ {0, 1, 2}. Square each case:
• a = 3q ⇒ a² = 9q² = 3(3q²) = 3m, taking m = 3q².
• a = 3q + 1 ⇒ a² = 9q² + 6q + 1 = 3(3q² + 2q) + 1 = 3m + 1, taking m = 3q² + 2q.
• a = 3q + 2 ⇒ a² = 9q² + 12q + 4 = 3(3q² + 4q + 1) + 1 = 3m + 1, taking m = 3q² + 4q + 1.
Answer: In every case a² is 3m or 3m + 1 — never 3m + 2. Proved. Check: 4² = 16 = 3×5 + 1 (form 3m+1); 6² = 36 = 3×12 (form 3m) ✓

Example 6 — Tricky: word problem (maximum equal columns)

Q: Two groups of 616 army cadets and 32 army members are to march behind their band such that both groups have the same number of columns, and this number is the greatest possible. Find the maximum number of columns.
Given: We need the greatest common measure of 616 and 32, i.e. HCF(616, 32).
Solve:
616 = 32 × 19 + 8 (remainder 8)
32 = 8 × 4 + 0 (remainder 0 — stop)
Last divisor = 8.
Answer: The maximum number of columns is 8. Check: 616 = 8 × 77 and 32 = 8 × 4, so both groups split evenly into 8 columns ✓

Example 7 — Tricky: assertion–reason trap

Q: Assertion (A): HCF(455, 42) = 7. Reason (R): In Euclid's algorithm, the HCF is the last remainder obtained (that is, 0). State whether A and R are true, and whether R correctly explains A.
Solve: Compute the HCF. 455 = 42 × 10 + 35; 42 = 35 × 1 + 7; 35 = 7 × 5 + 0. Last divisor = 7, so A is TRUE. Now examine R: the HCF is the last non-zero remainder / last divisor, which is 7 here — it is not the last remainder 0. So R is FALSE (it states the wrong rule).
Answer: A is true, R is false. The correct reason is that the HCF is the last non-zero remainder (the last divisor), not the final remainder 0. Trap dodged ✓

Example 8 — Tricky: three numbers via HCF

Q: Find the largest number that divides 245 and 1029 leaving remainder 5 in each case.
Given: If the number leaves remainder 5, then it divides (245 − 5) = 240 and (1029 − 5) = 1024 exactly. So we need HCF(240, 1024), and the answer must also be greater than 5 (so that a remainder of 5 is possible).
Solve:
1024 = 240 × 4 + 64 (remainder 64)
240 = 64 × 3 + 48 (remainder 48)
64 = 48 × 1 + 16 (remainder 16)
48 = 16 × 3 + 0 (remainder 0 — stop)
Last divisor = 16.
Answer: The largest such number is 16 (and 16 > 5, so a remainder of 5 is valid). Check: 245 = 16 × 15 + 5 and 1029 = 16 × 64 + 5 ✓

Using division with remainder to find the HCF of two numbers.

• 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.
• Here a = dividend, b = divisor, q = quotient, r = remainder.
• Euclid’s Division Algorithm uses the lemma repeatedly to find the HCF of two numbers.
• Steps: divide the larger by the smaller; if remainder is 0, the divisor is the HCF; else make the remainder the new divisor and repeat.
• The HCF is the last non-zero remainder (the last divisor).
• Example: HCF(455, 42): 455 = 42×10 + 35; 42 = 35×1 + 7; 35 = 7×5 + 0 → HCF = 7.

Cover the answer, recall, then check. 7 cards on Euclid’s division method.

Q1. State Euclid’s Division Lemma.
A1. For positive integers a and b, there exist unique q and r with a = bq + r and 0 ≤ r < b.

Q2. What does Euclid’s Division Algorithm find?
A2. The HCF (highest common factor) of two positive integers.

Q3. In a = bq + r, what are a, b, q and r?
A3. a = dividend, b = divisor, q = quotient, r = remainder.

Q4. How do you know you have reached the HCF in the algorithm?
A4. When the remainder becomes 0; the divisor at that step is the HCF.

Q5. Find the HCF of 455 and 42 using the algorithm.
A5. 455 = 42×10+35; 42 = 35×1+7; 35 = 7×5+0 → HCF = 7.

Q6. What is the range of the remainder r in the lemma?
A6. 0 ≤ r < b (it is at least 0 and less than the divisor).

Q7. If a = bq + r and r = 0, what does it mean?
A7. b divides a exactly, so b is a factor of a.