Factoring polynomials of degree 8 A question in my book asks me to factor $x^8+3x^3-1$ and in the answers, it gives me the correct factorization but gives no explanation on how this was done. Can someone explain how this is factored, Thanks.
 A: Easy enough to try all possible factors into two parts. We know the first two fail, there are no rational roots.
In each of seven cases, we make conclusions both from the left and from the right, as we will be getting the $x^7$ and $x^6$ terms to have coefficient zero on the left, also the $x^2$ and $x$ terms. We do not write out the whole messy system at once. 
For example
$ \left( x^2 + ax - 1 \right)  \left( x^6 + b x^5 + c x^4 + d x^3 + e x^2 + fx +1 \right)   $ requires $a+b=0,$ then $c +ab -1 = 0.$ So far $b =-a, c = 1 + a^2.$ On the right end, $a-f=0,$ then $1 + af -e = 0,$ so $f=a, e = 1 + a^2.$ Continue with
$$ \left( x^2 + ax - 1 \right)  \left( x^6 -a x^5 + (1+a^2) x^4 + d x^3 + (1+a^2) x^2 + ax +1 \right)   $$
and see whether $a$ and $d$ come out as integers.
Indeed, after correcting $c,$ I get
$$ x^8 + (2a+a^3 + d)x^5 + ad x^4 + (2a+a^3 - d)x^3 - 1.  $$
This means that $ad = 0.$ From $2a+a^3 + d =0,$ this means that both $a,d = 0$ or $a$ is irrational, which means this example fails with $2a+a^3 - d=0 \neq 3.$
==========================================
$$ \left( x-1 \right)  \left( x^7 + a x^6 + b x^5 + c x^4 + d x^3 + e x^2 + fx +1 \right)   $$
$$ \left( x+1 \right)  \left( x^7 + a x^6 + b x^5 + c x^4 + d x^3 + e x^2 + fx -1 \right)   $$
$$ \left( x^2 + ax - 1 \right)  \left( x^6 + b x^5 + c x^4 + d x^3 + e x^2 + fx +1 \right)   $$
$$ \left( x^2 + ax + 1 \right)  \left( x^6 + b x^5 + c x^4 + d x^3 + e x^2 + fx - 1 \right)   $$
$$ \left( x^3 + a x^2 + bx -1 \right)  \left( x^5 + c x^4 + d x^3 + e x^2 + fx +1 \right)   $$
$$ \left( x^3 + a x^2 + bx +1 \right)  \left( x^5 + c x^4 + d x^3 + e x^2 + fx -1 \right)   $$
$$ \left( x^4 + a x^3 + b x^2 + c x - 1 \right)  \left( x^4 + d x^3 + e x^2 + fx + 1 \right)   $$
A: A good start may be working$\mod 2$.  Let $x^8+3x^3-1= f(x)$  We only need to check that there is no root (trivial) and that $(x^2+x+1)\not|\, f(x)$ to see that there are no linear or quadratic factors.  In looking for cubic factors we need to try $x^3+x+1$ and $x^3+x^2+1$.  The first is a factor.  The second is not.  This is enough to conclude that a factorization into irreducibles$\bmod 2$ is as follows: 
$$f(x) \equiv (x^3+x+1)(x^5+x^3+x^2+x+1)\bmod 2$$
This also tells us that $f(x)$ cannot have any quadratic or quartic factors over $\Bbb{Z}$, i.e. the best we could expect is a cubic and a quintic.
After that things get a bit hard to proceed by hand.  The Landau-Mignotte bounds tells us for $g(x)=x^3+ax^2+bx+c$, we must have $|a|\leq 9$ and $|b|\leq 9$.  We also know $c$ to be $\pm 1$.  Considering the parity of $a$ and $b$ as well we need to check 9 values of $a$, 10 values of $b$ and 2 values of $c$ to determine whether we can find a divisor $f(x)$.  Looking at $f(1)$ to determine the possible coefficient sums might reduce the number of values to check a little further.
