Mathematical-Reasoning · Unit 12 · Video 4 · Interactive Practice

Why Both Steps Matter: Proving 4 Divides 5ⁿ − 1

IKey Formulas

Formula	Name	Role here
$P(1) \land (\forall k \in \mathbb{N})\,(P(k) \to P(k+1))$ gives $(\forall n \in \mathbb{N})\,(P(n))$	Principle of Mathematical Induction	Basis step and inductive step are both required
$5^{k+1} - 1 = 5 \cdot 5^k - 1 = 5(4m + 1) - 1 = 4(5m + 1)$	Divisibility proof	Uses $5^k = 4m + 1$ from the hypothesis $5^k - 1 = 4m$
$4 \mid (5^n - 1) \iff 5^n \equiv 1 \pmod 4$	Same statement as a congruence	$a \equiv b \pmod n$ means $n \mid (a - b)$
$5 \cdot 5^k \equiv 5 \cdot 1 \pmod 4$ , then $5 \equiv 1 \pmod 4$	Congruence proof	Multiply the hypothesis by $5$ , finish by transitivity

Key Insight: $3 \mid (4^n + 1)$ has a provable inductive step but a false basis step, and it is false for every $n$ ; $n^2 - n + 41$ is prime for $n = 1, \dots, 40$ yet fails at $n = 41$ . Neither step can be skipped.

IIVisualization 1 — Which Step Fails?

Induction needs a true $P(1)$ and a true conditional $P(k) \to P(k+1)$ for every $k \in \mathbb{N}$ .

Statement Case n 40

IIIVisualization 2 — The Know-Show Table for $4 \mid (5^{k+1} - 1)$

The forward and backward processes meet once $5^{k+1} = 5 \cdot 5^k$ links the known equation to the goal.

Step 1

Step	Know / Show	Reason
P	$k \in \mathbb{N}$ and $4 \mid (5^k - 1)$	inductive hypothesis
P1	$(\exists m \in \mathbb{Z})\,(5^k - 1 = 4m)$	definition of divides
P2	$5^k = 4m + 1$	solve P1 for $5^k$
link: $5^{k+1} = 5 \cdot 5^k$ $5 \cdot 5^k - 1 = 5(4m + 1) - 1 = 20m + 4 = 4(5m + 1)$
Q2	$5^{k+1} - 1 = 5 \cdot 5^k - 1$	$5^{k+1} = 5 \cdot 5^k$ ; then substitute P2
Q1	$(\exists s \in \mathbb{Z})\,(5^{k+1} - 1 = 4s)$	?show $5 \cdot 5^k - 1$ is a multiple of $4$
Q	$4 \mid (5^{k+1} - 1)$	definition of divides

IVVisualization 3 — Two Proofs, One Link

The divisibility proof and the congruence proof both rest on $5^{k+1} = 5 \cdot 5^k$ , checked here with numbers.

k 1

divides

≡ (mod 4)

VQuiz Questions

Problem 1 · Close the Gap

Given: In the inductive step for $P(n)\colon 4 \mid (5^n - 1)$ , the hypothesis gives $5^k = 4m + 1$ for some integer $m$ . Find the result of substituting this into $5^{k+1} - 1 = 5 \cdot 5^k - 1$ .

✅ Correct!

5(4m + 1) - 1 = 20m + 4 = 4(5m + 1)

, and

5m + 1

is an integer, so

4 \mid (5^{k+1} - 1)

❌ Not quite. This treats

5^{k+1}

5^k + 5

. The rule is

5^{k+1} = 5 \cdot 5^k

, so the whole of

4m + 1

is multiplied by

5

❌ Close, but… the

5

multiplies both terms of

4m + 1

5(4m + 1) = 20m + 5

, and then subtracting

1

gives

20m + 4

❌ Check the sign. The expression is

5(4m + 1) - 1

, so the constant is

5 - 1 = 4

, not

5 + 1

Show solution

Since $5^{k+1} = 5 \cdot 5^k$ and $5^k = 4m + 1$ ,

