Proving Divisibility

Proving divisibility problems with mathematical induction is common in number theory. The key is to use the properties of divisibility and modular arithmetic.

Basic Knowledge

Proof Strategy

The steps to prove $a | f(n)$:

1. Base case: verify that $a | f(n_0)$
2. Inductive hypothesis: assume $a | f(k)$, i.e., $f(k) = ma$ ($m$ is an integer)
3. Inductive step: express $f(k+1)$ in a form containing $f(k)$, then use the inductive hypothesis

Worked Examples

Example 1: Basic Divisibility

Proposition: prove that $n^3 - n$ is divisible by 6.

Proof:

Base case: when $n = 1$, $1^3 - 1 = 0 = 6 \times 0$, divisible by 6.

Inductive hypothesis: assume $k^3 - k$ is divisible by 6, i.e., $k^3 - k = 6m$ ($m$ is an integer)

Inductive step:

$$\begin{aligned} (k+1)^3 - (k+1) &= k^3 + 3k^2 + 3k + 1 - k - 1 \\ &= k^3 - k + 3k^2 + 3k \\ &= (k^3 - k) + 3k(k + 1) \\ &= 6m + 3k(k+1) \quad \text{(inductive hypothesis)} \end{aligned}$$

Since $k$ and $k+1$ are consecutive integers, one of them must be even, so $k(k+1)$ is even. Let $k(k+1) = 2p$:

$(k+1)^3 - (k+1) = 6m + 3 \times 2p = 6m + 6p = 6(m+p)$

Therefore it is divisible by 6.

Conclusion: by mathematical induction, $n^3 - n$ is divisible by 6 for all $n \geq 1$.

Example 2: Divisibility of a Difference of Powers

Proposition: prove that $7^n - 1$ is divisible by 6.

Proof:

Base case: when $n = 1$, $7^1 - 1 = 6$, divisible by 6.

Inductive hypothesis: assume $7^k - 1$ is divisible by 6, i.e., $7^k - 1 = 6m$

Inductive step:

$$\begin{aligned} 7^{k+1} - 1 &= 7 \cdot 7^k - 1 \\ &= 7(7^k - 1) + 7 - 1 \\ &= 7 \times 6m + 6 \quad \text{(inductive hypothesis)} \\ &= 6(7m + 1) \end{aligned}$$

Therefore it is divisible by 6.

Conclusion: by mathematical induction, $7^n - 1$ is divisible by 6 for all $n \geq 1$.

Example 3: Divisibility in the Fibonacci Sequence

Proposition: the Fibonacci sequence $F_1 = 1, F_2 = 1, F_{n+2} = F_{n+1} + F_n$. Prove that $F_{3n}$ is divisible by 2.

Proof:

First compute the first few terms: $F_1=1, F_2=1, F_3=2, F_4=3, F_5=5, F_6=8, F_7=13, F_8=21, F_9=34$

Base case: when $n = 1$, $F_3 = 2$, divisible by 2.

Inductive hypothesis: assume $F_{3k}$ is divisible by 2.

Inductive step: we need to prove that $F_{3(k+1)} = F_{3k+3}$ is divisible by 2.

Use the property of the Fibonacci sequence: $F_{n+3} = F_{n+2} + F_{n+1} = (F_{n+1} + F_n) + F_{n+1} = 2F_{n+1} + F_n$

Therefore: $F_{3k+3} = 2F_{3k+1} + F_{3k}$

By the inductive hypothesis, $F_{3k}$ is divisible by 2, while $2F_{3k+1}$ is clearly divisible by 2, so $F_{3k+3}$ is divisible by 2.

Conclusion: by mathematical induction, $F_{3n}$ is divisible by 2 for all $n \geq 1$.

Practice Problems

Exercise 1

Prove: $5^n - 1$ is divisible by 4.

Exercise 2

Prove: $n^5 - n$ is divisible by 5.

---

Summary

Symbols Used in This Article

中英对照