# Fibonacci Numbers and Legendre symbol

How to prove congruence below ?

$$F_{p-\left( \frac{5}{p}\right)} \equiv 0 \pmod p$$

Where $\displaystyle \left( \frac{}{}\right)$ is legendre symbol, and $\displaystyle p$ is a prime number.

Below is an approach through algebraic number theory, which I hope is acceptable.
Let $\varphi=\frac{1+\sqrt5}{2}.$ Then $F_n=\frac{\varphi^n-\overline\varphi^n}{\varphi-\overline\varphi}\in\mathcal O:=\mathbb Z[\frac{1+\sqrt5}{2}].$ And we may study the divisibility of $F_n$ in $\mathcal O,$ as the divisibility of two rational integers in $\mathcal O$ is equivalent with the divisibility in $\mathbb Z$.
The case $p=5$ is either checked by $F_5\equiv(\varphi-\overline\varphi)^4\pmod5$ or by direct computation: $F_5=5.$ Also, the case $p=2$ is easily checked by $F_3=2.$
So in the following we suppose that $p$ is a prime different from $2$ and $5.$

Lemma I. $F_p\equiv\left(\dfrac{5}{p}\right)\pmod p.$
Indeed, $F_p\equiv(\varphi-\overline\varphi)^{p-1},$ as $(x-y)^p\equiv(x^p-y^p)\pmod p$ as polynomials. So $F_p\equiv(\sqrt5)^{p-1}=5^{\frac{p-1}{2}}\equiv\left(\dfrac{5}{p}\right)\pmod p$
$\square$

Lemma II. $\varphi\equiv\frac{p+1}{2}(1+\sqrt5)\pmod p.$
Notice that if $x$ is a solution to $2x\equiv(1+\sqrt5)\pmod p,$ then, multiplying both sides by $\frac{p+1}{2},$ we find $x\equiv\frac{p+1}{2}(1+\sqrt5)\pmod p.$ Then the result follows as $\varphi$ is a solution to the above equation.
$\square$

Lemma III. $\overline\varphi^p\equiv(\frac{p+1}{2})^p(1-\sqrt5)^p\equiv(\frac{p+1}{2})(1-(\sqrt5)^{p-1}\sqrt5)=\begin{cases} \varphi&\text{ if }\left(\dfrac{5}{p}\right)=-1\\\overline{\varphi}&\text{ if } \left(\dfrac{5}{p}\right)=1\end{cases}\pmod p.$
The statement itself can be counted as a proof as well.
$\square$

Two more observations: $$\begin{cases}F_{p+1}=\varphi F_p+\overline\varphi^p\\F_{p-1}=\varphi^{-1}F_p-\overline\varphi^p(\frac{\overline\varphi^{-1}-\varphi^{-1}}{\varphi-\overline\varphi})=\varphi^{-1}F_p+\overline\varphi^p\end{cases}.$$ These are easily check by writing out the expressions on both sides.
Finally, we see that, if $\left(\dfrac{5}{p}\right)=1,$ then $F_{p-1}\equiv\varphi^{-1}+\overline{\varphi}=-\overline\varphi+\overline\varphi=0\pmod p,$ while, if $\left(\dfrac{5}{p}\right)=-1,$ then $F_{p+1}\equiv -\varphi+\varphi=0\pmod p.$ Q.E.D.

If there are any errors or inappropriate points, or if you don't understand something, please tell me so that I can improve upon this answer, thanks in advance.
P.S. (In the above discussion the prime $2$ is excluded as there is no $2^{-1}$ in this case, but the case $p=2$ is easily checked.)

