Mathematics · Class 10 · Numbers and Algebraic Structures · Term 1

Euclid's Division Lemma and Algorithm

Students will understand Euclid's Division Lemma and apply the algorithm to find the HCF of two positive integers.

• CBSE Learning Outcomes
• NCERT: Real Numbers - Class 10

About This Topic

Euclid's Division Lemma states that for any two positive integers a and b, with b not zero, there exist unique integers q and r such that a equals b times q plus r, where r is between zero and b minus one. Class 10 students apply this lemma through Euclid's algorithm to find the highest common factor, or HCF, of two numbers by repeated division until the remainder is zero. The last non-zero remainder gives the HCF. This method connects to daily applications, such as simplifying fractions or dividing resources equally.

In the CBSE Real Numbers unit, this topic lays the groundwork for the Fundamental Theorem of Arithmetic and proofs of irrationality. Students practise step-by-step solutions, justify why the algorithm terminates since remainders strictly decrease, and explore its efficiency over trial division. These exercises sharpen logical reasoning and procedural fluency, key for algebra and beyond.

Active learning suits this topic well. When students use physical objects like sticks or beads to model divisions, or compete in algorithm races, they grasp the iterative process intuitively. Group problem-solving reveals patterns in HCFs, while peer teaching reinforces justifications, making abstract number theory concrete and engaging.

Key Questions

1. Explain how Euclid's Division Lemma provides a foundation for number theory.
2. Construct a step-by-step solution to find the HCF of two numbers using Euclid's algorithm.
3. Justify the termination of Euclid's algorithm in finding the HCF.

Learning Objectives

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

Before You Start

Basic Division and Remainders

Why: Students need to be comfortable with the concept of division, identifying the quotient and remainder, before applying the lemma.

Factors and Multiples

Why: Understanding factors is foundational to grasping the concept of the Highest Common Factor (HCF).

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.

Watch Out for These Misconceptions

Common Misconception

HCF is found only by listing all factors.

What to Teach Instead

Euclid's algorithm uses repeated division for efficiency, avoiding exhaustive lists. Hands-on races show it works faster for large numbers. Peer comparisons during activities help students see why division lemma underpins this method.

Common Misconception

The algorithm never ends for some numbers.

What to Teach Instead

Remainders decrease strictly and become zero since they are non-negative integers less than the previous divisor. Group puzzles demonstrate termination quickly. Discussing patterns in class builds confidence in the proof.

Common Misconception

Euclid's lemma applies only when one number divides the other exactly.

What to Teach Instead

The lemma holds for any remainder, including non-zero. Manipulative demos let students model non-exact divisions. Sharing observations corrects this, linking to HCF as the last non-zero remainder.

Active Learning Ideas

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.

30 min·Pairs

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.

45 min·Small Groups

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.

35 min·Whole Class

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.

20 min·Individual

Real-World Connections

• Choreographers use the HCF to divide dancers into equal groups for formations on stage, ensuring balanced visual patterns.
• Logistics managers in shipping companies might use HCF principles to determine the largest possible container size that can perfectly fit multiple smaller items, minimizing wasted space.
• Gardeners can apply HCF to determine the largest possible equal spacing for planting different types of saplings in a rectangular plot, ensuring uniform distribution.

Assessment Ideas

Quick Check

Present students with two numbers, say 135 and 225. Ask them to write down the first step of applying Euclid's Division Lemma: '135 = 225 * q + r' or '225 = 135 * q + r'. Then, ask them to identify the divisor and remainder in their chosen equation.

Exit Ticket

On a slip of paper, ask students to calculate the HCF of 48 and 18 using Euclid's algorithm. They must show at least two steps. Also, ask them to write one sentence explaining why the remainder must be smaller than the divisor.

Discussion Prompt

Pose the question: 'Imagine you have 72 sweets and want to divide them equally among a group of friends. What are the possible numbers of friends you could have, based on finding factors? How does Euclid's algorithm help find the largest possible equal group size if you also had 108 biscuits?'

Frequently Asked Questions

How to explain Euclid's division lemma to class 10 students?

Start with the statement: for integers a and b (b > 0), a = bq + r, 0 ≤ r < b. Use everyday examples like dividing 23 sweets among 5 children: 23 = 5*4 + 3. Practise with visuals, then move to algorithm steps. This builds from concrete to abstract understanding.

What is Euclid's algorithm for finding HCF?

Divide larger by smaller number, replace with divisor and remainder, repeat until remainder is zero. HCF is the last non-zero remainder. For 196 and 382: 382=196*1+186, 196=186*1+10, etc., HCF=2. Students justify termination as remainders decrease.

How can active learning help teach Euclid's algorithm?

Activities like pair races or manipulative divisions make the iterative process visible and fun. Students physically group objects to see q and r, track decreasing remainders in groups, and explain steps to peers. This shifts from rote memorisation to deep comprehension and quick application.

Why does Euclid's algorithm always terminate?

Each step produces a smaller positive remainder, forming a decreasing sequence of non-negative integers, which must end at zero. No infinite descent possible. Class discussions after hands-on trials reinforce this logical proof, preparing students for number theory proofs.