Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question
10  
Please 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. –  Arturo Magidin Mar 7 '11 at 5:40
4  
Hint: 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}$. –  David Speyer Mar 7 '11 at 16:31
    
I've seen this result in a few books. But I can't see why it is interesting. Can someone please enlighten me? –  lhf Jan 12 '12 at 13:13

3 Answers 3

If $g$ is a primitive root of $p$ then Thm 10.9 of Apostol says the sum in question, $S$, is given by

$S=\displaystyle\sum_{k=1}_{(k,p-1)=1}^{p-1}g^k=\displaystyle\sum_{k=1}^{p-1}g^k\displaystyle\sum_{d|k}_{d|p-1}\mu(d)=\displaystyle\sum_{d|p-1}\mu(d)\displaystyle\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$.

share|improve this answer

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

share|improve this answer
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. –  awllower Feb 8 '12 at 9:12

Let f(d) sum the elements u of order d, and let g(d) sum the elements u whose dth 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.)

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.