You now understand WHY Euclid's Division Algorithm works. The next challenge is executing it smoothly and accurately.

EDA is a procedure, and procedures require practice.

Each step involves a division of multi-digit numbers, and one arithmetic error in any step corrupts every step that follows.

In this section, you will:

Work through examples of increasing difficulty
Develop strategies for quick estimation of quotients

You will also encounter two important special cases:

When the algorithm terminates in a single step
When you accidentally start by dividing the smaller number by the larger

By the end, you should be able to execute EDA on any pair of numbers the CBSE board exam can throw at you, with confidence in both your speed and your accuracy.

Target	Goal
Speed	Quick estimation
Accuracy	Zero arithmetic errors

1. Full EDA execution — a three-step chain

Building EDA Fluency 🔢

The best way to build fluency with Euclid's Division Algorithm (EDA) is to execute it from start to finish on a fresh problem.

Find the HCF of the given pair of numbers.
Write every step as a numbered EDL equation ( $a = b q + r$ ).

This chain will have three steps, which is typical of CBSE board exam questions.

✍️ Question

Your Turn ✏️

Execute Euclid's Division Algorithm (EDA) on the pair:

(1651, 2032)

Number your steps clearly.
Write each step as an EDL equation ( $a = b q + r$ ).
State the HCF clearly at the end.

Let me work through this step by step.

We need to find the Highest Common Factor, or $H C F (1651, 2032)$ .

✍️ MCQ

Choose one

In the lemma

a = bq + r

, what is the standard rule for choosing '

a

'?

Since $2032 > 1651$ , we divide $2032$ by $1651$ .

✍️ MCQ

Choose one

Estimate the quotient for

2032 \div 1651

.

Step (i): 2032 ÷ 1651

How many times does 1651 fit into 2032?

$1651 \times 1 = 1651$ (fits, since $1651 < 2032$ )
$1651 \times 2 = 3302$ (too big, since $3302 > 2032$ )

✍️ FIB

Fill in the blank

What is the remainder for

2032 - 1651

?

So quotient = 1. Remainder = $2032 - 1651 = 381$ .

Equation: $2032 = 1651 \times 1 + 381$

Verify: $1651 + 381 = 2032$ . ✓ Correct.

✍️ MCQ

Choose one

Which numbers become the new pair for the next step?

Remainder 381 is not 0, so continue. New pair: (1651, 381).

Step (ii): $1651 \div 381$

Following the algorithm, our previous divisor (1651) now becomes the dividend, and our previous remainder (381) becomes the new divisor.

✍️ MCQ

Choose one

Estimate the quotient: How many times does

381

fit into

1651

?

How many times does 381 fit into 1651?

$381 \times 4 = 1524$ (fits, since $1524 < 1651$ )
$381 \times 5 = 1905$ (too big, since $1905 > 1651$ )

Mental Math Tip: Break down $381 \times 4$ . $380 \times 4 = 1520$ $1 \times 4 = 4$ Total = 1524

✍️ FIB

Fill in the blank

What is the remainder:

1651 - 1524

?

So, Quotient = 4 and Remainder = 127.

Equation: $1651 = 381 \times 4 + 127$

Verify: $1524 + 127 = 1651$ . ✅ Correct.

Since the remainder 127 is not 0, we must continue.

New pair for Step (iii): (381, 127)

Step (iii): $381 \div 127$

Earlier, we found our new divisor is $381$ and our remainder is $127$ . Now, we see how many times $127$ fits into $381$ .

✍️ MCQ

Choose one

Estimate the quotient for

381 \div 127

:

$127 \times 3 = 381$ . Exactly!

So, quotient = 3 and remainder = 0.

Equation: $381 = 127 \times 3 + 0$

Since the remainder is 0, we STOP here.

✍️ MCQ

Choose one

The HCF is the divisor at the stage where the remainder becomes zero. What is the HCF here?

The Final Result

HCF(1651, 2032) = 127

As we just saw, 127 was the last divisor in the step where the remainder finally reached zero.

Verification

It is always good practice to verify our result:

$1651 \div 127 = 13$ (integer)
$2032 \div 127 = 16$ (integer)

Both divide evenly. ✓ Confirmed.

✍️ Yes/No

Yes or No?

Does the fact that both original numbers divide evenly by

127

confirm that

127

is a common factor?

✍️ MCQ

Choose one

If we had found that

1651 \div 127

resulted in a decimal like

13.5

, what would that tell us?

2. One-step termination — when one number divides the other

Not every EDA chain requires multiple steps. Sometimes the smaller number divides the larger one exactly, and the algorithm terminates immediately.

This is an important case to recognise because:

It frequently appears on exams
It reinforces the stopping condition (remainder = $0$ )

