# What are primitive roots modulo n?

I'm trying to understand what primitive roots are for a given $\bmod\ n$. Wolfram's definition is as follows:

A primitive root of a prime $p$ is an integer $g$ such that $g\ (\bmod\ p)$ has multiplicative order $p-1$

The main thing I'm confused about is what "multiplicative order" is. Also, for the notation $g\ (\bmod\ p)$, is it saying $g$ times $\bmod\ p$ or does it have something to do with its congruence?

Sorry for the basic question, any clarification would be great!

Another equivalent definition of a primitive root mod $$n$$ is (from Wikipedia),

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

For example, $$3$$ is a primitive root modulo $$7$$, but not modulo $$11$$, because

Modulo $$7$$, $$3^0\equiv1,\; 3^1\equiv3,\; 3^2\equiv2,\; 3^3\equiv6,\; 3^4\equiv4,\; 3^5\equiv5,\; 3^6\equiv1\pmod{7}$$

And you got all the possible results: $$1, 3, 2, 6, 4, 5$$. You can't get a $$0$$, but $$0$$ is not coprime to $$7$$, so it's not a problem. Hence $$3$$ is a primitive root modulo $$7$$.

Whereas, modulo $$11$$, $$3^0\equiv1,\; 3^1\equiv3,\; 3^2\equiv9,\; 3^3\equiv5,\; 3^4\equiv4,\; 3^5\equiv1\pmod{11}$$

And modulo $$11$$, you only got the possible values $$1, 3, 9, 5, 4$$ and the sequence starts repeating after $$3^5$$, sou you will never get a $$3^k\equiv2$$, for example. Hence $$3$$ is not a primitive root modulo $$11$$.

The sequence $$g^k$$ is always repeating modulo $$n$$ after some value of $$k$$, since it can undertake only a finite number of values (so at least one value appears at least twice, for say $$r,s$$ and $$r>s$$ you have $$g^r \equiv g^{s}$$), and one term depends only on the preceding: $$g^{k+1}\equiv g\cdot g^k$$. Thus $$g^{r+k}\equiv g^{s+k}$$ for all $$k$$.

If $$g$$ and $$n$$ are coprime, it gets a bit simpler, because $$g^k\equiv g^{k'} \pmod{n}$$ for some $$k, k'$$ with $$k>k'$$ implies $$g^{k-k'}\equiv 1$$ (you can take the modular inverse because then all $$g^k$$ are coprime to $$n$$), then with $$r=k-k'$$, you have $$g^{k+r}\equiv g^kg^r\equiv g^k$$ for all $$k$$.

If $$g$$ and $$n$$ are not coprime, it's not as simple: if $$g^r \equiv 0 \pmod{n}$$ for some $$r$$ then $$g^{k+r}\equiv g^kg^r\equiv 0$$ for all $$k$$. But you may also have a repeating sequence without any $$1$$, for example, modulo $$15$$,

$$3^0\equiv1,\; 3^1\equiv3,\; 3^2\equiv9,\; 3^3\equiv12,\; 3^4\equiv6,\; 3^5\equiv3\pmod{15}$$

And it starts repeating after $$3^4$$, with numbers not coprime to $$15$$ since $$g=3$$ is not coprime to $$n$$ either. And actually, if $$g$$ and $$n$$ are not coprime, you never get a $$1$$ again after $$g^0\equiv1 \pmod{n}$$, because all $$g^k$$ have a common factor with $$n$$.

Alternately, the multiplicative order of $$g$$ modulo $$n$$ is the smallest exponent $$k$$ such that $$g^k\equiv 1\pmod{n}$$.

Here you see that the multiplicative order of $$3$$ modulo $$7$$ is $$6$$, and the multiplicative order of $$3$$ modulo $$11$$ is $$5$$, so by your definition, $$3$$ is indeed a primitive root modulo $$7$$, but not modulo $$11$$.

