Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Is it possible to find out a general formula for one polynomial of degree $n$ that is irreducible over $\mathbb F_p$ ?

share|cite|improve this question
What’s the quantification on the $n$ and the $p$? – Lubin Nov 25 '12 at 18:36
It looks like there is some useful information in… – Gerry Myerson Nov 26 '12 at 0:13

Markus Nijmeijer and Mike Staring, A formula that produces all, and nothing but, irreducible polynomials in ${\bf Z}_p[x]$, Mathematics Magazine Vol. 61, No. 1, Feb., 1988, pages 41-44, says

Let $p$ be a prime and let $A_p$ denote the collection of all polynomials of degree $2$ or more in ${\bf Z}_p[x]$, then the formula $$F(P(x))=[Q^2(x)\bmod{P(x)}]P(x)+[(1-Q^2(x))\bmod{P(x)}](x^p-x-1),$$ $P(x)$ in $A_p$, generates all irreducible polynomials in ${\bf Z}_p[x]$.

I don't think it's meant to be a practical method for generating irreducible polynomials of a given degree.

EDIT: $Q(x)$ denotes the product of all the nonzero elements of the ring ${\bf Z}_p[x]/(P(x))$. The result rests on a polynomial analogue of Wilson's Theorem.

share|cite|improve this answer
Sorry, what is $Q$ supposed to be? – Martin Brandenburg Nov 26 '12 at 0:31

Partial answer for $n=p$: the polynomial $x^p - x - j$ is irreducible over $Z/p[x]$ for $1 \leq j \leq p-1$ (this was a homework problem when I took Galois theory). In general, of course, one can count the number of irreducible polynomials of any fixed degree (see Lidl and Niederreiter) but finding them is quite hard.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.