# Prove by induction that $5^n - 1$ is divisible by $4$.

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

How should I use induction in this problem. Do you have any hints for solving this problem?

Thank you so much.

• What do you know about the question or what have you tried? Dec 6 '13 at 7:10
• I have a vague feeling that this question has already been covered on the site.
Dec 6 '13 at 12:37

We prove that for all $n \in \mathbb{N}$, $4 \mid \left( 5^n-1 \right)$. (Notationally, this says $4$ divides $5^n-1$ with a zero remainder).

1. For a basis, let $n=1$. Then $$5^1-1=4,$$ and clearly $4\mid4$.

2. Assume that $5^n-1$ is is divisible by $4$ for $n=k, \, k \in\mathbb{N}$. Then by this assumption, $$4 \mid \left( 5^k-1 \right) \Rightarrow 5^k-1=4m, \, m \in \mathbb{Z}.$$ (This notationally means that $5^k-1$ is an integer multiple of $4$.)

3. Let $n=k+1$. Then \begin{align*} 5^{k+1}-1 &= 5^k \cdot 5-1 \\ &=5^k(4+1)-1 \\ &=4\cdot 5^k+5^k -1 \\ &=4\cdot5^k+4m\\ &=4\left( 5^k+m \right). \end{align*} Since $4\mid4\left( 5^k+m \right)$, we may conclude, by the axiom of induction, that the property holds for all $n \in \mathbb{N}$.

• Nice, clear, clean... a good answer indeed! Dec 6 '13 at 16:53
• this should be the accepted answer Jan 15 '17 at 5:43

First prove the base case $n=1$. Then induct and make use of the fact that $$(5^{n+1}-1) - (5^n-1) = 4 \cdot 5^n$$to conclude what you want.

Without induction, you can use the identity

$$a^n-1=(a-1)(a^{n-1}+a^{n-2}+...+a+1)$$

Of course you would still need induction or something to prove this identity.

• Yes. I removed my comment once I saw your updated answer. To be really pedantic, even in my answer, we still need induction first to show that $5^n$ is an integer, to then claim that $4$ divides $4 \cdot 5^n$.
– user17762
Dec 6 '13 at 7:24

without induction $$5^n-1=(4+1)^n-1$$ $$=4^n+n4^{n-2}+...+1-1$$ the only term in $(1+4)^n$ not being multiplied by a power of $4$ is $1$ but it disappears due to the $-1$.

Why induction? $5^n$ ends in $\dots25$ for $n>1$, so $5^n-1$ ends in $\dots24$.

• Technically, you still need induction to show that $5^n$ ends in $25$ for $n>1$.
– user17762
Dec 6 '13 at 7:17
• @user17762 $25 * 5 = 25 \mod 100$ Dec 6 '13 at 13:48
• @ratchetfreak Technically I think you still need induction to prove the statement about an arbitrary $n$. Of course, using the fact you mention, the induction becomes trivial (like proving by induction that $1^n = 1$ for all $n$ using the fact that 1 is the multiplicative identity.) Dec 6 '13 at 18:48

$\displaystyle{5^{n + 1} - 1 = \left(5^{n} - 1\right)5 + 4}$

it's even more general:

$k$ divides $(k+1)^n-1$ with $k,n \in \mathbb{N}$

simply by modular arithmetic:

$$k+1 = 1 \mod {k} \\ \Downarrow \\(k+1)^n=1 \mod {k}$$

To prove by induction you:

1. Assume the proposition is true for n

2. Show that if it is true for n, then it is also true for n+1

3. Show that it is true for n=1

Then you know that it will be true for all natural numbers.

In this case:

1. Assume $5^n-1$ is divisible by 4

2. Say $m=5^n$, so $m-1$ is divisible by 4

• $5^{n+1}-1$ = $5m - 1$
• $5m - 1$ = $5(m-1) + 4$
• Since $m-1$ is divisible by 4 and 4 is divisible by 4, then this expression is divisible by 4.
3. For $n=1$, $5^1 - 1 = 4$ which is divisible by 4

And there you are...

This isn't by induction, but I think it's a nice proof nonetheless, certainly more enlightening: $\displaystyle 5^n-1=(1+4)^n-1=\sum_{k=0}^n {n\choose k}4^k-1=1+\sum_{k=1}^n {n\choose k}4^k-1=\sum_{k=1}^n {n\choose k}4^k$ which is clearly divisible by $4$.