Linear recurrence sequences satisfying congruence conditions

Abstract

It is well-known that there exist integer linear recurrence sequences $\{x_n\}$ such that $x_p \equiv 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} \equiv x_{p^{n-1}}$ (mod $p^n$) for all primes $p$ and $n \ge 1$, or even $m \mid \sum _{d \mid m} \mu (m/d) x_d$ for all $m \ge 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.