Proof of Generalized Little Theorem of Fermat


Every linear recurrence (with integer coefficients) is effectively a pseudo-primality test. This is simply a slight generalization of Fermat's Little Theorem, np = 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 r1, r2, ..., rd of f(x). In other words,



where the coefficients bj are constants determined by the arbitrary initial values of the sequence. For example, if we set bj = 1 for all j, then the value of sn 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 s0 = d and s1 = c1. By the multinomial theorem we know that if p is a prime then the coefficient of every cross-product 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 r1p, r2p,.., rdp. Thus we have



where the summation is evaluated over all sets of non-negative integers {aj} where each aj is less than p and Σ aj = 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 sp = s1 (mod p) for every prime p. In fact, it proves that skp = sk (mod p) for any integer k and prime p.


Any composite integer c such that skc = sk (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 x2 - x - 1 is 705. The smallest such composite relative to Perrin's cubic x3 - x - 1 is 27664033. The smallest relative to the quintic x5 - x3 - 2x2 + 1 is 2258745004684033.


Return to MathPages Main Menu