Your weak spots

Insights load after your first practice round.

Module 11 · L09 of 12 ~40 min ⚡ +90 XP available

Divisibility Induction

A cryptographer needs to prove that $7^n - 1$ is divisible by $6$ for every positive integer $n$ — an infinite cascade of claims that no calculator can verify. Mathematical induction is the engine that proves all of them in two short steps. In this lesson you train the divisibility technique: how to manipulate the inductive step so the divisor literally falls out of the algebra.

Today's hook — Check by hand that $7^1 - 1 = 6$, $7^2 - 1 = 48$, and $7^3 - 1 = 342$. Are all three divisible by $6$? Now: do you believe this works for $n = 100$? For $n = 10^9$? Before reading on, write down what you would need to prove — not just check — that $6 \mid 7^n - 1$ for all $n \geq 1$.

0/5QUESTS

Recall — your gut answer first

+5 XP warm-up

You want to prove $6 \mid 7^n - 1$ for all positive integers $n$. Before any algebra — what are the two things mathematical induction asks you to establish, and which one is the harder of the two for a divisibility claim? Write your thinking below.

auto-saved

The two moves for divisibility induction

+5 XP to read

Every divisibility induction proof rewards two habits: name the assumption as an equation (write $f(k) = dM$ for some integer $M$), then rewrite $f(k+1)$ as $q \cdot f(k) + (\text{multiple of } d)$. Once you have that form, the divisor literally falls out by inspection.

The assume-and-rearrange strategy: (1) state $P(k)$: $f(k) = dM$, $M \in \mathbb{Z}$, (2) compute $f(k+1)$ and rewrite it so $f(k)$ appears as a sub-expression, (3) substitute $f(k) = dM$ and factor out $d$ from every term that remains.

$f(k+1) = q\,f(k) + d\,r \Rightarrow f(k+1) = q(dM) + dr = d(qM + r)$

$f(k+1) = q\,f(k) + d\,r$

Name $M$ as an integer

Write the inductive hypothesis as an equation: $7^k - 1 = 6M$, $M \in \mathbb{Z}$. Naming $M$ lets you substitute it cleanly later — never leave the hypothesis as a vague claim.

Engineer $f(k)$ to appear

Manipulate $f(k+1)$ so the expression $f(k)$ literally shows up. For $7^{k+1} - 1$, write it as $7 \cdot 7^k - 1 = 7(7^k - 1) + 6$.

Conclude with a $d \cdot (\text{integer})$

Your final line must read $f(k+1) = d \cdot N$, where $N$ is built from $M$ and other integers. State "$N \in \mathbb{Z}$" — that's the formal close.

What you'll master

Know

Key facts

Induction structure: base case, inductive hypothesis, inductive step, conclusion
Divisibility notation: $d \mid n$ means $n = dM$ for some integer $M$
The rewrite identity $a^{k+1} = a \cdot a^k$ is the engine for $a^n \pm c$ divisibility proofs

Understand

Concepts

Why naming the integer $M$ in the hypothesis is essential — not optional
How to engineer $f(k)$ to appear inside $f(k+1)$ via factoring
Why a divisibility induction always ends with $d \cdot (\text{integer})$, not a numerical residue

Can do

Skills

Prove $a^n - 1$ is divisible by $a - 1$ for any integer $a \geq 2$
Prove polynomial divisibility statements like $3 \mid n^3 + 2n$
Write a clean, examinable induction proof: base, assume, prove, conclude

Key terms

Base caseThe starting value, usually $n = 1$. Verify the statement holds by direct calculation. Without a base case the induction chain has nothing to start from.

Inductive hypothesisThe assumption "$P(k)$ is true for some integer $k \geq 1$". For divisibility, write it as $f(k) = dM$ with $M \in \mathbb{Z}$.

Inductive stepThe proof that "$P(k) \Rightarrow P(k+1)$". For divisibility, this means showing $f(k+1) = d \cdot (\text{integer})$ using the hypothesis.

Divides ($d \mid n$)$d$ divides $n$ means $n = dM$ for some integer $M$. Equivalently, $n / d$ is an integer.

Rewrite identity$a^{k+1} = a \cdot a^k$. Used to engineer $f(k)$ to appear inside $f(k+1)$ when $f$ is an exponential expression.

MEX-P2NESA outcome: proof by mathematical induction, including divisibility, sequences and inequalities — Mathematics Extension 2 syllabus.

The divisibility induction strategy

core concept

Every divisibility induction problem follows the same four-step skeleton — only the algebraic manipulation in step 3 changes:

