6
$\begingroup$

The following exercise is from Golan's book on linear algebra.

Problem: Consider the algebra of polynomials over $GF(7)$, the field with 7 elements.

a) Find a nonzero polynomial such that the corresponding polynomial function is identically equal to zero.

b) Is the polynomial $6x^4+3x^3+6x^2+2x+5$ irreducible?

Work so far: The first part is easy. The polynomial $x^7-x$ works by Fermat's little theorem. The second part is trickier. If the polynomial is reducible, it facts into the product of a linear term and something else, or it factors as two quadratics. The first case is easy to exclude; simply plug all seven elements of $\mathbb{Z}_7$ into the polynomial and confirm none of them are a root. The second is harder. Of course, one could just set up the systems of equations resulting from

$(ax^2+bx+c)(dx^2+ex+f)$

and go through all the possible values of $a,c,d,f$ and see if the resulting values of $b$ and $e$ are permissible, and while I know that would eventually give me the answer, I have no desire to do all of those computations. Is there a slicker way?

  • 0
    @Bill, (+1) to your answer, a nice trick getting rid of the cubic term! I knew that it can be done. You cut the number of choices to smaller number than I faced [here,](http://math.stackexchange.com/a/131708/11619) but the difference is not too great (I had to guess one coefficient modulo 3).2012-05-31

2 Answers 2

3

Hint $\ $ As suggested you could use trial-and-error, and program a computer to test the $7^4 = 2401$ cases that arise from $4$ undetermined coefficients in a factorization into two quadratics. But, as is often true, a little insight trumps brute force. By exploiting innate symmetry, we can reduce the $2401$ cases to $2$ cases. First, shifting $\rm\:x\to x\!-\!1\:$ to kill the $\rm\:x^3\:$ term yields

$\rm\begin{eqnarray} -f(x\!-\!1) &\equiv&\rm\ \ \ x^4\ +\ 2\ x^2\ -\ 3\ x\ +\ 2\pmod 7 \\ &\equiv&\rm\ (x^2\!- a\, x + b)\ (x^2\! + a\, x + c)\\ &\equiv&\rm\ \ x^4\! + (b\!+\!c\!-\!a^2)\!\: x^2\! + a(b\!-\!c)\:\!x + bc\end{eqnarray} $

Up to $\rm\, b,c\, $ swaps, $\rm\: bc\equiv 2\!\iff\! (b,c)\, \equiv\, \pm(2,1),\, \pm\:\!(3,3).\:$ $\rm\:b\not\equiv c\:$ else coef of $\rm\,x\,$ is $\,0\not\equiv -3$.

If $\rm\ (b,c) \equiv\ \ \: (\ 2,\ 1\ )\ $ then $\rm\:-3 \equiv a(b\!-\!c)\equiv\ \: a\:\ $ so $\rm\:b\!+\!c\!-\!a^2\equiv\ \ \ \, 2\!+\!1\!-\!(-3)^2\equiv\ \ 1\:\not\equiv 2$

If $\rm\ (b,c) \equiv (-2,\!-1)\:$ then $\rm\:-3 \equiv a(b\!-\!c)\equiv -a\:$ so $\rm\:b\!+\!c\!-\!a^2\equiv\, -2\!-\!1\!-\!(+3)^2\equiv -5 \equiv 2$

So $\rm\:a,b,c \equiv 3,-2,-1,\:$ is a solution, which yields the factorization $\rm -f(x\!-\!1)\, \equiv\, x^4 + 2\,x^2 - 3\,x+2\, \equiv\, (x^2-3\,x-2)(x^2+3\,x-1)\pmod 7$

Therefore $\rm\:f(x)\:$ is reducible since $\rm\:x\to x\!+\!1\:$ above yields a factorization of $\rm\:-f(x).\ \ $ QED

Remark $\ $ Alternatively, you could use the Euclidean algorithm to compute $\rm\:gcd(f(x\!+\!c),x^{24}\!-\!1)\:$ for random $\rm\:c,\:$ which, $\,$ for $\rm\:c=1\:$ quickly yields $\rm\:x^2\!+\!2\:|\:f(x\!+\!1),\:$ hence $\rm\:f(x)\:$ has the factor $\rm\:(x\!-\!1)^2\!+\!2\, =\, x^2-2\,x+3.\:$ This is how some factoring algorithms work.

3

The answer for (a) is to use Fermat's Little Theorem for the coprime case, ie we know that $ x^7 \equiv x \pmod{7} $ so $ x^7 - x \equiv 0 \pmod{7}. $ The noncoprime case, ie $x \equiv 0 \pmod{7}$ is clear.

For the second answer, the best way really is guess and check (there are more complicated algorithms though). It factors into $ 6(x^2 + 5x + 3)(x^2 + 6x + 3). $

  • 0
    I expect that a computer would make short work of it, although if one is allowed to do that then he could just call `f.factor()` in Sage.2012-05-31