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, 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₁, r₂, ..., 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₀ = d and s₁ = c₁. 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 r₁^p, r₂^p,.., r_d^p. Thus we have

where the summation is evaluated over all sets of non-negative 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₁ (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² − x − 1 is 705. The smallest such composite relative to Perrin's cubic x³ − x − 1 is 27664033. The smallest relative to the quintic x⁵ − x³ − 2x² + 1 is 2258745004684033.

Return to MathPages Main Menu