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

  • 2
    $\begingroup$ 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$. $\endgroup$ – darij grinberg Sep 19 '15 at 19:50
  • 2
    $\begingroup$ 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 ... $\endgroup$ – darij grinberg Sep 19 '15 at 20:12
  • 2
    $\begingroup$ ... 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. $\endgroup$ – darij grinberg Sep 19 '15 at 20:13
  • 2
    $\begingroup$ 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 ... $\endgroup$ – darij grinberg Sep 19 '15 at 20:16
  • 2
    $\begingroup$ ... 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$. $\endgroup$ – 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}$.

The explicit formula for Fibonacci numbers give:

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


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.