3
$\begingroup$

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.

$\endgroup$
3
$\begingroup$

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.)

$\endgroup$
  • $\begingroup$ We must exclude the cases p=2 and p=5 $\endgroup$ – DanielWainfleet Apr 5 '16 at 8:12
  • $\begingroup$ The case $p=5$ is already separately discussed. $\endgroup$ – awllower Apr 5 '16 at 8:14
  • $\begingroup$ 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. $\endgroup$ – Israel Meireles Chrisostomo Apr 5 '16 at 9:16
  • $\begingroup$ 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. $\endgroup$ – awllower Apr 5 '16 at 9:35
  • $\begingroup$ This is the point : I have not learned about congruence with fractional remains.Ok, i need study more! Thank's! $\endgroup$ – Israel Meireles Chrisostomo Apr 5 '16 at 9:55
1
$\begingroup$

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.$

$\endgroup$
  • $\begingroup$ 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 {" }$$ $\endgroup$ – Israel Meireles Chrisostomo Apr 6 '16 at 7:56
  • $\begingroup$ 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. $\endgroup$ – DanielWainfleet Apr 6 '16 at 9:03
  • $\begingroup$ 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).$ $\endgroup$ – DanielWainfleet Apr 6 '16 at 9:21
  • $\begingroup$ The summation is equal to $2^{p+1}F(p+1) $ which is $\equiv 4 F(p+1)$ mod $p$. $\endgroup$ – DanielWainfleet Apr 6 '16 at 12:05
  • 1
    $\begingroup$ 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. $\endgroup$ – DanielWainfleet Apr 7 '16 at 1:04

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.