Mathematical-Reasoning · Unit 10 · Video 3 · Interactive Practice

Proof by Remainders: Why 3 Divides n³ − n

IKey Formulas

Formula	Name	Role in the proof
$n = 3q + r$ , $\ 0 \le r < 3$	Division Algorithm with divisor $3$	Every integer has exactly one of the forms $3q$ , $3q + 1$ , $3q + 2$
$3 \mid m \iff m = 3k$ for some $k \in \mathbb{Z}$	Definition of divides	The goal in every case: write $n^3 - n$ as $3$ times an integer
$(x + y)^3 = x^3 + 3x^2y + 3xy^2 + y^3$	Cube of a sum	Expands $(3q + 1)^3$ and $(3q + 2)^3$
$3(9q^3 - q)$ ; $\ 3(9q^3 + 9q^2 + 2q)$ ; $\ 3(9q^3 + 18q^2 + 11q + 2)$	$n^3 - n$ for $r = 0$ , $1$ , $2$	Each bracket is an integer, so $3 \mid (n^3 - n)$ in each case

Key Insight: No list of examples can prove a claim about every integer, but three computations can: the Division Algorithm guarantees that the three remainder cases cover every integer, negative ones included.

IIVisualization 1 — Every Integer Falls in Exactly One Case

Every integer, negative ones included, has exactly one form $3q + r$ , and that case's formula reproduces $n^3 - n$ .

n 4

IIIVisualization 2 — Where the Factor of 3 Comes From

The cube's constant term $r^3$ is the only possible obstacle, and subtracting $n$ turns it into $r^3 - r$ , a multiple of $3$ .

Case Step 1

Step 1 — Substitute.

n^3 - n = (3q)^3 - 3q

Step 2 — Expand the cube.

(3q)^3 = 3^3q^3 = 27q^3

Step 3 — Subtract $n$ .

n^3 - n = 27q^3 - 3q

Step 4 — Factor out $3$ .

n^3 - n = 3(9q^3 - q)

, and

9q^3 - q \in \mathbb{Z}

because the integers are closed under multiplication and subtraction.

Step 1 — Substitute.

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

Step 2 — Expand the cube with

x = 3q

y = 1

(3q + 1)^3 = 27q^3 + 3(9q^2)(1) + 3(3q)(1) + 1 = 27q^3 + 27q^2 + 9q + 1

Step 3 — Subtract $n = 3q + 1$ .

n^3 - n = 27q^3 + 27q^2 + (9q - 3q) + (1 - 1) = 27q^3 + 27q^2 + 6q

Step 4 — Factor out $3$ .

n^3 - n = 3(9q^3 + 9q^2 + 2q)

, and

9q^3 + 9q^2 + 2q \in \mathbb{Z}

Step 1 — Substitute.

n^3 - n = (3q + 2)^3 - (3q + 2)

Step 2 — Expand the cube with

x = 3q

y = 2

(3q + 2)^3 = 27q^3 + 3(9q^2)(2) + 3(3q)(4) + 8 = 27q^3 + 54q^2 + 36q + 8

Step 3 — Subtract $n = 3q + 2$ .

n^3 - n = 27q^3 + 54q^2 + (36q - 3q) + (8 - 2) = 27q^3 + 54q^2 + 33q + 6

Step 4 — Factor out $3$ .

n^3 - n = 3(9q^3 + 18q^2 + 11q + 2)

, and

9q^3 + 18q^2 + 11q + 2 \in \mathbb{Z}

IVVisualization 3 — The Same Method for Any Divisor

With $n = dq + r$ , every term containing $q$ carries a factor of $d$ , so each case stands or falls on its constant term.

Expression Divisor d

💡 A failing case is a counterexample at once: take $q = 0$ , so $n = r$ and the expression equals its constant term.

VQuiz Questions

Problem 1 · A Negative Integer in Its Case

Given: $n = -14$ . Use the Division Algorithm to write $n = 3q + r$ with $0 \le r < 3$ , then use the case formula to write $n^3 - n = 3k$ .

What are q and r?

Which integer k gives n³ − n = 3k?

✅ Correct!

-14 = 3(-5) + 1

puts

n

in the case

r = 1

, and

3(-910) = -2730 = (-14)^3 - (-14)

❌ Not quite.

3(-4) - 2 = -14

is true, but the Division Algorithm requires

0 \le r < 3

, so

r = -2

is not allowed. Go one multiple of

3

lower.

❌ Not quite.

3(-4) + 2 = -10

, not

-14

. Writing

14 = 3 \cdot 4 + 2

and attaching minus signs does not work for negative integers.

❌ Not quite.

3(-6) + 4 = -14

is true, but

r = 4

is not less than

3

❌ Not quite.

-728

comes from the

r = 2

formula

9q^3 + 18q^2 + 11q + 2

, but

-14

has remainder

1

, so use

9q^3 + 9q^2 + 2q

❌ Not quite.

-2730

n^3 - n

itself, which is

3k

