13
$\begingroup$

Suppose that $p$ is a prime. Prove that the sum of the primitive roots modulo $p$ is congruent to $\mu(p − 1) \pmod{p}$.

  • 0
    Related: http://math.stacke$x$change.com/questions/7378922015-03-14

3 Answers 3

9

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

  • 0
    For more than one condition under the $\sum$ sign, you can use `\sum_{\substack{xx\\ yy}}`.2015-03-14
6

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

  • 2
    I 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
2

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.)