You already know Euclid's Division Lemma:

Given two positive integers $a$ and $b$ , you can always write:

$a = b q + r$

where $0 \leq r < b$ .

That was a fact about a single division.

But here is a surprising question:

What if you do another division?
What if you use the divisor and remainder from the first one?
What if you repeat this over and over?

It turns out that this chain of divisions — each one feeding into the next — is a machine that finds the HCF of the original two numbers.

Feature	The HCF Machine
Reliability	It always stops
Accuracy	It always gives the right answer

In this section, you will see WHY this works.

The central insight is a single equation:

$HCF (a, b) = HCF (b, r)$

Everything else follows from this.

1. Applying EDL once — the first step of the chain

Before you can understand the full algorithm, you need to be comfortable performing a single EDL step on a new pair of numbers.

This is the basic operation that gets repeated in every step of the algorithm.
You already practised this in CL-01, but now the numbers are larger and the context is different.

You are dividing to find the HCF, not just to verify an equation.

📋 Given Info

Here's what you know:

Euclid's Division Lemma states that for positive integers $a$ and $b$ with $a > b$ , we can write:

$a = b q + r where 0 \leq r < b$

To find the $HCF (272, 1032)$ , the first step is to divide the larger number ( $1032$ ) by the smaller one ( $272$ ).

✍️ Question

Your turn ✏️

Divide $1032$ by $272$ and write the result as an EDL equation:

$a = b q + r$

Show how you found the quotient.

Let me walk through the division carefully.

We need to find how many times 272 fits into 1032. The strategy is: estimate by trying multiples of 272.

✍️ Yes/No

Yes or No?

If

272 \times 2 = 544

, is this value still less than

1032

?

$272 \times 1 = 272$ $272 \times 2 = 544$ $272 \times 3 = 816$ $272 \times 4 = 1088$

✍️ MCQ

Choose one

Which is the largest multiple of

272

that is still less than

1032

?

1088 is bigger than 1032, so 272 fits 3 times (not 4). The quotient is 3.

The remainder is what is left over:

$1032 - 816 = 216$

✍️ Subjective

Your turn

Why did we subtract

816

from

1032

to find the remainder?

Type your answer below, or hold Space to speak

So the EDL equation is:

$1032 = 272 \times 3 + 216$

Let us verify: $272 \times 3 = 816$ , and $816 + 216 = 1032$ . ✓ Correct.

✍️ Yes/No

Yes or No?

If we had a remainder of

300

while dividing by

272

, would that be a valid division according to Euclid's Lemma?

Constraint check:

$0 \leq 216 < 272$

✓ Valid.

A Useful Estimation Trick

When working with large numbers in Euclid's Division Algorithm, don't just guess!

Rounding helps: Since 272 is close to 250, and we know that $250 \times 4 = 1000$ , we can immediately narrow down our quotient.

✍️ MCQ

Choose one

If

250 \times 4 = 1000

, which is very close to

1032

, what are the most likely candidates for our actual quotient?

Now we check both possibilities to be sure:

$272 \times 3 = 816$ (This fits!)
$272 \times 4 = 1088$ (Wait, this is too big!)

So, the quotient must be 3.

✍️ Yes/No

Yes or No?

In Euclid's Division Lemma

a = bq + r

, can the value of

bq

be greater than

a

?

This kind of estimation becomes important when you execute EDA on exam problems — you need to find quotients quickly for 3-4 digit numbers.

2. The key insight — HCF(a, b) = HCF(b, r)

You have just written:

$1032 = 272 \times 3 + 216$

This single equation contains the most important idea in the entire algorithm:

The HCF of the original pair $(1032, 272)$
is the same as the HCF of the new pair $(272, 216)$ .

If you understand WHY this is true, you understand the algorithm. If you do not, the algorithm is just a "black box."

From the division we performed:

$1032 = 272 \times 3 + 216$

This means we can also write:

$216 = 1032 - 272 \times 3$

The Claim: $HCF (1032, 272) = HCF (272, 216)$

Let's see if you can figure out why this must be true.

✍️ Question

Think about this carefully 🤔

Suppose a number $d$ divides both $1032$ and $272$ .

Using the equation $1032 = 272 \times 3 + 216$ :

Explain why $d$ must also divide $216$ .
Then explain the reverse: If $d$ divides both $272$ and $216$ , why must $d$ also divide $1032$ ?

This is the heart of the algorithm, so let me explain it carefully with a concrete example.

We have the equation from earlier:

$1032 = 272 \times 3 + 216$

Which means we can also write the remainder as:

$216 = 1032 - 272 \times 3$

The Claim:

