Let $$F_{n} = \frac{1}{\sqrt{5}} \left[ \left( \frac{1+\sqrt{5}}{2}\right)^{n} - \left( \frac{1-\sqrt{5}}{2} \right)^{n} \right]$$ be a Fibonacci number. If $$p\neq 2, 5$$ is a prime, then I want to show that $$F_{p} \equiv \left( \frac{p}{5}\right) \mathrm{mod }\,p ,$$ where $$\left( \frac{p}{5}\right)$$ is understood as a Legendre symbol.

My solution is following: I just expand $$F_{n}$$ using the binomial theorem and get $$F_{p} \equiv 2^{p-1}F_{p} \equiv \binom{p}{1} + \binom{p}{3}\cdot 5 + \cdots + 5^{(p-1)/2} \equiv 5^{(p-1)/2} \equiv \left( \frac{5}{p} \right) \equiv \left( \frac{p}{5}\right) \mathrm{mod}\,p$$ Here I used quadratic reciprocity in the last equality. I want to know if there's any alternative proof that does not use quadratic reciprocity and show the congruence directly.

• See Exercise 2.26 in "Reciprocity Laws. From Euler to Eisenstein". Google books displays the page 73. – franz lemmermeyer Mar 26 at 14:52
• @franzlemmermeyer Thanks! Is there any generalization of the proof? Actually, I hope that one can find a family of sequences that can be used to prove quadratic reciprocity. I want to know if this kind of proof is already known or not. – Seewoo Lee Mar 26 at 14:58
• Robin Chapman found such a proof, which essentially boiled down to computing quadratic Gauss sums, so he did not publish it. – franz lemmermeyer Mar 26 at 16:34
• @franzlemmermeyer That's sad...anyway thank you very much. – Seewoo Lee Mar 26 at 16:52
• Gauss, who discovered the Quadratic Reciprocity Law, gave 5 or 6 different proofs of it. – DanielWainfleet Mar 27 at 4:55

Let $$\zeta$$ be a primitive $$5$$-th root of unity, which is a root of the polynomial $$1+x+x^2+x^3+x^4$$. The Fibonacci numbers satisfy $$F_n = \left(\frac{1}{5}+\frac{2}{5}\big(\zeta+\zeta^{-1}\big)\right)\bigg[\big(1+\zeta+\zeta^{4}\big)^n-\big(1+\zeta^2+\zeta^3\big)^n\bigg],$$ which is straightforward to prove by induction. I will write $$\equiv_p$$ for congruence modulo $$p$$. Using the identity $$(x+y)^p\equiv_p x^p+y^p$$, we find $$F_p\equiv_p \left(\frac{1}{5}+\frac{2}{5}\big(\zeta+\zeta^{-1}\big)\right)\bigg[\zeta^p+\zeta^{4p}-\zeta^{2p}-\zeta^{3p}\bigg].$$ Since $$\zeta^5=1$$, the value of $$\zeta^{k}$$ depends only on the residue of $$k$$ mod $$5$$. If $$p\equiv 1$$, $$4$$ mod $$5$$, then $$F_p\equiv_p \left(\frac{1}{5}+\frac{2}{5}\big(\zeta+\zeta^{-1}\big)\right)\bigg[\zeta+\zeta^{4}-\zeta^{2}-\zeta^{3}\bigg]= F_1= 1,$$ while if $$p\equiv 2$$, $$3$$ mod $$5$$, then $$F_p\equiv_p \left(\frac{1}{5}+\frac{2}{5}\big(\zeta+\zeta^{-1}\big)\right)\bigg[\zeta^2+\zeta^{3}-\zeta-\zeta^{4}\bigg]= -F_1= -1.$$