Notice also that the multiplicative order of $$g$$ modulo a prime $$p$$ is always less or equal to $$p-1$$, since Fermat's little theorem states that for a prime $$p$$ and $$a$$ not divisible by $$p$$, $$a^{p-1}\equiv 1 \pmod{p}$$. Then the multiplicative order is also always a divisor of $$p-1$$, and it leads to a simple algorithm to look for primitive roots:

To test a possible $$g$$, take the integer factorization of $$p-1$$, and for every prime factor $$d$$ of $$p-1$$, compute $$g^{(p-1)/d}$$ modulo $$p$$. If none of these is $$1$$, then $$g$$ is a primitive root modulo $$p$$, since $$k=p-1$$ is then the smallest $$k$$ such that $$g^k\equiv 1\pmod{p}$$.

For large $$p$$ and using modular exponentiation by squaring, it's much faster than computing all $$g^k$$ modulo $$p$$ for $$k=0,1,\ldots,p-1$$ and checking if all possible values are there (but you still need an integer factorization).

• Thank you so much for the answer! It's really descriptive so it'll take some time for me to understand this fully. I'm still a little stuck on the first part. Aren't there infinite coprimes to n ? May 15, 2014 at 5:00
• Sorry, I don't understand your question (in case it's that, notice that modulo $n$, $g^k$ can only take values in $0, 1 \ldots, n-1$). Also, I corrected a small mistake in the "repeating" part: if $g$ and $n$ are coprime it's quite nice, but if $g$ and $n$ have a common factor, you don't always get a repeating $0$ (I added an example). May 15, 2014 at 5:02
• Sorry for the confusion. The phrase where it says " if every number comprime to n", where in the following expression are these coprimes? Also, "all the possible results", what exactly are the results? Thanks again May 15, 2014 at 5:10
• Ok, actually, in "all possible numbers coprime to $n$", you need only check numbers below $n$, since as explained the sequence is repeating. For example, modulo $7$, you have $4\equiv 3^4\equiv3^{10}\equiv3^{16}\equiv\ldots$. The results are the values of $g^k$ modulo $n$. For example, with $g=3$ and $n=7$, they are $1,3,2,6,4,5$ (for $k=0,1,2,3,4,5$). May 15, 2014 at 5:13
• This clears things up a lot, thank you so much! If you don't mind, I'm going to ask you later if I get stuck on the other information you've provided. May 15, 2014 at 5:15

You’re wondering about the ring (with additive structure and multiplicative structure) $\mathbb Z$ modulo $n$, often denoted $\mathbb Z/(n)$. You can add and you can multiply modulo $n$, the operations make good sense.

For a general (not necessarily prime) $n$, the multiplicative structure can be fairly ill-behaved. For instance, when $n=8$, you have $4\cdot2=0$, product of two nonzero things coming out to be zero. There are quantities modulo $n$ (“residues mod $n$”) that have reciprocals, however: for the case $n=15$, we have $2\cdot8=1$, modulo $15$. The residues that do have reciprocals can be denoted $(\mathbb Z/(n))^*$ or some such, and this system is a multiplicative structure on its own, a “multiplicative group”. Under certain circumstances, this multiplicative group is “cyclic”, that is, there is one particular element whose powers run through all the things in $(\mathbb Z/(n))^*$. For instance, you can check that the elements of $(\mathbb Z/(9))^*$ are $\{1,2,4,5,7,8\}$, and you can also check that every one of these is a power of two, modulo nine. When there is such a nice residue as $2$ is here, it’s called a primitive root, and it’s a serious Theorem that when $n$ is a prime, there always is a primitive root. For instance, $n=5$ has $2$ for a p.r., $n=7$ can’t use $2$, but $3$ is a good p.r. There are some helpful guidelines for finding a primitive root, but I don’t want to go there tonight. The important fact is that the only numbers $n$ that have primitive roots modulo $n$ are of the form $2^\varepsilon p^m$, where $\varepsilon$ is either $0$ or $1$, $p$ is an odd prime, and $m\ge0$