$HCF (1032, 272) = HCF (272, 216)$

To prove this, I need to show that the common divisors of the pair $(1032, 272)$ are EXACTLY the same as the common divisors of the pair $(272, 216)$ .

Direction 1: Any common divisor of $(1032, 272)$ is also a common divisor of $(272, 216)$ .

Suppose $d$ divides both $1032$ and $272$ . I need to show $d$ divides $216$ .

Since $216 = 1032 - 272 \times 3$ , and $d$ divides $1032$ (so $1032$ is a multiple of $d$ ), and $d$ divides $272$ (so $272 \times 3$ is a multiple of $d$ ), the difference $1032 - 272 \times 3 = 216$ must also be a multiple of $d$ .

✍️ T/F

True or False?

If a number

d

is a factor of

x

and

y

, is

d

also a factor of their difference

(x - y)

?

Concrete example: $d = 8$ .

Does $8$ divide $1032$ ? Yes: $1032 = 8 \times 129$ .
Does $8$ divide $272$ ? Yes: $272 = 8 \times 34$ .

Then $216 = 1032 - 816 = 8 \times 129 - 8 \times 102 = 8 \times 27$ .

Yes, $8$ divides $216$ .

✍️ Yes/No

Yes or No?

Since

8

divides both

272

and

216

, is

8

a common divisor of

(272, 216)

?

So $d$ also divides $272$ (already given) and $216$ (just proved). Hence $d$ is a common divisor of $(272, 216)$ .

Direction 2: Any common divisor of $(272, 216)$ is also a common divisor of $(1032, 272)$ .

Suppose $d$ divides both $272$ and $216$ . I need to show $d$ divides $1032$ .

✍️ MCQ

Choose one

If

d

is a common divisor of

272

and

216

, which number are we trying to prove it also divides?

Since $1032 = 272 \times 3 + 216$ , and $d$ divides $272$ (so $272 \times 3$ is a multiple of $d$ ), and $d$ divides $216$ , the sum $272 \times 3 + 216 = 1032$ must also be a multiple of $d$ .

✍️ Yes/No

Yes or No?

If

d

is a factor of

x

and

y

, is

d

also a factor of the sum

(x + y)

?

So $d$ divides both $1032$ (just proved) and $272$ (already given). Hence $d$ is a common divisor of $(1032, 272)$ .

Conclusion: The Shared Set of Divisors

The common divisors of $(1032, 272)$ and $(272, 216)$ are the same set.

✍️ Yes/No

Yes or No?

If two sets of numbers contain exactly the same values, must their largest (highest) values also be identical?

Therefore the HIGHEST one must be the same:

$HCF (1032, 272) = HCF (272, 216)$

This is the key identity that makes the algorithm work. At each step, the HCF does not change — only the numbers get smaller.

✍️ MCQ

Choose one

In Euclid's Division Algorithm, what happens to the value of the HCF as we move from one step to the next?

3. Continuing the chain — the next EDA step

You now know that:

HCF(1032, 272) = HCF(272, 216)

The numbers have shrunk, making our task much easier!

What do you do next?

The answer is to repeat the process: divide the larger of the new pair by the smaller.

This is the 'successive division' that gives the algorithm its name. Each remainder becomes the new divisor in the next step.

From the previous steps:

$1032 = 272 \times 3 + 216$

Consequently, $HCF (1032, 272) = HCF (272, 216)$

The next step in our process is to divide 272 by 216.

✍️ Question

Your turn! ✏️

(a) Divide $272$ by $216$ and write the EDL equation.

(b) What is the new pair of numbers for the next step?

(c) Write the updated chain of equal HCFs.

The Rule for Successive Division

At each step of the Euclid's Division Algorithm (EDA), the rule for finding the next pair is:

The OLD DIVISOR becomes the NEW DIVIDEND.
The OLD REMAINDER becomes the NEW DIVISOR.

✍️ MCQ

Choose one

If

a = bq + r

, which two values form the next pair?

Applying the Rule

In our last step, we divided 272 (dividend) by 216 (divisor) and got a remainder of 56.

$Equation: 272 = 216 \times 1 + 56$

✍️ FIB

Fill in the blank

In the next step, the new dividend will be:

So, for the next step:

New dividend = old divisor = 216
New divisor = old remainder = 56

This gives us the new pair: (216, 56).

Let me do the division: $272 \div 216$ .

How many times does 216 fit into 272?

$216 \times 1 = 216$ . That fits ( $216 < 272$ ).
$216 \times 2 = 432$ . That is too big ( $432 > 272$ ).

✍️ MCQ

Choose one

What is the quotient of

272 \div 216

?

