Mathacadabra
Home > Discussions > Number Theory
Note: this page uses MathJax for formatting, so may take a few seconds to load.


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.

Note: This article is scheduled to appear in the Fibonacci Quarterly, and appears here by permission of the journal's editor.

Acknowledgements
The authors would like to thank Dr. Martin Erickson for his support in reviewing and refining this paper to completion.

References
  1. S. A. Burr , "On Moduli for Which the Fibonacci Sequence Contains a Complete System of Residues", Fibonacci Quarterly, December 1971, pp. 497-504.
  2. M. Erickson , Beautiful Mathematics, Mathematical Association of America, 2011, p. 132.