0
$\begingroup$

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,

From wiki

I wonder why is it, or should I just take it as a basic fact of our universe?

$\endgroup$
  • 1
    $\begingroup$ 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$"? $\endgroup$ – fgrieu Nov 29 '19 at 17:51
  • $\begingroup$ @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. $\endgroup$ – yyforyongyu Nov 30 '19 at 5:54
  • $\begingroup$ @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. $\endgroup$ – fgrieu Nov 30 '19 at 8:54
  • $\begingroup$ @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. $\endgroup$ – yyforyongyu Nov 30 '19 at 9:05
2
$\begingroup$

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.

|improve this answer|||||
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.