# Cyclotomic Polynomials and GCD

Since Cyclotomic polynomials are irreducible over $\mathbb{Q}$, $\phi_n(x)$, $\phi_m(x)$ are coprime as polynomials in $\mathbb{Z}[x]$.

1. Working over $\mathbb{Q}$, $(\phi_n(x)$, $\phi_m(x))=(1)$. This implies that $(\phi_n(x), \phi_m(x))=(c)$ for some $c \in \mathbb{N}$ when this ideal is considered in $\mathbb{Z}[X]$. Can this $c$ be evaluated as a function of $n,m$?
2. What can be said about $f(x) = gcd(\phi_n(x),\phi_m(x))$, when the polynomials are considered as scalars, i.e. evaluated at some $x$? $\forall x: f(x) | c$ from question 1, but can something stronger be said? More concretely, what is the image of $f$?

EDIT:

This paper by Apostol, provided in the comments to Greg's answer, gives a pretty good answer, which Greg guessed.

It basically calculates the resultant of 2 cyclotomic polynomials, which gives a number that is divisible by the optimal constant $c=(\phi_n(x), \phi_m(x))$, and it is either 1 (when $\frac{n}{m}$ is not a prime power) or a power of a prime ($p^{\phi(m)}$ when $\frac{n}{m}$ is a power of $p$).

When it is $1$ (the common case), we have a full answer for both questions. When it is a prime power, we only have an upper bound for the multiplicity ($\phi(m)$, when $m|n$).

This elementary paper gives some weaker result but it is simpler.

• Thanks anon, I removed the tag (originally I had a 3rd question about factoring Cyclotomic polynomials over finite fields but I found it on the site and removed it from the post). – Ofir Dec 13 '12 at 8:10

The resultant $R$ of two polynomials $f,g$ has the property that there exist other polynomials $p,q$ such that $p(x)f(x)+q(x)g(x) = R$ identically. (Originally I had stated that $|R|$ is the least such positive integer, but this seems to be incorrect; see the comments.)

Therefore your question 1 is related to calculating the resultant of distinct cyclotomic polynomials $\phi_n, \phi_m$. Experimentally, the answer seems to be $1$ unless $m$ divides $n$ (or vice versa), in which case it seems to be a power of $n/m$. Just eyeballing some data, it seems the answer is $\exp(\phi(m)\Lambda(n/m))$, where $\Lambda$ is the von Mangoldt function.

• I've seen proofs of the exitence of $f,g$ to make $R$ but never a proof its the least. Can you give some sort of reference to a proof? – dinoboy Dec 13 '12 at 1:30
• Greg, the resultant is not, in general, the least integer. See my paper, On resultants, Proc. Amer. Math. Soc. 89 (1983), 419-420, ams.org/journals/proc/1983-089-03/S0002-9939-1983-0715856-2/… – Gerry Myerson Dec 13 '12 at 1:33
• See also Tom Apostol, Resultants of cyclotomic polynomials, Proc. Amer. Math. Soc. 24 (1970), 457-462, ams.org/journals/proc/1970-024-03/S0002-9939-1970-0251010-X/… – Gerry Myerson Dec 13 '12 at 1:36
• @GerryMyerson - Thank you for those papers, they fully answer my first question and they are readable too... – Ofir Dec 13 '12 at 10:20
• @GregMartin - Your empirical answer coincides with Apostol's paper. – Ofir Dec 13 '12 at 10:23

Note that $(x^m-1,x^n-1)=x^{n,m} - 1$ in $\mathbb{Z}[x]$.
i.e. $\exists p(x),q(x)\in \mathbb{Z}[x]$ such that $$(x^m-1)p(x)+(x^n-1)q(x)=x^{(n,m)}-1$$.

Now since $x^{(n,m)}-1 | x^n -1$ and $x^{(n,m)}-1|x^m-1$ in $\mathbb{Z}[x]$
we can say that $$\frac{x^m-1}{x^{(n,m)}-1}p(x)+\frac{x^n-1}{x^{(n,m)}-1}q(x)=1$$.
Now whenever $a|b$ and $a<b$ we have $\phi_b(x)|\frac{x^b-1}{x^a-1}$ in $\mathbb{Z}[x]$.

