Here's a fun challenge problem!
Show that the product of all primitive roots modulo is congruent to modulo .
Show that the sum of all primitive roots modulo is congruent to modulo .
Here's a fun challenge problem!
Show that the product of all primitive roots modulo is congruent to modulo .
Show that the sum of all primitive roots modulo is congruent to modulo .
Here is a hint. If is a primitive root, then all primitive roots of mod are where and .
So we approach this by the hint, let be a primitive root. Then the product of all primitive roots mod is . Now for every primitive root we see that is a primitive root also. Therefore, we can pair the primitive roots with their inverses. We just need to be careful, we need to know that is not paired with itself. But if . Thus, if we get and if then we get . And so it is correct to write because is even for .
This one should be approached like the one above. But this one is tricker. Let us focus on an easier case first, say . Now is a primitive then is a primitive root too (prove this). And so the entire sum can be paired to cancel out mod . And so we are left with zero. Notice that if then divides and so . Now you need to consider other cases.Show that the sum of all primitive roots modulo is congruent to modulo .
Another approach for the second question. (this also works for the first one)
First a little Theorem that always comes in handy.
Theorem: Let then with
Proof.
We will show first that all of the terms of the RHS are appear once and only once on the LHS.
So, consider: with then where note also that this implies: , hence it corresponds to one of the terms (and only one) in (we are considering each of the terms as if they were different elements)
Conversly, it's easy to see that each of the terms on the LHS of our identity appears once only on the RHS.
_______________________________________
Now let's go to our problem, let be a primitive root module , then our sum is congruent to module (since the exponents must be coprime with for them to be primitive roots, and that is sufficient). So consider in general: then we'll set
We have: hence by Möbius inversion formula:
Thus:
Next note that: and when simply because g is a primitive root.
Thus:
If is primitive root say for then all other primitive roots are congruent with because we need to have where here so we have which happens with .
I meant that . But the idea is still okay, again if then product of primitive roots is congruent to . Now pair the inverses and everything collapses to 1 mod p.And isn't the inverse of congruent to because ?