Proof of Generalized Little Theorem of Fermat 

Every linear recurrence (with integer coefficients) is effectively a pseudoprimality test. This is simply a slight generalization of Fermat's Little Theorem, n^{p} = n (mod p). Consider the general linear recurrence of order d 

_{} 

The characteristic polynomial of this recurrence is 

_{} 

If r is any root of this polynomial then clearly the sequence 

_{} 

satisfies recurrence (1). The general solution of (1) (assuming the roots of (2) are distinct) is just a linear combination of powers of the roots r_{1}, r_{2}, ..., r_{d} of f(x). In other words, 

_{} 

where the coefficients b_{j} are constants determined by the arbitrary initial values of the sequence. For example, if we set b_{j} = 1 for all j, then the value of s_{n} is just the nth "Newton Sum" for f(x), i.e., the sum of the nth powers of the roots. In other words, 

_{} 

In this case s_{0} = d and s_{1} = c_{1}. By the multinomial theorem we know that if p is a prime then the coefficient of every crossproduct term in the expansion of (x+y+..+z)^{p} is divisible by p. (The standard "additive" proof of Fermat's Little Theorem uses this same fact.) It follows immediately that in the expansion of 

_{} 

the coefficient of every term is divisible by p, with the exception of the terms r_{1}^{p}, r_{2}^{p},.., r_{d}^{p}. Thus we have 

_{} 

where the summation is evaluated over all sets of nonnegative integers {a_{j}} where each a_{j} is less than p and Σ a_{j} = p. This sum is a symmetrical sum and product function of the roots of f(x), so it can be expressed in terms of the coefficients of f, which implies that the summation is an integer. As a result, we have 

_{} 

which establishes that s_{p} = s_{1} (mod p) for every prime p. In fact, it proves that s_{kp} = s_{k} (mod p) for any integer k and prime p. 

Any composite integer c such that s_{kc }= s_{k} (mod c) for all positive integers k is called a symmetric pseudoprime relative to f(x). (Note that if the congruence is satisfied for k = 1, 2, ..., d, then it will be satisfied for all k, so these d congruences are a generalization of the "signature" referred to in Shanks and Adams 1982 paper.) The larger the Galois group of a polynomial, the more rare are symmetric pseudoprimes relative to that polynomial. The smallest such composite relative to the Fibonacci polynomial x^{2}  x  1 is 705. The smallest such composite relative to Perrin's cubic x^{3}  x  1 is 27664033. The smallest relative to the quintic x^{5}  x^{3}  2x^{2} + 1 is 2258745004684033. 
