M
hscscience Ext 2 · Y12
0/100daily goal
0
0
0 due
0
L1 · 0 XP
KJ
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
1
You are here

Recall, your gut answer first

Start with the warm-up and record your first reasoning.

01
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
2

The two moves for divisibility induction

Orient yourself to the lesson goals, language, and core approach.

02
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)$

Divisibility induction flow as a sequence
$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.
03
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
04
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.
3

The divisibility induction strategy

Work through the concept and complete its check.

05
The divisibility induction strategy
core concept

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

  1. Base case. Verify $P(1)$ (or the smallest stated $n$) by direct substitution.
  2. Hypothesis. Assume $P(k)$ is true. Write it as an equation: $f(k) = dM$, $M \in \mathbb{Z}$.
  3. Step. Compute $f(k+1)$; rewrite as $f(k+1) = q \cdot f(k) + d \cdot r$; substitute the hypothesis; factor out $d$.
  4. 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?

4

When the divisor changes with $n$

Build the next proof move and complete its check.

06
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$.

5

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

Follow the worked examples, then complete the check.

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$.

1
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.
1 of 3
PROBLEM 2 · POLYNOMIAL DIVISIBILITY

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

1
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.
1 of 3
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$.

1
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.
1 of 3

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 = 6Q$, where $Q =$ .

6

Misconceptions to fix · the 3 traps that cost marks

Correct the common traps and test your understanding.

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$.

7

Revisit your thinking

Complete the practice activities and revisit your opening thinking.

Activities · practice with the ideas

1

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

2

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

3

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

4

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

5

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?

11
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
1

Show what you have learned

Multiple choice, then short answer under exam conditions.

01
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.

02
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].