Author |
Topic: GCDs of cyclotomic polynomials (Read 1458 times) |
|
Eigenray
wu::riddles Moderator
Uberpuzzler
Gender: 
Posts: 1948
|
 |
GCDs of cyclotomic polynomials
« on: Jul 31st, 2007, 11:25am » |
 Quote  Modify
|
Let  n(x) denote the n-th 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:
(2-x)*(x+1) + 1*(x2-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:
(1-x)*(x2+x+1) + (1+x)*(x2-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 2nd, 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 3rd, 2007, 10:05am » |
Quote Modify
|
...Later (no proof):
- if gcd(m, n) = 1, then d = 1.
- if m = pa, n = pb, then d = p (p is a prime).
|
|
IP Logged |
|
|
|
Barukh
Uberpuzzler
Gender:
Posts: 2276
|
|
Re: GCDs of cyclotomic polynomials
« Reply #3 on: Aug 4th, 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 xn – 1 into cyclotomic polynomials, we have:
(xma - 1)/(x-1) = 1 + x + … + xma-1 = f(x) m(x)
(xnb - 1)/(x-1) = 1 + x + … + xnb-1 = g(x)n(x)
Therefore, f(x)m(x) – xg(x)n(x) = 1.
|
| « Last Edit: Aug 4th, 2007, 5:45am by Barukh » |
IP Logged |
|
|
|
Eigenray
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 1948
|
|
Re: GCDs of cyclotomic polynomials
« Reply #4 on: Aug 5th, 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 pk, 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 5th, 2007, 12:23am by Eigenray » |
IP Logged |
|
|
|
Eigenray
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 1948
|
|
Re: GCDs of cyclotomic polynomials
« Reply #5 on: Aug 6th, 2007, 1:13am » |
Quote Modify
|
I finally have the complete answer for (2). Hint: It turns out pn(x) is never divisible by p2, except when p=2 and n=1.
|
| « Last Edit: Aug 6th, 2007, 1:29am by Eigenray » |
IP Logged |
|
|
|
Barukh
Uberpuzzler
Gender:
Posts: 2276
|
|
Re: GCDs of cyclotomic polynomials
« Reply #6 on: Aug 8th, 2007, 9:12am » |
Quote Modify
|
on Aug 5th, 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 pk, 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 9th, 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 well-defined. That is, if the coefficients of f and g have no common factor, and
d = fn + gm,
does it follow that there is equality of ideals
(d) = (n[x] + m[x])  ?
|
|
IP Logged |
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print