Complete Residue Systems for Lucas Numbers
B. Avila, Y. Chen

Introduction

In 1971, Burr proved the complete set of moduli $m$ for which the Fibonacci numbers $(F_n)_{n=0}^\infty$ contain a complete set of residues to be all $m$ taking the following forms: $5^k,\,2\cdot 5^k,\,3^j\cdot 5^k,\,4\cdot 5^k,\,6\cdot 5^k,\,7\cdot 5^k,\,14\cdot 5^k\text{ for }k\geq 0,\,j\geq 1.$

For example, the reduction of the Fibonacci numbers modulo 5 yields the sequence $0, 1, 1, 2, 3, 0, 3, 3, 1, 4, \ldots$, where every residue is seen. But when reducing the sequence modulo $8$, we find the repeating pattern $0, 1, 1, 2, 3, 5, 0, 5, 5, 2, 7, 1, 0, \ldots$, which does not contain $4$ or $6$.

The Lucas numbers $(L_n)_{n=0}^\infty$ are defined with the same recursion as the Fibonacci numbers ($L_n=L_{n-1}+L_{n-2}$), but with starting values $L_0=2$ and $L_1=1$. Here we explore the Lucas numbers, and those moduli for which the same property is seen. For the sake of brevity, we will call the moduli $m$ for which the Fibonacci numbers and Lucas numbers contain all the residues mod $m$, Fibonacci-complete and Lucas-complete, respectively.

The theorem discussed in this paper was first conjectured by Erickson in 2011.

Main Result

Theorem. The Lucas-complete moduli are those of the following forms: $2,\,4,\,6,\,7,\,14,\,3^k\text{ for }k\geq 0.$

First, we observe that the Lucas sequence modulo 5 is ($2, 1, 3, 4, 2, 1, 3, 4, \ldots$), in which no multiple of 5 appears. Thus it follows that if $m$ is a multiple of 5, then $m$ is not Lucas-complete. Also observe that if $m$ is Lucas-complete, then $L_r\equiv 0\pmod m$ for some $r$. We present the following lemmas.

Lemma 1. If $L_r\equiv 0\pmod m$ and $L_{r+1}\equiv k\pmod m$, then $\gcd(m, k)=1$.

Proof. Let $g=\gcd(m, k)$. Because $g$ divides these two consecutive terms in the sequence, it follows by straightforward induction that $g$ divides every term in the Lucas sequence. But $L_1=1$, so $g$ divides $1$, which implies that $g=1$.

Lemma 2. If $m$ is Fibonacci-complete and $L_r\equiv 0 \pmod m$ for some $r$, then $m$ is Lucas-complete. If $m$ is Lucas-complete, then $m$ is Fibonacci-complete.

Proof. For this proof, we will work in $\mathbb{Z}/m\mathbb{Z}$. First, suppose that $m$ is Fibonacci-complete and that $L_r=0$, and let $k=L_{r+1}$. Then it follows by induction that $L_{r+n}=kF_n$ for all $n\geq 0$, that is, each term in the tail $(L_{n+r})_{n=0}^\infty$ is $k$ times the corresponding term in $(F_n)_{n=0}^\infty$. In addition, we have $\gcd(m, k)=1$ by Lemma 1. Therefore, if $(F_n)_{n=0}^\infty$ contains a complete residue system, then so does $(kF_n)_{n=0}^\infty=(L_{n+r})_{n=0}^\infty$. This proves the first statement.

Now suppose that $(L_n)_{n=0}^\infty$ contains a complete residue system. Then so does the tail $(L_{n+r})_{n=0}^\infty$, because $(L_n)_{n=0}^\infty$ is completely periodic. We have now that $(k^{-1}L_{n+r})_{n=0}^\infty=(F_n)_{n=0}^\infty$ also contains a complete residue system. This proves the second statement.

At this point, it follows that if $m$ is Lucas-complete, then $m$ is of the form $2,\,4,\,6,\,7,\,14,\,3^k\text{ for }k\geq 0.$ It remains to show that all of the above moduli are indeed Lucas-complete. By Lemma 1, it suffices to show that there is a Lucas number divisible by $m$, for each of the above values of $m$.

It is easy to check that $1$, $2$, $4$, $6$, $7$, and $14$ have this property. We simply write out the sequences to show that $1\mid L_0$, $2\mid L_0$, $4\mid L_3$, $6\mid L_6$, $7\mid L_4$, and $14\mid L_{12}$. It remains to show that $3^k$ divides some Lucas number for all $k\geq 1$. We first make use of the following lemma.

Lemma 3. If $a$ and $b$ are real numbers such that both $a+b$ and $ab$ are integers, and if $k$ is a positive integer such that $3^k\mid a+b$, then $3^{k+1}\mid a^3+b^3$.

Proof. Write $a^3+b^3=(a+b)(a^2-ab+b^2)=(a+b)((a+b)^2-3ab)$. Since $3^k\mid a+b$ and $3\mid (a+b)^2-3ab$, it follows that $3^{k+1}$ divides their product, that is, $a^3+b^3$.

We now claim that if $3^k\mid L_r$ for some positive integer $r$, then $3^{k+1}\mid L_{3r}$. This follows from Lemma 3 once we write $L_r$ in its closed form $\alpha^r+\beta^r$, where $\alpha=(1+\sqrt5)/2$ and $\beta=(1-\sqrt5)/2$. By hypothesis, $3^k\mid \alpha^r+\beta^r$, and by definition, $\alpha^r+\beta^r=L_r\in\mathbb Z$ and $\alpha^r\beta^r=(-1)^r\in\mathbb Z$, so we may invoke Lemma 3 to find that $3^{k+1}\mid\alpha^{3r}+\beta^{3r}=L_{3r}$, which proves the claim.

Since $3\mid L_2=3$, by induction, $3^k$ divides some Lucas number for every positive integer $k$, and the theorem is proven.

Brandon Avila is a first-year student at Massachusetts Institute of Technology, and plans to double major in Mathematics and Physics.
Yongyi Chen is also a first-year student at MIT, and plans to major in a combination of Mathematics and Computer Science.