Why does a primitive root mod n gives a uniform distribution over n? The result from a primitive root mod n seemly has a uniform distribution over n, is it true? For instance, 3 is a primitive root mod 7, and the result seems to be randomly distributed over 1 and 6,



I wonder why is it, or should I just take it as a basic fact of our universe?
From the definition of a primitive root, as recovered by fgrieu:


  A number $g$ is a primitive root modulo $n$ if every number $a$ coprime to $n$ is congruent to a power of $g$ modulo $n$


and following-up from that:

This implies that $f(x)=g^x\bmod n$ is a bijection into $\mathbb Z_n^*$, the set of all integers smaller than and co-prime to $n$ greater than 0, i.e. $\{1,2,3,\ldots,n-1\}$ for a prime $n$. It's a bijection because every element can be reached (surjective) and no element is reached twice (injective) when iterating through all values $x$ just until (exclusive) you hit the first repetition in values. It's also a classic result that applying a bijection to a uniformly distributed variable results in a still uniformly distributed variable, i.e. bijections preserve uniform distribution.