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

If you know about Fermat little theorem then :

If p is prime and (a, p)=1 (that means they are co-prime), then $a^{p-1}equiv 1 mod (p)$

In your question $p=19$ and 2 is co-prime to 19 that is $(2, 19)=1$ so we can write:

$2^{19-1}equiv 1 mod (19)$

$2^{18}=(2^6)^3equiv 1 mod(19)$

We can conclude following congruence:

$(2^6)^{2 n} equiv 1 mod(19)=19 t+1$; $ t ∈mathbb N$

Therefore:

$2^{2^{6k+2}}=2^{6^{2k}}times 2^4=16times(19t+1)$

Finally:

$2^{2^{6k+2}}+3=19(16t)+16+3=19(16t+1)$

That is $19|2^{2^{6k+2}}+3$

Solving with pari/gp.

For $2^xequiv -3pmod{19}$ we have

m=Mod(2,19);h=znorder(m)=18 and znlog(-3,m,h)=4.

I.e. $2^{6k+2}=xequiv 4pmod{18}implies 2^{6k+1}equiv 2pmod{9}$.

For $2^yequiv 2pmod{9}$ we have

m=Mod(2,9);h=znorder(m)=6 and znlog(2,m,h)=1.

I.e. $6k+1=yequiv 1pmod{6}$.

Thus $kin$0,1,2,3,...

We just need to find $2^{2^{6k+2}} pmod {19}$ for natural $k$.

We have $2^{18} equiv 1 pmod {19}$ by Fermat's Little Theorem.

Hence we need to find $2^{6k+2} pmod {18}$.

We have $2^{6k+2} equiv 0 pmod 2$ and $2^{6k+2} = 4 times 64^k equiv 4 pmod 9$.

By Chinese Remainder Theorem, $2^{6k+2} equiv 4 pmod {18}$.

Hence $2^{2^{6k+2}} equiv 2^4 equiv 16 pmod {19}$, thus showing that $19 mid 2^{2^{6k+2}} +3$.

Modulo $19$ we have $2^{2^2}=2^4=16equiv-3$ (the $k=0$ base step) and$$(-3)^{64}=9^{32}equiv5^{16}equiv6^8equiv(-2)^4=16equiv-3,$$proving by induction $2^{2^{6k+2}}equiv-3$ since $(2^{2^{6j+2}})^{2^6}=2^{2^{6j+2}2^6}=2^{2^{6(j+1)+2}}$ (the inductive step from $k=j$ to $k=j+1$).

The sequence $a_j=3^{2^j}bmod 19$ (so $a_{j+1}=a_j^2bmod 19$) goes like this (starting with $j=0$): $$3,color{green}9,5,6,17,4,16,color{green}9 $$ and from here on repeats (except for the initial $3$).

---

The sequence $b_j=2^{2^j}bmod 19$ (so $b_{j+1}=b_j^2bmod 19$) goes like this (starting with $j=0$): $$2,color{green}4,16,9,5,6,17,color{green}4 $$ and from here on repeats (except for the initial $2$).