# Lucas numbers modulo m

The Lucas numbers $L(n)$ are defined by $L(0)=2$, $L(1)=1$, and $L(n)=L(n-1)+L(n-2)$, for $n\ge2$. Looking at the sequence $\{L(n)\}$ modulo various numbers, we are lead to conjecture that $\{L(n) \mod m\}$ contains a complete residue system modulo $m$ if and only if $m$ is one of the following: $2, 4, 6, 7, 14, 3^k$, $k\ge1$. Example: Modulo 5 we have the sequence $2,1,3,4,2,1,\dots$, and since the sequence repeats we never obtain $0 \mod 5$. Example: Modulo 6 we have $2,1,3,4,1,5,0,\dots$ and we obtain a complete residue system $\mod 6$.

The corresponding problem for the Fibonacci sequence was solved by S. A. Burr in "On Moduli for Which the Fibonacci Sequence Contains a Complete System of Residues," Fibonacci Quarterly, December 1971, pp. 497-504. The sequence $\{F(n) \mod m\}$ contains a complete residue systems modulo $m$ if and only if $m$ is one of $5^k, 2\cdot5^k, 4\cdot5^k, 3^j\cdot5^k, 6\cdot5^k, 7\cdot5^k, 14\cdot5^k$, $k\ge0$, $j\ge1$.

Although 40 years later, I don't find that anyone has looked at the Lucas version. If someone supplies a reference or a proof, I would appreciate it. Thank you.

• For what values of $k$ do you know that it is a complete residue system modulo $3^k$? – Will Sawin Mar 19 '12 at 15:31
• I've tested the conjecture by computer for all m up to 3^5. ---M.E. – Martin Erickson Mar 19 '12 at 15:58

• Your argument goes both ways: the Lucas sequence is a complete set of residues mod $m$ iff the Fibonacci sequence is, and $m\mid L(n)$ for some $n$ (because then $L(n+1)$ must be coprime to $m$). Thus, in order to confirm the conjecture, it is enough to show that for every $k$, there is $n$ such that $3^k\mid L(n)$. – Emil Jeřábek Mar 19 '12 at 17:12
• Since $L(n)=\phi^n+(-\phi)^{-n}$, where $\phi=(1+\sqrt5)/2$, this is in turn equivalent to: for every $k$, there is $n$ such that $(-(3+\sqrt5)/2)^n\equiv-1\pmod{3^k}$, where the computation is done in the extension $\mathbb Z_3[\sqrt5]$ of the $3$-adic integers. – Emil Jeřábek Mar 19 '12 at 17:27
• @Martin: Indeed. $3\mid F_n$ iff $4\mid n$, and $3\mid L_n$ iff $n\equiv2\pod4$; in particular, $F_n$ and $L_n$ are never both divisible by $3$. Thus, if $n>0$ is smallest such that $3^k\mid F_n$, then $n$ is even, and $3^k\mid L_{n/2}$. – Emil Jeřábek Mar 21 '12 at 17:47