As a result whenever $min(n,m)>(n,m)$

we have $\phi_m(x)|\frac{x^m-1}{x^{(n,m)}-1}$ and $\phi_n(x)|\frac{x^n-1}{x^{(n,m)}-1}$ in $\mathbb{Z}[x]$ we can say $$\phi_m(x)\cdot\frac{x^m-1}{\phi_m(x)\cdot(x^{(n,m)}-1)}p(x)+\phi_n(x)\cdot\frac{x^n-1}{\phi_n(x)(x^{(n,m)}-1)}q(x)=1$$ Thus, we have $1$ is the least number expressible by $(\phi_n(x), \phi_m(x))$ whenever $min(n,m)>(n,m)$. Or a better way to put it would be $$1\in (\phi_n(x), \phi_m(x))$$ when seen as an ideal in $\mathbb{Z}[x]$

The case where $n=mk$ we see that $$\frac{x^{mk}-1}{x^m-1}=(x^m)^{k-1} + (x^m)^{k-2}+ ... + (x^m) + 1 \equiv k \pmod{x^m-1}$$ $$\implies \frac{x^{mk}-1}{x^m-1} + (x^m-1)\cdot d(x) = k$$ for some $d(x)\in \mathbb{Z}[x]$
Since $\phi_m(x)|x^m-1$ and $\phi_{mk}(x)|\frac{x^{mk}-1}{x^m-1}$ we get that $$\phi_{mk}(x)\cdot\frac{x^{mk}-1}{\phi_{mk}(x)\cdot(x^m-1)} + \phi_m(x)\cdot\frac{x^m-1}{\phi_m(x)}\cdot d(x) = k$$ $$\implies k\in (\phi_m(x),\phi_{mk}(x))$$ when seen as an ideal in $\mathbb{Z}[x]$

However, it is not necessarily $k$ as illustrated by taking $m=1$ and $n=6$ and can be $k$ as illustrated by the example $m=1$ and $n=3$. In fact, using the properties using a bit of algebraic number theory/cyclotomic fields. Once can show, $$(\phi_m(x),\phi_{mk}(x))\cap \mathbb{Z} = \begin{cases} \mathbb{Z}& k\neq p^r\\ p\mathbb{Z}, &k=p^r\\ \end{cases}$$ To see this let $z_n=exp(\frac{2\pi i}{n})$ denote the nth primitive roots of unity.

Let $I_{m,k}=(\phi_m(x),\phi_{mk}(x))$ and $I_m=(\phi_m(x))$. Then we have a canonical map $$R:=\frac{\mathbb{Z}[x]}{I_m}\longrightarrow \frac{\mathbb{Z}[x]}{I_{m,k}}$$ which tells us we have to determine the ideal $(\phi_{mk}(z_m))$ in $R$.

Now $$\phi_{mk}(z_m)=\prod_{(a,mk)=1}^{mk}(z_m-(z_{mk})^a)$$ $$\implies (\phi_{mk}(z_m))=\prod_{(a,mk)=1}^{mk}((z_m-(z_{mk})^a))$$ Since $z_m$ is a unit $$(\phi_{mk}(z_m))=\prod_{(a,mk)=1}^{mk}((1-(z_{mk})^az_m^{-1}))$$ Now note $1-u$ is a unit for all $t$-th roots of unity where $t$ not a power of a prime.(Calculate $\phi_n(1)$ to see this.) Thus the RHS will be a unit if k is not a power of a prime. Furthermore, if $k=p^r$, Sieving out non-units you get $$(\phi_{mk}(z_m))=\prod_{(a,k)=1 }^{k}((1-(z_{k})^a))$$ $$(\phi_{mk}(z_m))= (\phi_k(1))=(p)$$ And thus $\frac{R}{(p)}=\frac{R}{I_mk}= \frac{\mathbb{Z}[x]}{I_{m,k}}$ Which gives us the result since $pR\cap \mathbb{Z}=p\mathbb{Z}$