Divisibility of $(4^{2^{2n+1}}-3)$ by 13. The question is to simply proof that $13\space|(\space4^{2^{2n+1}}-3)$ for all $n\in\mathbb{N}$. Since the chapter in my book is about the Euler-phi function and Euler's theorem, my guess would be to look at $4^{2^{2n+1}}\equiv3\space \pmod{13}$ and do something with Euler's theorem. Another guess is to solve this by induction, but in both approaches I am very stuck.
As you correctly note, to compute 
$$
4^{2^{2n+1}} \pmod{13}
$$
you can compute
$$
2^{2n+1} \pmod{12}.
$$
It is advisable to use CRT, and compute separately modulo $3$ and modulo $4$.

Modulo $3$ you have 
$$
2^{2n+1} \equiv (-1)^{2n+1} \equiv -1 \pmod{3},
$$
whereas modulo $4$ you have 
$$
2^{2n+1} \equiv 0 \pmod{4},
$$
for $n \ge 1$.

Therefore 
$$
2^{2n+1} \equiv 8 \pmod{12}.
$$
(This usually implies solving the system of congruences
$$
\begin{cases}
x \equiv -1 \pmod{3}\\
x \equiv 0 \pmod{4}\\
\end{cases}
$$
but in this case it is just a matter of checking which of $x = 0, 4, 8$ is a solution.)

Thus
$$
4^{2^{2n+1}} \equiv 4^8 \equiv 3^4 \equiv 3  \pmod{13}
$$
as $4^2 = 16 \equiv 3 \pmod{13}$ and $3^3 = 27 \equiv 1 \pmod{13}$.
You can prove this by induction.



First, show that this is true for $n=0$:

$4^{2^{2\cdot0+1}}=13+3$

Second, assume that this is true for $n$:

$4^{2^{2n+1}}=13k+3$

Third, prove that this is true for $n+1$:

$4^{2^{2(n+1)+1}}=$

$4^{2^{2n+2+1}}=$

$4^{2^{2n+1+2}}=$

$4^{2^{2n+1}\cdot2^2}=$

$4^{2^{2n+1}\cdot4}=$

$(\color\red{4^{2^{2n+1}}})^4=$

$(\color\red{13k+3})^{4}=$

$28561k^4+26364k^3+9126k^2+1404k+81=$

$28561k^4+26364k^3+9126k^2+1404k+78+3=$

$13(2197k^4+2028k^3+702k^2+108k+6)+3$



Please note that the assumption is used only in the part marked red.