# Finding primes such that a given polynomial is irreducible modulo $p$

Let $f \in \mathbb{Z}[x]$ be irreducible, and let $\bar{f} \in \mathbb{F}_{p}[x]$ be the image of $f$ in the polynomial ring over the finite field with $p$ elements. Is there a general procedure, given $f$ to find the primes $p$ such that $\bar{f}$ is irreducible over $\mathbb{F}_{p}$?

More specifically, the polynomial I am interested in is the 'Fibonacci polynomial' $\phi(x) = x^2 - x - 1$. For which primes is $\bar{\phi}$ irreducible over $\mathbb{F}_{p}$?

• Being quadratic, your example is irreducible iff it does not have roots in the field. So the quadratic formula tells you in this case. Mar 3, 2015 at 16:45
• Note that a polynomial can be irreducible in the integers but reducible mod $p$ for every prime $p$. Mar 3, 2015 at 17:00
• Undoubtedly you know this but there is a connection between this factorization modulo $p$ and the period of the sequence you get by reducing Fibonacci numbers modulo $p$ (assume $p\neq2,5$). If the polynomial factors, the period is a factor of $p-1$. Otherwise it's a factor of $2(p+1)$. Mar 4, 2015 at 6:32

We look only at the specific polynomial $x^2-x-1$ mentioned in the OP. Let $p$ be odd. The polynomial is irreducible modulo $p$ if and only if the congruence $x^2-x-1\equiv 0$ has no solutions modulo $p$. This congruence can be rewritten as $(2x-1)^2-5\equiv 0\pmod{p}$, and has a solution if and only if $5$ is a quadratic residue modulo $p$.
Now we do a Legendre symbol calculation, using Quadratic Reciprocity. We have $(5/p)=(p/5)$. If $p\ne 5$, then $(p/5)=1$ if and only if $p\equiv \pm 1\pmod{5}$.
So the odd primes other than $5$ for which $x^2-x-1$ is irreducible modulo $p$ are the primes $\equiv \pm 2\pmod{5}$. It is easy to deal separately with $p=2$ and $p=5$.
• How do you rewrite the polynomial as $(2x -1)^2 - 5$ ? Mar 3, 2015 at 17:01
• Not the polynomial, the congruence. For odd primes $p$ we have $x^2-x-1\equiv 0\pmod{p}$ iff $4x^2-4x-4\equiv 0\pmod{p}$. Complete the square. We have $4x^2-4x-4=(2x-1)^2-5$. Mar 3, 2015 at 17:03