Prove $5 \mid (3^{4n} - 1)$ by induction

Question

I need to prove by induction that $5 \mid 3^{4n} - 1$ for $n \ge 1$. Base case is true, so now I have to prove that $5 \mid 3^{4(n+1)} - 1$.

I did

$$= 3^{4n+4} -1$$ $$= 3^{4n} 3^{4}-1$$

I guess I need to make a $3^{4n}-1$ appear somewhere to use the inductive hypothesis, but I don't know how. Should I use logarithm?

Answer 1

Your goal is to show that $5\mid(3^{4n}-1)$ for all $n\geq 1$, and you already know the base case is true. Now, notice that your claim also amounts to proving that $S(n)$ holds for all $n\geq 1$ where $$ S(n) : 3^{4n}-1=5\ell, \ell\in\mathbb{Z}. $$ The base case holds, as you already observed; thus, assume that $S(k)$ is true for some fixed $k\geq 1$, where $$ S(k) : 3^{4k}-1=5\eta, \eta\in\mathbb{Z}. $$ To be shown is that $S(k+1)$ follows, where $$ S(k+1) : 3^{4(k+1)}-1=5\phi, \phi\in\mathbb{Z}. $$ Starting with the left-hand side of $S(k+1)$, \begin{align} 3^{4(k+1)}-1 &= 3^{4k+4}-1\tag{expand}\\[0.5em] &= 3^4(3^{4k}-1)+80\tag{rearrange}\\[0.5em] &= 3^4(5\eta)+80\tag{by $S(k)$, the ind. hyp.}\\[0.5em] &= 5(3^4\eta+16)\tag{rearrange}\\[0.5em] &= 5\phi,\tag{$\phi=3^4\eta+16, \phi\in\mathbb{Z}$} \end{align} we end up at the right-hand side of $S(k+1)$, completing the inductive step.

By mathematical induction, the claim $S(n)$ is true for all $n\geq 1$. $\blacksquare$

Answer 2

$$3^{4(n+1)}-1=3^{4n}3^4-1$$ $$=3^4(3^{4n}-1)+3^4-1$$ $$=3^4(3^{4n}-1)+80$$

Answer 3

Hint We can replace $3^{4n} 3^4$ with $(3^{4n} - 1) 3^4$ if we add a compensating term.

Additional hint More explicitly, $$3^{4n} 3^4 - 1 = 3^{4n} 3^4 - 3^4 + 3^4 - 1 = (3^{4n} - 1) 3^4 + 3^4 - 1.$$

Answer 4

Without induction:

$$3^{4n}-1=81^n-1^n=(81-1)\left(81^{n-1}+81^{n-2}+\cdots+1\right)$$