5^{k+1} - 1 = 5 \cdot 5^k - 1 = 5(4m + 1) - 1 = 20m + 5 - 1 = 20m + 4 = 4(5m + 1).

Because $m$ is an integer, $5m + 1$ is an integer, so $4 \mid (5^{k+1} - 1)$ . That is $P(k+1)$ .

Problem 2 · An Inductive Step Without a Basis

Given: $P(n)\colon 3 \mid (4^n + 1)$ , where $a \mid b$ means $b = aq$ for some integer $q$ . The inductive step can be proved: from $4^k + 1 = 3m$ we get $4^{k+1} + 1 = 4(3m - 1) + 1 = 3(4m - 1)$ . Which statement is correct?

✅ Correct! Every value

4^n + 1

leaves remainder

2

on division by

3

, so no case is true; the inductive step only transfers truth that is never there.

❌ Not quite. Induction also needs the basis step, and

P(1)

is false:

4^1 + 1 = 5

and

3 \nmid 5

❌ Not quite. The algebra is correct:

4(3m - 1) + 1 = 12m - 3 = 3(4m - 1)

. A conditional

P(k) \to P(k+1)

whose hypothesis is false is true, so the inductive step can be proved here.

❌ Check the division.

17 = 3 \cdot 5 + 2

, so

3 \nmid 17

and

P(2)

is false too.

Show solution

Inductive step. If $4^k + 1 = 3m$ , then $4^k = 3m - 1$ and

4^{k+1} + 1 = 4 \cdot 4^k + 1 = 4(3m - 1) + 1 = 12m - 3 = 3(4m - 1),

so $P(k) \to P(k+1)$ holds for every $k \in \mathbb{N}$ .

Basis step. $4^1 + 1 = 5$ and $3 \nmid 5$ , so $P(1)$ is false. The next cases are $17$ and $65$ , also not multiples of $3$ .

Every case. $4 \equiv 1 \pmod 3$ , so $4^n \equiv 1 \pmod 3$ and $4^n + 1 \equiv 2 \pmod 3$ . Thus $P(n)$ is false for every $n \in \mathbb{N}$ : without a true basis step, the inductive step proves nothing.

Problem 3 · Forty Cases Are Not a Proof

Given: $P(n)\colon n^2 - n + 41$ is prime. The cases $P(1), P(2), \dots, P(40)$ are all true.

What is $41^2 - 41 + 41$ , and is it prime?

Among these values of $k$ , for which is the conditional $P(k) \to P(k+1)$ false?

✅ Correct!

P(40)

is true and

P(41)

is false, so

(\forall k \in \mathbb{N})\,(P(k) \to P(k+1))

is false and no inductive step can ever be proved.

❌ Not quite.

1601

is the value at

n = 40

40^2 - 40 + 41 = 1601

. At

n = 41

the last two terms cancel.

❌ Close, but…

1681

is the right value, but

41^2 - 41 + 41 = 41^2 = 41 \cdot 41

, which is not prime.

❌ Not quite.

1763

is the value at

n = 42

42^2 - 42 + 41 = 1763

. At

n = 41

the value is

41^2

❌ Not quite.

P(39)

is true (

1523

is prime) and

P(40)

is true (

1601

is prime), so

P(39) \to P(40)

is true.

❌ Not quite.

P(41)

is false, and a conditional with a false hypothesis is true, so

P(41) \to P(42)

is true.

❌ Not quite.

P(42)

is false (

1763 = 41 \cdot 43

), so the conditional

P(42) \to P(43)

has a false hypothesis and is true.

❌ Not quite. Substitute

n = 41

41^2 - 41 + 41 = 41^2

❌ Not quite. A conditional is false only when its hypothesis is true and its conclusion is false.

Show solution

The value at $n = 41$ . The last two terms cancel:

41^2 - 41 + 41 = 41^2 = 1681 = 41 \cdot 41,

so $1681$ is not prime and $P(41)$ is false.

The failing conditional. $P(k) \to P(k+1)$ is false exactly when $P(k)$ is true and $P(k+1)$ is false.

