# Trouble Proving Cyclotomic Polynomial Identity

We are required to show that $$x^n-1=\prod_{d|n}\phi_{d}(x)$$ I am aware this is considered a trivial identity and that there are numerous ways to prove it, however, I am having trouble understanding this specific argument used by the author. I am particularily confused as to how he was motivated in defining various variables such as d = n/g where g = hcf(n,k) etc.

http://people.maths.ox.ac.uk/earl/complex/0164.pdf - Author's proof

• What is your definition of cyclotomic polynomials? To me, $x^n-1=\prod_{d\mid n}\phi_d(x)$ is the definition of cyclotomic polynomials. – Batominovski Mar 26 at 7:37

The argument boils down to this : Note $$\omega = \exp\left(\frac{2\pi i}{n}\right)$$. We know that $$x^n - 1 = \prod_{k = 1}^{n}(x - \omega^k).$$ Now, we want to partition those roots into primitive roots of some order (to make the cyclotomic polynomials appear). We claim that a $$n$$-th root of unity $$\omega^k$$ is necessarily a $$d$$-th primitive root of unity for some divisor $$d$$ of $$n$$. Indeed, take $$g = \gcd(k, n)$$ and $$k'$$ such that $$k = gk'$$, and $$d$$ such that $$n = gd$$. Then $$\omega^k = \exp\left(\frac{2\pi i k}{n}\right) = \exp\left(\frac{2\pi k'}{d}\right)$$. Now, $$k'$$ and $$d$$ are necessarily coprime (by the definition of the greatest common divisor). Thus, for all considered $$k$$, $$\omega^k$$ is a $$d$$-th primitive root of unity for some $$d$$, where $$d$$ is a divisor of $$n$$. Therefore, as all roots of $$x^n - 1$$ are simple roots, $$x^n - 1 \text{ divides }\prod_{d | n}\Phi_{d}(x)$$ Reciprocally, take a root of the polynomial on the right, say $$\lambda$$. First, $$\lambda$$ is a simple root. We also know $$\lambda^d = 1$$ for some divisor $$d$$ of $$n$$. So, $$\lambda^{n} = \left(\lambda^d\right)^{n/d} = 1$$, and $$\lambda$$ is a root of the polynomial on the left. Therefore, $$\prod_{d | n}\Phi_{d}(x) \text{ divides } x^n - 1$$ We conclude that $$x^n - 1 = \prod_{d | n}\Phi_{d}(x)$$ The author uses the same argument, but is very succint in his exposition.
• We want to "extract" the common factors from $k$ and $n$. So, we define $d = n/g$ and $k' = k/g$ to "name" what will remain after we simplify by $g$. We know $d$ and $k'$ are integers by the definition of greatest common divisor. Does that help ? – Sachiko.Shinozaki Mar 28 at 19:11