# 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?

-
Otherwise, you will get a 'simple formula' for generating infinitely many primes for some $k$, feels not true. –  Chulumba Mar 7 '12 at 19:10
If you square 2 repeatedly modulo a prime p that is 3 mod 4, it cycles through a cyclic group of odd order (soon enough). You probably want to choose p so that it hits the residue class of -k; because then you are done. A proof conditional on the Artin conjecture on primitive roots then looks likely (i.e. on GRH) via quadratic reciprocity and enough on primes in arithmetic progressions. It gets more interesting if it is possible to do something with a small sledgehammer. –  Charles Matthews Mar 7 '12 at 20:02
You've already seen a proof, but you might like to know that many related results (including the one you're after) are discussed in a paper of Shapiro and Sparer: Composite Values of Exponential and Related Sequences (Comm. Pure Appl. Math.), vol. 25, pp. 569--615, 1972. As a corollary of a more general theorem on exponential polynomials, they note the following: "For odd integers $b$, $m^{n^x}+b$ is composite infinitely often except possibly in the case of $m$ even, $b=1$, and $n=2^{\alpha}$. For $b$ even, the only possible exception would be for $m$ odd and $b=2$." –  Anonymous Mar 7 '12 at 22:47
The answer for $2^{2^n}+1$ is unknown? –  Mark Sapir Mar 8 '12 at 23:30
@alberto.bosia: yes I did, but it did not really help in solving the question for every k (other than 1). @Mark Sapir: yes it breaks very nicely (besides being very nice in general) –  quid Mar 9 '12 at 0:54
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.