Prove $F_n=2^{2^{k}}+1, F_n=5\mod{12}$for all $n\in\Bbb{N}$

Question

how would you prove that for $F_n=2^{2^{n}}+1, F_n=5\mod{12}$ for all $n\in\Bbb{N}$. I know that you have to use induction to show that if $F_n=2^{2^{n+1}}+1$ then $F_n=5\mod{12}$

Answer 1

Well, $F_{n+1}=(2^{2^{n}})^2+1=(F_n-1)^2+1$. Now use induction.

Answer 2

$$2^{2^k} + 1 \equiv 1 \mod 2$$ $$2^{2^k} + 1 \equiv 2^22^22^2... +1 \equiv 1 \cdot 1 \cdot 1... +1 \equiv 2 \mod 3\text{ by Fermat's little theorem}$$

Therefore, $2^{2^k}+1$ is not $0,2,3,4,6,8,9,10\mod12 $

This leaves us with $1,5,7,11$

$$2^{2^k}+1 \equiv 1 \mod 12$$ This suggests that $2^{2^k}$ is divisible by $12$, which is impossible since $12$ has a $3$ $$2^{2^k}+1 \equiv 7 \mod 12$$ $$2^{2^k} = 12a + 6 = 6(2a+1)$$ This suggests that $2^{2^k}$ is divisible by $6$, which is impossible since $6$ has a $3$. Furthermore, it only has one value of $2$ $$2^{2^k}+1 \equiv 11 \mod 12$$ $$2^{2^k} = 12a + 10 = 2(6a+5)$$ Since this number only has one factor of $2$ in it, it can't be true for all values of $a$ $$2^{2^k}+1 \equiv 5 \mod 12$$ $$2^{2^k} = 12a + 4 = 4(3a+1)$$ This is the only remaining possibility $\mod 12$, therefore it must be true. Furthermore, we can see that it has an infinite factors of $2$ based on the value of $a$

Answer 3

Your base case would just be $n=1$. This is pretty simple:

$F_1 = 2^{2^1}+1=5\equiv 5$ (mod $12$).

Now, we assume the claim holds for $n$ and show it holds for $n+1$.

Consider $F_{n+1}$, which can be written as $2^{2^{n+1}} + 1$. We can rewrite this as:

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

Now, we note $F_n = 2^{2^n}+1$, so $2^{2^n} = F_n - 1$. We know by the inductive hypothesis that $F_n \equiv 5$ (mod $12$), so $2^{2^n} \equiv 5 - 1 \equiv 4$ (mod $12$). Plugging this in ...

$(2^{2^n})^2+1 \equiv 4^2+1 \equiv 17 \equiv 5$ (mod $12$)

And so, we are done