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

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$$

• Do you know about the cyclotomic polynomials? Jan 29, 2022 at 18:05
• no. i did hear this particular term from many people but i don't know it. Jan 29, 2022 at 18:08
• Recent duplicate by the same author: math.stackexchange.com/q/4368211/589
– lhf
Jan 29, 2022 at 18:08
• no not a duplicate. i jus didn't get an answer. I really need to understand this, guys. Pls help me. Jan 29, 2022 at 18:10
• Does this answer your question? Find the sum of all primitive roots of $n$
– lulu
Jan 29, 2022 at 18:12

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.