Question

5. Prove that $19|2^{2^{6k+2}}+3$ for k = 0, 1, 2, .... 

Answer 1

Since $gcd(4,19)=gcd(16,19)$, then by Fermat's Little Theorem, $4^{19-1}\equiv4^{18}\equiv16^{18}\equiv1(mod\ 19)$.

Let $P(k)$ be the statement $2^{2^{6k+2}}\equiv16(mod\ 19)$

Proof by induction on $k$ that $P(k)$ is true for all $k\geq0$:

Base case: Let $k=0$, then $2^{2^{6k+2}}\equiv2^{2^{6\cdot0+2}}\equiv2^{2^2}\equiv16(mod\ 19)$, hence $P(0)$ is true.

Inductive step: Suppose $P(k)$ is true, then $2^{2^{6k+2}}\equiv16(mod\ 19)$, hence

$2^{2^{6(k+1)+2}}\equiv2^{2^{6k+6+2}}\equiv2^{2^{6k+2}\cdot 2^6}\equiv(2^{2^{6k+2}})^{2^6}\equiv\\16^{2^6} \equiv16^{64}\equiv16^{3\cdot18+10}\equiv16^{10}\equiv4^{20}\equiv4^{18+2}\equiv\\ 4^2\equiv16(mod \ 19)$

so $P(k)\implies P(k+1)$.

Thus, by induction, $P(k)$ is true for all $k\geq0.$

Since $2^{2^{6k+2}}\equiv16(mod\ 19)$, then

$2^{2^{6k+2}}+3\equiv16+3(mod\ 19)\equiv19(mod\ 19)\equiv 0(mod\ 19)$, so $19|2^{2^{6k+2}}+3.$