Author 
Topic: GCDs of cyclotomic polynomials (Read 1463 times) 

Eigenray
wu::riddles Moderator Uberpuzzler
Gender:
Posts: 1948


GCDs of cyclotomic polynomials
« on: Jul 31^{st}, 2007, 11:25am » 
Quote Modify

Let _{n}(x) denote the nth cyclotomic polynomial. For n m, _{n} and _{m} are relatively prime, since they are both irreducible in the PID [x], and therefore 1 can be expressed as a linear combination of _{n}(x) and _{m}(x), with coefficients in [x]. Clearing denominators, we have: d = f(x)_{n}(x) + g(x)_{m}(x), where d , and f,g [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(_{n}(x), _{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(_{2}(x), _{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(_{3}(x), _{6}(x)) always divides 2. However, in this case, the gcd is always 1.


IP Logged 



Barukh
Uberpuzzler
Gender:
Posts: 2276


Re: GCDs of cyclotomic polynomials
« Reply #1 on: Aug 2^{nd}, 2007, 11:39am » 
Quote Modify

To start with: if n, m are prime numbers, then d = 1.


IP Logged 



Barukh
Uberpuzzler
Gender:
Posts: 2276


Re: GCDs of cyclotomic polynomials
« Reply #2 on: Aug 3^{rd}, 2007, 10:05am » 
Quote Modify

...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).


IP Logged 



Barukh
Uberpuzzler
Gender:
Posts: 2276


Re: GCDs of cyclotomic polynomials
« Reply #3 on: Aug 4^{th}, 2007, 5:44am » 
Quote Modify

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, we have: (x^{ma}  1)/(x1) = 1 + x + … + x^{ma1} = f(x)_{m}(x) (x^{nb}  1)/(x1) = 1 + x + … + x^{nb1} = g(x)_{n}(x) Therefore, f(x)_{m}(x) – xg(x)_{n}(x) = 1.

« Last Edit: Aug 4^{th}, 2007, 5:45am by Barukh » 
IP Logged 



Eigenray
wu::riddles Moderator Uberpuzzler
Gender:
Posts: 1948


Re: GCDs of cyclotomic polynomials
« Reply #4 on: Aug 5^{th}, 2007, 12:10am » 
Quote Modify

I think I know what the answer to (1) is based on some sample data: d=1 unless m/n or n/m is a prime power p^{k}, in which case d=p, but I'd be interested in a proof. I was originally thinking about this because of this. 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): The polynomials _{pn}(x) and _{n}(x) are related mod p (in two different cases). 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.

« Last Edit: Aug 5^{th}, 2007, 12:23am by Eigenray » 
IP Logged 



Eigenray
wu::riddles Moderator Uberpuzzler
Gender:
Posts: 1948


Re: GCDs of cyclotomic polynomials
« Reply #5 on: Aug 6^{th}, 2007, 1:13am » 
Quote Modify

I finally have the complete answer for (2). Hint: It turns out _{pn}(x) is never divisible by p^{2}, except when p=2 and n=1.

« Last Edit: Aug 6^{th}, 2007, 1:29am by Eigenray » 
IP Logged 



Barukh
Uberpuzzler
Gender:
Posts: 2276


Re: GCDs of cyclotomic polynomials
« Reply #6 on: Aug 8^{th}, 2007, 9:12am » 
Quote Modify

on Aug 5^{th}, 2007, 12:10am, Eigenray wrote:I think I know what the answer to (1) is based on some sample data: d=1 unless m/n or n/m is a prime power p^{k}, in which case d=p 
 That makes sense! It explains why (2, 12) is 1, while (2, 6) is 3. Quote:but I'd be interested in a proof.] 
 Does that mean this result is new?


IP Logged 



Eigenray
wu::riddles Moderator Uberpuzzler
Gender:
Posts: 1948


Re: GCDs of cyclotomic polynomials
« Reply #7 on: Aug 9^{th}, 2007, 6:06am » 
Quote Modify

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 = f_{n} + g_{m}, does it follow that there is equality of ideals (d) = (_{n}[x] + _{m}[x]) ?


IP Logged 



