Find sum of primitive roots of $z^{36} − 1 = 0$ [closed]

Question

I am trying to understand this concept of sum of primitive roots of unity and here is a typical problem based on it. $z^{36} − 1 = 0$

Answer 1

Even though there are duplicates, maybe this will be a good place to deliver a short lesson, in the hope it will be of benefit to more than one person.

I suppose there are many different approaches, but in my mind, the key to the problem is the Möbius Inversion Theorem, which says that if you have a functions $f,g:\Bbb N\to\Bbb R$ with the property that $\forall n\ge1$ the relation $f(n)=\sum_{d|n}g(d)$, then you can get $g$ in terms of $f$, namely $g(n)=\sum_{d|n}\mu(n/d)f(d)$. And that’s the Möbius function $\mu$ there: $\mu(m)=0$ if $m$ is not square-free, and otherwise, $\mu(m)=(-1)^\nu$ where $\nu$ is the number of distinct primes dividing $m$. So $\mu(10)=1,\mu(11)=-1,\mu(12)=0$. You can prove the MIT via the special case $\sum_{d|n}\mu(d)=1$ if and only if $n=1$; otherwise, the sum is zero. As I recall, one step is to notice that the alternating sum of entries of any one row of the Pascal Triangle is zero, except for the top row; but my memory may be deceiving me here.

Anyway, you should check MIT with the case of the Euler function $\phi(n)=$ the count of numbers $\le n$ that are relatively prime to $n$. You see that $n=\sum_{d|n}\phi(d)$, and get a formula for $\phi(n)=\sum_{d|n}\mu(n/d)d$. Example, $\phi(6)=6-3-2+1=2$, as it should be. Do the same for $n=36$, so that $\phi(36)=36-18-12+6$.

What does this have to do with your problem? Calling $\Phi_n(X)$ the monic polynomial whose roots are the primitive $n$-th roots of unity (that’s the $n$-th cyclotomic polynomial), you have, just as with $\phi$, $$ X^n-1=\prod_{d|n}\Phi_d(X)\,, $$ and you draw from that, by MIT, the consequence $$ \Phi_n(X)=\prod_{d|n}(X^d-1)^{\mu(n/d)}\,. $$ And so? You have your formula for $\Phi_{36}(X)$, namely $$ \Phi_{36}(X)=\frac{(X^{36}-1)(X^6-1)}{(X^{18}-1)(X^{12}-1)}\,. $$

Now look for the coefficient of $X^{35}$, and there you are.