Welcome! Today we're exploring Euclid's Division Algorithm — a method for chaining divisions together to find the HCF of any two numbers.

You can now perform a single division step confidently — bracketing, verifying, self-correcting.

The question is: how do you chain these steps together to actually find the HCF of two numbers?

Euclid's Division Algorithm is the answer.

Fact	Detail
Age	Over 2300 years old
Status	Still the most efficient method for computing HCF by hand

The beauty of this algorithm:

No factorisation required
Just divide, swap, and repeat
The HCF appears automatically at the end

By the end of this section, you'll understand:

Why this algorithm works — not just how
What HCF really means at a deeper level
Preparation for the back-substitution technique (expressing HCF as a linear combination)

1. The three-step algorithm

We are trying to describe a mechanical procedure — a recipe — that takes any two positive integers and produces their HCF.

The challenge is to be precise about what happens at each stage:

What you divide
What you check
What you swap
When you stop

Euclid's Division Algorithm is a method for finding the HCF of two positive integers.

It uses the division equation $a = bq + r$ repeatedlykey.

✍️ Question

Describe the algorithm in steps. 🤔

Given two positive integers $a$ and $b$ (with $a > b$ ):

What do you do first?
What do you check?
What do you do if the remainder is not 0?
When do you stop, and what is the HCFgoal?

Euclid's Division AlgorithmThree steps on repeat, power is in the repetition is three steps on repeatThe repetition is what makes it work:

Step 1: Divide the larger number ( $a$ ) by the smaller number ( $b$ ). Write: $a = b q + r$ , where $0 \leq r < b$ If remainder equals or exceeds divisor, you made an error.

Step 2: Check the remainder. If $r = 0$ stop!Your signal to stop dividing, you're done — the divisor $b$ is the HCFDon't keep dividing after you hit zero.

✍️ MCQ

Choose one

In Euclid's Division Algorithm, when do you stop the process?

✓

Step 3: If $r \neq 0$ , swap the pairThis is what makes numbers shrink each round: the old divisor becomes the new dividendOld divisor becomes new dividend, and the old remainder becomes the new divisorOld remainder becomes new divisor. Now you have the pair $(b, r)$ . Go back to Step 1Keep going until remainder hits zero.

✍️ MCQ

Choose one

If you apply Euclid's Division Lemma to

a = 56

and

b = 20

, and get

56 = 20 \times 2 + 16

, what pair do you work with next?

✓

The swapThe crucial step you must master is the crucial move.

After dividing $a$ by $b$ to get remainder $r$ , the NEXT division is $b$ divided by $r$ Divisor moves up to dividend position — not $a$ divided by $r$ .

This is where students often slip up. You don't keep dividing the original number $a$ . The divisor from the previous step becomes the dividend for the next step.Divisor becomes dividend, remainder becomes divisor

✍️ MCQ

Choose one

In Euclid's Division Algorithm, after dividing

56

by

20

and getting remainder

16

, what becomes the dividend in the next step?

✓

The old divisor moves up to become the new dividend.Numbers slide down one position each step

Step	Dividend	Divisor	Remainder
1	$a$	$b$	$r_{1}$
2	$b$	$r_{1}$	$r_{2}$
3	$r_{1}$	$r_{2}$	$r_{3}$

Notice the pattern: each row's divisor becomes the next row's dividend!

This creates a chainNumbers cascade down getting smaller — the numbers cascade down, getting smaller each time until the remainder hits zeroSTOPZero remainder signals you've found the HCF.

✍️ MCQ

Choose one

Following the pattern in the table, what will be the divisor in Step 4?

✓

2. Why HCF(a, b) = HCF(b, r)

We now know the steps of Euclid's algorithm. But knowing the steps does not explain why they work.

The next piece we need is the mathematical reason behind the swap:

When we replace the pair $(a, b)$ with $(b, r)$ , we need to be sure the HCF has not changed.

This is the engine that powers the entire algorithm.

📋 Given Info

Here's what we know:

The algorithm replaces the pair $(a, b)$ with $(b, r)$ at each step.

For this to work, $\text{HCF}(a, b)$ must equal $\text{HCF}(b, r)$ whenever $a = bq + r$ .

✍️ Question

