3
$\begingroup$

I found that the Fibonacci numbers $F_n$, taken$ \bmod n$, have the property that, for prime $n\ne 5$, $F_{n-1}$ and $F_{n+1}$ are $0$ and $1$, with the order depending on the value of $n\bmod 5$.

So if prime $n\equiv \pm 1\bmod 5$, $F_{n-1}\equiv 0$ and $F_{n+1}\equiv 1 \bmod n$
If prime $n\equiv \pm 2\bmod 5$, $F_{n-1}\equiv 1$ and $F_{n+1}\equiv 0 \bmod n$

It also turns out this is a fairly reliable test of whether $n$ is prime - that is, there are not many composites passing the test. The first composite number to masquerade as a prime is $4181$, then $5777, 6721, 10877, 13201, 15251$ are the remaining pseudoprimes under $20000$. This sequence is listed under OEIS A212424.

What I haven't been able to do is prove that this property does in fact hold for prime numbers. Can anyone produce a proof of the correctness of this relation?


Greg Martin gave some useful terminology:

The first positive integer $m$ for which $F_m\equiv 0 \bmod n$ is called the "rank of apparition" of $n$

Then ($\equiv \bmod n$) the "apparition multiplier" (my term) $k:\equiv F_{m-1}\equiv F_{m+1}\equiv F_{m+2}$ means that $F_{i+m}\equiv k F_i$ and $F_{i+jm}\equiv k^j F_i$. $k$ must be coprime to $n$ because the Fibonacci sequence can be generated in reverse so some $d\ne 1$ that divides both $k$ and $n$ would preclude $F_1=1$ (since $d$ would divide every element). This guarantees that $F_s\equiv 0 \Rightarrow m\mid s$ and that since at some point $k^j\equiv 1$, we will have the period $r, \bmod n$.

For the result above on primes we need $r\mid n{-}1$ in the first case and $m\mid n{+}1, r\mid 2(n{+}1)$ in the second case.

I was still thinking about what values the rank of apparition $m$ can take and working through http://www.fq.math.ca/Scanned/1-2/vinson.pdf .

$\endgroup$
2
  • 2
    $\begingroup$ Related : math.stackexchange.com/a/37957/78967 $\endgroup$ – mathlove Mar 19 '17 at 7:41
  • 1
    $\begingroup$ The first positive integer $m$ for which $F_m\equiv0\pmod n$ is called the "rank of apparition" of $n$; that will help you search for relevant mathematics. $\endgroup$ – Greg Martin Mar 19 '17 at 7:42
3
$\begingroup$

If $p\equiv \pm 1 \pmod 5$ then $x^2-x-1$ factors as $(x-\phi)(x-\overline{\phi})$ in $\mathbb{F}_p$. Then your identities follow from $$F_n\equiv \frac{\phi^n-\overline{\phi}^n}{\phi - \overline{\phi}} \pmod p$$ since in this case $\phi^{p-1}\equiv 1$ (by Fermat) and $$\phi^{p+1}\equiv \phi^2 \equiv \phi+1$$ and likewise for $\overline{\phi}$.

If $p\equiv \pm 2 \pmod 5$ then the same polynomial factors in $\mathbb{F}_{p^2}$ and the Frobenius automorphism exchanges the roots. That is, $\phi^p=\overline{\phi}$ and $\overline{\phi}^p=\phi$. Your identities now follow from $$\phi^{p-1}\equiv \overline{\phi} \phi^{-1} \equiv -\overline{\phi}^2 \equiv -\overline{\phi}-1$$ and $$\phi^{p+1}\equiv \overline{\phi} \phi \equiv -1$$ and likewise for $\overline{\phi}$.

$\endgroup$
2
  • $\begingroup$ Thanks, can you expand on how these work to produce the identities? $\endgroup$ – Joffan Mar 19 '17 at 18:10
  • $\begingroup$ Added some more details. $\endgroup$ – WimC Mar 19 '17 at 20:42

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.