Euclid's Division Lemma and Algorithm

Active learning works well for Euclid's Division Lemma because students often struggle with abstract division steps until they see the process unfold concretely. When learners physically divide numbers or race to find remainders, they bridge the gap between theory and practice, making the algorithm feel like a practical tool rather than a formula to memorise.

• Class 10
• Mathematics
• 4 activities
• 20 min–45 min

Learning Objectives

1. Calculate the HCF of two positive integers using Euclid's Division Algorithm.
2. Explain the mathematical principle behind Euclid's Division Lemma and its role in number theory.
3. Justify the termination condition of Euclid's Division Algorithm by analyzing the decreasing sequence of remainders.
4. Apply Euclid's Division Lemma to solve problems involving the distribution of items into equal groups.

Collaborative Problem-Solving

⏱ 30 min·Pairs

Pairs: Algorithm Race

Pair students and give each pair two numbers, such as 867 and 255. They apply Euclid's algorithm step-by-step on mini-whiteboards, racing to find the HCF first. The winning pair explains their steps to the class. Switch numbers for multiple rounds.

Prepare & details

Explain how Euclid's Division Lemma provides a foundation for number theory.

Facilitation Tip: During Algorithm Race, circulate and listen for pairs to verbalise each step aloud, ensuring they connect 'a = bq + r' with actual numbers.

Setup: Flexible seating that allows clusters of 5-6 students; desks can be grouped in rows of three facing each other if fixed furniture limits rearrangement. Wall or board space for displaying group norm charts and the session agenda is helpful.

Materials: Printed problem brief cards (one per group), Role cards: Facilitator, Questioner, Recorder, Devil's Advocate, Communicator, Group norm chart (printable poster format), Individual reflection sheet and exit ticket, Timer visible to the class (board countdown or projected timer)

• Apply
• Analyze
• Evaluate
• Create
• Relationship Skills
• Decision-Making
• Self-Management

Collaborative Problem-Solving

⏱ 45 min·Small Groups

Small Groups: HCF Puzzle Stations

Set up four stations with pairs of numbers and real-life contexts, like dividing 48 kg of rice and 18 kg equally. Groups rotate, apply the algorithm, and record steps on charts. Discuss solutions as a class at the end.

Prepare & details

Construct a step-by-step solution to find the HCF of two numbers using Euclid's algorithm.

Facilitation Tip: In HCF Puzzle Stations, provide calculators only after students attempt manual divisions to reinforce the logic behind each step.

Setup: Flexible seating that allows clusters of 5-6 students; desks can be grouped in rows of three facing each other if fixed furniture limits rearrangement. Wall or board space for displaying group norm charts and the session agenda is helpful.

Materials: Printed problem brief cards (one per group), Role cards: Facilitator, Questioner, Recorder, Devil's Advocate, Communicator, Group norm chart (printable poster format), Individual reflection sheet and exit ticket, Timer visible to the class (board countdown or projected timer)

• Apply
• Analyze
• Evaluate
• Create
• Relationship Skills
• Decision-Making
• Self-Management

Collaborative Problem-Solving

⏱ 35 min·Whole Class

Whole Class: Division Lemma Manipulatives

Distribute straws or blocks to represent dividends. Demonstrate a equals bq plus r with physical grouping. Students replicate with given numbers, then share how remainders decrease. Collect materials for verification.

Prepare & details

Justify the termination of Euclid's algorithm in finding the HCF.

Facilitation Tip: With Division Lemma Manipulatives, ask students to model both exact and non-exact divisions before generalising the lemma.

Setup: Flexible seating that allows clusters of 5-6 students; desks can be grouped in rows of three facing each other if fixed furniture limits rearrangement. Wall or board space for displaying group norm charts and the session agenda is helpful.

Materials: Printed problem brief cards (one per group), Role cards: Facilitator, Questioner, Recorder, Devil's Advocate, Communicator, Group norm chart (printable poster format), Individual reflection sheet and exit ticket, Timer visible to the class (board countdown or projected timer)

• Apply
• Analyze
• Evaluate
• Create
• Relationship Skills
• Decision-Making
• Self-Management

Collaborative Problem-Solving

⏱ 20 min·Individual

Individual: Step-by-Step HCF Journal

