LINEAR RECURRENCE SEQUENCES SATISFYING CONGRUENCE CONDITIONS

It is well-known that there exist integer linear recurrence sequences {x(n)} such that x(p) = x(1) (mod p) for all primes p. It is less well-known, but still classical, that there exist such sequences satisfying the stronger condition x(p)n = x(p)n-1 (mod p(n)) for all primes p and n >= 1, or even m vertical bar Sigma(d)vertical bar(m) mu(m/d)x(d) for all m >= 1. These congruence conditions generalize Fermat's little theorem, Euler's theorem, and Gauss's congruence, respectively. In this paper we classify sequences of these three types. Our classification for the first type is in terms of linear dependencies of the characteristic zeros; for the second, it involves recurrence sequences vanishing on arithmetic progressions; and for the last type we give an explicit classification in terms of traces of powers.