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

I have tried to prove that $t^2+1$ is irreducible over $F_3$ by supposing to the contrary $t^2+1=(t+\alpha)(t+\beta)=t^2+(\alpha+\beta)t+\alpha\beta$.

Then, $\alpha+\beta\equiv 0 \pmod 3, \alpha\beta\equiv 1 \pmod 3$. But this leads to $\beta ^2\equiv 2 \pmod 3$ which is not possible by considering cases.

My question would be how do I prove that $t^{23}+1$ (or other similar polynomials like $t^5+1$) is irreducible over $F_p$? Considering cases (linear factors, quadratic factors) seems too tedious to be a feasible method.

Sincere thanks for any help!

[apologies: I have edited the question. The first polynomial should be $t^2+1$ instead of $t^3+1$]

share|cite|improve this question
maple> factor(x^23+1) mod 3 returns $( 1+t ) ( 1+2\,t+{t}^{2}+2\,{t}^{3}+{t}^{4}+2\,{t}^{ 5}+{t}^{6}+2\,{t}^{7}+{t}^{8}+2\,{t}^{9}+{t}^{10}+2\,{t}^{11}+{t}^{12} +2\,{t}^{13}+{t}^{14}+2\,{t}^{15}+{t}^{16}+2\,{t}^{17}+{t}^{18}+2\,{t} ^{19}+{t}^{20}+2\,{t}^{21}+{t}^{22} ) $ – user2468 Aug 28 '12 at 2:03
In $\Bbb Z$ the irreducible factors of $t^n-1$ are the cyclotomic polynomials $\Phi_d(t)$ for divisors $d\mid n$ (which includes at least $d=1$ and $n$). In arbitrary fields even these factors may reduce further. – anon Aug 28 '12 at 2:15
up vote 7 down vote accepted

The polynomial $t^3+1$ has the root $-1$ in $F_3$, so it is not irreducible. The same is true of $t^{23}+1$, indeed $t^n+1$ where $n$ is odd. In all cases, the polynomial is divisible by $t-(-1)$, that is, $t+1$.

The same result holds in any field $F$. If $n\gt 1$ is odd, then $t^n+1$ is not irreducible over $F$. The proof is the same.

share|cite|improve this answer
Why is $t+1$ aka $t+2$ mod 3? – user2468 Aug 28 '12 at 2:07
@Jennifer Dylan: Thanks! Because I was thinking of $t-2$. – André Nicolas Aug 28 '12 at 2:08

Update: this post is now obsolete. I was referring to a typo in an earlier version of the question.

I want to make a comment about a mistake in your contradiction proof that $x^3 + 1$ is irreducible over $\Bbb{Z}/3\mathbb{Z}$. You begin by assuming: $$t^3+1=(t+\alpha)(t+\beta)=t^2+(\alpha+\beta)t+\alpha\beta$$ How come a degree $3$ polynomial is equal to a degree $2$ polynomial?

Fixing it, we should assume: $$ t^3 + 1 = (t+a)(t+b)(t+c) = t^3 + (a+b+c) t^2 +(bc+ac+ab) t+ abc$$ which leads to the system: $$\begin{eqnarray} a+b+c & \equiv & 0 \pmod{3} \\ bc + ac + ab & \equiv & 0 \pmod{3} \\ abc & \equiv & 1 \pmod{3} \\ \end{eqnarray}$$ The $3$rd equivalence gives $4$ possibilities for $(a,b,c)$: $(1, 1, 1)$, $(1, 2, 2)$, $(2, 1, 2)$ and $(1, 1, 2)$. Filtering through the $1$st equivalence, we are left with $(1, 1, 1)$, which is consistent with the $2$nd second equivalence. Hence $-1$ is a root of $t^3 + 1$ over $\Bbb{Z}/3\mathbb{Z}$. So $$ t^3 + 1 \equiv (t+1)^3 \pmod{3}$$

share|cite|improve this answer
Sincere thanks! I actually meant $t^2+1$. [question edited] – yoyostein Aug 28 '12 at 3:28

This special form is relatively easy, since its roots are roots of unity. Every solution is a 23rd root of -1, which must be a 46th root of unity.

I'm going to assume you're not in characteristic 2 or 23: I'll let you work out that special case yourself.

Breaking the group of 46th roots of unity into its relatively prime parts, we have a primitive square root of unity -1 and a primitive 23rd root of unity $\omega$. Your particular polynomials roots are of the form $-\omega^n$. That is,

$$ t^{23} + 1 = \prod_{n=0}^{22} (t + \omega^n) $$

This is its factorization in the splitting field. How can we understand how it factors in the field we are actually interested in?

The answer is Galois theory! You group the roots into conjugacy classes, and factor the product accordingly. Each factor will be a polynomial over your base field.

So, how can we group the roots into conjugacy classes? One simple way is to simply figure out what field a particular root generates.

Suppose your base field is $\mathbb{F}_{13}$, the finite field of 13 elements. It has a primitive 12th root of unity. Its quadratic extension has a primitive 168th root of unity. Its cubic extension has a primitive $13^{3}-1$ root of unity. But which one can have a 23rd root of unity?

The answer is simple! We just need $23 | 13^n - 1$, or $13^n \equiv 1 \pmod{23}$.

The only possibilities for $n$ are $1,2,11,22$, being the divisors of $\phi(23)$. $n=11$ is the smallest one that works.

So, $\omega$ generates a degree 11 extension of $\mathbb{F}_{13}$: its conjugacy class has 11 terms. Another 23rd root of unity is 1. What about the other 11 primitive roots of unity? Well, this field has all of the 23rd roots of unity, so those 11 must also be in a conjugacy class.

Therefore, $t^{23}+1$ factors as $t+1$ and a product of two degree 11 factors. The Galois action is generated by Frobenius: by $x \mapsto x^{13}$, so an explicit formula for those factors is

$$ \prod_{n=0}^{10} (t + \omega^{13^n}) $$ and $$ \prod_{n=0}^{10} (t + \omega^{5 \cdot 13^n}) $$

Where did the $5$ come from? It's not a power of 13 (modulo 23). Any such exponent would do in its place.

share|cite|improve this answer

$t^r+1$ has the root $t=-1$ as long as $r$ is odd, so it is reducible over $F_p$ for any $p$.

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.