Provide worksheets with 5-6 number pairs. Students write the lemma, apply the algorithm, and justify termination. They colour-code quotients, dividends, and remainders for clarity. Review journals next class.

Prepare & details

Explain how Euclid's Division Lemma provides a foundation for number theory.

Facilitation Tip: For Step-by-Step HCF Journal, model the first entry on the board with think-aloud narration to set clear expectations.

Setup: Flexible seating that allows clusters of 5-6 students; desks can be grouped in rows of three facing each other if fixed furniture limits rearrangement. Wall or board space for displaying group norm charts and the session agenda is helpful.

Materials: Printed problem brief cards (one per group), Role cards: Facilitator, Questioner, Recorder, Devil's Advocate, Communicator, Group norm chart (printable poster format), Individual reflection sheet and exit ticket, Timer visible to the class (board countdown or projected timer)

• Apply
• Analyze
• Evaluate
• Create
• Relationship Skills
• Decision-Making
• Self-Management

Teaching This Topic

Experienced teachers start by letting students discover the division lemma through tangible examples, like dividing marbles or sweets, before formalising it. Avoid rushing to the proof; instead, build confidence with repeated successful applications. Research shows that students grasp the shrinking remainder concept better when they physically reduce numbers in each step, so avoid abstract explanations until they see the pattern themselves.

What to Expect

Successful learning shows students confidently applying Euclid's algorithm to find HCF, explaining why remainders shrink with each step, and connecting the method to real-life situations like sharing items. They should also articulate the division lemma in their own words and correct peers' misconceptions during group work.

Watch Out for These Misconceptions

Common Misconception

During Algorithm Race, watch for pairs who skip steps because they assume the largest number must divide the smaller one.

What to Teach Instead

Ask them to model the first division step with counters or paper strips to see that 5 = 3 × 1 + 2 is valid, even though 3 does not divide 5 exactly.

Common Misconception

During HCF Puzzle Stations, watch for students who stop when they find a remainder of 1, assuming it is the HCF for any pair.

What to Teach Instead

Have them verify with a calculator that an HCF of 1 means the numbers are co-prime, not that 1 is always the answer.

Common Misconception

During Division Lemma Manipulatives, watch for students who believe the lemma only works when the remainder is zero.

What to Teach Instead

Prompt them to rearrange the equation (e.g., 7 = 3 × 2 + 1) and show how the remainder 1 fits within the lemma’s range (0 ≤ r < b).

Assessment Ideas

Quick Check

After Algorithm Race, write two numbers on the board (e.g., 376 and 24) and ask students to write the first step of Euclid’s Division Lemma on mini-whiteboards, identifying q and r in '376 = 24q + r'.

Exit Ticket

During Step-by-Step HCF Journal, collect journals to check that students show at least two correct steps for 48 and 18, and include a sentence explaining why remainders must be smaller than divisors.

Discussion Prompt

After HCF Puzzle Stations, ask students to discuss: 'How would you divide 72 chocolates and 108 toffees among the maximum number of friends equally? Share your steps with a partner and explain your answer.'

Extensions & Scaffolding

• Challenge: Ask students to find the HCF of three numbers, say 120, 180, and 252, using Euclid’s algorithm. They must explain why the algorithm still applies.
• Scaffolding: Provide a partially completed HCF calculation for 105 and 90 (e.g., 105 = 90 × 1 + 15, 90 = 15 × 6 + 0) and ask them to finish it.
• Deeper exploration: Explore how Euclid’s algorithm connects to the extended Euclidean algorithm for finding integers x and y such that ax + by = HCF(a,b).

Key Vocabulary

Euclid's Division Lemma	For any two positive integers a and b, there exist unique integers q (quotient) and r (remainder) such that a = bq + r, where 0 ≤ r < b.
Euclid's Division Algorithm	A step-by-step procedure based on Euclid's Division Lemma to find the Highest Common Factor (HCF) of two positive integers.
Quotient	The result obtained when one number is divided by another. In a = bq + r, q is the quotient.
Remainder	The amount left over after division. In a = bq + r, r is the remainder, and it must be less than the divisor b.
Highest Common Factor (HCF)	The largest positive integer that divides two or more integers without leaving a remainder.