## Computing sums of primitive roots

Remember this picture? It, and other pictures like it, express the fact that for a given $n$, if we take the primitive roots for each of the divisors of $n$, together they make up exactly the set of all $n$th roots of unity. The above picture is for the specific case of $n=12$: the $12$th roots of unity (the dots on the bottom circle) are composed of the primitive roots for $n=1$, $2$, $3$, $4$, $6$, and $12$ (the dots on each of the top circles). I proved this in another post.

Of course, if two sets of complex numbers are the same, then their sums must also be the same. Let’s write $S(n)$ for the sum of all the primitive $n$th roots: in my previous post we worked out $S(n)$ for certain $n$ but weren’t sure how to compute it in other cases. Well, today that’s going to change!

We already know by symmetry that the sum of all the $n$th roots of unity is zero, except when $n=1$ in which case the sum is $1$. Putting all of this together, $\displaystyle \sum_{0 \leq k < n} \omega_n^k = \sum_{d \mid n} S(d) = \begin{cases}1 \qquad n=1 \\ 0 \qquad n>1\end{cases}$

That is, the sum of all $n$th roots of unity is the same as summing the primitive roots, $S(d)$, for each divisor $d$ of $n$. (The notation $d \mid n$ means $d$ evenly divides $n$, so the summation symbol with $d \mid n$ underneath means we are summing over all divisors of $n$.)

So what have we gained? Well, we can use this equation “backwards” to compute values for $S(d)$!

• We already know $S(1) = 1$.
• When $n = 2$, the equation tells us that $S(1) + S(2) = 0$, so it must be that $S(2) = -1$. (Of course we already knew that too.)
• When $n = 3$, we have $S(1) + S(3) = 0$ (note that $S(2)$ is not included since $2$ is not a divisor of $3$), so $S(3) = -1$ as well.
• $S(1) + S(2) + S(4) = 1 + (-1) + S(4) = 0$, so $S(4) = 0$, which also checks out with our previous knowledge.
• Recall that $S(10)$ was the first value we were unsure about. Well, $S(1) + S(2) + S(5) + S(10) = 1 + (-1) + (-1) + S(10) = 0$, so $S(10)$ must be $1$.

And so on. Since each value of $S(n)$ can be computed in this way once we know $S(d)$ for all the divisors of $n$ (which are smaller than $n$), we can continue filling in a table of values of $S(n)$ like this forever. $\displaystyle \begin{array}{c|rrrrrrrrrrrrrrrrrrrr} n & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11 & 12 & 13 & 14 & 15 & 16 & 17 & 18 & 19 & 20 \\ \hline S(n) & 1 & -1 & -1 & 0 & -1 & 1 & -1 & 0 & 0 & 1 & -1 & 0 & -1 & 1 & 1 & 0 & -1 & 0 & -1 & 0 \end{array}$

For example, to fill in $S(20)$ we compute $S(1) + S(2) + S(4) + S(5) + S(10) + S(20) = 1 - 1 + 0 - 1 + 1 + S(20) = 0$ and hence $S(20) = 0$.

Do you notice any patterns? It is not too hard to see that $S(n)$ must always be an integer (why?), but so far it has always been either $-1$, $0$, or $1$; will it always be one of those three values? Before my next post you might like to try extending the table of values for $S(n)$ further and exploring these questions yourself! Assistant Professor of Computer Science at Hendrix College. Functional programmer, mathematician, teacher, pianist, follower of Jesus.
This entry was posted in geometry, pictures and tagged , , , , , , . Bookmark the permalink.

### 9 Responses to Computing sums of primitive roots

1. Michael Paul Goldenberg says:

Quick observation: S(p) will be -1 for all primes, since S(1) = 1 and p is divisible only by 1 and p. So given that S(1) + S(p) = 0, it follows that S(p) must equal -1.

If n = p*q with p,q prime, S(1)+ S(p) + S(q) + S(n) = 0
so 1 + -1 + -1 + S(n) = 0 and thus S(n) = 1
It follows that S(n) = 1 for n = the product of any 2 primes.

From that, I expect some sort of generalization follows for n = the product of k primes. If I weren’t finishing breakfast before rushing to work, I’d try to work that out and see what else might follow from it. My hypothesis is that S(n) can’t escape the set {-1,0,1} but I’m not at all sure yet.

• Brent says:

Good observations! I can confirm that you have started down an interesting path…

• Michael Paul Goldenberg says:

Your reply was just about simultaneous with my next set of observations. 🙂 Thanks for confirming the first ones.

2. Michael Paul Goldenberg says:

Picking up from my previous comment: it looks like for n = pqr, all primes, S(n) = -1. Again, we have S(1) = 1, S(p) for any prime = -1, S(pq) = 1. For 3 primes, we get S(1) + 3*S(p) + 3*S(a*b) [pairwise prime products] + S(pqr) = 0. Thus S(pqr) = -(1 + -3 + 3) = -1.

Building on this, S(pqrs) = 1 since it is equal to -[1 + 4(-1) + 6(1) + 4(-1)] = -(-8+7) = -(-1) = 1.

The coefficients are coming from the binomial expansion, hence represent rows of Pascal’s triangle. It shouldn’t be hard to write a general formula; if I had some coffee and my neck weren’t tight as a drum from sitting at a desk much of the day, I could likely whip one up. Maybe some interested reader will beat me to the punch. 🙂

• Brent says:

Nice work!

3. Michael Paul Goldenberg says:

I think there’s a not difficult way to write a formula for S(n) with an inductive proof. The connection to Pascal’s Triangle hadn’t occurred to me until I saw it, and then it made sense. Grabbing different groups via (n choose k) was suddenly obvious, and then you’re just multiplying those coefficients by 1 or -1. Either all the terms other than S(n) cancel to 1 or to -1, making S(n) the additive inverse of the sum of the other terms.

So may I assume this leads somewhere(s) deeper?

• Brent says:

Your assumption would be correct! If you are impatient you can read http://mathworld.wolfram.com/MoebiusFunction.html (I’d link to Wikipedia as well but it seems to be down for me at the moment…)