*if n is odd and not divisible by *3*, then f(n) =
2*^{p} + p^{2} ≡ 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^{2}
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} + 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} + n^{q-1} ≡ –1 + 1 = 0 (mod *q*). We see that the only way *g(n) = (q - 1)*^{n} + 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} = (2^{p} - 2) + 3 + (p^{2} - 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* = 2*k* + 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} = 3*K* + 1 for some integer *K*.) Since 3 is by definition divisible by 3, it remains to show that p^{2} - 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^{2} - 1.