Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Where$$\Phi_p(x^n)=1+x^n+\cdots+x^{n(p-1)}$$ is the $p$th cyclotomic polynomial in $x^n$, and $p$ is prime. For instance,

$$\frac{\Phi_5(x^3)}{\Phi_5(x)}=\frac{1+x^3+x^6+x^9+x^{12}}{1+x+x^2+x^3+x^4}$$ $$=x^8-x^7+x^5-x^4+x^3-x+1=\Phi_{15}(x)$$ which, although I could mechanistically calculate, I find a coincidental and unintuitive answer. However, the alternating signs look a lot like the inclusion-exclusion principle may be at work underneath. Also, the little I know about generating functions suggests that this problem may be amenable to a generating-function approach.

TL,DR: Is there a general form for $$\frac{\Phi_p(x^n)}{\Phi_p(x)}$$ , and, if so, can it be arrived at via the inclusion-exclusion principle or generating functions?

share|cite|improve this question
My apologies, I was confused. – Qiaochu Yuan Aug 13 '13 at 17:24
up vote 2 down vote accepted

NB: This doesn't use the inclusion-exclusion principle nor generating functions, and it is for $n$ prime only, but I think it generalises with some care.

Conjecture: For $n, p$ prime the cyclotomic polynomials satisfy the following equation: $$\Phi_p(x)\Phi_{pn}(x)=\Phi_p(x^n).$$

Recall that $$\Phi_m(x) = \prod_{d|m}(1-x^d)^{\mu(m/d)}$$ where $\mu$ is the Möbius function. Plug this into $LHS$ above to find that $$LHS=\prod_{d|p}(1-x^d)^{\mu(p/d)}\cdot\prod_{d|pn}(1-x^d)^{\mu(pn/d)}.$$

Since $p$ and $n$ are prime, for the first product we have $d=1$ and $d=p$, and for the second product we have that $d$ takes the values $1,p,n$ and $pn$. Grouping similar terms we find that $$LHS=\underbrace{\underbrace{(1-x)^{\mu(p)+\mu(pn)}}_{d=1}\cdot\underbrace{(1-x^p)^{\mu(1)+\mu(n)}}_{d=p}}_{1}\cdot \underbrace{\underbrace{(1-x^n)^{\mu(p)}}_{d=n}\cdot\underbrace{(1-x^{pn})^{\mu(1)}}_{d=pn}}_{RHS}=RHS.$$

(The exponents of the first two factors are both $0$, so these factors vanish, and the last two factors is precisely $RHS$.)

share|cite|improve this answer
I'm a novice, and so don't recall. Could you link to the proof? – Alyosha Aug 15 '13 at 17:18
@Alyosha If you are familiar with the Möbius function and Möbius inversion, there's a derivation on page 63 in generatingfunctionology by Wilf. – ET3 Aug 19 '13 at 14:34
I did know of them, but had forgotten. Thanks! – Alyosha Aug 19 '13 at 15:42
Now I understand it, it's quite a pretty answer, it easily generalises to non-prime $n$. – Alyosha Aug 19 '13 at 15:48
If link rot occurs, use this instead, it's still page 63. – Alyosha Sep 28 '13 at 19:31

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.