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.
 A: 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}$.
A: ${\rm mod}\ 13\!:\,\  4^{\large 2^{\Large 2n+1}}\!\!\!= 4^{\large 2\cdot 4^{\Large n}}\!\!= 16^{\large  4^{\Large n}}\!\!\equiv 3^{\large  4^{\Large n}}.\ $ But $\ {3^{\large 4}\!\equiv 3}\ $ so $\ \color{#c00}{3^{\large  4^{\Large n}}\!\!\equiv 3}\ $ by induction, viz.
$$ 3^{\large  4^{\Large n+1}}\!\!\equiv (\color{#c00}{3^{\large  4^{\Large n}}})^{\large 4}\equiv \color{#c00}3^{\large 4}\equiv 3$$
A: First check for $n=0$:
$$4^{2^{2\cdot0+1}}=4^2=16 \equiv 3 \pmod{13}$$
Then assume, that $4^{2^{2k+1}} \equiv 3 \pmod{13}$ for $k\geq 0$
$$4^{2^{2(k+1)+1}}= 4^{2^{2k+1+2}}= 4^{2^{2k+1}\cdot 4}=\left(4^{2^{2k+1}}\right)^4 \equiv 3^4 \pmod{13} \equiv (-4)^2 \pmod{13} \equiv 3 \pmod{13}$$
Using the mathematical induction we've proved that the equation $4^{2^{2n+1}}\equiv3\space \pmod{13}$ is true for all $n\geq 0$
A: Here is another way of viewing the solution.
You are looking at $$4^{2\times 2\times \cdots \times 2}=(4^2)^{2^\cdots}\pmod {13}.$$
You know that $4^2\equiv3\pmod {13}$, $3^2\equiv9\pmod{13}$ and $9^2\equiv (-4)^2\equiv 3\pmod {13}$.
So if the number of twos is odd (which is the case here), then 
$$4^{2^{2n+1}}\equiv 3\pmod {13}.$$
A: By the binomial theorem,
$$
4^{2^{2n+1}}=4^{2\cdot 2^{2n}}=16^{2^{2n}}=(13+3)^{2^{2n}}=13a+3^{2^{2n}}
$$
Now $3^{3} \equiv 1 \bmod 13$ and so we have to compute $2^{2n} \bmod 3$. But this is easy:
$$
2^{2n} = 4^n  \equiv 1^n =1 \bmod 3
$$
Therefore,
$$
4^{2^{2n+1}} \equiv 3 \bmod 13
$$
A: As you are aware from looking at Euler's theorem, exponents follow a cycle of values in modular arithmetic. Euler's theorem tells you that $4$ follows a cycle of at most $\phi(13)=12$ under $\bmod 13$ arthimetic, but you can immediately see that $4$ is a square and so will follow a cycle of at most $6$ (because its root(s) must follow a cycle of $12$).
So we need to find the value of $2^{2n+1} \bmod 6$ to find out where we are in this cycle. Since $4^n\equiv 4 \bmod 6$ for any $n\in \Bbb N$, we can see that likewise $2^{2n+1} \equiv 2 \bmod 6$ for any $n$.
So $4^{2^{2n+1}}\equiv 4^2\equiv 3 \bmod 13$ as required.
A: 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.
