On the number of residues of linear recurrences

Abstract

For every nonconstant monic polynomial $g\in \mathbb{Z}[X]$, let $\mathfrak{M}(g)$ be the set of positive integers $m$ for which there exist an integer linear recurrence $(s_n{)}_{n\ge 0}$ having characteristic polynomial $g$ and a positive integer $M$ such that $(s_n{)}_{n\ge 0}$ has exactly $m$ distinct residues modulo $M$. Dubickas and Novikas proved that $\mathfrak{M}(X^2-X-1)=\mathbb{N}$. We study $\mathfrak{M}(g)$ in the case in which $g$ is divisible by a monic quadratic polynomial $f\in \mathbb{Z}[X]$ with roots $\alpha ,\beta$ such that $\alpha \beta =\pm 1$ and $\alpha /\beta$ is not a root of unity. We show that this problem is related to the existence of special primitive divisors of certain Lehmer sequences, and we deduce some consequences on $\mathfrak{M}(g)$. In particular, for $\alpha \beta =-1$, we prove that $m\in \mathfrak{M}(g)$ for every integer $m\ge 7$ with $m\ne 10$ and $4\nmid m$.