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)a | f(n):

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

Worked Examples

Example 1: Basic Divisibility

Proposition: prove that n3−nn^3 - n is divisible by 6.

Proof:

Base case: when n=1n = 1, 13−1=0=6×01^3 - 1 = 0 = 6 \times 0, divisible by 6.

Inductive hypothesis: assume k3−kk^3 - k is divisible by 6, i.e., k3−k=6mk^3 - k = 6m (mm is an integer)

Inductive step:

(k+1)3−(k+1)=k3+3k2+3k+1−k−1=k3−k+3k2+3k=(k3−k)+3k(k+1)=6m+3k(k+1)(inductive hypothesis)\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 kk and k+1k+1 are consecutive integers, one of them must be even, so k(k+1)k(k+1) is even. Let k(k+1)=2pk(k+1) = 2p:

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

Therefore it is divisible by 6.

Conclusion: by mathematical induction, n3−nn^3 - n is divisible by 6 for all n≥1n \geq 1.

Example 2: Divisibility of a Difference of Powers

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

Proof:

Base case: when n=1n = 1, 71−1=67^1 - 1 = 6, divisible by 6.

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

Inductive step:

7k+1−1=7⋅7k−1=7(7k−1)+7−1=7×6m+6(inductive hypothesis)=6(7m+1)\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, 7n−17^n - 1 is divisible by 6 for all n≥1n \geq 1.

Example 3: Divisibility in the Fibonacci Sequence

Proposition: the Fibonacci sequence F1=1,F2=1,Fn+2=Fn+1+FnF_1 = 1, F_2 = 1, F_{n+2} = F_{n+1} + F_n. Prove that F3nF_{3n} is divisible by 2.

Proof:

First compute the first few terms: F1=1,F2=1,F3=2,F4=3,F5=5,F6=8,F7=13,F8=21,F9=34F_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=1n = 1, F3=2F_3 = 2, divisible by 2.

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

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

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

Therefore: F3k+3=2F3k+1+F3kF_{3k+3} = 2F_{3k+1} + F_{3k}

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

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

Practice Problems

Exercise 1

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

mathematical inductiondivisibility proof

Approach: Prove the divisibility by mathematical induction: first check the divisibility in the base case, then use the induction hypothesis to obtain the divisibility for n+1n + 1.

Steps:

Base case: when n=1n = 1, 51−1=45^1 - 1 = 4, divisible by 4.

Inductive hypothesis: assume 5k−15^k - 1 is divisible by 4, i.e., 5k−1=4m5^k - 1 = 4m

Inductive step:

5k+1−1=5⋅5k−1=5(5k−1)+5−1=5×4m+4=4(5m+1)\begin{aligned} 5^{k+1} - 1 &= 5 \cdot 5^k - 1 \\ &= 5(5^k - 1) + 5 - 1 \\ &= 5 \times 4m + 4 \\ &= 4(5m + 1) \end{aligned}

Conclusion: by mathematical induction, 5n−15^n - 1 is divisible by 4.

Answer: By mathematical induction, 5n−15^n - 1 is divisible by 4.

Exercise 2

Prove: n5−nn^5 - n is divisible by 5.

mathematical inductiondivisibility proof

Approach: Prove the divisibility by mathematical induction: first check the divisibility in the base case, then use the induction hypothesis to obtain the divisibility for n+1n + 1.

Steps:

Base case: when n=1n = 1, 15−1=01^5 - 1 = 0, divisible by 5.

Inductive hypothesis: assume k5−kk^5 - k is divisible by 5.

Inductive step:

(k+1)5−(k+1)=k5+5k4+10k3+10k2+5k+1−k−1=k5−k+5k4+10k3+10k2+5k=(k5−k)+5(k4+2k3+2k2+k)\begin{aligned} (k+1)^5 - (k+1) &= k^5 + 5k^4 + 10k^3 + 10k^2 + 5k + 1 - k - 1 \\ &= k^5 - k + 5k^4 + 10k^3 + 10k^2 + 5k \\ &= (k^5 - k) + 5(k^4 + 2k^3 + 2k^2 + k) \end{aligned}

By the inductive hypothesis, k5−kk^5 - k is divisible by 5, while 5(k4+2k3+2k2+k)5(k^4 + 2k^3 + 2k^2 + k) is clearly divisible by 5.

Conclusion: by mathematical induction, n5−nn^5 - n is divisible by 5.

Answer: By mathematical induction, n5−nn^5 - n is divisible by 5.


Summary

Symbols Used in This Article

Symbol notation
SymbolTypePronunciation/ExplanationMeaning in This Article
a∣ba \mid bMathematical symbola divides baa divides bb
kkMathematical symbolkAn integer
f(n)f(n)Mathematical symbolf of nA proposition function of nn
n0n_0Mathematical symboln-sub-zeroThe starting value of induction
m,pm, pMathematical symbolm, pIntegers
FnF_nMathematical symbolF-sub-nThe nnth term of the Fibonacci sequence
≥\geqMathematical symbolgreater than or equal toGreater than or equal to

Found an issue with this content?

Tell us what could be improved.