Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

Suppose $p$ and $q$ primes and $p$ is odd. Then, are there nice and clever ways to factorize polynomials of the form $$f(x)=1+x+\cdots +x^{p-1}$$ in the ring $\mathbb{F}_q[x]$ ? What about the case when $q=2$ ?

I know that there are factorization algorithms but they are too general. I want to know if there are clever ways to do this for these special type of polynomials. Like for example, in $\mathbb{F}_2$ one might add terms $x^r+x^r$ and rearrange them so that $f(x)$ gets factorized.

In case there are no good methods to factorize, are there nice ways to check whether $f(x)$ is irreducible in $\mathbb{F}_q[x]$ ?

share|cite|improve this question
Since $q^{p-1}-1$ is divisible by $p$, $x^{q^{p-1}}-x$ is divisible by $x^p-1=(x-1)(1+x+x^2+\dots+x^{p-1})$. In general, $x^{q^n}-x$ is divisible by exactly the prime polynomials of degree $d|n$. Therefore, the only prime factors of $1+x+\dots +x^{p-1}$ can be primes of degree $d|p-1$. Not sure where that leads you, however. – Thomas Andrews Jul 1 '13 at 16:48
The general theory is described in Dtseng's (+1) answer. A similar approach will see you home for all exponents $p$ (even non-prime) as long as $\gcd(p,q)=1$. See this answer to a related question. In the case $p$ prime you get the extra bit that all the irreducible factors of $f(x)$ will have the same degree. A noteworthy observation is that $f(x)$ is irreducible, if and only if $q$ is a primitive element of $\mathbb{F}_p^*$. – Jyrki Lahtonen Jul 2 '13 at 14:00
It just occured to me that the algorithm for finding the idempotents of cyclic codes of length $p$ with alphabet $\mathbb{F}_q$ can be tweaked to produce a factorization as well. It is easy to give a spanning set of idempotents of the ring $R=\mathbb{F}_q[x]/(x^p-1)$. Then multiplying them in $R$ allows us to find the basic idempotents. The basic idempotents $e(x)$ have the property that $(x^p-1)/\gcd(e(x),x^p-1)$ is an irreducible factor (possibly together with the trivial factor $x-1$, I'm not sure). The theory is described in J.H. van Lint's book from the 70s (earlier than his GTM book). – Jyrki Lahtonen Jul 6 '13 at 18:32

We can write $f(x)=\frac{x^p-1}{x-1}$, so it suffices to see how $x^p-1$ factors.

If $p=q$, then $x^p-1=(x-1)^p$.

If $q\neq p$, then $x^p-1$ is separable (and its solutions are the $p^{th}$ roots of unity). We know what the multiplicative group $\mathbb{F}_{q'}^{\times}$ is for any field extension $\mathbb{F}_{q'}$ of $\mathbb{F}_{q}$ (namely, a cyclic group of order $q'-1$). Then we can solve for the minimum value of $q'$ such that $x^p-1$ splits by finding when $p$ divides $q'-1$. Then, to factor over $\mathbb{F}_{q}$, we can take Galois orbits of the $p^{th}$ roots of unity under the Galois extension $\mathbb{F}_{q'}$ of $\mathbb{F}_{q}$.

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.