<s>[INST] Calculate modulo of large numbers I have $2^{2^n}+1$ and i want to calculate ($(2^{2^{^n}} +1 )\mod 19$). How can i do it if for example i choose $n = 19$. Can i use Fermat's Little Theorem?
 [/INST] Because $\phi(19)=18$, we have $2^a\equiv 2^b\pmod{19}$ if and only if $a\equiv b\pmod{18}$. This is equivalent to Fermat's Little Theorem.
Hence you need to find a small number $m$ such that $2^n\equiv m\pmod{18}$.
We compute and see the pattern mod 18: $2^1\equiv 2, 2^2\equiv 4, 2^3\equiv 8, 2^4\equiv 16, 2^5\equiv 32\equiv 14, 2^6\equiv 28\equiv 10, 2^7\equiv 20\equiv 2$, and then it repeats.  So $2\equiv 2^1\equiv 2^7\equiv 2^{13}\equiv 2^{19}$.  
Hence $2^{19}\equiv 2\pmod{18}$ and hence $2^{2^{19}}\equiv 2^2\pmod{19}$.
</s>