# 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?

• Welcome to CSE. What exactly remains unclear after looking at the definition of a primitive root modulo $n$: "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$"?
– fgrieu
Nov 29, 2019 at 17:51
• @fgrieu the definition gives no information about the assumption/conclusion on the distribution generated from $g^x$ mod n. I'm curious about whether it preserves uniform distribution and why so. Nov 30, 2019 at 5:54
• @yyforyongyu: I often answer classical exercises with hints, here the definition is an important one. SEJPM went further. Be sure to understand his line of thought: with appropriate $n$, $g$ including $n=7$, $g=3$, the transformation $x\to g^x\bmod n$ is a reversible mapping of the set $\{1,\ldots,n-1\}$, hence for uniform $x$ on that set the outcome is uniform (further, we can map $0$ to itself for a reversible mapping of the full $\Bbb Z_n$). Beware that natural phenomenon often are Gaussian, that's not the case here.
– fgrieu
Nov 30, 2019 at 8:54
• @fgrieu thanks for the clarification. I guess I should be careful when choosing words here. When I say natural phenomenon, what I meant was, the uniform distribution is created by the nature of the universe, just like the value $π$, thus I will take its existence for granted since it's beyond explanation. I have to say I'm still learning the necessary terminologies here to be able to construct a clear and meaningful question/discussion. Thanks again. Nov 30, 2019 at 9:05

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$$
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.