How to factor (x^7+1) to (x+1)(x^3+x+1)(x^3+x^2+1)?

[ricksidd]

can somebody tell me how to factor (x^7+1) to (x+1)(x^3+x+1)(x^3+x^2+1).
Is there any basic book to learn these stuffs.
thanks
Sidd

 

[safwatonline]

Factoring

if u know the answer then just long division, the main idea is to try to solve on simple steps,
like X^7=-1 >>> which has an obvious solution of x=-1
then divide to get the 6th order polynomial , then it will be real hard to solve since it will get complex roots so the best is some program like matlab:

>> roots([1 0 0 0 0 0 0 1])

ans =

  -1.0000          
  -0.6235 + 0.7818i
  -0.6235 - 0.7818i
   0.2225 + 0.9749i
   0.2225 - 0.9749i
   0.9010 + 0.4339i
   0.9010 - 0.4339i

there were some methodes for estimating the solution of some high order polynomial but i cannot really remember them , so try to search if u r interested.
regards

 

[ricksidd]

Re: Factoring

Thanks buddy..
Is there any basic book to learn these simple algebra stuff

 

[safwatonline]

Factoring

i think it isnt that simple but check the 3rd order for example.
https://mathworld.wolfram.com/CubicFormula.html

 

[itsthetimetodisco]

Re: Factoring

from algebriac coding theory perspective, this factoring problem has to deal with finding the 7th root of unity.

To factor x^n + 1 over a finite field Fq:
Find the smallest m such that n divides q^m - 1 (always possible)
Compute cyclotomic cosets modulo n
Compute the corresponding minimal/primitive polynomials m(x) .

Taking x^7 + 1, we find the cyclotomic cosets for it and hence its primitive polynomials in GF(2).
For example, one root is x = 1 (note 1 is same as -1 in binary galois fields).
and so on.

 

[safwatonline]

Factoring

Huh , i dont understand a single word: galois fileds!!

 

[itsthetimetodisco]

Re: Factoring

The question may be solved by other methods as well. Bur using Galois Field theory is far simpler. GF is a finite field where the numbers are limited. In the normal number system, you can have infinite numbers. Whereas in a field, you restrict to a certain set of numbers thereby calling it a finite field. These theory was developed by Galois and hence named after him. For example, GF(2) will have elements 0 and 1 only; GF(4) will have 0, 1, 2 and 3 only. To be noted, the elements in GF(p) will be integers modulo p.
In every finite field, we can construct polynomials, like x^7+1. When we solve this over GF(2), the elements are 0 and 1. So next we find the 7th roots of unity for this polynomial. The basic idea is to find a primitive polynomial.
A primitive element in a finite field means that it can generate all other elements of that field. likewise for a primitive polynomial. Primitive polys are always irreducible polys, cant factor them more.

Please refer the book "Fundamentals of Error Correcting Codes" by Huffman and Pless to get precise mathematical description for this if you want to solve it by field theory.

 

[neils_arm_strong]

Factoring

Refer Higher Algebra by Hall and Knight.

 

[joi]

Re: Factoring

The question may be solved by other methods as well. Bur using Galois Field theory is far simpler. GF is a finite field where the numbers are limited. In the normal number system, you can have infinite numbers. Whereas in a field, you restrict to a certain set of numbers thereby calling it a finite field. These theory was developed by Galois and hence named after him. For example, GF(2) will have elements 0 and 1 only; GF(4) will have 0, 1, 2 and 3 only. To be noted, the elements in GF(p) will be integers modulo p.
In every finite field, we can construct polynomials, like x^7+1. When we solve this over GF(2), the elements are 0 and 1. So next we find the 7th roots of unity for this polynomial. The basic idea is to find a primitive polynomial.
A primitive element in a finite field means that it can generate all other elements of that field. likewise for a primitive polynomial. Primitive polys are always irreducible polys, cant factor them more.

Please refer the book "Fundamentals of Error Correcting Codes" by Huffman and Pless to get precise mathematical description for this if you want to solve it by field theory.
h**p://

When I click the above link, I get a message that the page is removed. Can you pl. give any other links to the above book by Huffman? I would appreciate it very much.
Links for other books on error correcting codes are welcome!

 

[Shweta_S]

Factoring

Can somebody upload Higher algebra by Hall and Knight
I have been looking for it long time

Thanks