7
$\begingroup$

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.

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

Note that if the Lucas sequence modulo m contains a complete set of residues then the Fibonacci sequence must also. (If the Lucas sequence contains 0 followed by d, then it continues as d times the Fibonacci sequence.)

As 5 does not work this rules out all m divisible by 5, checking 2,4,6,7,14 by hand only leaves the powers of 3 undecided.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ 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)$. $\endgroup$ – Emil Jeřábek Mar 19 '12 at 17:12
  • $\begingroup$ 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. $\endgroup$ – Emil Jeřábek Mar 19 '12 at 17:27
  • 1
    $\begingroup$ It looks like we can complete the argument from your ideas, Chris and Emil, using the identity F_{2n}=L_n F_n, the fact that 3^k | F(n) for some n, and the behavior of both sequences mod 3. ---M.E. $\endgroup$ – Martin Erickson Mar 19 '12 at 18:26
  • $\begingroup$ @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}$. $\endgroup$ – Emil Jeřábek Mar 21 '12 at 17:47
  • $\begingroup$ Copied from a deleted answer: @Emil: Exactly! I would call the result pretty, and certainly simpler than the corresponding characterization for Fibonacci numbers. I wonder if, among all generalized Fibonacci sequences, the sequence of Lucas numbers is the one with the simplest description for when it contains a complete residue system modulo an integer. ---M.E. $\endgroup$ – S. Carnahan Mar 25 '12 at 4:45

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.