In such cases, the smaller of the two numbers is itself the HCF.

✍️ Question

Find HCF(196, 38220) using Euclid's Division Algorithm (EDA).

Execute EDA on the pair $(196, 38220)$ .
How many steps does it take?
What is the HCF?

A Surprising Single-Step Case

This is a special case that catches students off guard — they expect the algorithm to always require multiple steps.

Since $38220 > 196$ , we divide $38220$ by $196$ .

✍️ MCQ

Choose one

If the remainder is zero in the first division, how many steps does the algorithm take?

Estimation Strategy

To find the quotient, let us estimate:

$196$ is close to $200$ .
$200 \times 190 = 38000$ , which is close to $38220$ .

So the quotient is around $195$ .

✍️ MCQ

Choose one

Is

196 \times 190

greater than or less than

38000

?

Verifying the Calculation

Let me verify: $196 \times 195$ .

Instead of long multiplication, let's break it down:

$196 \times 200 = 39200$
$196 \times 5 = 980$

✍️ FIB

Fill in the blank

What is

39200 - 980

?

$39200 - 980 = 38220$

So, $196 \times 195 = 38220$ exactly.

The remainder is $0$ .

Here is our result in the form of the Euclid's Division Lemma (EDL) equation:

$38220 = 196 \times 195 + 0$

Since the remainder is $0$ right away, the algorithm stops here. The HCF is the divisor: $196$ .

$HCF (196, 38220) = 196$

✍️ MCQ

Choose one

In the equation

a = bq + r

, if

r = 0

, what is

\text{HCF}(a, b)

?

This makes sense: $196$ divides $38220$ exactly ( $38220 \div 196 = 195$ ), so $196$ is a factor of $38220$ . And the HCF of any number with one of its factors is that factor itself.

✍️ FIB

Fill in the blank

What is

\text{HCF}(15, 45)

?

Exam Tip: Single-Step Solutions

On the exam, do not be surprised if the algorithm terminates in one step.

Just write the single equation, note that the remainder is $0$ , and state the HCF. You are done.

3. Starting order — what happens if you divide smaller by larger?

Quick scenario to think about 🤔

The textbook says to start Euclid's Division Algorithm with $a > b$ — divide the larger number by the smaller one.

But what if you accidentally mix up the order? Let's explore what happens — this reveals a nice self-correcting property of the algorithm.

📋 Given Info

Here's the situation:

A student wants to find $HCF (45, 120)$ .

Expected Step: Divide $120$ by $45$ (larger $\div$ smaller).
Accidental Step: They divide $45$ by $120$ (smaller $\div$ larger).

Will the algorithm still work, or will it break down?

✍️ Question

Your turn to investigate ✏️

a) Write the Euclid's Division Lemma equation for $45$ divided by $120$ .

What are the quotient ( $q$ ) and remainder ( $r$ )?

b) Based on your result, what pair of numbers would the student use for the next step of the algorithm?

c) Is the algorithm now on the correct track? What is the lesson here?

What happens when you divide a smaller number by a larger number?

Let us try a specific example to see how the math behaves: divide 45 by 120.

✍️ MCQ

Choose one

How many times does

120

fit into

45

?

Since 120 is bigger than 45, it fits Zero times.

So, the quotient is 0.

To find the remainder: Remainder = $45 - (120 \times 0)$ Remainder = $45 - 0 = 45$

✍️ FIB

Fill in the blank

In the equation

a = bq + r

, if

a = 45

and

b = 120

, what is the value of

r

?

Putting it all together into the EDL equation:

$45 = 120 \times 0 + 45$

Notice that in the next step of the algorithm, the numbers will effectively 'swap' places.

Checking Validity

Let us check: is this a valid EDL equation?

The constraint says $0 \leq r < b$ .

✍️ Yes/No

Yes or No?

Is the remainder

r = 45

valid for the divisor

b = 120

?

i.e., $0 \leq 45 < 120$ . Yes, this is valid.

So this is a perfectly legal step — it just does not make progress toward finding the HCF.

✍️ MCQ

Choose one

What is the next division step?

Now, for the next step: our old divisor ( $120$ ) becomes the new dividend, and our old remainder ( $45$ ) becomes the new divisor.

This gives us the next pair: (120, 45).

✍️ MCQ

Choose one

What is the next division step?

But notice something— $(120, 45)$ is the pair we should have started with in the first place!

So the student's first step was effectively 'wasted'—it didn't perform any actual division, it just swapped the numbers into the correct order ( $a > b$ ) for us.

✍️ Yes/No

Yes or No?

Does starting with the smaller number first change the final HCF result?

As we discussed, our first step effectively swapped the numbers. Now, we continue correctly with the larger number as the dividend:

