0

I am asked to show if

  • $f(x)=x^3+x+1$ over $\mathbb{F}_5$
  • $g(x)=x^4+x+1$ over $\mathbb{F}_2$

are reducible or not.

I was able to show in each case they are irreducible. For $f(x)$ I assumed it is reducible and I considered $a$ to be a root. This means $a^3+a=a(a^2+1)=-1=4$. The only possibilities are $2 \times2 = 3 \times 3=4 \times 1=4$. Each would give a contradiction. Therefore, it must be irreducible.

Same reasonings apply to $g(x)$. If it is reducible then $b$ is a root and then $b^4+b=b(b^3+1)=-1=1$. The only possibility is $1 \times 1 =1$, which again gives a contradiction.

First, I'd like to know if my reasonings are fine. Secondly, I am curious to know if there are more elegant ways to solve these problems.

Josh
  • 1,086
  • 4
  • 15
  • 5
    It is possible for a fourth degree polynomial to be reducible, but not have a root. – xxxxxxxxx Feb 20 '21 at 20:12
  • can you give an example? I cannot think of one right now for finite fields. – Josh Feb 20 '21 at 20:22
  • 1
    Try $(x^2+x+1)^2=x^4+x^2+1$ over $\mathbb F_2$ as an example of a reducible quartic with no root. All you have to do is multiply two irreducible quadratics. – Mark Bennet Feb 20 '21 at 20:30
  • I see! I had to check $(x^2+ax+b)(x^2+cx+d)$ too. Here we must have $c=d=1$ and since $g(x)$ has a $x$ term then at least one of $a$ or $b$ must be 1. Above comment shows we cannot have $a=b=1$. So we must have, WLOG, $a=1$ and $b=0$. In that situation, $(x^2+x+1)(x^2+1) \neq g(x)$, so $g(x)$ does not have quadratic factors. I already showed it does not have a linear factor, so still it follows that $g(x)$ is irreducible. – Josh Feb 20 '21 at 21:10
  • If a polynomial $\ f(x)\ $ of degree $\ n\ $ over $\ \mathbb{F}_q\ $ is reducible, it must have an irreducible factor of degree $\ d\le\frac{n}{2}\ $, and this polynomial must be a divisor of $\ x^{q^d}-x\ $, so $\ \gcd\big(f(x),x^{q^d}-x\big)\ $ is the product of all irreducible factors of $\ f(x)\ $ of degrees that divide $\ d\ $. Therefore, if $\ \gcd\big(f(x),x^{q^d}-x\big)\ne1\ $, then $\ f(x)\ $ is reducible. On the other hand, if $\ \gcd\big(f(x),x^{q^d}-x\big)=1\ $ for all $\ d\le\frac{n}{2}\ $ then $\ f(x)\ $ must be irreducible. – lonza leggiera Feb 21 '21 at 00:53

0 Answers0