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

  • 1
    $\begingroup$ 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. $\endgroup$ – 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.

| cite | improve this answer | |
  • $\begingroup$ Thanks for your pristine clarification of the authors proof. Is it possible that you can explain a bit more why you set n = gd. Or rather why the author defines d as n/g. Thank you $\endgroup$ – Integrable Mar 28 at 19:07
  • $\begingroup$ 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 ? $\endgroup$ – Sachiko.Shinozaki Mar 28 at 19:11
  • $\begingroup$ Ohh thank you soo much. It all clicked when you used the word "extract". Power of words right? Btw do you have any suggestions of ways i can practice proving number theory proofs like this because you seem quite proficient. Thanks $\endgroup$ – Integrable Mar 28 at 20:02
  • $\begingroup$ The proof in question is algebra more than number theory, but (as frustrating as it may seem), practice is the best way to get better. Moreover, it is important to understand "why" some tactic worked (here, our idea to factorize stems from the fact that we "want" to make the cyclotomic polynomials appear). It can also be helpful to have a mental model of the problem and toy around with it before attempting a rigorous proof (it helps outline "what" the problem asks, what property of the studied system is important...). If you would like to continue talking, we should create a chat room. $\endgroup$ – Sachiko.Shinozaki Mar 28 at 20:28

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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