# 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

• Finding primitive roots is generally difficult. For $761$, there are exactly $\phi(\phi(761)) = \phi(760) = \phi(2^3\times 5\times 19) = 2^2\times 4\times 18 = 288$ primitive roots, so you have about a 3/8 change of picking a primitive root by picking one at random. So pick one at random and check to see if $a^{380}\equiv -1\pmod{761}$; if yes, then $a$ is a primitive root; if not, then pick something else. – Arturo Magidin Mar 25 '12 at 22:25
• Hi Arturo, could you shed more light on how to verify a, picked randomly, is a primitive root? – user27617 Mar 25 '12 at 22:54
• A given $a$ is a primitive root modulo $761$ if and only if the order of $a$ modulo $761$ is exactly $760$. Since $761$ is prime, there are only two elements whose square is $1$: $1$ and $-1$. Since $a^{760}\equiv 1\pmod{761}$ (Fermat's Little Theorem), we know that $a^{380}\equiv 1$ or $a^{380}\equiv -1$. In the former case, the order of $a$ divides $380$, so $a$ is not a primitive root. In the latter case, the smallest $k$ such that $a^k\equiv1\pmod{761}$ is $760$, so $a$ is in fact a primitive root. So all you need to do is compute $a^{380}\bmod 761$. – Arturo Magidin Mar 25 '12 at 23:18
• Wolfram Alpha says that 6 is the smallest primitive root of 761. – lhf Mar 26 '12 at 0:29
• @Arturo This is a necessary condition, but not sufficient. :( – Vadim Apr 19 '12 at 1:30

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.

• I was wondering - why did you skip 4 when looking for a primitive root? Does it have to do with the fact that it's $2^2$? You're not just testing primes, though, as you find one at 6.. – Joost Nov 18 '12 at 20:44
• @Joost Yes, being a perfect power prevents an integer from being the smallest(!) primitive root. – Peter Košinár May 21 '13 at 19:03
• Right. If $2^2$ was one, then 2 would've been one as well. Thanks. – Joost May 26 '13 at 15:56
• A quadratic residue cannot be a primitive root of an odd prime. – André Nicolas Nov 11 '13 at 18:25
• Please read more carefully. You do not raise $a$ to the power of all prime factors of $\phi(p)$. You find those factors $p_i$ and raise $a$ to the powers $s/p_i$. In your case: $p=43$, $\phi(p)=42$, $\{p_i\}=\{2,3,7\}$, so that you check $2^{42/7}=2^6\equiv 21\mod 43$, $2^{42/3}=2^{14}\equiv 1\mod 43$, so stop, $2$ is not a primitive root. – Vadim Feb 15 '15 at 2:25

You could pick the candidates randomly. If p >= 3 and p-1 is therefore even, x^2 modulo p cannot be a primitive root, and if x^3 modulo p is a primitive root then so is x. 1 cannot be a primitive root. That removes 1, 4, 8, 9 and others. I think composite numbers are a bit less likely to be primitive roots when their factors aren't (someone will know the details).

Since you can store quite large powers of small primes in a table, calculating their powers will be a little bit faster. So I'd check small primes first. Just because it is a tiny bit faster. For p = 761, a lot faster.

Obvious question: Does every prime p >= 3 have a prime number as a primitive root? Is that hard to prove?

Let $p$ be an odd prime number. If $p-1$ is divisible by $4$ and $a$ is a primitive element then $p-a$ is also primitive. For example $761-6=755$ is primitive because $760$ is divisible by $4$.

• This can be proved as follows. Let $p$ be a prime with $p\equiv 1\pmod4$, and let $g$ be a primitive root modulo $p.$ Then $-1\equiv g^{\frac{p-1}{2}}\pmod p,$ so $-g\equiv g^{\frac{p+1}{2}}\pmod p.$ Since $\frac{p+1}{2}$ is prime to $p-1,$ $-g$ is also a primitive root modulo $p.$ – awllower Apr 16 '16 at 18:31