Welcome! Today we're exploring The Proof-by-Cases Template Using Division — a powerful technique that will make a whole family of proofs feel almost automatic.

You already know that dividing by 2 splits all integers into even and odd.

What if you divide by 3, or by 5, or by any number?

You get a complete set of cases — and that's the engine behind a whole family of proofs.

Divide by	Number of cases
2	2 (even, odd)
3	3 (remainder 0, 1, 2)
n	n cases

By the end of this section, you'll be able to:

Take any 'show that every integer is of the form ...' question
Write the proof from a clean four-step template

1. How dividing by b produces exactly b cases

We're starting at the very foundation of proof-by-cases.

Before writing any proof, you need to see:

Why dividing all integers by a fixed number creates a complete, gap-free partition into cases
How many cases you get

This partition is the engine behind a whole family of proofs.

📋 Given Info

Here's what you already know:

When you divide any positive integer by 2, the remainder is either 0 or 1 — giving two forms:

$2q$ (even)
$2q + 1$ (odd)

Every integer is exactly one of these.

Now let's think about dividing by a larger numberkey...

✍️ Question

Your turn 🤔

If you divide every positive integer by 5, how many different forms do you get?

List all of them.

Then explain: Why is there no form $5q + 5$ ?

When you divide any positive integer by $b$ , the division lemmaThe starting point for proof-by-cases says there's a unique remainder $r$ satisfying $0 \leq r < b$ This constraint limits your cases.

The possible remainders are $0, 1, 2, \dots, b - 1$ — that's exactly $b$ valuesTells you how much work your proof needs in total.

✍️ MCQ

Choose one

When dividing by

5

, what are all the possible remainders?

✓

✍️ MCQ

Choose one

Why is there no form

5q + 5

when dividing by

5

?

✓

For $b = 5$ , the remainders are $0, 1, 2, 3, 4$ .

So every positive integer takes one of these five formsEvery positive integer fits exactly one form:

$5 q$ (remainder 0)
$5 q + 1$ (remainder 1)
$5 q + 2$ (remainder 2)
$5 q + 3$ (remainder 3)
$5 q + 4$ (remainder 4)

✍️ MCQ

Choose one

Why is there no form

5q + 5

?

✓

Now, why no $5 q + 5$ ? Because the constraint says $r < 5$ Remainder must be strictly less than divisor, and $5$ is not less than $5$ Only possible remainders are 0 through 4.

✍️ Yes/No

Yes or No?

If we're dividing by

7

, can the remainder be

7

?

✓

But there's a deeper reason: $5q + 5 = 5(q + 1)$ 5q+5 is just 5(q+1) in disguise. That's just a multiple of 5 — the $r = 0$ casesame!It's the r=0 case with different quotient with a different quotient.

The 'extra' remainder wraps aroundRemainder wraps around to next quotient and gets absorbed into the next quotient. This is exactly why the constraint $r < b$ exists — it prevents double-countingEnsures each integer has exactly one representation.

✍️ MCQ

Choose one

The expression

5q + 5

simplifies to which of the following?

✓

2. The four-step proof template

Now that you see how division creates a complete partition, let's turn that into a proof method.

There's a clean four-step structure that every proof of the form 'show that every integer is of the form ...' follows.

📋 Given Info

Here's the template for proving that every positive integer falls into certain forms:

Step 1: Choose a divisor $b$ .

Step 2: Write $n = bq + r$ with $0 \leq r < b$ , and list all possible remainders.

Step 3: For each remainder, write out the corresponding form of $n$ .

Step 4: Conclude which forms are valid.

You've seen this done for divisor 2b=2 (even/odd) and divisor 3b=3 (three forms).

✍️ Question

Your turn! 📝

Using this template, prove that every positive integer is of the form $4q$ , $4q + 1$ , $4q + 2$ , or $4q + 3$ .

Write out the full proof, making sure you:

