A couple ideas.
Idea 1: Let be a primitive root module .
What you want to compute is: in module p.
Idea 2: Let and
Then it can be shown that: - prove this!.
Mixing these 2 well works, I leave you the rest.
Let p be a prime, show that the sum of all the primitive roots module p is congruent to module p. u is the mobius function.
I am considering the polymonial in , where g is a primitive root, and the product is taken over all k such that g^k is also a primitive root. and...???
Any help or new idea would be appriciated.
First, we begin ignoring the module (and then eventually we will take the module).
We want to be able to compute where for a fixed
We know that
Now we apply Möbius inversion formula:
Set and
Thus: - no module involved yet.
But now, and for all such that ( since g is a primitive root) and so in those cases we have that is a multiple of (it's not difficult to see it's an integer).
Hence , therefore
But is what we wanted to compute! - by idea 1.
but then 1-g^(p-1) is equivlent to 0 mod p. what is 0/0 mod p? I think, it can be any nonzero element in Z/pZ, or even 0 itself. It is not well defined, and I am not convinced that it equals 1. why not 2 ?
we can't just ignore the fraction part, right? I believe, you have noticed that, too.
Although a little disagreement appears, thank you all the same.
I am expecting your reply on this disagreement.