So quotient = 1. Remainder = 272 − 216 = 56.

EDL equation: $272 = 216 \times 1 + 56$

✍️ Yes/No

Yes or No?

Is the remainder

56

valid for a divisor of

216

?

Verify: $216 \times 1 + 56 = 216 + 56 = 272$ . ✓ Correct. And $0 \leq 56 < 216$ . ✓ Valid.

The updated chain:

HCF(1032, 272) = HCF(272, 216) = HCF(216, 56)

Notice the pattern:

$(1032, 272) \to (272, 216) \to (216, 56)$

At each step, the first number becomes the second number, and the second number is replaced by the remainder.

✍️ MCQ

Choose one

If

216 = 56 \times 3 + 48

, what is the next pair?

The numbers are shrinking:

$1032 > 272 > 216 > 56$

This shrinking is what guarantees the algorithm will eventually stop.

✍️ Yes/No

Yes or No?

If the remainders were increasing, would the algorithm be guaranteed to stop?

4. Recognising when to stop — remainder equals zero

The algorithm keeps going as long as the remainder is non-zero ( $r \neq 0$ ).

The Stopping Condition

The process ends when the remainder is 0 ( $r = 0$ ).
When that happens, the HCF is the divisor in that final step.

Task: Look at the partially completed chain below to identify the stopping point and the final HCF.

📋 Given Info

Complete EDA Chain for $HCF (1032, 272)$

Following the pattern where the old divisor becomes the new dividend and the old remainder becomes the new divisor:

Step 1: $1032 = 272 \times 3 + 216$
Step 2: $272 = 216 \times 1 + 56$
Step 3: $216 = 56 \times 3 + 48$
Step 4: $56 = 48 \times 1 + 8$
Step 5: $48 = 8 \times 6 + 0$

Result: Since the remainder is now $0$ , the HCF is the last divisor, which is 8.

✍️ Question

Now answer the following:

(a) At which step does the algorithm stop, and why?
(b) What is $HCF (272, 1032)$ ? Be specific: is it the last dividend, the last divisor, or the last remainder?
(c) Write the chain of remainders from Step 1 to Step 5. Are they strictly decreasing? Why does this guarantee the algorithm will always stop?

When do we stop?

Let me clarify the stopping condition and how to read the HCF.

The algorithm proceeds step by step, and at each step you check: is the remainder 0?

✍️ Yes/No

Yes or No?

If the remainder is

5

, do we stop or continue?

Let's trace our progress through the steps:

Step 1: $1032 = 272 \times 3 + 216$ . Remainder = 216. Not 0 — continue.
Step 2: $272 = 216 \times 1 + 56$ . Remainder = 56. Not 0 — continue.
Step 3: $216 = 56 \times 3 + 48$ . Remainder = 48. Not 0 — continue.
Step 4: $56 = 48 \times 1 + 8$ . Remainder = 8. Not 0 — continue.

✍️ MCQ

Choose one

In Step 4 (

56 = 48 \times 1 + 8

), what is the new dividend for Step 5?

Step 5: $48 = 8 \times 6 + 0$ . Remainder = 0. STOP!

The algorithm stops at Step 5 because the remainder reached 0 for the first time.

Now, which number is the HCF? Look at Step 5:

$48 = 8 \times 6 + 0$

The divisor in this step is 8. That is the HCF.

✍️ MCQ

Choose one

In the equation

48 = 8 \times 6 + 0

, which number is the divisor?

⚠️ A common confusion: students sometimes say the HCF is 48 (the dividend in Step 5) or 0 (the remainder in Step 5). Neither is correct.

The HCF is always the DIVISOR in the step where the remainder is 0.

✍️ FIB

Fill in the blank

If a division step in the algorithm is

15 = 5 \times 3 + 0

, what is the HCF?

Another way to think about it: the HCF is the last NON-ZERO remainder.

✍️ MCQ

Choose one

In a sequence of remainders like

56, 48, 8, 0

, which one is the last non-zero remainder?

In Step 4, the remainder was 8 — the last time the remainder was not zero. That same 8 became the divisor in Step 5.

So 'last divisor' and 'last non-zero remainder' refer to the same number.

✍️ Yes/No

Yes or No?

Does the 'last divisor' always represent the same value as the 'last non-zero remainder' in this algorithm?

Why must the algorithm always stop?

Look at the sequence of remainders we found: $216, 56, 48, 8, 0$ .

Each remainder is strictly less than the previous divisor (because EDL requires $r < b$ ). And since each remainder becomes the next divisor, the sequence of numbers we are dealing with keeps shrinking.

✍️ Yes/No

Yes or No?

If the divisor is

