Factoring Fibonacci polynomials

Question

A numerical evidence given by WA strongly suggests that, when $p$ is an odd prime, the Fibonacci polynomial $F_{p}(x)$ factors mod $p$ explicitly as follows: $$ F_{p}(x) = (x^2+4)^{\frac{p-1}{2}} $$

I've love to see a proof. You may want to start here.

The factorization above can be refined as follows:

• If $p \equiv 1 \bmod 4$, then $x^2+4=(x-a)(x+a)$, where $a^2 \equiv -4 \bmod p$.

• If $p \equiv 3 \bmod 4$, then $x^2+4$ is irreducible mod $p$.

but this is well known.

Answer 1

As mentioned in the "Identities" section of the Wikipedia article you linked to, one has for all $n$ $$ \sqrt{x^2 + 4}F_n(x) = (\alpha(x) - \beta(x))F_n(x) = \alpha(x)^n - \beta(x)^n $$ where $$ \alpha(x) = \frac{x + \sqrt{x^2 + 4}}{2} \quad \text{and} \quad \beta(x) = \frac{x - \sqrt{x^2 + 4}}{2}. $$ Thus when $p$ is an odd prime number we have in $\mathbb{Z}_p(x)[\sqrt{x^2 + 4}]$ $$ \sqrt{x^2 + 4}F_p(x) = \alpha(x)^p - \beta(x)^p = (\alpha(x) - \beta(x))^p = \sqrt{x^2 + 4}^p. $$

The used explicit formula for $F_n(x)$ can be derived by diagonalizing the matrix of the recurrence relation as N. S. did. Alternatively, it can be proved by induction. A proof by induction is shorter, but does not provide the insight that the matrix approach does (i.e. it does not show how one would every come up with such a formula).

Answer 2

Attempted solution, I think that this works:

The case $p=2$ is easy, so let us set $p \neq 2$.

Consider the recurrence $$F_{n+1}(X)=XF_{n}(X)+F_{n-1}(X)$$ in the field $\mathbb Z_p(X)$.

Then, by a standard argument $$\begin{bmatrix} F_{n+1}(X) \\ F_n(X) \end{bmatrix}=\begin{bmatrix} X & 1 \\1 &0 \end{bmatrix} ^n \begin{bmatrix} F_{1}(X) \\ F_0(X) \end{bmatrix}$$

The characteristic equation of $\begin{bmatrix} X & 1 \\1 &0 \end{bmatrix} $ is $$Y^2-XY-1=0$$ with solutions $$Y=\frac{X \pm \sqrt{X^2+4}}{2}$$ either in $\mathbb Z_p(X)$ or in an algebraic extension $\mathbb Z_p(X) \subseteq K$ of degree 2.

Since the eigenvalues are distinct, by Diagonalizing the matrix we get $$\begin{bmatrix} F_{p+1}(X) \\ F_p(X) \end{bmatrix}=P\begin{bmatrix} \left(\frac{X + \sqrt{X^2+4}}{2}\right)^p & 0 \\0 &\left(\frac{X - \sqrt{X^2+4}}{2}\right)^p\end{bmatrix} P^{-1} \begin{bmatrix} F_{1}(X) \\ F_0(X) \end{bmatrix}$$

Now, using the Frobenius homomorphism we get $$\begin{bmatrix} F_{p+1}(X) \\ F_p(X) \end{bmatrix}=P\begin{bmatrix}\frac{X^p + (X^2+4)^\frac{p}{2}}{2^p} & 0 \\0 &\frac{X^p - (X^2+4)^\frac{p}{2}}{2^p}\end{bmatrix} P^{-1} \begin{bmatrix} F_{1}(X) \\ F_0(X) \end{bmatrix}$$

Now, if everything works nicely, when we calculate $P,P^{-1}$ explicitly (this can likely be done with software) you get the desired result.