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.

  • $\begingroup$ See Exercise 2.26 in "Reciprocity Laws. From Euler to Eisenstein". Google books displays the page 73. $\endgroup$ – franz lemmermeyer Mar 26 at 14:52
  • $\begingroup$ @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. $\endgroup$ – Seewoo Lee Mar 26 at 14:58
  • $\begingroup$ Robin Chapman found such a proof, which essentially boiled down to computing quadratic Gauss sums, so he did not publish it. $\endgroup$ – franz lemmermeyer Mar 26 at 16:34
  • $\begingroup$ @franzlemmermeyer That's sad...anyway thank you very much. $\endgroup$ – Seewoo Lee Mar 26 at 16:52
  • $\begingroup$ Gauss, who discovered the Quadratic Reciprocity Law, gave 5 or 6 different proofs of it. $\endgroup$ – DanielWainfleet Mar 27 at 4:55

I'm just unwinding the proof of quadratic reciprocity using cyclotomic fields.

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


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.