48

, can the remainder be

50

?

So the remainders strictly decrease:

$216 > 56 > 48 > 8 > 0$

A decreasing sequence of non-negative whole numbers cannot go on forever — it must reach $0$ eventually. This means the algorithm is guaranteed to terminate (stop).

✍️ Yes/No

Yes or No?

Is it possible for the algorithm to run infinitely without reaching

0

?

5. Why the algorithm gives the CORRECT HCF

You know the algorithm terminates (because remainders decrease to $0$ ) and you know how to read the HCF (the last divisor).

But why is that number actually the HCF?

This is the correctness argument, and it uses the key insight from earlier:

$HCF (a, b) = HCF (b, r)$ at every step.

Here is the EDA chain we've been working with:

$HCF (1032, 272) = HCF (272, 216) = HCF (216, 56) = HCF (56, 48) = HCF (48, 8)$

The final step is: $48 = 8 \times 6 + 0$

✍️ Question

The chain ends with $HCF (48, 8)$ .

(a) Why does $HCF (48, 8) = 8$ ?
(b) Using the chain of equal HCFs, explain why $HCF (1032, 272) = 8$ .
(c) How would you verify that 8 is indeed the HCF of 1032 and 272 — not just a common factor, but the HIGHEST one?

Let me connect all the pieces.

Why HCF(48, 8) = 8:

The equation $48 = 8 \times 6 + 0$ tells us that 8 divides 48 exactly (48 = 8 × 6, no remainder).

✍️ Yes/No

Yes or No?

If

48 = 8 \times 6 + 0

, is

8

a factor of

48

?

So every factor of 8 is also a factor of 48. The factors of 8 are: 1, 2, 4, 8. All of these divide 48 as well:

$48 = 1 \times 48$
$48 = 2 \times 24$
$48 = 4 \times 12$
$48 = 8 \times 6$

✍️ MCQ

Choose one

Among the common factors

\{1, 2, 4, 8\}

, which one is the highest?

The highest of these is 8 itself. So HCF(48, 8) = 8.

Why HCF(1032, 272) = 8

At every step of EDA, we proved that $HCF (a, b) = HCF (b, r)$ . This gives us a chain of equalities.

✍️ Yes/No

Yes or No?

If

\text{HCF}(1032, 272) = \text{HCF}(272, 216)

and

\text{HCF}(272, 216) = \text{HCF}(216, 56)

, is

\text{HCF}(1032, 272)

equal to

\text{HCF}(216, 56)

?

$HCF (1032, 272) = HCF (272, 216) = HCF (216, 56) = HCF (56, 48) = HCF (48, 8) = 8$

The HCF is the same at every link in the chain. Since the chain ends at 8, the original HCF must be 8.

How to verify

Now that we have our answer, the simplest way to check if it's correct is to divide both original numbers by our result, 8.

$1032 \div 8 = 129$ (a whole number, so 8 divides 1032)
$272 \div 8 = 34$ (a whole number, so 8 divides 272)

✍️ MCQ

Choose one

What is the remainder when you divide a number by its factor?

So 8 is definitely a common factor. But is it the HIGHEST common factor?

One way to check: after dividing both numbers by 8, you get the quotients 129 and 34.

Rule: If these two numbers share no common factor (other than 1), then 8 must be the HCF. In other words, they must be co-prime.

✍️ FIB

Fill in the blank

Two numbers that share no common factors other than

1

are called _____.

Let's check the factors of our quotients:

$129 = 3 \times 43$
$34 = 2 \times 17$

These share no prime factors at all! This means: $HCF (129, 34) = 1$

This confirms that 8 is indeed the highest common factor of 1032 and 272.

For exam purposes, simply showing that 8 divides both numbers is usually sufficient verification.

The coprimality check is extra confirmation.

Why Successive Division Finds the HCF

1. Applying EDL once — the first step of the chain

Here's what you know:

Your turn ✏️

A Useful Estimation Trick

2. The key insight — HCF(a, b) = HCF(b, r)

Think about this carefully 🤔

Conclusion: The Shared Set of Divisors

3. Continuing the chain — the next EDA step

What do you do next?

Your turn! ✏️

The Rule for Successive Division

Applying the Rule

4. Recognising when to stop — remainder equals zero

The Stopping Condition

Complete EDA Chain for HCF(1032,272)\text{HCF}(1032, 272)HCF(1032,272)

When do we stop?

Why must the algorithm always stop?

5. Why the algorithm gives the CORRECT HCF

But why is that number actually the HCF?

Why HCF(1032, 272) = 8

How to verify

Complete EDA Chain for $HCF (1032, 272)$