Welcome! Today we're looking at The Formal Statement of Euclid's Division Lemma — the precise mathematical language behind something you've been doing all along.

You have been writing division as an equation and applying the remainder constraint.

Now it is time to give this result its proper mathematical name and state it with the precision that mathematics demands.

Euclid's Division Lemma is over two thousand years old, yet every word in its statement earns its place:

If you...	Then...
Drop 'uniquecritical'	The statement becomes trivially true for infinitely many pairs
Change a single inequality sign	It breaks for exact divisions

Precision in mathematical language is not pedantry — it is the difference between a statement that proves things and one that proves nothing.

Mastering this precise statement is essential because it is the foundation for:

The division algorithm that finds HCF
Case-analysis proofs about the forms integers can take

1. Complete formal statement of EDL

We've been working with division and writing it as an equation. Now it's time to give this result its proper mathematical name and state it with the precision that mathematics demands.

We are trying to capture everything we know about division:

The equation $a = bq + r$
The constraint $0 \leq r < b$
The uniqueness of the pair $(q, r)$

...all in one precise mathematical statementgoal.

The challenge is to include every necessary word without leaving any gaps that would weaken the result.

Here's what you've learned so far:

For any division of $a$ by $b$ , the equation $a = bq + r$ holds
The constraint $0 \leq r < b$ must be satisfied
Exactly one pair $(q, r)$ satisfies this

This fact has a formal name: Euclid's Division Lemma.

✍️ Question

Your turn ✍️

State Euclid's Division Lemma in full.

Make sure you include every necessary part:

What kind of numbers are involved?
What is guaranteed to exist?
What conditions must hold?

Here is the precise statement:

Euclid's Division LemmaThe formal name for division with quotient and remainder: For any two given positive integers $a$ and $b$ , there exist uniqueOnly ONE possible pair of q and r works whole numbers $q$ and $r$ such that $a = bq + r$ What happens when you divide, where $0 \leq r < b$ The remainder can never be negative or reach the divisor.

Let's break down the key parts:

Input: Two positive integers $a$ and $b$
Guarantee: There exist unique values $q$ (quotient) and $r$ (remainder)
Equation: $a = bq + r$
Constraint: $0 \leq r < b$ key constraint (remainder is non-negative and strictly less than divisor)

✍️ MCQ

Choose one

In Euclid's Division Lemma, what is the constraint on the remainder

r

?

✓

In simpler words: When you divide any positive integer by another, you always get exactly one quotient and one remainderExactly one answer guaranteed — and the remainder is always between 0 and one less than the divisorCan be zero but never equals the divisor.

✍️ T/F

True or False?

Euclid's Division Lemma guarantees that the quotient and remainder are unique.

✓

Every word earns its place:

'positive integers $a$ and $b$ ' — the lemma applies to all positive integers, no exceptions. Whether $a$ is 7 or 7 million, whether $b$ is 2 or 2 billion — the lemma works.
'there existFor ANY positive integers, you WILL find q and r' — for any $a$ and $b$ , such $q$ and $r$ can always be found. This is a guaranteeYou will never fail to find them — you will never fail to find them.

'uniqueThis is what makes the statement powerful' — there is exactly one pair $(q, r)$ keyThe constraint forces exactly one pair that works. This is the power of the statement. Without 'unique', we'd just be saying some $q$ and $r$ exist, but infinitely many pairsWithout uniqueness, many solutions exist could satisfy $a = b q + r$ if we removed the constraint.
'whole numbers $q$ and $r$ ' — $q$ and $r$ are non-negative integers (0, 1, 2, 3, ...).

✍️ MCQ

Choose one

Why is the word 'unique' so important in Euclid's Division Lemma?

✓

' $a = b q + r$ ' — the division equation. This is the relationship that ties everything together.
' $0 \leq r < b$ Two key things about this constraint' — the constraint. The lower bound allows $r = 0$ Zero remainder means exact division (exact division is perfectly valid — like $12 = 3 \times 4 + 0$ ). The upper bound is strictIf r equaled b, you'd bump up q by 1 — $r$ cannot equal $b$ , because if it did, we could increase $q$ by 1 and reduce $r$ by $b$ .

