# How to prove $t^{23}+1$ irreducible in $F_p$?

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

• 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

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.

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

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

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