A064539 All...are divisible by 3 but why?

[Simon Nickerson]

On Thu, 23 Jun 2005, zak seidov wrote:
> Dear seqfans,
> A064539= (*Numbers n such that 2^n+n^2 is
> prime*){1,3,9,15,21,33,2007,2127,3759,29355,34653,57285,99069}All
> except first are divisible by 3 but why? zak

Let f(n) = 2^n+n^2. Each integer n can be written uniquely as n=6k+l with
0<=l<=5.

f(n) = f(6k+l)
     = 2^(6k+l) + (6k+l)^2
     = 4^k 2^l + l^2 (mod 6)

Now if k>1, then 4^k = 4 (mod 6) (4*4=16=4 (mod 6), then use induction),
so the residue of f(6k+l) mod 6 is 4,3,2,5,2,3 for l=0..5. If k=1, then
the residues turn out to be 1,3,2,5,2,3.

Now if p>3 is prime, then p is congruent to 1 or 5 modulo 6. It is clear
that f(n)>3 if n>1. So if f(n) is prime, n must be equal to 1 or congruent
to 3 modulo 6 (i.e. odd and divisible by 3).

-- 
| Simon Nickerson            http://web.mat.bham.ac.uk/S.Nickerson
| simonn at maths.bham.ac.uk                    School of Mathematics
|                                     The University of Birmingham
|_________________________________   Edgbaston, Birmingham B15 2TT