Your task 🎯

Explain why $\text{HCF}(a, b) = \text{HCF}(b, r)$ when $a = bq + r$ .

Your explanation should cover both directions:

Why every common divisor of $(a, b)$ is also a common divisor of $(b, r)$
Why every common divisor of $(b, r)$ is also a common divisor of $(a, b)$

Here's why swapping the pair doesn't change the HCF. We need to show that $(a, b)$ and $(b, r)$ have exactly the same common divisors.

Think about it this way: if both pairs share the exact same set of common divisors, then their greatest common divisor must also be the sameSame divisors means same HCF!

✍️ Yes/No

Yes or No?

If two pairs of numbers have exactly the same set of common divisors, must their HCFs be equal?

✓

So our proof strategy is clear:

Direction 1:First one way, then the other Show that every common divisor of $(a, b)$ is also a common divisor of $(b, r)$ .

Direction 2:(Then prove the reverse direction) Show that every common divisor of $(b, r)$ is also a common divisor of $(a, b)$ .

If we prove both directions, the two sets of common divisors are identicalBoth directions proven means identical sets — and therefore $\text{HCF}(a, b) = \text{HCF}(b, r)$ Goal(Identical divisor sets give same HCF).

Forward directionChecking if divisors of a and b also divide r: Take any number $d$ that divides both $a$ and $b$ First half of proving common divisors stay the same. Does $d$ also divide $r$ ?

Yes: $r = a - bq$ The rearrangement that makes everything work. Since $d$ divides $a$ and $d$ divides $b$ (and hence $b q$ ), $d$ must divide $a - b q = r$ . So $d$ divides both $b$ and $r$ proven!The conclusion follows automatically.

✍️ Yes/No

Yes or No?

If

d

divides both

m

and

n

, does

d

also divide

m - n

?

✓

Reverse direction: Now let's go the other way. Take any number $d$ that divides both $b$ and $r$ . The question is — does $d$ also divide $a$ ?

Yes! Look at the original equationTracing back through the equation: $a = b q + r$ . Since $d$ divides $b$ , it must divide $b q$ . And $d$ divides $r$ d divides both quantities by assumption. So $d$ divides $bq + r$ Dividing both means dividing their sum, which is exactly $a$ . Therefore $d$ divides both $a$ and $b$ ✓The divisibility rule in action.

✍️ MCQ

Choose one

If

(a, b)

and

(b, r)

have exactly the same set of common divisors, then

\text{HCF}(a, b)

and

\text{HCF}(b, r)

must be:

✓

Both directions together:Both pairs have identical common divisors Every common divisor of $(a, b)$ is a common divisor of $(b, r)$ , and every common divisor of $(b, r)$ is a common divisor of $(a, b)$ . The two pairs share exactly the sameNot just some overlap — complete sharing common divisors — so their greatest common divisor must be equal. That's why (Key Result) $\text{HCF}(a, b) = \text{HCF}(b, r)$ The greatest element of the same set must be equal.

Since every common divisor of one pair is a common divisor of the other, the two pairs share the exact same set of common divisors.

Therefore they share the same greatest common divisor:

\text{HCF}(a, b) = \text{HCF}(b, r)

golden equation(The key equation that lets you swap pairs)

✍️ MCQ

Choose one

If

\text{HCF}(a, b) = \text{HCF}(b, r)

, what happens to the HCF as we keep swapping pairs in the algorithm?

✓

This is the mathematical engine of the algorithm. Each step replaces the problem with an equivalent one — same HCFThe HCF stays the same throughout, but smaller numbersNumbers get smaller until you hit zero.

3. Executing EDA on a concrete example

We have established both the procedure and the reason it preserves HCF.

Now it is time to put it all together:

Execute the full algorithm on an actual pair of numbers, chaining division steps with correct pair-swaps until the remainder hits zerogoal.

📋 Given Info

Let's find HCF(867, 255).

Since $867 > 255$ , start by dividing $867$ by $255$ .

✍️ Question

Find HCF(867, 255) by executing Euclid's Division Algorithm.

Show every step, including the pair swap at each stage.

What is the HCF?

Let's walk through HCF(867, 255) step by step.

Step 1: Divide 867 by 255.

