# Lowering the degree of an polynomial with an assumption that the polynomial has a factor x^2+ax+b

Let's assume $x^{10}+x^5+1$ has a factor $x^2+ax+b$

Then, If $x^2=-ax-b$, $x^{10}+x^5+1 =0$.

If we successively apply $x^2=-ax-b$ to $x^{10}+x^5+1$,

we can make $x^{10}+x^5+1$ to degree 1, such as $mx +n$

and it should be that $m=0, n=0$

So having it on my mind, I tried,

x^10+x^5+1 //. x^2-> -a x -b


Didn't work.

x^10+x^5+1 //. x_^2-> -a x -b


Didn't work.

x^10 + x^5 + 1 //. { x^c_?EvenQ :> (-a x - b)^(c/2),
x^c_?OddQ  :> x (-a x - b)^((c - 1)/2)} // Expand

1 - b^5 + b^2 x - 5 a b^4 x + 2 a b x^2 - 10 a^2 b^3 x^2 + a^2 x^3 - 10 a^3 b^2 x^3
- 5 a^4 b x^4 - a^5 x^5

% // TraditionalForm


In order to get the first order polynomial in x at the end we can do this:

x^10 + x^5 + 1 //.{ x^c_?EvenQ :> Expand[(-a x - b)^(c/2)],
x^c_?OddQ  :> Expand[x (-a x - b)^((c - 1)/2)]} // Collect[#, x] &

   1 + a^3 b - a^8 b - 2 a b^2 + 7 a^6 b^2 - 15 a^4 b^3 + 10 a^2 b^4 - b^5
+ (a^4 - a^9 - 3 a^2 b + 8 a^7 b + b^2 - 21 a^5 b^2 + 20 a^3 b^3 - 5 a b^4) x


Edit

This question deserves more detailed answer concerning solutions $a$ and $b$ to given system.

sol =
Solve[{ 1 + a^3 b - a^8 b - 2 a b^2 + 7 a^6 b^2 - 15 a^4 b^3 + 10 a^2 b^4 - b^5 == 0,
a^4 - a^9 - 3 a^2 b + 8 a^7 b + b^2 - 21 a^5 b^2 + 20 a^3 b^3 - 5 a b^4 == 0},
{a, b}] // FullSimplify;


There are 45 solutions:

Length @ sol

45


but to a given b there are multiple a :

Grid[ Prepend[{#[[1, 1, 2]], Sequence @@ #[[1, All, 2]]} & /@
Transpose /@ Gather[ToRadicals @ sol, Last @ #1 == Last @ #2 &],
{"b", "a", "a", "a", "a", "a"}], Frame -> All] // TraditionalForm


I'm not sure why polynomial division should be ruled out. To "successively apply $x^2=−ax−b$ to $x^{10}+x^5+1$" is to me leads to the same steps as division. Since the question was for any suggestions, I would suggest this:

Collect[
PolynomialRemainder[x^10 + x^5 + 1, x^2 + a x + b, x],
x]
(* 1 + a^3 b - a^8 b - 2 a b^2 + 7 a^6 b^2 - 15 a^4 b^3 + 10 a^2 b^4 - b^5 +
(a^4 - a^9 - 3 a^2 b + 8 a^7 b + b^2 - 21 a^5 b^2 + 20 a^3 b^3 - 5 a b^4) x *)


This way it can be achieved as well,

rulesk = {x^s_ /; s >= 2 /; Mod[s, 2] == 0 -> -(a x + b)^(s/2)}

rulesk2 = {x^s_ /; s >= 2 /;
Mod[s, 2] =!= 0 -> -x (a x + b)^((s - 1)/2)}


One rule will work on even power and one on odd power. Now using them as,

eq //. rulesk //. rulesk2 // Expand


$1 - b^5 - b^2 x - 5 a b^4 x - 2 a b x^2 - 10 a^2 b^3 x^2 - a^2 x^3 - 10 a^3 b^2 x^3 - 5 a^4 b x^4 - a^5 x^5$

or

eq //. rulesk2 //. rulesk // Expand


$1 - b^5 - b^2 x - 5 a b^4 x - 2 a b x^2 - 10 a^2 b^3 x^2 - a^2 x^3 - 10 a^3 b^2 x^3 - 5 a^4 b x^4 - a^5 x^5$

This is somewhat less worthy solution because it is always good to use build in functions like @Artes has used for even and odd power.

I think you want to make the replacements until only a first-degree polynomial is left. To do this, I'd modify Artes' answer (which I upvoted because I'm stealing from it) by using FixedPoint:

firstDegree =
FixedPoint[
Expand[# /. {x^c_?EvenQ :> (-a x - b)^(c/2),
x^c_?OddQ :> x (-a x - b)^((c - 1)/2)}] &, x^10 + x^5 + 1]

(*
==> 1 + a^3 b - a^8 b - 2 a b^2 + 7 a^6 b^2 - 15 a^4 b^3 +
10 a^2 b^4 - b^5 + a^4 x - a^9 x - 3 a^2 b x + 8 a^7 b x + b^2 x -
21 a^5 b^2 x + 20 a^3 b^3 x - 5 a b^4 x
*)

Simplify[
First@Solve[Thread[CoefficientList[firstDegree, x] == 0], {a, b}]]

(* ==> {a -> 1, b -> 1} *)


This finds one of the solutions for a and b such that the assumption $m = n = 0$ is satisfied, as stated in your post.

Of course there are simpler methods (e.g., using PolynomialQuotient), but this is what you asked for.

• Yes, I wanted make the replacements until only a first-degree polynomial is left. So this is the answer I wanted! Commented Jul 15, 2013 at 23:27
• @KHKim It wasn't clear enough what you really wanted, so I've updated my answer. Commented Jul 16, 2013 at 0:21

PolynomialReduce is the function to use for this. Accept no substitutes (or substitutions).

--- edit ---

Actually PolynomialRemainder is also fine here, and I see that (a) @Michael E2 had shown how to use that here and (b) I had upvoted that answer when it first appeared.

--- end edit ---

remainder = PolynomialReduce[x^10 + x^5 + 1, x^2 + a*x + b, x][[2]]

(* Out[32]= 1 + a^3 b - a^8 b - 2 a b^2 + 7 a^6 b^2 - 15 a^4 b^3 +
10 a^2 b^4 - b^5 + (a^4 - a^9 - 3 a^2 b + 8 a^7 b + b^2 -
21 a^5 b^2 + 20 a^3 b^3 - 5 a b^4) x *)


To get say rational solutions in the variables {a,b] one could then do as below.

Select[{a, b} /. Solve[CoefficientList[remainder, x] == 0],
Element[##, Rationals] &]

(* Out[38]= {{1, 1}} *)


In place of the Solve one might instead do SolveAlways[remainder == 0, x].

Of course if one wants a factorization over the rationals, there is already Factor` for that.