# Finding a primitive root of a prime number

How would you find a primitive root of a prime number such as 761? How do you pick the primitive roots to test? Randomly?

Thanks

There is no general formula to find a primitive root. Typically, what you do is you pick a number and test. Once you find one primitive root, you find all the others.

How you test

To test that $a$ is a primitive root of $p$ you need to do the following. First, let $s=\phi(p)$ where $\phi()$ is the Euler’s totient function. If $p$ is prime, then $s=p-1$. Then you need to determine all the prime factors of $s$: $p_1,\ldots,p_k$. Finally, calculate $a^{s/p_i}\mod p$ for all $i=1\ldots k$, and if you find $1$ among residuals then it is NOT a primitive root, otherwise it is.

So, basically you need to calculate and check $k$ numbers where $k$ is the number of different prime factors in $\phi(p)$.

Let us find the lowest primitive root of $761$:

• $s=\phi(761)=760=2^3\times5\times19$
• the powers to test are: $760/2=380$, $760/5=152$ and $760/19=40$ (just 3 instead of testing all of them)
• test 2:
• $2^{380}\equiv 1\mod 761$ oops
• test 3:
• $3^{380}\equiv -1\mod 761$ OK
• $3^{152}\equiv 1\mod 761$ oops
• test 5 (skip 4 because it is $2^2$):
• $5^{380}\equiv 1\mod 761$ oops
• test 6:
• $6^{380}\equiv -1\mod 761$ OK
• $6^{152}\equiv 67\mod 761$ OK
• $6^{40}\equiv -263\mod 761$ hooray!

So, the least primitive root of 761 is 6.

How you pick

Typically, you either pick at random, or starting from 2 and going up (when looking for the least primitive root, for example), or in any other sequence depending on your needs.

Note that when you choose at random, the more prime factors are there in $\phi(p)$, the less, in general, is the probability of finding one at random. Also, there will be more powers to test.

For example, if you pick a random number to test for being a primitive root of $761$, then the probability of finding one is roughly $\frac{1}{2}\times\frac{4}{5}\times\frac{18}{19}$ or 38%, and there are 3 powers to test. But if you are looking for primitive roots of, say, $2311$ then the probability of finding one at random is about 20% and there are 5 powers to test.

How you find all the other primitive roots

Once you have found one primitive root, you can easily find all the others. Indeed, if $a$ is a primitive root mod $p$, and $p$ is prime (for simplicity), then $a$ can generate all other remainders $1\ldots(p-1)$ as powers: $a^1\equiv a,a^2,\ldots,a^{p-1}\equiv 1$. And $a^m \mod p$ is another primitive root if and only if $m$ and $p-1$ are coprime (if $\gcd(m,p-1)=d$ then $(a^m)^{(p-1)/d}\equiv (a^{p-1})^{m/d}\equiv 1\mod p$, so we need $d=1$). By the way, this is exactly why you have $\phi(p-1)$ primitive roots when $p$ is prime.

For example, $6^2=36$ or $6^{15}\equiv 686$ are not primitive roots of $761$ because $\gcd(2,760)=2>1$ and $\gcd(15,760)=5>1$, but, for example, $6^3=216$ is another primitive root of 761.