How can I show that $4^{2n}-1$ is divisible by $15 $ for all $n$ greater or equal to $1$ Ok so this is a question from a book that has no included solution and I think I'm on the right way but I just need a little help.
The question is:
Show, for all $n \ge 1$ such that   $4^{2n} - 1$ is divisible by 15.
My solution:
Rewrite it to ${4^2}^n - 1\Rightarrow 16^{n} - 1$ 
Base step: $16^1 - 1 = 15$ works fine
Try with  $n = k + 1 $ for $16^n$: $16^{(k+1)} - 1 = 16^k * 16^1 - 1 = (15+1)^k * (15+1) - 1$
Now I don't know what to do to actually prove it.
 A: We can use arithmetic rules in the ring $\mathbb{Z}_{15}.$ We  have $$16=1\quad {\rm mod }\ 15$$ Raising to the power $n$ gives $$16^n=1\quad {\rm mod}\  15$$ Hence $16^n-1$ is divisible by $15.$
A: Hint: $a^n-b^n= (a-b)(a^{n-1} + a^{n-2} b + \ldots + b^{n-1})$.
A: $16^n-1=(1+15)^n-1=(1+ {n \choose 1}15+{n \choose 2}15^2\cdots+15^n)-1$ (By Binomial theorom)
$={n \choose 1}15+{n \choose 2}15^2\cdots+15^n)=15({n \choose 1}+{n \choose 2}15\cdots+15^{n-1}))$
which is divisible by $15$ for all $n\geq1$
A: $$ 4^{2n}-1 = 16^n-1=(15+1)^n-1=\sum_{k=1}^n{n\choose k}15^k=15m,0<m\in\mathbb{Z}.$$
A: Classic induction:
Base case: When $n=1$, $4^2 -1 = 15 \equiv 0 \pmod{15}$
Let's assume ${4^2}^n - 1 \equiv 0 \pmod{15}$ is true for some n. Then
$$ {4^2}^{(n+1)} - 1 = {4^2}^n.4^2 - 1 = 16({4^2}^n - 1) + 15 \equiv 0 \pmod{15}$$
A: CCRT:  $$4^{2n}\equiv(4^n)^2\equiv 1\pmod 3,$$ and $4^{2n}\equiv(2^n)^4\equiv1\pmod5,$ both by lil' Fermat.
A: Factorization
$$4^{2n}-1=16^n-1$$
This will equal to
$$(16−1)(16^{n−1}+16^{n−2}+\dotsb+1)$$
Since the first bracket is divisible by $5$, and the second bracket is an integer, so we can conclude the expression is divisible by $5$. Hence:
$$4^{2n}=16^n\equiv 1^n\equiv 1 \pmod 5.$$
So the expression is divisible by $5$.
If you want  to prove by induction, this is by far the least efficient method. So I will leave the inductive step to you (the initial step of $n=1$ is trivial $→ 15$ is divisible by $5$.)
A: Assume it to be true for $n=k$, so we will have
$4^2k - 1 = 15q$, for $q \in \mathbb{N}$ ---(1)
Now, for $k+1$, the $$f(k+1) = 4^2(k+1) - 1
= 4^2 \cdot 4^{2k} - 1$$
Now use 1, so we will get
\begin{align*}
f(k+1) & = 16(15q+1)-1\\
       & = 240q+15\\
       & = 15(16q+1)
\end{align*}
which is divisible by $15$.
