# primitive roots of unity

How to prove that if $\theta _1,\theta _2,\theta _3$ be the arguments of the primitive roots of unity, $\sum \cos p\theta = 0$ when $p$ is a positive integer less than $\dfrac {n} {abc\ldots k}$, where $a, b, c, \ldots, k$ are the different constituent primes of n and when $p=\dfrac {n} {abc\cdots k}$, $\sum \cos p\theta = \dfrac {\left( -\right)^\mu n} {abc\cdots k}$, where $\mu$ is the number of the constituent primes.

Any help would be much appreciated.

Here is where i got stuck i was hoping for a direct proof starting with the LHS of $\sum \cos p\theta = 0$.

Solution attempt

Well as we know the number of primitive roots(roots the power of which give all the roots) is the number of integers(including unity) less than n and prime to it. Hence we get this number from Euler's totient or phi function.

In the first part of the problem we are asked to assume $0 < p < \dfrac {n} {abc\ldots k}$.

So applying Taylor's series expansion to LHS we get $\sum _{i=1}^{i=\varphi \left( n\right) }\cos p\theta _{i} = \sum _{i=1}^{i=\varphi \left( n\right) }\left( 1-\dfrac {\left( p\theta _{i}\right) ^{2}} {2!}+\dfrac {\left( p\theta _{i}\right) ^{4}} {4!}-...\right)$

Combining terms from various expansions we get $\sum _{i=1}^{i=\varphi \left( n\right) }\cos p\theta _{i} = \varphi \left( n\right) -\dfrac {p^{2}} {2!}\sum _{i=1}^{i=\varphi \left( n\right) }\theta _{i}^{2} + \dfrac {p^{4}} {24}\sum _{i=1}^{i=\varphi \left( n\right) }\theta _{i}^{4} - ...$

I am unsure how to proceed from here although the pattern of alternating signs required for the second result are starting to appear. Any clues or pointers about results related to arguments of primitive roots, would be highly appreciated.

-
Also posted to mathoverflow.net/questions/89039/…, as Hardy should have told us. – Gerry Myerson Feb 20 '12 at 21:55
@Hardy: Hey do you have a collection of those Math Tripos problems. I would like to take a look at them – user9413 Feb 22 '12 at 19:47
@Chandrasekhar, That problem is from this book. amazon.com/gp/product/1178365905/… Sorry i do n't know about any other sources of Math Tripos problems. – Comic Book Guy Feb 22 '12 at 20:01
@Chandrasekhar I recently came to learn that there are a whole lot of Math Tripos problems available maths.cam.ac.uk/undergrad/pastpapers and maths.cam.ac.uk/postgrad/mathiii/pastpapers The first bunch are at an undergrad level and later link is for the post grad level. Enjoy ! – Comic Book Guy Apr 18 '12 at 19:33
@Hardy: Hey thanks for the links. – user9413 Apr 18 '12 at 19:35

If $\zeta_k=e^\frac{2\pi ik}{n}$ is a primitive $n^\text{th}$ root of unity for $n\in\mathbb{Z}^+$, then $k\in\mathbb{Z}$ is relatively prime to $n$. Furthermore, $\zeta_j=\zeta_k\iff j\equiv k\pmod n$. So the set of all primitive $n^\text{th}$ roots of unity is parametrized by the set $K$ of all $1\le k<n$ relatively prime to $n$, i.e. the reduced residue system modulo $n$, which can be identified with $(\mathbb{Z}/n\mathbb{Z})^*$.
Now $s(n,p)=\zeta_k^p=e^\frac{2\pi ikp}{n}=\cos\frac{2\pi kp}{n}+i\sin\frac{2\pi kp}{n}$ and $\Re\,\sum\zeta_k^p=\sum\cos\frac{2\pi kp}{n}$, so we might hope that the full complex sum is zero or not zero under the respective conditions. This will depend on what happens to the residues $k$ modulo $n$ when they are multiplied by $p$. For $p$ relatively prime to $n$, they get permuted ($pK=K$), so that the sum is zero (in the complex plane, both the real and imaginary parts). If, however, $d=\gcd(p,n)>1$, then $\zeta_k^p$ is a primitive root of order $\frac{n}{d}$. So how do we get a complex sum of zero from primitive roots? One way is to sum all the vertices of the regular $n$-gon, i.e. all $n^\text{th}$ roots of unity: $\sum_{j=0}^{n-1}\zeta_j=0$. However, these can be regrouped by their order: $\sum_{d|n}s(d,1)=0$, in terms of the sums $s(n,p)$ defined above. What is $\sum_{d|n}s(d,p)$?
Let $r=\href{http://en.wikipedia.org/wiki/Radical_of_an_integer}{\text{rad}}\,n$ $=\prod_{q\mid n}q$ be the product of all primes $q$ dividing $n$ (also called the radical or squarefree kernel of $n$). What does it tell us when the positive (but not necessarily prime) integer $p$ is less than $\frac{n}r$? Or equal to $\frac{n}r$? What does that tell us about $\frac{n}p$ in relation to $r$? It must be less than $r$ and therefore relatively prime to at least one prime $q$ dividing $r$ and $n$.
You may also find the Möbius inversion formula helpful; your $\mu$ is $\mu(r)$, where my $\mu$ is the Möbius function.