$120 = 45 \times 2 + 30$

✍️ MCQ

Choose one

Which pair will be used in the next division step?

Exactly! We move forward with $45$ and $30$ , then keep going until the remainder is zero:

$45 = 30 \times 1 + 15$

$30 = 15 \times 2 + 0$

HCF(45, 120) = 15.

✍️ FIB

Fill in the blank

The HCF of

45

and

120

is ___

The algorithm produced the correct answer — it just took 4 steps instead of 3.

Key Takeaway: The self-correcting property is nice to know (you will never get a wrong answer from a wrong starting order), but starting with the larger number is better because it saves a step.

4. Verifying each EDA step to catch arithmetic errors

Catching Errors in EDA 🔍

Arithmetic errors are the most common source of wrong answers in Euclid's Division Algorithm problems.

Since each step feeds into the next, one error cascades through the entire chain.
A mistake in the first remainder will make every subsequent step incorrect.

The Antidote: Verify each equation immediately after writing it.

📋 Given Info

A student is finding HCF(4052, 420) and writes:

Step 1: $4052 = 420 \times 9 + 272$
Step 2: $420 = 272 \times 1 + 158$
Step 3: $272 = 158 \times 1 + 114$

(continues from here...)

Let's check if these steps are correct before proceeding.

✍️ Question

Your task: 🧮

(a) Verify Step 1 by computing $420 \times 9 + 272$ . Is it correct?

(b) Verify Step 2 by computing $272 \times 1 + 158$ . Is it correct?

(c) If any step is wrong, find the correct equation for that step.

Let me show you the verification process for each step.

The verification rule:

For any equation $a = b \times q + r$ , check that $b \times q + r$ actually equals $a$ .

✍️ Yes/No

Yes or No?

Does

9 \times 5 + 2 = 47

?

Why verify?

Because the HCF is the last non-zero divisor, one wrong remainder in step 1 will lead to the wrong HCF in the final step.

Remember our earlier example: $1651 = 381 \times 4 + 127$

If we check: $381 \times 4 + 127 = 1524 + 127 = 1651$ . Matches! ✓

Step 1: $4052 = 420 \times 9 + 272$

✍️ MCQ

Choose one

What is

420 \times 9

?

Compute $420 \times 9$ :

$400 \times 9 = 3600$
$20 \times 9 = 180$
Total $= 3780$

✍️ Yes/No

Yes or No?

Does

3780 + 272

equal

4052

?

Now add the remainder: $3780 + 272 = 4052$ .

Does this equal the dividend? $4052 = 4052$ . YES. Step 1 is correct. ✓

Step 2: Verification

Step 2: $420 = 272 \times 1 + 158$

✍️ FIB

Fill in the blank

Calculate

272 + 158

.

Compute $272 \times 1$ : $272$ .

Now add the remainder: $272 + 158 = 430$ .

✍️ Yes/No

Yes or No?

Does

430

equal the dividend

420

?

Does this equal the dividend? $430$ vs $420$ .

NO! $430 \neq 420$ .

Step 2 is WRONG. ✗

The error is in the remainder. The correct computation is:

$r = 420 - (272 \times 1) = 420 - 272 = 148$

✍️ MCQ

Choose one

Which is the correct equation for Step 2?

So the correct Step 2 is:

$420 = 272 \times 1 + 148$

Verify: $272 + 148 = 420$ . ✅ Correct.

The student wrote $158$ instead of $148$ — a simple subtraction error ( $420 - 272 = 148$ , not $158$ ).

The Danger: This one error would corrupt every subsequent step and eventually give the wrong HCF.

The 10-Second Rule

After writing each EDA equation, take 10 seconds to verify it.

The Verification Step:

Multiply the divisor by the quotient.
Add the remainder.
Check if the total equals the dividend.

✍️ MCQ

Choose one

To verify the step

420 = 272 \times 1 + 148

, which calculation would you perform?

This quick check catches errors before they cascade.

As we saw in the previous example, one small arithmetic mistake in the remainder can ruin the entire process. Verification keeps your solution on the right track.

Exam Strategy

On the exam, you do not need to write out the verification — just do it mentally or in the margin.

Important: Do it for every step, not just the hard ones!

✍️ Yes/No

Yes or No?

Is it mandatory to show the verification calculations as part of your final answer in the exam?

5. Complete EDA on a fresh problem with verification

Time to put everything together!

You have learned why Euclid's Division Algorithm works and how to verify your steps. Now, let's see if you can execute the full algorithm on a problem you haven't seen before.

This is exactly what you would face on a board exam:

Execute the full algorithm step-by-step.
Verify each equation using the "10-second check."
State the final HCF clearly.

✍️ Question

Find HCF(306, 657) using Euclid's Division Algorithm