State which divisor you're using
Explain why there are exactly four caseswhy 4?
Show what each case gives you

Let's walk through the template with divisor 4.

Step 1: Choose divisor $b = 4$ b. (The question mentions $4 q$ , so the divisor is 4.)

Step 2: By Euclid's Division Lemma, for any positive integer $n$ , there exist unique $q$ and $r$ such that $n = 4 q + r$ , where $0 \leq r < 4$ .

So $r$ can be 0, 1, 2, or 3Divisor 4 gives these four possible remainders — giving us exactly four casescasesDivisor 4 means exactly four cases to check to consider.

✍️ MCQ

Choose one

Why can't the remainder

r

be equal to

4

when dividing by

4

?

✓

Step 3: Write out each case:

$r = 0$ : $n = 4q$ Number is exactly divisible by 4 — this is a multiple of 4(When remainder is zero, it divides evenly)
$r = 1$ : $n = 4q + 1$ One more than a multiple of 4 — one more than a multiple of 4The remainder tells you how far from a multiple

$r = 2$ : $n = 4 q + 2$ — two more than a multiple of 4
$r = 3$ : $n = 4 q + 3$ — three more than a multiple of 4

Notice something? Every positive integer lands in exactly one of these four buckets.Each number belongs to exactly one case No overlaps, no gaps!key insightNo overlaps means no double counting, no gaps means complete coverage

✍️ MCQ

Choose one

The number

23

can be written in the form

4q + r

. What is the value of

r

?

✓

Step 4: Since the division lemma guaranteesThis makes the proof airtight with no ambiguity every positive integer has a unique remainderNo ambiguity about which form a number takes when divided by 4, and the only possible remainders are 0, 1, 2, 3, every positive integer falls into exactly one of these four formsNot at least one, not possibly more — exactly one:

$4 q$ (remainder 0)
$4 q + 1$ (remainder 1)
$4 q + 2$ (remainder 2)
$4 q + 3$ (remainder 3)

This completes the proof.

The key point: The proof works because the division lemma gives you a complete, non-overlapping partitionEvery integer accounted for with no duplicates.

Complete:no gaps(No gaps in coverage) Every integer is covered (no gaps)
Non-overlapping:no duplicatesEach number in exactly one group Each integer belongs to exactly one form (no duplicates)

Number line from 0 to 12 with integers marked, colored by remainder mod 4: 0,4,8,12 in blue (4k), 1,5,9 in green (4k+1), 2,6,10 in orange (4k+2), 3,7,11 in red (4k+3), showing complete non-overlapping partition

Look at the number line on the board — notice how every integer from 0 to 12 is colored exactly once? Blue for multiples of 4, green for 4k+1, orange for 4k+2, red for 4k+3. No number is left out, and no number has two colors.

You don't need to check specific numbers — the lemma handles all integers at onceNever need to check individual cases.

✍️ MCQ

Choose one

If we used divisor

b = 6

instead, how many distinct forms would every positive integer fall into?

✓

3. Why uniqueness makes the proof valid

You've seen the template and used it to list cases.

But there's a subtlety people often miss — the proof only works because of one specific property of the division lemma.

Without it, listing cases wouldn't prove anything.

📋 Given Info

Suppose someone writes:

'Every integer is of the form $3q$ , $3q + 1$ , or $3q + 2$ .'

They list the three forms and say 'done.'

A mathematician says:

'Your proof has two gaps — you haven't shown that every integer falls into at least one of these forms, and you haven't shown that no integer falls into more than one.'

✍️ Question

Think about this 🤔

How does the division lemma fill both of these gaps?

Specifically:

Which word in the lemma's statement guarantees no overlaps?
Which part guarantees no gaps?

The division lemma says: for any positive integers $n$ and $b$ , there EXIST UNIQUE whole numbers $q$ and $r$ such that $n = b q + r$ with $0 \leq r < b$ .