. The integer

k

is the bracket, one third of it.

❌ Not quite. Check the sign:

q = -5

makes

9q^3 = -1125

, which dominates, so

k

is negative.

Show solution

The multiple of $3$ at or just below $-14$ is $-15 = 3(-5)$ , and $-14 - (-15) = 1$ . So

-14 = 3(-5) + 1, \qquad q = -5,\ r = 1.

The case $r = 1$ gives $n^3 - n = 3(9q^3 + 9q^2 + 2q)$ , so

k = 9(-5)^3 + 9(-5)^2 + 2(-5) = -1125 + 225 - 10 = -910.

Check directly: $(-14)^3 - (-14) = -2744 + 14 = -2730 = 3(-910)$ .

Problem 2 · A Missing Case

Given: A student proves $3 \mid (n^3 - n)$ by working out only the cases $n = 3q$ and $n = 3q + 1$ , then writes "the remaining integers behave the same way." What is wrong with the proof?

✅ Correct! Division by

3

leaves three possible remainders, so a complete proof needs all three cases; "behaves the same way" is a claim, not a proof.

❌ Not quite. The integer

2

is neither

3q

nor

3q + 1

for any integer

q

, so it is not covered.

❌ Not quite.

q

may be negative:

-3 = 3(-1)

and

-2 = 3(-1) + 1

. The gap is a remainder, not a sign.

❌ Not quite. Nothing forces even and odd cases. The cases from division by

3

are a fine choice, as long as all three are done.

Show solution

By the Division Algorithm every integer $n$ is $3q + r$ with $r \in \{0, 1, 2\}$ , and exactly one $r$ applies. The cases $r = 0$ and $r = 1$ handle only some integers; for example $2 = 3 \cdot 0 + 2$ , $5 = 3 \cdot 1 + 2$ and $-1 = 3(-1) + 2$ all fall in the case $r = 2$ .

The proof is complete only after the third computation: $(3q + 2)^3 - (3q + 2) = 3(9q^3 + 18q^2 + 11q + 2)$ . A case is proved by its own calculation, not by resemblance to the others.

Problem 3 · A New Expression, Case r = 2

Given: To prove $3 \mid (n^3 + 2n)$ for every integer $n$ , consider the case $n = 3q + 2$ . Find the integer expression $k$ with $n^3 + 2n = 3k$ .

✅ Correct!

n^3 + 2n = 27q^3 + 54q^2 + 42q + 12 = 3(9q^3 + 18q^2 + 14q + 4)

❌ Not quite. That is the bracket for

n^3 - n

. Here you add

2n = 6q + 4

instead of subtracting

3q + 2

❌ Not quite. That is

n^3 + 2n

itself, which equals

3k

. Factor out the

3

to find

k

❌ Not quite.

(3q + 2)^3 \ne 27q^3 + 8

: the cube of a sum also has the middle terms

3x^2y

and

3xy^2

Show solution

With $x = 3q$ , $y = 2$ in the cube of a sum:

(3q + 2)^3 = 27q^3 + 54q^2 + 36q + 8.

Add $2n = 2(3q + 2) = 6q + 4$ :

n^3 + 2n = 27q^3 + 54q^2 + 42q + 12 = 3(9q^3 + 18q^2 + 14q + 4).

The bracket is an integer, so $3 \mid (n^3 + 2n)$ in this case. Check with $q = 0$ , $n = 2$ : $8 + 4 = 12 = 3 \cdot 4$ .

Problem 4 · Divisor 4

Given: Use the divisor $4$ . In the case $n = 4q + 3$ , write $n^2 = 4k + s$ with $k \in \mathbb{Z}$ and $0 \le s < 4$ . Find $s$ .

✅ Correct!

n^2 = 16q^2 + 24q + 9 = 4(4q^2 + 6q + 2) + 1

❌ Not quite.

9

is the constant term, but

s

must satisfy

s < 4

. Move

8 = 4 \cdot 2

into the multiple of

4

❌ Not quite.

3

is the remainder of

n

, not of

n^2

. Try

n = 3

n^2 = 9 = 4 \cdot 2 + 1

❌ Not quite.

n = 3

gives

n^2 = 9

, which is not a multiple of

4

Show solution

With $x = 4q$ , $y = 3$ in $(x + y)^2 = x^2 + 2xy + y^2$ :

n^2 = (4q + 3)^2 = 16q^2 + 24q + 9 = 16q^2 + 24q + 8 + 1 = 4(4q^2 + 6q + 2) + 1.

Here $k = 4q^2 + 6q + 2$ is an integer and $s = 1$ satisfies $0 \le s < 4$ , so by the uniqueness in the Division Algorithm $s = 1$ . Checks: $3^2 = 9 = 4 \cdot 2 + 1$ , $7^2 = 49 = 4 \cdot 12 + 1$ , and $(-1)^2 = 1 = 4 \cdot 0 + 1$ with $-1 = 4(-1) + 3$ .

Solved: 0 / 4