$k = 39$ : $P(39)$ ( $1523$ , prime) and $P(40)$ ( $1601$ , prime) are both true, so the conditional is true.
$k = 40$ : $P(40)$ is true and $P(41)$ is false, so the conditional is false.
$k = 41$ and $k = 42$ : $P(41)$ and $P(42)$ are false ( $1763 = 41 \cdot 43$ ), so both conditionals are true.

Since the inductive step must hold for every $k$ , including $k = 40$ , it cannot be proved. Forty true cases are evidence, not a proof.

Problem 4 · The Same Proof for $6 \mid (7^n - 1)$

Given: $P(n)\colon 6 \mid (7^n - 1)$ . In the inductive step, assume $7^k - 1 = 6m$ for some integer $m$ .

Then $7^{k+1} - 1 = 6s$ for which integer $s$ ?

Which congruence states the same proposition? ( $a \equiv b \pmod n$ means $n \mid (a - b)$ .)

✅ Correct!

7^{k+1} - 1 = 7(6m + 1) - 1 = 42m + 6 = 6(7m + 1)

, and

6 \mid (7^n - 1)

says exactly that

7^n \equiv 1 \pmod 6

❌ Close, but… the

7

multiplies both terms of

6m + 1

7(6m + 1) - 1 = 42m + 7 - 1 = 42m + 6

❌ Not quite.

6m + 1

7^k

, from the hypothesis. The goal needs

7^{k+1} - 1 = 7 \cdot 7^k - 1

written as

6

times an integer.

❌ Check the sign.

7(6m + 1) - 1 = 42m + 6 = 6(7m + 1)

; the factor

4m - 1

in the

3 \mid (4^n + 1)

example came from a different hypothesis.

❌ Not quite.

7^n \equiv 0 \pmod 6

means

6 \mid 7^n

, which is false:

7 = 6 \cdot 1 + 1

❌ Not quite. That means

7 \mid (7^n - 1)

, which is false because

7 \mid 7^n

. The modulus must be

6

❌ Not quite.

7^n \equiv -1 \pmod 6

means

6 \mid (7^n + 1)

; already

7 + 1 = 8

is not a multiple of

6

❌ Not quite. Write

7^{k+1} - 1 = 7 \cdot 7^k - 1

and substitute

7^k = 6m + 1

❌ Not quite.

6 \mid (7^n - 1)

is the definition of

7^n \equiv 1 \pmod 6

Show solution

Inductive step. From $7^k - 1 = 6m$ we get $7^k = 6m + 1$ . Since $7^{k+1} = 7 \cdot 7^k$ ,

7^{k+1} - 1 = 7 \cdot 7^k - 1 = 7(6m + 1) - 1 = 42m + 7 - 1 = 42m + 6 = 6(7m + 1).

So $s = 7m + 1$ , an integer, and $6 \mid (7^{k+1} - 1)$ .

Congruence form. By definition, $7^n \equiv 1 \pmod 6$ means $6 \mid (7^n - 1)$ , so the proposition is: for every $n \in \mathbb{N}$ , $7^n \equiv 1 \pmod 6$ . The congruence proof mirrors the video's: $7 \equiv 1 \pmod 6$ gives $P(1)$ , and multiplying $7^k \equiv 1 \pmod 6$ by $7 \equiv 7 \pmod 6$ gives $7^{k+1} \equiv 7 \pmod 6$ ; since $7 \equiv 1 \pmod 6$ , transitivity gives $7^{k+1} \equiv 1 \pmod 6$ .

Solved: 0 / 4

Why Both Steps Matter: Proving 4 Divides 5ⁿ − 1

IKey Formulas

IIVisualization 1 — Which Step Fails?

IIIVisualization 2 — The Know-Show Table for 4∣(5k+1−1)4 \mid (5^{k+1} - 1)4∣(5k+1−1)

IVVisualization 3 — Two Proofs, One Link

VQuiz Questions

IIIVisualization 2 — The Know-Show Table for $4 \mid (5^{k+1} - 1)$