Editing Primitive root modulo n (section)

==Properties==

Gauss proved<ref>{{Harvnb|Gauss|1986|loc=arts. 80}}.</ref> that for any prime number {{mvar|p}} (with the sole exception of {{nowrap|{{mvar|p}} {{=}} 3),}} the product of its primitive roots is congruent to 1 modulo {{mvar|p}}.

He also proved<ref>{{Harvnb|Gauss|1986|loc=art 81}}.</ref> that for any prime number {{mvar|p}}, the sum of its primitive roots is congruent to {{mvar|μ}}({{mvar|p}} − 1) modulo {{mvar|p}}, where {{mvar|μ}} is the [[Möbius function]].

For example,
:{|
|-
|{{mvar|p}} = 3, || {{mvar|μ}}(2) = −1. || The primitive root is 2.
|-
|{{mvar|p}} = 5, || {{mvar|μ}}(4) = 0. || The primitive roots are 2 and 3.
|-
|{{mvar|p}} = 7, || {{mvar|μ}}(6) = 1. || The primitive roots are 3 and 5.
|-
|{{mvar|p}} = 31, ||{{mvar|μ}}(30) = −1. || The primitive roots are 3, 11, 12, 13, 17, 21, 22 and 24.
|}

E.g., the product of the latter primitive roots is <math>2^6\cdot 3^4\cdot 7\cdot 11^2\cdot 13\cdot 17 = 970377408 \equiv 1 \pmod{31}</math>, and their sum is <math>123 \equiv -1 \equiv \mu(31-1) \pmod{31}</math>.

If <math>a</math> is a primitive root modulo the prime <math>p</math>, then <math>a^\frac{p-1}{2}\equiv -1 \pmod p</math>.

[[Artin's conjecture on primitive roots]] states that a given integer {{mvar|a}} that is neither a [[Square number|perfect square]] nor &minus;1 is a primitive root modulo infinitely many [[prime number|primes]].