Skip to main content

Induction: 5^n − 1 divisible by 4

Short answer

Base n=0: 5⁰ − 1 = 0, divisible by 4. Assume 5ᵘ − 1 = 4m. Then 5ᵘ⁺¹ − 1 = 5(5ᵘ − 1) + 4 = 5·4m + 4 = 4(5m+1), divisible by 4.

Use the principle of mathematical induction to prove that (5^n − 1) is divisible by 4 for all integers n ≥ 0.

Let P(n): 5ⁿ − 1 is divisible by 4. We prove P(n) for all n ≥ 0.

Basis (n = 0)

5⁰ − 1 = 1 − 1 = 0 = 4·0, which is divisible by 4. So P(0) is true.

Induction hypothesis

Assume P(k) for some k ≥ 0, i.e. 5ᵏ − 1 = 4m for some integer m.

Induction step

We show that 5^(k+1) − 1 is divisible by 4.

5^(k+1) − 1 = 5·5ᵏ − 1
            = 5(5ᵏ − 1) + 5 − 1
            = 5(4m) + 4            (by hypothesis)
            = 4(5m + 1)

Since 5m + 1 is an integer, 5^(k+1) − 1 is divisible by 4. So P(k+1) is true.

Conclusion

By mathematical induction, 5ⁿ − 1 is divisible by 4 for all n ≥ 0. ∎

✓ Answer checked by Claude Opus 5.5 (high effort)

Related questions

All Theory of Computation chapter 1 questions →