Two words do all the heavy lifting here: 'Exist'Every number has a place, no gaps and 'Unique'Every number has only ONE place, no overlaps.

'Exist' guarantees no gapsexist(Every integer falls into at least one form) — every integer DOES fall into at least one of the forms $b q, b q + 1, \dots, b q + (b - 1)$ .
'Unique' guarantees no overlapsuniqueNo integer falls into more than one form — no integer falls into more than one form.

✍️ MCQ

Choose one

In the division lemma, which word guarantees that no integer falls into more than one form?

✓

'Exist'(Guarantees every integer falls into at least one case) — this means for every integer $n$ , at least one $(q, r)$ pair works. So every integer lands in at least one of the $b$ casesNo integer is missed by your cases. No integer is left out. This fills the 'no gaps'keyYou need to be sure you haven't missed any integer requirement.

'Unique'Only one quotient-remainder pair exists for any number — this means for each $n$ , exactly one $(q, r)$ pair works. So no integer can land in two different cases simultaneouslySplitting into remainder cases gives non-overlapping groups.

The number 10 can't be both $3 (3) + 1$ and $3 (2) + 4$ , because only one of these has a valid remainder.

This fills the 'no overlaps'Each integer lands in exactly one remainder case requirement.

✍️ MCQ

Choose one

In the division lemma statement, which word guarantees no overlaps between the different remainder cases?

✓

Number line showing integers partitioned into 3 colored groups: remainders 0, 1, 2 when divided by 3, with labels showing each integer belongs to exactly one group

Together, existence and uniqueness give you a partitionThis is the key concept here: every integer belongs to exactly one caseNo gaps, no overlaps in coverage.

Look at the diagram on the board — see how every integer lands in exactly one colored group? No integer is left floating outside, and no integer appears in two colors at once. That's a partition.

That's what makes proof by exhaustive cases logically airtightYou can trust you've covered everything — you check every case, knowing nothing slips through and nothing gets counted twice.

So when someone says "every integer is of the form $3 q$ , $3 q + 1$ , or $3 q + 2$ " — the division lemma with $b = 3$ guarantees this is a valid partitionPick your divisor and write out remainders. ExistEvery integer falls into some case means no gaps. UniqueEach integer in exactly one remainder class means no overlaps.

✍️ MCQ

Choose one

In the division lemma, which word guarantees that no integer falls into more than one of the forms

3q

,

3q+1

,

3q+2

?

✓

4. Even/odd proof as a two-case instance of the template

We've established the proof-by-cases template and understood why it works mathematically.

Now let's make sure you can execute it on the simplest possible example — the one that splits all integers into just two groups.

📋 Given Info

Consider the statement:

"Every positive integer is either even or odd."

Recall:

An even number is a multiple of 2
An odd number is one more than a multiple of 2

✍️ Question

Your Task ✍️

Write a proof of this statement using the division lemma.

Your proof should make clear why there are exactly two cases and no third possibility.

Here's the even/odd proof using the division lemma templateYour go-to method for proving things about all integers:

Choose divisor $b = 2$ Matches what we're trying to show — even versus odd. By the division lemma, for any positive integer $n$ , there exist unique $q$ and $r$ with: $n = 2 q + r where 0 \leq r < 2$

Number line showing integers 0 to 10, with even numbers (0,2,4,6,8,10) marked in one color and odd numbers (1,3,5,7,9) in another, illustrating the two cases r=0 and r=1

Since $r$ must be a whole number that's at least 0 and strictly less than 2This constraint limits r to only 0 or 1, the only possibilities are:

$r = 0$ → $n = 2 q$ → $n$ is even
$r = 1$ → $n = 2 q + 1$ → $n$ is odd

Just two cases. The division lemma guarantees there's no third possibilitykey!Division lemma guarantees completeness — every integer covered!

✍️ MCQ

Choose one

Why can't there be a third case where

r = 2

in this proof?

