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