Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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!

share|improve this question
add comment

2 Answers 2

up vote 4 down vote accepted

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$ and $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 copime 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$ and $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{11}$$

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 lends 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).

share|improve this answer
    
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 ? –  user2200321 May 15 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). –  Jean-Claude Arbaut May 15 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 –  user2200321 May 15 at 5:10
1  
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$). –  Jean-Claude Arbaut May 15 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. –  user2200321 May 15 at 5:15
show 3 more comments

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$

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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