Lesson 3 · Number proofs · McIntyre Maths

Learning intentionTo write clear direct proofs of results about integers, including parity and divisibility.

Success criteria · I can…

write even, odd, consecutive and multiple integers algebraically
use the notation $a \mid b$ (“ $a$ divides $b$ ”) correctly
write a direct proof with a clear conclusion
split a proof into cases using remainders
disprove a claim with a counterexample and fix it

ResourcesLesson slides
Practice worksheet
Worked solutions

Lesson flow

LaunchWarm-up · Algebra we will needSlide 2 DefinitionsWriting integers algebraically · NotationSlide 3 ExamplesExample 1 · Odd and evenSlide 4 ExamplesExample 2 · Parity and divisibilitySlide 5 Key ideaProof by casesSlide 6 ExamplesExample 4 · Consecutive integersSlide 7 HSC practiceHSC practice · Divisible by 8Slide 8 HSC practiceHSC practice · Odd for every integerSlide 9 ExamplesExample 5 · When a claim failsSlide 10 HSC practiceHSC practice · DivisibilitySlide 11 ExamplesExample 6 · A divisibility test for 7Slide 12 ExamplesExample 7 · Proving two numbers are not equalSlide 13 ThinkSpot the flaw · Two odd integersSlide 14 Exit ticketExit ticketSlide 15

Warm-up · Algebra we will need

Slide 2

(a) Expand

(2k+1)^2

Show answerHide answer

Answer

4k^2+4k+1=2(2k^2+2k)+1

Why

Expanding and then taking a factor of 2 out of the first two terms shows the result has the form “2 × integer + 1”, which is how an odd number looks.

(b) Factorise fully

n^3-n

Show answerHide answer

Answer

n(n-1)(n+1)

Why

Take out the common factor

n

to get

n(n^2-1)

, then use the difference of two squares. The factors are three consecutive integers.

(c) Show that

9k^2+12k+6

is a multiple of 3.

Show answerHide answer

Answer

9k^2+12k+6=3(3k^2+4k+2)

Why

Every term is divisible by 3, so 3 factors out and what remains is an integer when

k

is an integer.

(d) Explain in words why

n(n+1)

is always even.

Show answerHide answer

Answer

One of two consecutive integers is even, so the product is even.

Why

Consecutive integers alternate between even and odd. A product with an even factor is even.

Writing integers algebraically · Notation

Slide 3

Key idea

Useful forms (for some $k\in\mathbb{Z}$ )

even: $2k$ odd: $2k+1$
consecutive: $n,\ n+1,\ n+2$
multiple of $m$ : $mk$
every integer is $3k$ , $3k+1$ or $3k+2$

Key idea

Direct proof

Let … (define the letters and say they are integers) $\to$ manipulate $\to$ write in the required form $\to$ “Hence …” $\square$

Definition

Divisibility notation

$a\mid b$ reads “ $a$ divides $b$ ”: $b=ka$ for some $k\in\mathbb{Z}$ .
$a\nmid b$ reads “ $a$ does not divide $b$ ”.
For example, $3\mid 12$ is true and $5\nmid 12$ .

Watch out

a\mid b

is a statement (true or false), not a number. Do not confuse it with the fraction

a/b

Definition

Coprime

Integers are coprime if their highest common factor is 1, for example 4 and 9.

If $a\mid n$ and $b\mid n$ with $a,b$ coprime, then $ab\mid n$ .

Example 1 · Odd and even

Slide 4

(a) Prove that the sum of two odd integers is even.

Show answerHide answer

Answer

Let

a=2j+1

and

b=2k+1

with

j,k\in\mathbb{Z}

. Then

a+b=2j+2k+2=2(j+k+1)

, which is even since

j+k+1\in\mathbb{Z}

Why

Use two different letters, because the two odd integers need not be equal.

(b) Prove that the product of two odd integers is odd.

Show answerHide answer

Answer

With

a=2j+1

and

b=2k+1

ab=4jk+2j+2k+1=2(2jk+j+k)+1

, which is odd since

2jk+j+k\in\mathbb{Z}

Why

Expand, then group everything except the final 1 as 2 times an integer. Common error: writing

a=2k+1

and

b=2k+1

, which only proves the result for equal numbers.

Example 2 · Parity and divisibility

Slide 5

(a) Prove that if

n

is odd, then

n^2+4n+7

is even.

Show answerHide answer

Answer

Let

n=2k+1

k\in\mathbb{Z}

. Then

n^2+4n+7=4k^2+4k+1+8k+4+7=4k^2+12k+12=2(2k^2+6k+6)

, which is even.

Why

Substitute the algebraic form of an odd number, expand, and factor out 2.

(b) Let

3\mid a

and

3\mid b

. Prove that