Base case. Verify $P(1)$ (or the smallest stated $n$) by direct substitution.
Hypothesis. Assume $P(k)$ is true. Write it as an equation: $f(k) = dM$, $M \in \mathbb{Z}$.
Step. Compute $f(k+1)$; rewrite as $f(k+1) = q \cdot f(k) + d \cdot r$; substitute the hypothesis; factor out $d$.
Conclude. "By the principle of mathematical induction, $P(n)$ is true for all integers $n \geq 1$."

Worked through the hook — prove $6 \mid 7^n - 1$ for all $n \geq 1$:

Base ($n=1$): $7^1 - 1 = 6 = 6 \cdot 1$. True.
Hypothesis: Assume $7^k - 1 = 6M$ for some integer $M$.
Step: $7^{k+1} - 1 = 7 \cdot 7^k - 1 = 7(7^k - 1) + 7 - 1 = 7(6M) + 6 = 6(7M + 1)$.
Since $7M + 1 \in \mathbb{Z}$, $7^{k+1} - 1$ is divisible by $6$. By induction, the result holds for all $n \geq 1$. $\blacksquare$

Pattern recognition. Any statement of the form "$a^n - 1$ is divisible by $a - 1$" yields to the same rewrite: $a^{k+1} - 1 = a(a^k - 1) + (a - 1)$. The first term inherits divisibility from the hypothesis; the second is divisible by $a - 1$ by inspection.

Four steps: base, hypothesis (name $M$!), step (rewrite + substitute + factor), conclude · Hypothesis form: $f(k) = dM$, $M \in \mathbb{Z}$ — never skip the "$M \in \mathbb{Z}$" · $6 \mid 7^n - 1$: rewrite $7^{k+1} - 1 = 7(7^k - 1) + 6$ · General: $a^n - 1$ divisible by $a - 1$ uses $a^{k+1} - 1 = a(a^k - 1) + (a-1)$

Pause — copy the four divisibility-induction steps (base, hypothesis naming $M$, step rewriting + factoring, conclusion) and the $6 \mid 7^n-1$ rewrite $7^{k+1}-1 = 7(7^k-1)+6$ into your book.

Quick check: You are proving $3 \mid n^3 + 2n$ by induction. Which is the correct rearrangement of $(k+1)^3 + 2(k+1)$ that lets the hypothesis $k^3 + 2k = 3M$ do its job?

When the divisor changes with $n$

core concept

We just saw the divisibility induction strategy: write $f(k) = dM$ for some $M \in \mathbb{Z}$, rewrite $f(k+1)$ to expose the hypothesis block, and conclude with $d \cdot (\text{integer})$. That raises a question: what happens when the divisor itself contains the variable? This card answers it → the $x - y \mid x^n - y^n$ proof, using the add-and-subtract cross-term trick $x^{k+1} - y^{k+1} = x(x^k - y^k) + y^k(x-y)$.

Some statements look like "$n^n - 1$ is divisible by $n - 1$" or "$x^n - y^n$ is divisible by $x - y$" — the divisor is itself a function of the variables. The strategy is the same, but you treat $x - y$ (or whatever the divisor is) as a fixed constant in the manipulation and produce the answer as $(x - y) \cdot (\text{integer expression})$.

Example: Prove $x - y \mid x^n - y^n$ for all $n \geq 1$ (with $x, y$ integers, $x \neq y$).

Base ($n=1$): $x^1 - y^1 = x - y = (x - y) \cdot 1$. True.
Hypothesis: $x^k - y^k = (x - y)M$ for some integer $M$ (depending on $x, y, k$).
Step: $x^{k+1} - y^{k+1} = x \cdot x^k - y \cdot y^k = x \cdot x^k - x \cdot y^k + x \cdot y^k - y \cdot y^k = x(x^k - y^k) + y^k(x - y)$.
Substitute: $= x \cdot (x-y)M + y^k(x-y) = (x-y)(xM + y^k)$. Integer. $\blacksquare$

$$a^{k+1} - b^{k+1} = a(a^k - b^k) + b^k(a - b)$$

Common mistake. Students compute $x^{k+1} - y^{k+1} = x \cdot x^k - y \cdot y^k$ and then try to factor $(x-y)$ directly — but the cross term is missing. You must add and subtract $x \cdot y^k$ to create the $(x^k - y^k)$ block that the hypothesis applies to.

Variable divisor: treat $x - y$ as a constant during manipulation · Key trick: add and subtract a cross term (e.g. $x \cdot y^k$) to engineer the hypothesis block · $x - y \mid x^n - y^n$ rewrite: $x^{k+1} - y^{k+1} = x(x^k - y^k) + y^k(x - y)$ · Conclusion must always read $(\text{divisor}) \cdot (\text{integer})$

