Suppose that $p$ is a prime. Prove that the sum of the primitive roots modulo $p$ is congruent to $\mu(p − 1) \pmod{p}$.
Prove sum of primitive roots congruent to $\mu(p-1) \pmod{p}$
-
11Please don't post questions in the imperative mode; this may be homework for you, but you aren't assigning it as homework to *us*. You are asking a question, so kindly phrase it like a question. Also, given that this is homework, it would be nice (and polite, and helpful) if you say what you have tried, and where you are stuck. That way the answers can deal directly with whatever it is you are having trouble with. – 2011-03-07
-
4Hint: If $latex f = x^n + f_{n-1} x^{n-1} + \cdots + f_0$ is a polynomial whose roots are $r_1$, ..., $r_n$, then $- \sum r_i = f_{n-1}$. – 2011-03-07
-
0I've seen this result in a few books. But I can't see why it is interesting. Can someone please enlighten me? – 2012-01-12
-
0Related: http://math.stackexchange.com/questions/737892 – 2015-03-14
3 Answers
If $g$ is a primitive root of $p$ then Thm 10.9 of Apostol says the sum in question, $S$, is given by
$$S=\!\!\!\!\!\sum_{\substack{k=1\\(k,p-1)=1}}^{p-1}\!\!\!\!\!\!g^k=\sum_{k=1}^{p-1}g^k\sum_{\substack{d|k\\d|p-1}}\mu(d)=\sum_{d|p-1}\mu(d)\sum_{r=1}^{(p-1)/d}\!\!g^{rd}$$
The inner sum is congruent to $0$ unless $d=p-1$ when it is congruent to $1$.
-
0For more than one condition under the $\sum$ sign, you can use `\sum_{\substack{xx\\ yy}}`. – 2015-03-14
If $p - 1 = a^\alpha b^\beta c^\gamma ...$. Then if $A$ is an element of order $a^\alpha$, $B$ is an element of order $b^\beta$, etc. then ABC... is a primitive root.
If A, A', A'', etc. are the elements of order $a^\alpha$, B, B', B'', etc. are the elements of order $b^\beta$, then
(A + A' + ...) (B + B' + ...) (C + C' + ...) ... is the sum of the primitive roots.
Now consider the sum of the terms in any one of the factors, keeping in mind the fact that if $k$ is the order of $y$ and $l$ is relatively prime to $k$, then $y^l$ also has order $k$.
-
2I am glad to see this answer here; it reminds me of some forgotten facts... May I ask you a question? Is this answer out of the book *Disquisitions Arithmeticae* by **Gauß**? I see some hints and footprints here. Thanks for sharing. – 2012-02-08
Let $f(d)$ sum the elements $u$ of order $d$, and let $g(d)$ sum the elements $u$ whose $d$th powers are $1$. Thus $g$ can be evaluated as a geometric sum, and also it has an expression in terms of $f$ that sets up Möbius inversion to give $f$ in terms of $g$; the exercise is requesting $f(p − 1)$, so we are done. (This answer essentially repeats the others, but maybe invoking the Möbius inversion rather than redoing it in the middle of other things is tidy.)