

Title: GCDs of cyclotomic polynomials Post by Eigenray on Jul 31^{st}, 2007, 11:25am Let http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/phi.gif_{n}(x) denote the nth cyclotomic polynomial. For n http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/ne.gif m, http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/phi.gif_{n} and http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/phi.gif_{m} are relatively prime, since they are both irreducible in the PID http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/bbq.gif[x], and therefore 1 can be expressed as a linear combination of http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/phi.gif_{n}(x) and http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/phi.gif_{m}(x), with coefficients in http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/bbq.gif[x]. Clearing denominators, we have: d = f(x)http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/phi.gif_{n}(x) + g(x)http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/phi.gif_{m}(x), where d http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/in.gif http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/bbz.gif, and f,g http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/in.gif http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/bbz.gif[x]. (1) Give a closed form for d, in terms of n and m. (2) It follows from the above that for any integer x, gcd(http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/phi.gif_{n}(x), http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/phi.gif_{m}(x)) divides d. But what gcds are actually obtained? Example: (a) n=2, m=6: (2x)*(x+1) + 1*(x^{2}x+1) = 3, so gcd(http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/phi.gif_{2}(x), http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/phi.gif_{6}(x)) always divides 3. And in fact, for x=2, we do get 3. (b) n=3, m=6: (1x)*(x^{2}+x+1) + (1+x)*(x^{2}x+1) = 2, so gcd(http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/phi.gif_{3}(x), http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/phi.gif_{6}(x)) always divides 2. However, in this case, the gcd is always 1. 

Title: Re: GCDs of cyclotomic polynomials Post by Barukh on Aug 2^{nd}, 2007, 11:39am To start with: if n, m are prime numbers, then d = 1. 

Title: Re: GCDs of cyclotomic polynomials Post by Barukh on Aug 3^{rd}, 2007, 10:05am ...Later (no proof):  if gcd(m, n) = 1, then d = 1.  if m = p^{a}, n = p^{b}, then d = p (p is a prime). 

Title: Re: GCDs of cyclotomic polynomials Post by Barukh on Aug 4^{th}, 2007, 5:44am I think I've got a proof for the case m,n are relatively prime. If gcd(m, n) = 1, then there exist a, b s.t. ma  nb = 1. According to factorization of x^{n} – 1 into cyclotomic polynomials (http://en.wikipedia.org/wiki/Root_of_unity#Cyclotomic_polynomials), we have: (x^{ma}  1)/(x1) = 1 + x + … + x^{ma1} = f(x)http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/cphi.gif_{m}(x) (x^{nb}  1)/(x1) = 1 + x + … + x^{nb1} = g(x)http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/cphi.gif_{n}(x) Therefore, f(x)http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/cphi.gif_{m}(x) – xg(x)http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/cphi.gif_{n}(x) = 1. 

Title: Re: GCDs of cyclotomic polynomials Post by Eigenray on Aug 5^{th}, 2007, 12:10am I think I know what the answer to (1) is based on some sample data: [hide]d=1 unless m/n or n/m is a prime power p^{k}, in which case d=p[/hide], but I'd be interested in a proof. I was originally thinking about this because of [link=http://www.ocf.berkeley.edu/~wwu/cgibin/yabb/YaBB.cgi?board=riddles_easy;action=display;num=1185548773]this[/link]. In that problem, I was actually interested in the answer to part (2), and the approach I used there was to just solve the finitely many instances of part (1) with Mathematica. It wasn't until just now that I realized that part (2) is (probably) easier to solve directly. Hint for (2): [hide]The polynomials http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/varphi.gif_{pn}(x) and http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/varphi.gif_{n}(x) are related mod p (in two different cases)[/hide]. Edit: Actually, (2) isn't as easy as I thought: you still need to rule out the possibility of the gcd being a prime power. 

Title: Re: GCDs of cyclotomic polynomials Post by Eigenray on Aug 6^{th}, 2007, 1:13am I finally have the complete answer for (2). Hint: It turns out [hide]http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/varphi.gif_{pn}(x) is never divisible by p^{2}[/hide], except when p=2 and n=1. 

Title: Re: GCDs of cyclotomic polynomials Post by Barukh on Aug 8^{th}, 2007, 9:12am on 08/05/07 at 00:10:31, Eigenray wrote:
That makes sense! It explains why (2, 12) is 1, while (2, 6) is 3. Quote:
Does that mean this result is new? 

Title: Re: GCDs of cyclotomic polynomials Post by Eigenray on Aug 9^{th}, 2007, 6:06am I doubt it is new. I was interested in (1) to solve (2), which I've done by other means. But it's still a curious result. It's not even clear why d is welldefined. That is, if the coefficients of f and g have no common factor, and d = fhttp://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/varphi.gif_{n} + ghttp://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/varphi.gif_{m}, does it follow that there is equality of ideals (d) = (http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/varphi.gif_{n}http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/bbz.gif[x] + http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/varphi.gif_{m}http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/bbz.gif[x]) http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/cap.gif http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/bbz.gif? 

Powered by YaBB 1 Gold  SP 1.4! Forum software copyright © 20002004 Yet another Bulletin Board 