Pause — copy the variable-divisor trick $x^{k+1}-y^{k+1} = x(x^k-y^k)+y^k(x-y)$ and the conclusion form $(x-y) \cdot (\text{integer})$ into your book.

Did you get this? True or false: in the proof that $x - y \mid x^n - y^n$, the manipulation $x^{k+1} - y^{k+1} = x(x^k - y^k) + y^k(x - y)$ relies on adding and subtracting $x \cdot y^k$.

Worked examples · 3 in a row, reveal as you go

PROBLEM 1 · CLASSIC EXPONENTIAL DIVISIBILITY

Prove by mathematical induction that $6 \mid 7^n - 1$ for all positive integers $n$.

Base ($n=1$): $7^1 - 1 = 6 = 6 \cdot 1$, so $6 \mid 7^1 - 1$. True.
Hypothesis: Assume $7^k - 1 = 6M$ for some integer $M$.

Always verify the base case directly. Then state the hypothesis as an equation with a named integer $M$ — never as a vague divisibility claim.

PROBLEM 2 · POLYNOMIAL DIVISIBILITY

Prove by mathematical induction that $3 \mid n^3 + 2n$ for all positive integers $n$.

Base ($n=1$): $1^3 + 2(1) = 3 = 3 \cdot 1$, so $3 \mid 1^3 + 2 \cdot 1$. True.
Hypothesis: Assume $k^3 + 2k = 3M$ for some integer $M$.

Direct substitution at $n=1$, then name the integer $M$ in the hypothesis.

PROBLEM 3 · GENERAL $a^n - 1$ DIVISIBLE BY $a - 1$

Prove by mathematical induction that for any integer $a \geq 2$, $a - 1 \mid a^n - 1$ for all positive integers $n$.

Base ($n=1$): $a^1 - 1 = a - 1 = (a - 1) \cdot 1$, so $a - 1 \mid a^1 - 1$. True.
Hypothesis: Assume $a^k - 1 = (a - 1) M$ for some integer $M$.

$a$ is a fixed integer throughout the proof. Hypothesis names $M$ as the quotient integer.

Fill the gap: In the induction proof that $6 \mid 7^n - 1$, after assuming $7^k - 1 = 6M$, you rewrite $7^{k+1} - 1 = 7(7^k - 1) + 6 = 7(6M) + 6 = 6()$.

Misconceptions to fix · the 3 traps that cost marks

Trap 01

Skipping the "$M \in \mathbb{Z}$" in the hypothesis

Writing "Assume $7^k - 1$ is divisible by $6$" is too vague to substitute. You must write "Assume $7^k - 1 = 6M$ where $M$ is an integer". Without a named integer $M$, the substitution step is meaningless and markers deduct method marks.

Trap 02

Forgetting to state the final form is an integer multiple

After factoring $6(7M + 1)$, you must explicitly say "since $7M + 1 \in \mathbb{Z}$, $6$ divides $7^{k+1} - 1$". Examiners want to see the integer claim made out loud. Just writing $6(7M + 1)$ and stopping costs the final mark.

Trap 03

Confusing the rewrite $a \cdot a^k - 1$ with $a(a^k - 1)$

$a \cdot a^k - 1 \neq a(a^k - 1)$. The correct expansion is $a(a^k - 1) + (a - 1)$ — you forgot the $+ (a - 1)$ when you tried to factor. Always add back the leftover constant when manipulating $a^{k+1} - 1$.

Did you get this? True or false: in the inductive step for $6 \mid 7^n - 1$, the manipulation $7^{k+1} - 1 = 7 \cdot 7^k - 1 = 7(7^k - 1) + 6$ is valid because $7 \cdot 7^k - 7 = 7(7^k - 1)$ and $-1 + 7 = 6$.

Work mode · how are you completing this lesson?

Activities · practice with the ideas

Prove by induction that $5 \mid 6^n - 1$ for all positive integers $n$. Show the base, hypothesis, step, and conclusion clearly.

Prove by induction that $4 \mid 5^n - 1$ for all positive integers $n$.

Prove by induction that $9 \mid 4^n + 6n - 1$ for all positive integers $n$.

Prove by induction that $6 \mid n^3 - n$ for all positive integers $n$.

Prove by induction that $11 \mid 4^{2n+1} + 3^{n+2}$ for all integers $n \geq 0$. (Note: base case here is $n = 0$.)

Odd one out: Three of these statements about the proof that $6 \mid 7^n - 1$ are correct. Which one is NOT?

Revisit your thinking

Earlier you sketched what mathematical induction needs and which of the two steps is harder for divisibility claims.

