if n is odd and not divisible by 3, then f(n) =
2p + p2 ≡ 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 2p + p2
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 + nq-1.
Here q – 1 ≡ –1 (mod q), while nq – 1 ≡ 1 (mod q) by Fermat's little theorem; thus, in this more general setting g(n) = (q - 1)n + nq-1 ≡ –1 + 1 = 0 (mod q). We see that the only way g(n) = (q - 1)n + nq-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
2p + p2 = (2p - 2) + 3 + (p2 - 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,
2p - 2 = 22k+1 - 2 = 2(22k - 1) = 2(4k - 1),
which is divisible by 4 – 1 = 3 because 4k - 1 = (4 - 1)(4k-1 + 4k-2 + ··· + 4 + 1). (Alternatively, one can use induction on k, as Collignon did, to prove that 4k = 3K + 1 for some integer K.) Since 3 is by definition divisible by 3, it remains to show that p2 - 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 p2 - 1.