2
$\begingroup$

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}$?

$\endgroup$
3
  • $\begingroup$ Being quadratic, your example is irreducible iff it does not have roots in the field. So the quadratic formula tells you in this case. $\endgroup$
    – Colin McLarty
    Mar 3, 2015 at 16:45
  • $\begingroup$ Note that a polynomial can be irreducible in the integers but reducible mod $p$ for every prime $p$. $\endgroup$
    – André Nicolas
    Mar 3, 2015 at 17:00
  • $\begingroup$ 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)$. $\endgroup$
    – Jyrki Lahtonen
    Mar 4, 2015 at 6:32

1 Answer 1

Reset to default
2
$\begingroup$

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

$\endgroup$
2
  • $\begingroup$ How do you rewrite the polynomial as $(2x -1)^2 - 5$ ? $\endgroup$
    – simon holloway
    Mar 3, 2015 at 17:01
  • 2
    $\begingroup$ 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$. $\endgroup$
    – André Nicolas
    Mar 3, 2015 at 17:03

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.