2. Spotting errors in imprecise EDL statements

Now that we have the complete statement of Euclid's Division Lemma, we need to understand why every word matters.

The way to test that understanding is to look at imprecise versions and figure out exactly which piece is broken and what damage it causes.

📋 Given Info

Here are two statements a student might write:

(A) For positive integers $a$ and $b$ , $a = b q + r$ where $0 < r < b$ .

(B) For positive integers $a$ and $b$ , $a = b q + r$ where $0 \leq r \leq b$ .

✍️ Question

Both of these have problems. 🔍

Identify what is wrong with each one, and for each error, give a concrete example showing why it matters.

Let's look at each statement carefully.

Statement (A): 'For positive integers a and b, a = bq + r where 0 < r < bThe remainder can be zero when division is exact.'

✍️ FIB

Fill in the blank

In Statement (A), the condition is

0 < r < b

. What value of

r

is being excluded by writing

0 < r

instead of

0 \leq r

?

✓

Problem 1: The constraint says $0 < r$ errorZero is a valid remainder when one number divides another exactly, meaning $r$ must be strictly positive. But the remainder can be 0 — when one number divides the other exactly.

For instance, $42 = 14 \times 3 + 0$ . The remainder is 0, and that's a perfectly valid division. This statement would say it's invalid, which is wrong.

Problem 2: No mention of 'unique'The lemma guarantees exactly one pair of q and r. The statement just says some $q$ and $r$ exist with $a = b q + r$ , but infinitely many do.

For example, $17 = 5 \times 3 + 2$ , but also $17 = 5 \times 1 + 12$ , or $17 = 5 \times 0 + 17$ . The whole point of the lemma is that exactly one pairNot just any pair that works works when we require $0 \leq r < b$ .

✍️ MCQ

Choose one

Statement (A) is missing the word 'unique'. Why does this matter?

✓

Statement (B): 'For positive integers a and b, a = bq + r where $0 \leq r \leq b$ .'

Problem 1: The constraint allows $r = b$ . But if the remainder equals the divisor, you can form one more group.

Take $84 = 12 \times 6 + 12$ — the remainder is 12, same as the divisor. That means the quotient should really be 7: $84 = 12 \times 7 + 0$ .

✍️ MCQ

Choose one

In Statement (B), they wrote

0 \leq r \leq b

. What's wrong with allowing

r = b

?

✓

Problem 2: Again, no 'unique'.

Just like Statement (A), this statement is missing the word 'unique' — without it, we haven't captured what makes Euclid's Division Lemma special.

✍️ MCQ

Choose one

What is the correct constraint on

r

in Euclid's Division Lemma?

✓

The correct version: 'For any two given positive integers $a$ and $b$ , there exist uniqueExactly ONE pair of q and r works, not multiple possibilities whole numbers $q$ and $r$ such that $a = b q + r$ , where $0 \leq r < b$ The remainder must always be smaller than the divisor.'

✍️ MCQ

Choose one

Which of the following correctly states the constraint on

r

in Euclid's Division Lemma?

✓

Every word matters.

3. Why it's called a 'lemma'

We have established the statement of Euclid's Division Lemma and tested it for precision.

The next piece we need is context: where does this result sit in the landscape of mathematics?

Understanding its role — as a stepping stone, not a destination — reveals what it is used to build.

In mathematics, results can be called theorems, lemmas, or corollaries.

A theorem is a major result proved for its own sake
A lemma is a result proved mainly because it helps prove something bigger

✍️ Question

Question 🤔

Why is Euclid's Division Lemma called a 'lemma' rather than a 'theorem'?

Name two specific things in this topic that it enables.

A lemmaA helper result that proves something bigger is a proven mathematical statement that serves as a stepping stone for bigger results.

A theoremThe main result we actually want to prove is the main result itself.

Euclid's Division LemmaA tool, not a destination isn't the final destination — it's the tool that makes other things possibleUsed to find HCF and prove other theorems.

Think of EDL as a screwdriver: you don't display it, but you can't build anything without it.

✍️ T/F

True or False?

Euclid's Division Lemma is called a 'lemma' because it is used to prove bigger results like finding the HCF. True or False?

✓

