# Showing $F_{\frac{p^2+1}{2}}\equiv p-1 \pmod{p}$ when $p\equiv \pm 2 \pmod{5}$ and $p\equiv 3 \pmod{4}$

A while back I was messing around with representations of finite fields and found this problem above while doing so. I'll explain below how I came to this point but my question is:

Question: How would one show $$F_{\frac{p^2+1}{2}}\equiv p-1 \pmod{p}$$ when $p\equiv \pm 2 \pmod{5}$ and $p\equiv 3 \pmod{4}$?

Here $F_n$ represents the $n$th Fibonacci number and $p$ is a prime.

Motivation: It's a theorem of Gauss that when $p\equiv \pm 2 \pmod{5}$ then the equation $f(x)=x^2-x-1$ has no root in the field $\mathbb{F}_p$. To remedy this, we give a matrix $M$ with characteristic polynomial $f(x)$ and define a representation of $\mathbb{F}_{p^2}\cong \mathbb{F}_p[x]/(f(x))$ into the matrix ring $M_2(\mathbb{F}_p)$ by taking $M$ to be a root of $f$ (everything else the natural choice). A suitable matrix is:

$$M=\begin{pmatrix}1& 1\\ 1& 0 \end{pmatrix}$$

and observe, also by a known result,

$$M^n=\begin{pmatrix} 1 & 1 \\ 1 & 0 \end{pmatrix}^n=\begin{pmatrix} F_{n+1} & F_n \\ F_n & F_{n-1} \end{pmatrix} \pmod{p}$$

Here is where I obtained the above question (with many calculations to verify this for at least all primes less than 1,000 satisfying the given conditions).

• Can you prove that the roots of $x^2-x-1$ are non-squares in $\mathbb{F}_{p^2}$ ? Then, the claim will be easy, because you will see that these roots (call them $h$) satisfy $h^{\left(p^2-1\right)/2}=-1$, whence the matrix $M$ satisfies $M^{\left(p^2-1\right)/2}=-I_2$ (where $I_2$ is the $2\times 2$ identity matrix), whence its top-left entry $F_{\left(p^2+1\right)/2}\mod p$ is $-1$. – darij grinberg Sep 19 '15 at 19:50
• Ah, OK, I see why the roots of $x^2 - x - 1$ are non-squares in $\mathbb{F}_{p^2}$. In fact, let $h$ be a root of $x^2 - x - 1$. Assume that $h$ is a square in $\mathbb{F}_{p^2}$. Thus, $h = u^2$ for some $u \in \mathbb{F}_{p^2}$. Consider this $u$. The second root of $x^2 - x - 1$ must be a conjugate of $h$ (since $x^2 - x - 1$ is irreducible), and thus equals $h^p$. Now, $hh^p = -1$ (by Viete, since $h$ and $h^p$ are the two roots of $x^2 - x - 1$). That is, $h^{p+1} = -1$. Since $h = u^2$, this rewrites ... – darij grinberg Sep 19 '15 at 20:12
• ... as $u^{2\left(p+1\right)} = -1$. In other words, $\left(u^{p+1}\right)^2 = -1$. Now, $u^{p+1}$ is the Galois norm of $u$ and therefore lies in $\mathbb{F}_p$. Hence, $-1$ is the square of an element of $\mathbb{F}_p$. But this contradicts the fact that $-1$ is a quadratic nonresidue in $\mathbb{F}_p$ (since $p \equiv 3 \mod 4$). So we are done. – darij grinberg Sep 19 '15 at 20:13
• Actually here is a faster way to $h^{\left(p^2-1\right)/2} = -1$ (where $h$ is any root of $x^2 - x - 1$): The Frobenius automorphism is a field endomorphism of $\mathbb{F}_p$. Thus, $h^p$ is also a root of $x^2 - x - 1$. Since $h$ is not an element of $\mathbb{F}_p$ (since $x^2 - x - 1$ is irreducible over $\mathbb{F}_p$), we have $h^p \neq h$, and therefore the two roots $h$ and $h^p$ of $x^2 - x - 1$ are distinct. Thus, $h$ and $h^p$ are precisely the two roots of $x^2 - x - 1$. Therefore, Viete shows that $hh^p = -1$. In other words, $h^{p+1} = -1$. Taking this ... – darij grinberg Sep 19 '15 at 20:16
• ... to the $\left(p-1\right)/2$-th power, we obtain $h^{\left(p+1\right)\left(p-1\right)/2} = \left(-1\right)^{\left(p-1\right)/2} = -1$ (since $\left(p-1\right)/2$ is odd (since $p \equiv 3 \mod 4$)). In other words, $h^{\left(p^2-1\right)/2} = -1$. – darij grinberg Sep 19 '15 at 20:17

Given the constraints, we have that $\mathbb{F}_p[x]/(x^2-x-1)\simeq \mathbb{F}_{p^2}$.
$$F_n = \frac{1}{\sqrt{5}}\left(\sigma^n-\overline{\sigma}^n\right)\tag{1}$$ where $\sigma,\overline{\sigma}$ are the roots of the characteristic polynomial $x^2-x-1$. In the previous finite field/quotient ring such roots are represented by $x$ and $x^p$.
By Lagrange's theorem we have $x^{p^2-1}=1$, and since $p\equiv -1\pmod{4}$, we also have $x^{\frac{p^2-1}{2}}\equiv -1$, because Viète's theorem gives $x^{p+1}=x\cdot x^p \equiv -1$.
That implies: $$F_{\frac{p^2+1}{2}}\equiv\frac{1}{\sqrt{5}}\left(\sigma^{\frac{p^2-1}{2}}\cdot\sigma-\overline{\sigma}^{\frac{p^2-1}{2}}\cdot\overline{\sigma}\right)\equiv-\frac{1}{\sqrt{5}}\left(\sigma-\overline{\sigma}\right)\equiv-1\tag{2}$$ as wanted.