---
title: "Induction: 5^n − 1 divisible by 4"
subject: "Theory of Computation"
chapter: 1
key: "semester_3/theory_of_computation:induction-five-power"
source: https://www.bctengineer.com/q/semester_3/theory_of_computation/induction-five-power
site: BCT Engineering
---

# Induction: 5^n − 1 divisible by 4

Theory of Computation · Chapter 1: Introduction

- Asked in: 2071 Chaitra
- Video: [Use Mathematical Induction to show that 5^𝑛−1 is divisible by 4 for all 𝑛≥1.](https://www.youtube.com/watch?v=ph8Ad0jPc54) — Adeel Arif
- Answer checked by Claude Opus 5.5 (high effort) on 2026-10-14
- Page: https://www.bctengineer.com/q/semester_3/theory_of_computation/induction-five-power
- Whole chapter: https://www.bctengineer.com/md/semester_3/theory_of_computation/chapter-1

## Question

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

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

## Answer

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.

```text
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. ∎

## Check yourself

The answer's key points as multiple-choice questions, with the correct option and why.

1. What is the basis case for proving 5^n − 1 divisible by 4 for n ≥ 0?
   A. n = 1: 5 − 1 = 4 only, n = 0 is not needed
   B. n = 0: 5^0 − 1 = 1
   C. n = k: 5^k − 1 = 4m
   D. n = 0: 5^0 − 1 = 0 = 4·0
   Answer: D. The statement starts at n = 0, so the basis is 5^0 − 1 = 0, which is divisible by 4. (Key point: Basis)

2. What does the induction hypothesis assume?
   A. 5^(k+1) − 1 = 4m for some integer m
   B. 5^k − 1 = 4m for some integer m
   C. 5^n − 1 is divisible by 4 for all n
   D. 5^k = 4m for some integer m
   Answer: B. We assume P(k) only, written as 5^k − 1 = 4m, to be used to prove P(k+1). (Key point: Hypothesis form)

3. How is 5^(k+1) − 1 rewritten to use the hypothesis?
   A. 5(5^k − 1) + 4 = 5(4m) + 4 = 4(5m + 1)
   B. 5^k·5 − 1 = 5·4m − 1 = 4(5m) − 1
   C. (5^k − 1)^2 = 16m^2
   D. 5^k + 5 − 1 = 4m + 4
   Answer: A. Writing 5·5^k − 1 = 5(5^k − 1) + 4 isolates the hypothesis term, giving 4(5m+1), a multiple of 4. (Key point: Induction step trick)

## Close variants set in other exams

- [Induction: n⁴ − 4n² divisible by 3](https://www.bctengineer.com/question.md?key=semester_3%2Ftheory_of_computation%3Ainduction-n4-4n2) — Theory of Computation, chapter 1, asked 2×

## Related in Theory of Computation

- [Induction: sum of k·k! = (n+1)!−1](https://www.bctengineer.com/question.md?key=semester_3%2Ftheory_of_computation%3Ainduction-factorial-sum) — Theory of Computation, chapter 1, asked 2×

## Related in other subjects

- [Weak induction; 5^n − 1 divisible by 4](https://www.bctengineer.com/question.md?key=semester_4%2Fdiscrete_structure%3Ainduction-5-power-n-minus-1-divisible-4) — Discrete Structure, chapter 1
- [Operating principle of 3-phase induction motor](https://www.bctengineer.com/question.md?key=semester_4%2Felectrical_machines_i%3Ainduction-motor-operating-principle) — Electrical Machines I, chapter 5
- [Induction: n < 2^n](https://www.bctengineer.com/question.md?key=semester_4%2Fdiscrete_structure%3Ainduction-n-less-than-2-power-n) — Discrete Structure, chapter 1
- [Induction: 3+3·5+3·5²+...+3·5^n](https://www.bctengineer.com/question.md?key=semester_4%2Fdiscrete_structure%3Ainduction-sum-3-times-5-powers) — Discrete Structure, chapter 1, asked 2×