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 .

Printable View

- February 9th 2009, 06:13 PMchiph588@Primitive roots mod p
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 . - February 9th 2009, 06:40 PMThePerfectHacker
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 .

Quote:

Show that the sum of all primitive roots modulo is congruent to modulo .

__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. - February 10th 2009, 04:04 AMPaulRS
Another approach for the second question. (this also works for the first one)

First a little Theorem that always comes in handy.

: Let then with

Theorem

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: - February 11th 2009, 08:55 AMchiph588@
- February 11th 2009, 02:03 PMThePerfectHacker
(Nod) 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 .

Quote:

And isn't the inverse of congruent to because ?