EDL enables two major things:

1. Euclid's Division Algorithm for finding HCF — you apply the lemma repeatedly (divide, swap, repeat) until the remainder hits 0. Each step uses EDL once.

Look at the flowchart on the board — this shows exactly how the algorithm works. You divide $a$ by $b$ , get the remainder $r$ , and if $r$ is not zero, you swap: $a$ becomes $b$ , and $b$ becomes $r$ . Then repeat until $r = 0$ .

1. Euclid's Division Algorithm for finding HCF — you apply the lemma repeatedly (divide, swap, repeat) until the remainder hits 0. Each step uses EDL once.

Look at the flowchart on the board — this shows exactly how the algorithm works. You divide $a$ by $b$ , get the remainder $r$ , and if $r$ is not zero, you swap: $a$ becomes $b$ , and $b$ becomes $r$ . Then repeat until $r = 0$ .

✍️ MCQ

Choose one

In Euclid's Algorithm, when do we stop dividing?

✓

2. Case-analysis proofs about forms of integers — when you divide any integer by 3, EDL guarantees the remainder is 0, 1, or 2. So every integer is of the form $3 q$ , $3 q + 1$ , or $3 q + 2$ . This technique is used to prove results like "the square of any odd number is of the form $8 m + 1$ ".

✍️ MCQ

Choose one

If we divide any integer by

5

, how many possible forms can that integer take?

✓

4. Using EDL as a four-way relationship

📋 Given Info

The formal statement is now well understood. What remains is to see the division equation not as a formula that goes in one direction, but as a four-way relationship — given any three of the four quantities, we should be able to find the missing one and verify that the constraint still holds.

The equation $a = bq + r$ connects four numbers:

$a$ dividend (dividend)
$b$ divisor (divisor)
$q$ quotient (quotient)
$r$ remainder (remainder)

If you know any three, you can find the fourth.

Example: If $a = 253$ , $b = 17$ , and $r = 15$ , then:

q = \frac{253 - 15}{17} = \frac{238}{17} = 14

✍️ Question

Your Turn 🧮

A division gives:

Quotient = 23
Remainder = 19
Divisor = 31

What is the dividend?

Show your working and verify that the remainder constraint ( $0 \leq r < b$ ) is satisfied.

The equation $a = b q + r$ is a four-way relationshipFour values linked together. If you know any three of the four values, you can find the missing oneGiven three, solve for the missing one.

Finding each variable:

Know $b$ , $q$ , $r$ → find $a$ : $a = bq + r$ The base equation to remember
Know $a$ , $b$ , $r$ → find $q$ : $q = \frac{a - r}{b}$ Rearrange to find q
Know $a$ , $b$ , $q$ → find $r$ : $r = a - b q$
Know $a$ , $q$ , $r$ → find $b$ : $b = \frac{a - r}{q}$

✍️ MCQ

Choose one

In the problem, you're given quotient

= 23

, remainder

= 19

, and divisor

= 31

. Which formula should you use to find the dividend

a

?

✓

Here, we're given $b = 31$ , $q = 23$ , $r = 19$ . So we use the formula to find $a$ :

a = bq + r

formula(Your go-to when you know divisor, quotient, and remainder)

a = 31 \times 23 + 19

Let's compute $31 \times 23$ step by step:

$31 \times 20 = 620$
$31 \times 3 = 93$
So $31 \times 23 =$ $620 + 93 = 713$ sum

✍️ FIB

Fill in the blank

What is

713 + 19

?

✓

Then $a = 713 + 19 =$ $732$ .

The dividend is 732.answer

Verification: Is the remainder constraintMust be non-negative and strictly less than divisor satisfied?

We need $0 \leq r < b$ Non-negative and strictly less than divisor, i.e., $0 \leq 19 < 31$

✓ Yes!Verify even if not explicitly asked $19$ is non-negative and less than $31$ .

✍️ Yes/No

Yes or No?

If

r = 35

and

b = 31

, is the constraint

0 \leq r < b

satisfied?

✓

Always verify the remainder constraint:Check remainder is between zero and divisor Is $0 \leq 19 < 31$ ? Yes! This confirms the division equation is valid — the quotient wasn't too small or too large.