Problem 1372

1. Assume the contrary: Suppose that for all nonnegative integers $n$, the number $2^{2^n} + a$ is prime. Let $p = 2^{2^n} + a$ be a prime number for some $n$.

2. **Valuation of $p-1$**: Notice that $p - 1 = 2^{2^n} + a - 1$. We need to consider the 2-adic valuation $v_2(p-1)$. Since $a$ is a positive integer greater than 1, $v_2(a-1)$ is well-defined. Let $k = v_2(a-1)$. Then $v_2(p-1) = v_2(2^{2^n} + a - 1) = v_2(a-1) = k$.

3. **Condition on $n$**: Choose $n$ such that $n > k + 1$. This ensures that $2^n$ is much larger than $k$.

4. **Expression of $2^{2^n}$ modulo $p$**: Since $p = 2^{2^n} + a$ is prime, we have $2^{2^n} \equiv -a \pmod{p}$.

5. **Properties of $-1$ modulo $p$**: It is a well-known fact that $-1$ can be expressed as $x^{2^m} \pmod{p}$ for $m \leq v_2(p-1) - 1$. Since $v_2(p-1) = k$, we have $-1 \equiv x^{2^m} \pmod{p}$ for $m \leq k - 1$.

6. **Expression of $a$ modulo $p$**: Since $a = -2^{2^n} \pmod{p}$, we can write $a \equiv x^{2^m} \pmod{p}$ for $m \leq k - 1$. This implies $a^{\text{odd}} \equiv -1 \pmod{p}$ for some odd exponent.

7. Choosing the odd exponent: We can choose the odd exponent to be of the form $2^x - 1$ for $x > 1$. Thus, we have $a^{2^x - 1} \equiv -1 \pmod{p}$.

8. **Raising to the power $2^x$**: This implies $a^{2^x} \equiv -a \pmod{p}$. Substituting $a = -2^{2^n}$, we get $(-2^{2^n})^{2^x} \equiv -a \pmod{p}$.

9. Simplifying the expression: This simplifies to $2^{2^{n+x}} \equiv -a \pmod{p}$. Since $x > 1$, let $m = n + x$. Then $m > n$ and we have $2^{2^m} + a \equiv 0 \pmod{p}$.

10. Conclusion: This implies that $2^{2^m} + a$ is divisible by $p$, and hence it cannot be prime (since it is greater than $p$ and divisible by $p$).

Therefore, our initial assumption that $2^{2^n} + a$ is prime for all $n$ is false. Hence, for some nonnegative integer $n$, the number $2^{2^n} + a$ is not prime.

$\blacksquare$