7
$\begingroup$

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.

So, any suggestions? Thanks ahead!

$\endgroup$
8
$\begingroup$
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

enter image description here

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

enter image description here

$\endgroup$
8
$\begingroup$

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 *)
$\endgroup$
3
$\begingroup$

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.

$\endgroup$
3
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Yes, I wanted make the replacements until only a first-degree polynomial is left. So this is the answer I wanted! $\endgroup$ – KH Kim Jul 15 '13 at 23:27
  • $\begingroup$ @KHKim It wasn't clear enough what you really wanted, so I've updated my answer. $\endgroup$ – Artes Jul 16 '13 at 0:21
3
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.