Prove by mathematical induction that $\forall n \in \mathbb{N}: 20~|~4^{2n} + 4$ Prove by mathematical induction that $\forall n \in \mathbb{N}: 20~|~4^{2n} + 4$
Step 1: Show that the statement is true for n = 1:
$4^{2 \cdot 1} + 4 = 20$
Since $20~|~20$, the base case is completed.
Step 2: Show that if the statement is true for n = p, it is true for n = p + 1:
The general idea I had here was to try to get $4^{2(p+1)} + 4$ to look like the original statement, perhaps multiplied with a factor or a sum where each group of terms were divisible by 20.
$4^{2(p+1)} + 4 = 4^{2p+2} + 4$
By one of the exponential rules, we have:
$4^{2p+2} + 4 = 4^{2p} \cdot 4^{2} + 4$
At this point, we could use one of the 16 powers of 4 and together with the 4 term and show that this was divisible by 20, but there does not seem to be any clear reason why $20~|~4^{2p} \cdot 15$. The number $4^{2p}$ always have an even exponent and $4 \cdot 5 = 20$, but not sure how to proceed from here. Any suggestions?
 A: Try 
$$4^{2p+2}+4=16(4^{2p} +4)-60.$$
Remark: From a number-theoretic point of view, an approach like the one of BRIC-Fan is more natural. It is enough to prove that $4^{2n-1}+1\equiv 0\pmod{5}$. Note that $4\equiv -1\pmod{5}$. So we want to show that $(-1)^{2n-1}+1\equiv 0\pmod{5}$. In principle one proves this by induction. But since $-1$ to an odd power is $-1$, one can view the result as obvious.
A: hint:$4^{2n} + 4 = 4(4^{2n-1}+1^{2n-1}) = 4\cdot (4+1)\cdot (4^{2n-2} - 4^{2n-3} + \cdots + 1)$
A: We have
$$4^{2p}\cdot 4^2 + 4 = \color{blue}{ 4^{2p}\cdot 15} +\color{red}{4^{2p} + 4}$$
Now look at the red and blue part separately.
A: We assume that it is true for $n=p$, then $20|4^{2p} + 4$ so we can write $4^{2p} + 4$ as a product of 20 times an integer say, n, i.e. $4^{2p} + 4=20n$. Then,
$$4^2 (4^{2p} + 4)= 4^2 (20n) \\ 4^{2(p+1)} + 4^3 =4^2 (20n) \\  4^{2(p+1)} + (64 -60) +60 =4^2 (20n) \\ 4^{2(p+1)} +4 = 20 \cdotp 16 \cdotp n -60 \\ 4^{2(p+1)} +4 =20(16n-3)$$
and since $16n-3$ is an integer, then $20| 4^{2(p+1)} +4$, which completes the proof by induction.
A: $$\begin{align} {\bf Hint}\qquad  \color{#0a0}{a^{\large 2}}\ &\:\color{#0a0}{\equiv\, a},\qquad\quad\ \, \color{0a0}{P(1)}\\[.2em]
\ \ a^{\large2\color{#c00}n}&\equiv\, a,\qquad\quad\  \color{c00}{P(\color{#c00}n)}\\[.2em] 
\overset{\times}\Longrightarrow\ \ \, a^{\large 2n+2}&\equiv\, \color{#0a0}{a^2\equiv a},\ \ \ P(n\!+\!1)\\[.2em]
 {\rm OP\ is\ }  \ a\equiv -4\!\!\!&\pmod{\!20}\end{align}\qquad\quad$$
See here and here for more in such idempotent elements.
A: If $f(n)=4^{2n}+4$
$f(m+1)-a\cdot f(m)=\cdots=4^{2m}(4^2-a)+4(1-a)$
If we set $4^2-a=0\iff a=16,f(m+1)-16\cdot f(m)=+4(1-16)\equiv0\pmod{20}$
If we set $1-a=0\iff a=1,f(m+1)-f(m)=4^{2m}(16-1)\equiv0\pmod{20}$ for $m\ge1$
$\implies20|f(m+1)\iff20|f(m)$