Execute the full EDA.

Write each step as a numbered EDL equation ( $a = b q + r$ ).
Show your work clearly for each division.
State the final HCF once the remainder reaches zero.

Starting the HCF Journey

Let me walk through this process carefully, verifying every step as we go.

Our goal is to find HCF(306, 657).

✍️ MCQ

Choose one

Which number should be the dividend (

a

)?

That's right! Since $657 > 306$ , we follow the rule and divide the larger number by the smaller one.

So, our first step is to divide $657$ by $306$ .

✍️ MCQ

Choose one

Estimate the quotient:

657 \div 306

(i) 657 ÷ 306:

$306 \times 2 = 612$ (fits, since $612 < 657$ )

$306 \times 3 = 918$ (too big, since $918 > 657$ )

✍️ FIB

Fill in the blank

Calculate the remainder:

657 - 612

Quotient = 2. Remainder = $657 - 612 = 45$ .

Equation: $657 = 306 \times 2 + 45$ .

Verify: $612 + 45 = 657$ . ✓ Correct.

✍️ MCQ

Choose one

What is the next pair for the EDA?

Remainder 45 is not 0. Next pair: (306, 45).

(ii) 306 ÷ 45

Let's test our estimates for the division:

$45 \times 6 = 270$ (fits, since $270 < 306$ )
$45 \times 7 = 315$ (too big, since $315 > 306$ )

✍️ MCQ

Choose one

What is the quotient for

306 \div 45

?

Quotient = 6.

Remainder = $306 - 270 = 36$ .

The Equation: $306 = 45 \times 6 + 36$

✍️ Yes/No

Yes or No?

Does

45 \times 6 + 36

equal

306

?

Verify: $270 + 36 = 306$ . ✓ Correct.

Since the remainder 36 is not 0, we must continue.

Next pair: (45, 36).

Step (iii): $45 \div 36$

As we just decided, our new pair is $45$ and $36$ . Let's find out how many times $36$ goes into $45$ .

$36 \times 1 = 36$ (fits, since $36 < 45$ )
$36 \times 2 = 72$ (too big, since $72 > 45$ )

✍️ FIB

Fill in the blank

What is the remainder for

45 \div 36

?

Quotient = 1. Remainder = $45 - 36 = 9$ .

The Equation: $45 = 36 \times 1 + 9$

Verify: $36 + 9 = 45$ . ✓ Correct.

✍️ MCQ

Choose one

Identify the next pair for the EDA:

Remainder 9 is not 0.

Next pair: (36, 9).

Step (iv): The Final Division

(iv) 36 ÷ 9:

$9 \times 4 = 36$ . Exactly!

✍️ MCQ

Choose one

If

9 \times 4 = 36

, what is the remainder?

Quotient = 4. Remainder = 0.

Equation: $36 = 9 \times 4 + 0$

Verify: $36 + 0 = 36$ . ✓ Correct.

✍️ MCQ

Choose one

What is the next step when the remainder is

0

?

Remainder is 0. STOP.

HCF(306, 657) = 9.

Final verification: Does 9 divide both original numbers?

✍️ FIB

Fill in the blank

What is

306 \div 9

?

$306 \div 9 = 34$ (integer). ✓ Yes.

✍️ MCQ

Choose one

What is

657 \div 9

?

$657 \div 9 = 73$ (integer). ✓ Yes.

Confirmed: 9 is the HCF.

Executing Euclid's Division Algorithm on Different Number Pairs

1. Full EDA execution — a three-step chain

Building EDA Fluency 🔢

Your Turn ✏️

Step (ii): 1651÷3811651 \div 3811651÷381

Step (iii): 381÷127381 \div 127381÷127

The Final Result

Verification

2. One-step termination — when one number divides the other

A Surprising Single-Step Case

Estimation Strategy

Verifying the Calculation

Exam Tip: Single-Step Solutions

3. Starting order — what happens if you divide smaller by larger?

Quick scenario to think about 🤔

Here's the situation:

Your turn to investigate ✏️

What happens when you divide a smaller number by a larger number?

Checking Validity

4. Verifying each EDA step to catch arithmetic errors

Catching Errors in EDA 🔍

Your task: 🧮

The verification rule:

Why verify?

Step 2: Verification

The 10-Second Rule

Exam Strategy

5. Complete EDA on a fresh problem with verification

Time to put everything together!

Find HCF(306, 657) using Euclid's Division Algorithm

Starting the HCF Journey

(ii) 306 ÷ 45

Step (iii): 45÷3645 \div 3645÷36

Step (iv): The Final Division

Final verification: Does 9 divide both original numbers?

Step (ii): $1651 \div 381$

Step (iii): $381 \div 127$

Step (iii): $45 \div 36$