# Prove $5\mid2^{4n}-1$ by induction

For all $n\ge1$, use mathematical induction to establish each other the following divisibility statements: $$5\mid2^{4n}-1$$

I was wondering if someone could help me with the set up of this proof. I only have done proofs with mathematical induction when I am given a series of numbers and I can incorporate my induction hypothesis in for one of my terms in the series.

• I know the question asks for an induction, but I don't think we have to use the induction, by the way: $2^{4n}-1=(2^4-1)((2^4)^{n-1}+\cdots+1).$ – awllower Feb 9 '14 at 6:53

Since you're new to induction, I'll give the framework and let you fill in the details. The induction step goes something like this:

Suppose that $5| 2^{4n} - 1$, and write $5k = 2^{4n} - 1$. Then

\begin{align*} 2^{4(n + 1)} - 1 &= 2^{4n} \cdot 2^4 - 1 \\ &= (5k + 1) \cdot 16 - 1 \\ &= 5k + 16 - 1 \end{align*}

Can you finish it from here, justifying each step?

• why did you substitute (5k+1)?? wouldn't (2^4n)-1 all just be replaced with 5k? – Lil Feb 10 '14 at 23:30
• @Lil I am replacing $2^{4n}$ only. – user61527 Feb 10 '14 at 23:31

Since you asked for a set-up,

1. Show the statement is true for $n=1$, i.e.

$$5 \ \Big| \ 2^4-1$$

1. Let $n\in\mathbb{N}$ be fixed. Assume for all $k<n$ that

$$5 \ \Big| \ 2^{4k}-1$$

Show that

$$5 \ \Big| \ 2^{4n}-1$$

If $\displaystyle F(k)=2^{4k}-1,$

$\displaystyle F(k+1)-2^4\cdot F(k)=2^{4(k+1)}-1-2^4[2^{4k}-1]=2^4-1=15$

$\displaystyle\implies F(k+1)$ will be divisible by $15,$ (hence by $5$) if $F(k)$ is

Now establish the base case i.e., $k=0$

Hint $\$ Let $\,f_n = 2^{4n}\!-1$. Prove the base case $\,5\mid f_0.\,$ Next prove $\,5\mid \color{#0a0}{f_{n+1}\!-f_n},\,$ therefore $\,5\mid \color{#c00}{f_n}\,\Rightarrow\, 5\mid \color{#0a0}{f_{n+1}\!-f_n}+\color{#c00}{f_n} = f_{n+1},\$ i.e. $\ 5\mid f_n\,\Rightarrow\,5\mid f_{n+1} \,$ (the induction step).

Remark $\$ Unwinding the above telescopic cancellation we can write $\,f_n\,$ as the sum of its differences $\ f_{k+1}-f_k = (16-1) 16^k$ which yields the following simple proof

$$5\mid 16-1\,\Rightarrow\, 5\mid 16^{n}-1\, =\, (16-1)\,(16^{n-1}+\cdots + 16^2 + 16 + 1)$$

See my posts on telescopy for many more examples