Power of two plus integer is not prime Is it true that for every integer $k\neq 1$ there exists infinitely many natural numbers $n$ for which $2^{2^n}+k$ is a composite number?
 A: Yes it is true, here is a proof. Suppose that $2^s$ is the highest power of $2$ dividing $k-1$. Suppose also that all but finitely many numbers $2^{2^n}+k$ are primes. Take a very large such prime $p=2^{2^l}+k$, $l>s$. Then the maximal power of $2$ dividing $p-1$ is $2^s$ and $m=\frac{p-1}{2^s}$ is odd. Let $f=\phi(m)$ (the Euler function). Then $2^{ft}\equiv 1 \mod m$ for every $t\ge 1$. Then $2^{ft+s}\equiv 2^s \mod p-1$. Hence $2^{ft+l}=2^l \mod p-1$. Hence $2^{2^{ft+l}}\equiv 2^{2^l} \mod p$ and $2^{2^{ft+l}}+k\equiv 0 \mod p$, so it is never prime for $t\ge 1$. 
 Update 1. One can of course replace $2$ by any natural number $>1$ in the above proof. It is not clear what to do with numbers $m^{n^b}+k$ for fixed $m,n,k$ when $m\ne n$, but see a comment above.
 Update 2.  Actually the case $m\ne n$ is not very difficult either. Take a very large prime $p$ of the form $m^{n^l}+k$. We would like to have infinitely many $b$ such that  $n^b\equiv n^l \mod p-1$. The only thing needed for this is that $GCD(n^l,p-1)=GCD(n^c,p-1)$ for all big enough $c$. That seems to require very little work. 