3\mid(ma+nb)

for all integers

m

and

n

Show answerHide answer

Answer

Let

a=3p

and

b=3q

with

p,q\in\mathbb{Z}

. Then

ma+nb=3mp+3nq=3(mp+nq)

, and

mp+nq\in\mathbb{Z}

, so

3\mid(ma+nb)

Why

Translate

3\mid a

into “

a=3p

for some integer

p

”, using a new letter for each divisibility statement.

Proof by cases

Slide 6

Key idea

Proof by cases (exhaustion over remainders)

When an expression behaves differently for different remainders, split into every case: $n=2k$ or $2k+1$ ; $n=3k$ , $3k+1$ or $3k+2$ .

Prove the result in each case, then conclude “in all cases …”. This is proof by exhaustion, with infinitely many integers grouped into finitely many cases.

Example 3

Prove that the square of any integer has the form

3m

3m+1

, but never

3m+2

Show answerHide answer

Answer

Let

n\in\mathbb{Z}

.
Case 1,

n=3k

n^2=9k^2=3(3k^2)

.
Case 2,

n=3k+1

n^2=9k^2+6k+1=3(3k^2+2k)+1

.
Case 3,

n=3k+2

n^2=9k^2+12k+4=3(3k^2+4k+1)+1

.
So

n^2

is never of the form

3m+2

Why

Every integer leaves remainder 0, 1 or 2 on division by 3, so the three cases are exhaustive. We will use the consequence “if

3\mid n^2

then

3\mid n

” in Lesson 4.

Example 4 · Consecutive integers

Slide 7

(a) Prove that

n(n+1)

is even for every integer

n

, by considering

n

even and

n

odd.

Show answerHide answer

Answer

Case 1,

n=2k

n(n+1)=2k(2k+1)

, which is even.
Case 2,

n=2k+1

n(n+1)=(2k+1)(2k+2)=2(2k+1)(k+1)

, which is even.
In both cases

n(n+1)

is even.

Why

Every integer is even or odd, so the two cases are exhaustive. In each case a factor of 2 appears.

(b) Hence prove that

n^3-n

is divisible by 6 for every integer

n

Show answerHide answer

Answer

n^3-n=(n-1)n(n+1)

, a product of three consecutive integers. One of them is a multiple of 3. By part (a),

n(n+1)

is even, so the whole product is even. Since 2 and 3 are coprime,

6\mid n^3-n

Why

Divisible by 2 and by 3 gives divisible by

2\times3=6

