Take the 2-minute tour ×
Mathematica Stack Exchange is a question and answer site for users of Mathematica. It's 100% free, no registration required.

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!

share|improve this question

5 Answers 5

up vote 7 down vote accepted
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

share|improve this answer

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 *)
share|improve this answer

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.

share|improve this answer

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.

share|improve this answer
    
Yes, I wanted make the replacements until only a first-degree polynomial is left. So this is the answer I wanted! –  KH Kim Jul 15 '13 at 23:27
    
@KHKim It wasn't clear enough what you really wanted, so I've updated my answer. –  Artes Jul 16 '13 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.

share|improve this answer

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.