Symmetric Pseudoprimes

Fermat's Little Theorem states that for any integer c, if p is a 
prime, then c^p - c is divisible by p.  This is a necessary but not 
quite sufficient condition for primality, because there are (rare) 
composites that satisfy this type of test for certain values of c.  
For example, 2^341 - 2 is divisible by 341, but 341 is composite.  
That's why 341 is called a "pseudoprime relative to the base 2".  
There are even composites, called Carmichael numbers, that are 
pseudoprimes relative to EVERY integer base.  The smallest 
Carmichael number is 561.

Another way of stating Fermat's Little Theorem is that, given a 
polynomial of the form f(x) = x - c, if p is a prime, then the sum 
of the pth powers of the roots of f is congruent to the sum of the 
first powers (mod p).  Since f has just the single root c, this may 
seem like a trivial re-statement of the previous one.  However, it 
can be immediately generalized to integers of any degree, yielding 
much stronger primality tests.

Take the Fibonacci polynomial x^2 - x - 1, and let a,b denote the 
roots.  The nth term of the Lucas sequence is just L_n = a^n + b^n, 
and so, since a+b = 1, it follows from Fermat's Little Theorem that 
L_p = 1 (mod p) for every prime p.  Any composite number c such 
that L_c = 1 (mod c) is called a pseudoprime relative to the 
polynomial x^2 - x - 1.  The smallest such number is 705.

Most people who have written about generalized psuedoprime tests 
like this have just imposed the congruence condition on the sum of 
the nth powers of the roots, i.e., on the first symmetric function 
of the roots.  I've always thought that the only sensible 
generalization is to impose the appropriate congruence condition 
on ALL symmetric functions of the roots.  Composite numbers that 
satisfy such a test are what I call "symmetric pseudoprimes".  

On this basis, I would state the generalization of Fermat's Little 
Theorem as follows:  

  For any monic polynomial f with integer coefficients, if
  z is a (complex) root of f and p is a prime, then f(z^p)=0 
  (mod p).  A symmetric pseudoprime relative to f is any 
  composite integer c such that f(z^c)=0 (mod c) for every 
  root z of f.

We could also define symmetric pseudoprimes in terms of Newton's
sums for the roots of a polynomial.  Let f denote a monic polynomial 
of degree d with integer coefficients, and let s(k) denote the sum 
of the kth powers of the roots of f.  Lucas observed that s(pk)=s(k) 
(mod p) for every integer k and prime p.

A composite integer N such that s(Nk)=s(k) (mod N) for every positive
integer k is a symmetric pseudoprime relative to f.  For example, the 
smallest symmetric pseudoprime relative to  f(x)=x-2  is  341=(11)(31).  
The relative rarity of these pseudoprimes, along with the fact that 
s(N) (mod N) can be evaluated in O[log(N)] multiplications modulo N, 
makes them useful for primality testing.

Symmetric pseudoprimes tend to be more rare relative to polynomials 
with larger Galois groups. The Galois group of the quintic polynomial 

                  f(x) = x^5 - x^3 - 2x^2 + 1 

is the fully symmetric group S_5.  The smallest symmetric pseudoprime 
relative to this polynomial that is the product of two splitting 
primes is

         N = 2258745004684033 = (27439297)(82317889)

I suspect that this is the smallest symmetric pseudoprime of any 
composition relative to the quintic, but I have not made an exhaustive 
search.  Can anyone confirm or disprove that this is in fact the 
smallest?

For a more detailed discussion, see Symmetric Pseudoprimes.