• We must exclude the cases p=2 and p=5 – DanielWainfleet Apr 5 '16 at 8:12
• The case $p=5$ is already separately discussed. – awllower Apr 5 '16 at 8:14
• Please, Can you explain for me the manipulation? $$\left(\frac{1-\sqrt5}{2}\right)^p\equiv\frac{1-5^{\frac{p-1}{2}}\times\sqrt5}{2}\pmod p$$ I didn't understand that. – Israel Meireles Chrisostomo Apr 5 '16 at 9:16
• Observe that $x^p+y^p\equiv(x+y)^p\pmod p$ and $a^p\equiv a\pmod p$ if $a$ is prime to $p.$ Notice that here $1/2$ is actually an integer that satisfies $2x\equiv1\pmod p.$ Hope this helps; if not, then tell me again, thanks. – awllower Apr 5 '16 at 9:35
• This is the point : I have not learned about congruence with fractional remains.Ok, i need study more! Thank's! – Israel Meireles Chrisostomo Apr 5 '16 at 9:55

Let $x=(1+\sqrt 5)/2$ and $y=(1-\sqrt 5)/2$. Let $p$ be prime with $2\ne p\ne 5$.Let $q=(p-1)/2.$ We have $F(p)=(x^p-y^p)/\sqrt 5.$

Modulo $p$ we have $$2 F(p)\equiv 2^p F(p)\equiv [(1+\sqrt 5)^p-(1-\sqrt 5)^p]/\sqrt 5.$$ Expanding each of $(1\pm \sqrt 5)$ by the binomial theorem, and using the fact that $$\binom {p}{j}\equiv 0 \pmod p$$ when $1\leq j\leq p-1,$ we obtain $$2 F(p)\equiv 2 \cdot 5^q \pmod p.$$ Now apply the same method to find $2^{p+1}F(p+1)$, which is congruent to $4F(p+1)$ modulo $p$, using the fact that $$\binom {p+1}{j}=\binom {p}{j}+\binom {p}{j-1} \equiv 0 \pmod p$$ when $2\leq j\leq p-1,$ and $\binom {p+1}{1}=\binom {p+1}{p}=p+1\equiv 1 \pmod p.$

$$\text {We obtain }\quad 4 F(p+1)\equiv 2(1+5^q)\pmod p.$$

Therefore $F(p+1)\equiv 0\pmod p$ when $5$ is not a square mod $p$.

And when $5$ is a square mod $p$ we have $F(p+1)\equiv F(p)\equiv 1\pmod p$, so $F(p-1)=F(p+1)-F(p)\equiv 0\pmod p.$

• This is Important, how to prove $$F_{p-1} \equiv 1 \pmod p$$ I think that's valid only when 5 is not a square mod p. You used this when You said: $$\text {"We obtain }\quad 4 F(p+1)\equiv 2(1+5^q)\pmod p\text {" }$$ – Israel Meireles Chrisostomo Apr 6 '16 at 7:56
• With $x=\sqrt 5$ we have $4F(p+1)\equiv$ $\sum_{j=0}^{p+1} \binom {p+1}{j}(x^j-(-x)^j)/x\equiv$ $2 (\binom {p+1}{1}x+\binom {p+1}{p}x^p)/x$ $\equiv 2( 1+5^q)$ because, in the summation, the term in $x^j$ is $0$ when$j$ is even, and is an integer multiple of $p$ when $2\leq j\leq p-1.$ Similar to the method for finding $F(p)$ mod $p$. Do not need to know $F(p-1)$ mod $p$ in advance. – DanielWainfleet Apr 6 '16 at 9:03
• Ran out of edit time. Previous comment should say that the summation is $\equiv \sum_{j=0}^{n+1}A_j x^{j-1}$. And that $A_j=0$ when $j$ is even . And $A_jx^{j-1}$ is an integer multiple of $p$ when $j$ is odd and $3\leq j\leq p-1.$ This leaves only $A_1+A_px^q$ with $A_1=A_p=2(p+1).$ – DanielWainfleet Apr 6 '16 at 9:21
• The summation is equal to $2^{p+1}F(p+1)$ which is $\equiv 4 F(p+1)$ mod $p$. – DanielWainfleet Apr 6 '16 at 12:05
• BTW. Let $F(n_p)$ be the least positive Fibonacci number divisible by the prime $p$. The last time I checked Wikipedia, the conjecture that $p^2$ does not divide $F(n_p)$ was undecided. – DanielWainfleet Apr 7 '16 at 1:04