✓

Case $r = 0$ : $n = 2 q$ . This is divisible by 2This is what makes a number even, so it's evenThe definition of an even number.

Case $r = 1$ : $n = 2 q + 1$ . This is one more than a multiple of 2Exactly what defines an odd number, so it's oddOne more than a multiple of 2.

✍️ MCQ

Choose one

According to the division lemma with

b = 2

, what are the only possible values of

r

?

✓

The division lemmaThis mathematically guarantees the two cases guarantees there's no third option. The remainder when dividing by 2 can only be 0 or 1Only two possible remainders exist — those are the only whole numbers in the range $[0, 2)$ No third option is mathematically possible.

Number line from 0 to 7 showing integers, with even numbers (0,2,4,6) labeled as 2q and odd numbers (1,3,5,7) labeled as 2q+1, demonstrating the two exhaustive cases

So every positive integer is either $2q$ The form for all even numbers or $2q + 1$ The form for all odd numbers, and never bothMutually exclusive cases.

This is the simplest instance of the templateThe fundamental structure for case analysis: two caseskeyThey cover everything with no overlap, no elimination needed, and the conclusion follows directly.

✍️ MCQ

Choose one

If we used divisor

b = 5

instead of

b = 2

, how many cases would we have in our proof?

✓

5. Applying the template to a new divisor

You've seen the template with divisors 2 and 4.

Now let's test whether you can apply it independently to a divisor you haven't worked with before — and handle the complete write-up on your own.

📋 Given Info

Consider the claim:

'Every positive integer is of the form $7m$ , $7m + 1$ , $7m + 2$ , $7m + 3$ , $7m + 4$ , $7m + 5$ , or $7m + 6$ .'

✍️ Question

How many cases does this proof have, and why?

Also, a classmate says there should be an eighth form, $7 m + 7$ .

In one sentence, explain why that doesn't add a new case.

When you divide by 7, the division lemmaYour starting tool for this proof says: $n = 7 m + r$ with $0 \leq r < 7$ This limits your cases.

The possible remainders are 0, 1, 2, 3, 4, 5, 6Exactly seven remainders to check — that's seven valueskey!The divisor determines your case count, so seven casesNo more, no less.

✍️ MCQ

Choose one

Your classmate claims there should be an eighth form:

7m + 7

. Why doesn't this add a new case?

✓

Now, what about $7 m + 7$ ? Let's do the algebra:

$7 m + 7 = 7 (m + 1)$

This is a multiple of 7Any multiple of 7 is the r equals 0 case — it's the form $7 k$ where $k = m + 1$ . In other words, it's just the $r = 0$ casesame! with a different quotient. It's not a new formIt was already covered by the r equals 0 case.

✍️ MCQ

Choose one

Why doesn't

7m + 7

count as a new case separate from

7m

?

✓

This happens every time someone suggests $bq + b$ as an extra case.

The division lemma's constraint $r < b$ This constraint stops us from counting the same case twice catches this: if the remainder equals the divisor, you can absorb it into the quotientWhen remainder equals divisor, it gets absorbed.

That's the whole point of requiring $r < b$ key constraintExactly b cases, nothing extra — it prevents this kind of double-countingNo double-counting allowed.

✍️ MCQ

Choose one

If someone claims

5m + 5

is a new case when dividing by 5, which existing case does it actually belong to?

✓

General pattern: Dividing by $b$ always gives exactly $b$ casesThe divisor determines how many cases you get, with remainders $0$ through $b - 1$ . Never more.

This is the proof-by-cases templateYour standard approach for exam questions: choose your divisor $b$ Choose based on what your problem needs, and the division lemma automatically partitions all positive integers into exactly $b$ exhaustive, non-overlapping casesEvery integer falls into exactly one case.

✍️ FIB

Fill in the blank

If you're proving something about all positive integers by dividing by

12

, how many cases will your proof have?

✓