The two steps are the base case and the inductive step. For divisibility, the inductive step is the hard one: you must engineer $f(k)$ to appear inside $f(k+1)$ via a rewrite like $a^{k+1} = a \cdot a^k$, then substitute $f(k) = dM$, then factor out $d$. Without the named integer $M$ in the hypothesis, the substitution has nothing to grab onto.

auto-saved

Multiple choice

+5 XP per correct · +25 XP all-correct

Pick your answer, then rate your confidence — that tells the system what to drill next. Each retry pulls a fresh mix from the bank.

Short answer

ApplyBand 32 marks

Q1. Prove by mathematical induction that $5 \mid 6^n - 1$ for all positive integers $n$. (2 marks)

auto-saved

ApplyBand 43 marks

Q2. Prove by mathematical induction that $3 \mid n^3 + 2n$ for all positive integers $n$. (3 marks)

auto-saved

AnalyseBand 53 marks

Q3. Prove by mathematical induction that for any integer $a \geq 2$, $a - 1 \mid a^n - 1$ for all positive integers $n$. Then deduce as a special case that $11 \mid 12^n - 1$. (3 marks)

auto-saved

Comprehensive answers (click to reveal)

Activity answers:

1. Base $n=1$: $6-1=5=5\cdot 1$ ✓. Assume $6^k-1=5M$. $6^{k+1}-1 = 6(6^k-1)+5 = 30M+5 = 5(6M+1)$. Integer, so $5 \mid 6^{k+1}-1$. By induction, true for all $n \geq 1$.

2. Base: $5-1=4$ ✓. Assume $5^k-1=4M$. $5^{k+1}-1 = 5(5^k-1)+4 = 20M+4 = 4(5M+1)$. ∎

3. Base: $4+6-1=9$ ✓. Assume $4^k+6k-1=9M$. $4^{k+1}+6(k+1)-1 = 4\cdot 4^k + 6k+5 = 4(4^k+6k-1) - 24k+4+6k+5 = 4(9M) - 18k+9 = 9(4M-2k+1)$. ∎

4. Base: $0=6\cdot 0$ ✓. Assume $k^3-k=6M$. $(k+1)^3-(k+1) = (k^3-k)+3k(k+1) = 6M+3k(k+1)$. Now $k(k+1)$ is product of consecutive integers, so even: $k(k+1)=2L$. So $3k(k+1)=6L$. Total $=6(M+L)$. ∎

5. Verify: $4^{2\cdot 0+1}+3^{0+2} = 4+9=13$. So the claim as stated fails at $n=0$ (13 is not divisible by 11). The correct claim is $13 \mid 4^{2n+1}+3^{n+2}$ — students should flag this. (If you assume the intended divisor is $13$: base ✓; assume $4^{2k+1}+3^{k+2}=13M$; step $4^{2k+3}+3^{k+3} = 16\cdot 4^{2k+1}+3\cdot 3^{k+2} = 16(13M-3^{k+2})+3\cdot 3^{k+2} = 16\cdot 13M - 13\cdot 3^{k+2} = 13(16M-3^{k+2})$. ∎)

Q1 (2 marks): Base $n=1$: $6-1=5\cdot 1$ ✓ [1]. Assume $6^k-1=5M$, $M\in\mathbb{Z}$; $6^{k+1}-1=6(6^k-1)+5=5(6M+1)$, integer, so $5 \mid 6^{k+1}-1$. By induction. [1].

Q2 (3 marks): Base $n=1$: $1+2=3$ ✓ [1]. Assume $k^3+2k=3M$ [1]. $(k+1)^3+2(k+1) = (k^3+2k)+3(k^2+k+1) = 3M+3(k^2+k+1)=3(M+k^2+k+1)$, integer multiple of 3 [1].

Q3 (3 marks): Base $n=1$: $a-1=(a-1)\cdot 1$ ✓ [1]. Assume $a^k-1=(a-1)M$. $a^{k+1}-1 = a(a^k-1)+(a-1) = a(a-1)M+(a-1) = (a-1)(aM+1)$ ✓ [1]. Setting $a=12$: $11 \mid 12^n-1$ for all $n \geq 1$ [1].

Boss battle · The Divisibility Forge

earn bronze · silver · gold

Five timed divisibility induction problems. Beat the boss to bank a tier — gold (90% + speed), silver (75%), or bronze (50%). Replays welcome.

⚔ Enter the arena

Science Jump · platform challenge

Climb platforms by answering divisibility induction questions. Lighter alternative to the boss.

Mark lesson as complete

Tick when you've finished the practice and review.

← Lesson 08 Lesson 10 · Series Induction →

Module overview · Extension 2