Take the 2-minute tour ×
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.

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?

share|improve this question
2  
Guess-and-check is really the best way to go here. But instead of picking values for the coefficients, I prefer to just find all the irreducible quadratics (checking, by exhaustion, to see which ones have roots) and then see if any of them divide the given polynomial. –  Brett Frankel May 31 '12 at 2:59
4  
Rather than find all $21$ irreducible quadratics, it should be easier to consider $x^{49}-x$ (the product of all the monic irreducible polynomials of degree $1$ and $2$) and use Euclid's algorithm to take the GCD of it with your polynomial. –  Chris Eagle May 31 '12 at 3:03
2  
Switch the signs, we are trying to see whether $x^4+4x^3+x^2+5x+2=(x^2+bx+c)(x^2+ex+f)$. Not a lot of work. –  André Nicolas May 31 '12 at 3:31
4  
@Potato: Then you can multiply the first by $4$ and the second by $2$, and get a decomposition in which the coefficient of $x^2$ in each factor is $1$. –  André Nicolas May 31 '12 at 3:36
2  
@Jyrki: Fortunately, we aren't trying to find the factorization, so that's not a problem. –  Chris Eagle May 31 '12 at 10:33
show 10 more comments

2 Answers

up vote 3 down vote accepted

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.

share|improve this answer
add comment

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). $$

share|improve this answer
    
A brute-force "guess and check" would require checking $2401$ cases! But one can prune the search space by exploiting innate symmetry - see my answer. –  Bill Dubuque May 31 '12 at 18:57
    
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. –  Dylan Moreland May 31 '12 at 19:11
add comment

Your Answer

 
discard

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.