Solution for October 2010

Answer. p must be 3; more precisely, if p is a prime number, then f(p) = 2^p + p² is also prime if and only if p = 3.

Most of the submitted solutions were based on computations involving integers modulo 3, as follows. Readers who are unhappy with modular arithmetic can skip to the end where we look at an alternative approach.
Proof.
When p = 2, f(2) = 4 + 4 = 8, which is not prime; when p = 3, f(3) = 8 + 9 = 17, which is prime. It remains to show that for primes greater than 3, f(p) is a proper multiple of 3.
Let p be any prime number greater than 3. Since 2 ≡ –1 (mod 3) and p is odd,

Since we take p > 3 and prime, p ≡ ±1 (mod 3) (because it cannot be 0 (mod 3)), whence

p² ≡ (±1)² ≡ 1 (mod 3).

We conclude that f(p) = 2^p + p² ≡ -1 + 1 ≡ 0 (mod 3); that is, for primes greater than 3, 2^p + p² is divisible by 3. Since f(p) > 3 and is divisible by 3, it is therefore not prime.

Generalizations. Two of our correspondents observed that the above argument makes little use of p being prime. With no extra effort Straszak proved, more generally, that

if n is odd and not divisible by 3, then f(n) = 2^p + p² ≡ 0 (mod 3).

In other words, when n is not divisible by 3, f(n) is divisible by 3. But we have also, when n is even so is f(n). Thus, the only way 2^p + p² can be prime is for n to be an odd multiple of 3 or for n = 1 (in which case f(1) = 3). We compute that f(9) = 593, which is prime; and so are f(15) and f(21). But the pattern does not continue:

f(27) = 73·521·3529

is not prime; when n > 1 it follows that for f(n) to be prime, it is necessary that n be an odd multiple of 3, but not sufficient. Of course our problem is the special case when n is prime — 3 is the only prime that is an odd multiple of 3.

Lim proved that what works for 3, works also for an arbitrary odd prime:

If q > 2 is prime, then for any odd n that is not a multiple of q, q divides

g(n) = (q - 1)ⁿ + n^q-1.

Here q – 1 ≡ –1 (mod q), while n^{q – 1} ≡ 1 (mod q) by Fermat's little theorem; thus, in this more general setting g(n) = (q - 1)ⁿ + n^q-1 ≡ –1 + 1 = 0 (mod q). We see that the only way g(n) = (q - 1)ⁿ + n^q-1 could be prime is for n to be 1 (g(1) = q) or an odd multiple of q. Compare this generalization to our problem from April 2004 (where q = 5).

Alternative proof. We conclude with an argument that avoids modular arithmetic. Here is the way Kais proved that when p > 3 is prime, f(p) is divisible by 3. Because

2^p + p² = (2^p - 2) + 3 + (p² - 1),

it suffices to show that all three summands on the right are divisible by 3. Since p is a prime number greater than 3, it must be odd so that we can write it as p = 2k + 1 for some positive integer k. Then,

2^p - 2 = 2^2k+1 - 2 = 2(2^2k - 1) = 2(4^k - 1),

which is divisible by 4 – 1 = 3 because 4^k - 1 = (4 - 1)(4^k-1 + 4^k-2 + ··· + 4 + 1). (Alternatively, one can use induction on k, as Collignon did, to prove that 4^k = 3K + 1 for some integer K.) Since 3 is by definition divisible by 3, it remains to show that p² - 1 is also divisible by 3. Since by assumption p is not divisible by 3, either p – 1 or p + 1 must be, and therefore so must their product, namely p² - 1.