because 2 and 3 are coprime. (For the factor of 3, an alternative is cases

n=3k

3k+1

3k+2

HSC practice · Divisible by 8

Slide 8

2024 HSC Q14(a)Let

a

be an odd integer. By writing

a=4k+1

a=4k+3

, prove that

a^2-1

is divisible by 8. (Wording adapted from the paper.)

Show answerHide answer

Answer

Case 1,

a=4k+1

a^2-1=16k^2+8k=8(2k^2+k)

.
Case 2,

a=4k+3

a^2-1=16k^2+24k+8=8(2k^2+3k+1)

.
In both cases

8\mid a^2-1

Why

Every odd integer leaves remainder 1 or 3 on division by 4, so the cases are exhaustive. Alternative:

a^2-1=(a-1)(a+1)

is a product of two consecutive even numbers, and one of these is a multiple of 4.

HSC practice · Odd for every integer

Slide 9

Adapted from 2024 HSC Q12(d)Prove that

(n+1)^{41}-79n^{40}

is odd for every integer

n

Show answerHide answer

Answer

Case 1,

n

even:

n+1

is odd, so

(n+1)^{41}

is odd;

79n^{40}

is even. Odd minus even is odd.
Case 2,

n

odd:

n+1

is even, so

(n+1)^{41}

is even;

79n^{40}

is odd

\times

odd, which is odd. Even minus odd is odd.
In all cases the expression is odd.

Why

Facts used: odd

\times

odd is odd (Example 1), any positive power of an odd number is odd, and any positive power of an even number is even. (The original question goes on to deduce that the expression can never equal 2.)

Example 5 · When a claim fails

Slide 10

A student claims: “If an integer is divisible by both 4 and 6, then it is divisible by 24.”

(a) Disprove the claim with a counterexample.

Show answerHide answer

Answer

12 is divisible by 4 and by 6, but not by 24.

Why

One counterexample is enough to disprove a “for all” claim.

(b) Explain what went wrong, then state and prove a correct version.

Show answerHide answer

Answer

Correct version: if

4\mid n

and

6\mid n

, then

12\mid n

.
Proof: let

n=4a

with

a\in\mathbb{Z}

. Since

6\mid n

, we have

3\mid 4a

. As 3 and 4 are coprime,

3\mid a

, so

a=3b

and

n=12b

. Hence

12\mid n

Why

4 and 6 are not coprime: they share the factor 2, so multiplying them (

4\times6=24

) double-counts it. The correct number is the lowest common multiple, 12.

HSC practice · Divisibility

Slide 11

2020 HSC Q15(a)(i)Let

k

be an integer. Prove that if

k+1

is divisible by 3, then

k^3+1

is divisible by 3.

Show answerHide answer

Answer

k^3+1=(k+1)(k^2-k+1)

(sum of cubes). If

k+1=3m

with

m\in\mathbb{Z}

, then

k^3+1=3m(k^2-k+1)

, which is divisible by 3.

Why

Alternative:

k^3+1=(k+1)^3-3k^2-3k=27m^3-3k^2-3k=3(9m^3-k^2-k)

. The contrapositive and converse of this result are explored in Lesson 4.

Example 6 · A divisibility test for 7

Slide 12

Let $n=10x+y$ , where $x$ is a positive integer and $y\in\{0,1,\dots,9\}$ is the last digit of $n$ .

(a) Show that

10x+y=10(x-2y)+21y

. Hence prove that if

7\mid(x-2y)

, then

7\mid n

Show answerHide answer

Answer

10(x-2y)+21y=10x-20y+21y=10x+y

. If

x-2y=7m

, then

n=70m+21y=7(10m+3y)

, so

7\mid n

Why

Expand the right-hand side to verify the identity. Then substitute

x-2y=7m

and factor out 7.

(b) Show that

x-2y=21x-2n

. Hence prove the converse.

Show answerHide answer

Answer

21x-2(10x+y)=21x-20x-2y=x-2y

. If

n=7p

, then

x-2y=21x-14p=7(3x-2p)

, so

7\mid(x-2y)

Why

The converse says: if

7\mid n

, then

7\mid(x-2y)

. Start from

n=7p

and use the identity just shown.

(c) Write the result as an iff statement. Is 3871 divisible by 7?

Show answerHide answer

Answer

7\mid n\Leftrightarrow 7\mid(x-2y)

. For 3871:

387-2=385

, then

38-10=28=7\times4

. So

7\mid3871

(indeed

3871=7\times553

Why

Parts (a) and (b) give both directions, so the statement is an equivalence. Apply the test repeatedly until the number is small enough to check by eye.

Example 7 · Proving two numbers are not equal

Slide 13

To prove $A\neq B$ for real numbers, it is enough to prove $A<B$ or $A>B$ .

Prove that

(5+2)^n\neq5^n+2^n

for all integers

n\geq2

Show answerHide answer

Answer

By the binomial theorem,

(5+2)^n=5^n+\binom{n}{1}5^{n-1}\cdot2+\cdots+2^n

. For

n\geq2

there is at least one middle term and all middle terms are positive, so

(5+2)^n>5^n+2^n

. Hence

(5+2)^n\neq5^n+2^n

Why

Proving a strict inequality is an easy way to prove two quantities differ. Discussion:

n=1

gives equality, so the condition

n\geq2

is needed.

Spot the flaw · Two odd integers

Slide 14

A student wrote this. Find the flaw, explain why it matters, then write a correct version.

Claim

The product of two odd integers is odd.

Let the odd integers be $2k+1$ and $2k+1$ , where $k$ is an integer.
Their product is $(2k+1)^2=4k^2+4k+1=2(2k^2+2k)+1$ .
This is odd, so the product of two odd integers is odd. $\square$

Task Find the flaw, explain why it matters, and write a correct version.

Show answerHide answer

Answer

Flaw: using the same letter makes the two odd integers equal, so this only proves that the square of an odd integer is odd.
Correct version: let the integers be

2j+1

and

2k+1

with

j,k\in\mathbb{Z}

. Their product is

4jk+2j+2k+1=2(2jk+j+k)+1

, which is odd since

2jk+j+k\in\mathbb{Z}

Why

Every line of algebra is correct; the proof fails on generality. Two different odd integers need two different letters. Compare Example 1.

Exit ticket

Slide 15

(a) Prove that the sum of any three consecutive integers is divisible by 3.

Show answerHide answer

Answer

Let the integers be

n

n+1

n+2

. Their sum is

3n+3=3(n+1)

, which is divisible by 3 since

n+1\in\mathbb{Z}

Why

Define the letter, add, factor out 3, and write a conclusion.

(b) Disprove: “The sum of any four consecutive integers is divisible by 4.”

Show answerHide answer

Answer

Take

1+2+3+4=10

, which is not divisible by 4.

Why

One counterexample suffices. In general the sum is

n+(n+1)+(n+2)+(n+3)=4n+6

, which always leaves remainder 2 when divided by 4.