$255 \times 3 = 765$ (since $255 \times 4 = 1020 > 867$ ).

Remainder: $867 - 765 = 102$ .

867 = 255 \times 3 + 102

Euclid's form(Dividend equals divisor times quotient plus remainder)

✍️ MCQ

Choose one

We just found that

867 = 255 \times 3 + 102

. What becomes the new pair for the next division?

✓

Remainder is not 0We keep dividing until remainder is zero, so we continue.

Swap:The heart of the algorithm new pair is (255, 102)new pairDivisor becomes dividend, remainder becomes divisor.

Step 2: Divide 255 by 102.

$102 \times 2 = 204$ (since $102 \times 3 = 306 > 255$ ).

Remainder: $255 - 204 = 51$ .

255 = 102 \times 2 + 51

Format that enables chaining

✍️ MCQ

Choose one

After dividing

255

by

102

and getting remainder

51

, what becomes the new pair for the next division?

✓

Remainder is not 0, so we continue.

SwapOld divisor becomes new dividend: new pair is (102, 51)Repeat until remainder is zero.

Step 3: Divide 102 by 51.

$51 \times 2 = 102$ exactly.

102 = 51 \times 2 + 0

Remainder is 0STOPZero signals you've found the HCF. Stop!

The HCF is the divisor at this final step: 51The divisor in the final step is your answer.

$HCF (867, 255) = 51$

✍️ MCQ

Choose one

In Euclid's Division Algorithm, when do we know we've found the HCF?

✓

✍️ FIB

Fill in the blank

In our calculation of

\text{HCF}(867, 255)

, what was the divisor in the final step when the remainder became

0

?

✓

Notice the chain:

\text{HCF}(867, 255) = \text{HCF}(255, 102) = \text{HCF}(102, 51) = 51

(Each step preserves the original HCF)

Each step replaces the pair with a smaller equivalent one.

At the end, 51 divides 102 exactlyZero remainder signals we're done, so $\text{HCF}(102, 51) = 51$ HCFThe last divisor is the answer.

This is the power of Euclid's Algorithm — we keep reducing until the remainder becomes zeroRepeat until remainder is zero!

✍️ MCQ

Choose one

In the chain

\text{HCF}(867, 255) = \text{HCF}(255, 102) = \text{HCF}(102, 51)

, why does each equality hold?

✓

4. Why the algorithm must terminate

We can execute Euclid's algorithm and we understand why each swap preserves the HCF.

But there's a lurking question:

How do we know the remainders will ever reach zero? Could the algorithm run forever?

We need a mathematical guarantee that it must stop.

📋 Given Info

Here's what we know:

At each step of the algorithm, the pair $(a, b)$ is replaced by $(b, r)$ where $r < b$ .

So the sequence of remainders forms a decreasing chain:
$r_1 > r_2 > r_3 > \cdots$
decreasing

Vertical descending chain showing remainders: r1 > r2 > r3 > ... > 0, with arrows pointing downward between each term, labeled 'decreasing sequence of non-negative integers'

✍️ Question

Think about this 🤔

Why must the algorithm eventually stop?

What mathematical property guarantees that you won't keep dividing forever?

The key is the constraint $0 \leq r < b$ from each division step.

At every step, the remainder is strictly less than the divisorThis constraint forces the algorithm to eventually stop: $r < b$ .

This isn't just a small detail — it's the mathematical guaranteeWithout this, we'd have no proof the method always works that makes the whole algorithm work!

When we swap the pair, $r$ becomes the new divisor. So the divisors at successive steps form a strictly decreasing chainEach step, the new divisor is smaller than the previous one:

b > r_1 > r_2 > r_3 > \ldots

decreasing(You're always moving down, so it can't run forever)

Vertical chain showing b > r1 > r2 > r3 > ... > 0 with arrows pointing downward, emphasizing strictly decreasing positive integers terminating at 0

Look at the diagram on the board — each remainder is smaller than the one before, and they're all non-negative integers.

✍️ MCQ

Choose one

The remainders form a strictly decreasing sequence of non-negative integers:

b > r_1 > r_2 > r_3 > \ldots

Can this sequence continue forever, or must it eventually stop?

✓

