Prove $5 \mid (3^{4n} - 1)$ by induction 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? 
 A: $$3^{4(n+1)}-1=3^{4n}3^4-1$$ $$=3^4(3^{4n}-1)+3^4-1$$ $$=3^4(3^{4n}-1)+80$$
A: 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.$$

A: Without induction:
$$3^{4n}-1=81^n-1^n=(81-1)\left(81^{n-1}+81^{n-2}+\cdots+1\right)$$
A: 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$
