divisor

Printable View

April 14th 2009, 12:04 PM
sidi

divisor

Are we able to say, how do all the divisors of $x^m - 1$ like???
Thanks, nothing on my mind seems good now..(Doh)
April 14th 2009, 12:22 PM
NonCommAlg

Quote:

Originally Posted by sidi

Are we able to say, how do all the divisors of $x^m - 1$ like???
Thanks, nothing on my mind seems good now..(Doh)

yes. see cyclotomic polynomials.
April 14th 2009, 12:35 PM
sidi

Thanks, but
I haven´t heard about these polynomials before... I need it to prove that thing about d=gcd(m,n) $x^d - 1$ as the $gcd(x^m - 1,x^n - 1)$ from yesterday. But I think I needn`t use these polynomials...there might be easier way to show it, but it can`t come on my mind...
April 14th 2009, 03:33 PM
NonCommAlg

Quote:

Originally Posted by sidi

Thanks, but
I haven´t heard about these polynomials before... I need it to prove that thing about d=gcd(m,n) $x^d - 1$ as the $gcd(x^m - 1,x^n - 1)$ from yesterday. But I think I needn`t use these polynomials...there might be easier way to show it, but it can`t come on my mind...

i see! the one that i gave you: $\gcd(x^n - 1, x^m -1)=x^{\gcd(n,m)} - 1.$ here's a proof: let $\gcd(n,m)=d.$ since $d \mid n$ and $d \mid m,$ we have: $x^d -1 \mid x^n - 1$ and $x^d - 1 \mid x^m - 1.$

now suppose $f(x) \mid x^n - 1$ and $f(x) \mid x^m - 1.$ if we prove that $f(x) \mid x^d - 1,$ then we're done. we know that there exist $r,s \in \mathbb{N}$ such that $rn - sm=d.$ thus:

$x^{rn} - 1 = x^d(x^m)^s - 1 \equiv x^d - 1 \mod f(x),$ because $x^m \equiv 1 \mod f(x).$ on the other hand $x^{rn}-1 \equiv 0 \mod f(x),$ because $f(x) \mid x^n - 1.$ hence $x^d - 1 \equiv 0 \mod f(x).$ Q.E.D.
April 14th 2009, 09:31 PM
ThePerfectHacker

Quote:

Originally Posted by sidi

Thanks, but
I haven´t heard about these polynomials before... I need it to prove that thing about d=gcd(m,n) $x^d - 1$ as the $gcd(x^m - 1,x^n - 1)$ from yesterday. But I think I needn`t use these polynomials...there might be easier way to show it, but it can`t come on my mind...

Here is a similar problem and an alternate solution.
April 17th 2009, 04:43 AM
sidi

Thank you very much!