Here's the mathematical property: a strictly decreasing sequence of non-negative integers must terminateYou can't have one — you must eventually hit zero.

Why? There are only finitely many non-negative integers less than $b$ . You can't keep going down forever — eventually you must hit 0That's when you stop.

And when the remainder is 0, the algorithm stops!

Every value in this chain is a non-negative integerZero or positive whole numbers (remainders are always $\geq 0$ ). Now here's the mathematical fact: a strictly decreasing sequence of non-negative integers cannot go on foreverYou cannot keep going down forever from a finite start.

Why? Because there are only finitely many non-negative integersLimited count means the chain must end below $b$ . If $b = 255$ , the remainders can be at most $254, 253, 252, \dots$ and they must eventually reach $0$ stops hereThe chain has no choice but to stop here.

✍️ MCQ

Choose one

In Euclid's algorithm, if the current divisor is

b = 100

, what is the maximum number of steps before the algorithm must terminate?

✓

So the algorithm is guaranteed to terminate. You will never get stuck in an infinite loop of divisions.

This is the Well-Ordering Principle at work — every non-empty set of non-negative integers has a smallest element. Since our remainders form a strictly decreasing sequence of non-negative integers, we MUST reach 0keyWhy the algorithm always works, never gets stuck in finitely many steps.

✍️ MCQ

Choose one

The sequence of remainders

102 \to 51 \to 0

is strictly decreasing. What mathematical property guarantees this sequence must eventually reach

0

?

✓

5. Reading off the HCF correctly

The algorithm's logic and termination are now understood. The final detail — seemingly simple but a frequent source of lost marks — is reading the answer correctly from the last equation.

Three numbers appear on the right side of the final step, and only one of them is the HCF.

📋 Given Info

Here is the final step of an EDA computation:

$48 = 8 \times 6 + 0$

The remainder is 0, so the algorithm stops here.

✍️ Question

In the equation $48 = 8 \times 6 + 0$ , there are three numbers on the right side: 8, 6, and 0.

Which one is the HCF, and why are the other two not the answer?

Division equation 48 = 8 × 6 + 0 with arrows pointing to each number, labeling 8 as divisor (highlighted), 6 as quotient, and 0 as remainder

At the terminating step $48 = 8 \times 6 + 0$ , three numbers appear on the right: 8 (the divisor), 6 (the quotient), and 0 (the remainder). Students sometimes grab the wrong one.

The HCF is 8 — the divisor.The divisor at the final step is your answer

Why not 6? The quotientIt counts how many times something fits tells us how many times the divisor fits — it's just a count, not a common factorA count, not a common factor.

Why not 0? The remainder being 0 is the signalsignalZero tells you when to stop that we've found the HCF — it's not the HCF itself. Zero can't be the greatest common divisor of anything!

✍️ MCQ

Choose one

In Euclid's Division Algorithm, when the remainder becomes

0

, the HCF is:

✓

Why not 0? The remainder of 0 is the signalZero signals when to stop dividing that tells you to stop. It means the division was exact. But 0 is not itself the HCF — it's the 'stop sign', not the destinationIt marks the end, not the answer.

Why not 6? That's the quotientShows how many times 8 fits into 48 — it tells you how many times 8 fits into 48. It has nothing to do with the HCFQuotient is irrelevant for finding HCF of the original pair.

✍️ MCQ

Choose one

In the final step

48 = 8 \times 6 + 0

, the HCF is

8

because:

✓

The rule: The HCF is always the divisorThe divisor that gave you zero is your HCF at the step where the remainder first becomes 0When remainder hits zero, stop there.

In the equation $48 = 8 \times 6 + 0$ , the divisor is 8HCFThe divisor at the end holds the HCF. That's the number that divides the previous remainder exactly, and by the chain of HCF-preserving swapsEach division preserves the HCF through the chain, it's the HCF of the original pair too.

✍️ MCQ

Choose one

In the final step of Euclid's Division Algorithm, we get

72 = 24 \times 3 + 0

. What is the HCF?

✓

Euclid's Division Algorithm — Chaining Divisions to Find HCF

1. The three-step algorithm

2. Why HCF(a, b) = HCF(b, r)

3. Executing EDA on a concrete example

4. Why the algorithm must terminate

5. Reading off the HCF correctly