# Primitive roots modulo n

How do I find a primitive root for a given $n$?

For which $n$ does a primitive root exist (I would have guessed it's for all $n$ which are not divisible by 8)?

Is there a systematic way, to constuct all primitive roots for a given $n$?

I want to achieve this (if possible) without trial and error of calculating the discrete logarithm.

First, existence: there is a primitive root modulo $n$ if and only if $n$ is $1$ or $2$ or $4$ or $p^\alpha$ or $2p^\alpha$, where $p$ is prime, $p\ne2$, and $\alpha\ge1$.

Second, a systematic way of finding all primitive roots modulo $n$. Begin by finding one primitive root, say $g$. Then all the units modulo $n$ are $g^\alpha$ for $\alpha=0,1,2,\ldots,\phi(n)-1$, and the primitive roots are those in which the exponent $\alpha$ is relatively prime to $\phi(n)$.

Saving the difficult one for last. . . how to find a primitive root $g$ to begin with. Sadly, there is no straightforward way that is much better than trial and error: though as usual, intelligent trial and error is better than mindless trial and error.

Let's illustrate with an example. Suppose that we want to find a primitive root $g$ modulo $43$: since $43$ is prime, such a root does exist. For every $g\not\equiv0\pmod{43}$ we have $$g^\alpha=1$$ when $\alpha=\phi(43)=42$: to find a primitive root we need $g$ for which this is not true when $\alpha=1,2,\ldots,41$. However we don't need to check all of these: the order of any element modulo $43$ must be a factor of $42$, so we only have to rule out the possible orders $$1,2,3,6,7,14,21.$$ And we can do even better than this. Suppose we have checked that $g^{21}\not\equiv1$: then we can automatically say that $g^1,g^3,g^7\not\equiv1$ and we don't actually need to check them (see if you can explain why). So we only need to rule out $$2,6,14,21.$$ And for similar reasons, we don't need to check $2$. So what it comes down to is that we need to find by trial and error a value of $g$ such that $$g^6,\,g^{14},\,g^{21}\not\equiv1\pmod{43}\ .$$

Try $g=2$: we can save work by using repeated squaring to calculate powers. We have \eqalign{ 2^6&=64\equiv21\not\equiv1\cr 2^7&\equiv2\times21=42\equiv-1\cr 2^{14}&=(2^7)^2\equiv(-1)^2=1\cr} and so $g=2$ fails. Try $g=3$: we have \eqalign{ 3^4&=81\equiv-5\cr 3^6&\equiv9(-5)=-45\equiv-2\not\equiv1\cr 3^7&\equiv-6\cr 3^{14}&=(3^7)^2\equiv36\not\equiv1\cr 3^{21}&=3^{14}3^7\equiv(-7)(-6)=42\equiv-1\not\equiv1\ .\cr} Therefore $3$ is a primitive root modulo $43$, and all primitive roots are $3^\alpha$ where $$\alpha=1,5,11,13,17,19,23,25,29,31,37,41.$$ By generalising this example you can prove the following: if $n$ has a primitive root, then the condition for a unit $g$ to be a primitive root is: $$\hbox{for every prime factor q of \phi(n) we have g^{\phi(n)/q}\not\equiv1\pmod n}.$$

It can be proven that a primitive root modulo $n$ exists if and only if $$n \in \{ 1,2 , 4, p^k, 2 p^k \}$$ with $p$ odd prime.

For each $n$ of this form there are exactly $\phi(n)$ primitive roots.

As far as I know there is no closed formula for finding the primitive roots modulo $n$.

• $$1 + \sum_{a=1}^{n-1} \prod_{b=1}^{a} (1 - \prod_{d=1}^{n-2}(b^d -1)^{n-1} )$$ is a primitive root modulo $n$ if $n$ is prime. I believe this could be modified to more general modulus. What is true however, and what you likely meant, is that there is no effeciently computable formula as the problem is alorithmically difficult. – quid Jul 14 '14 at 14:00
• @quid where does that formula come from? Is that root distinguished from the other primitive roots in any way? – PrimeRibeyeDeal Jul 14 '14 at 22:19
• @PrimeRibeyeDeal I wrote it down last year to answer an MO question, and have no other reference for it (but likely there is one). It is the "first" when starting 2,3,4,... – quid Jul 14 '14 at 22:33
• @quid ok, that's slightly helpful, but I'm perplexed. You have no idea how you came up with that formula? It doesn't look like the type of formula that falls out of thin air. – PrimeRibeyeDeal Jul 15 '14 at 15:21
• @PrimeRibeyeDeal Sorry. I understood your remark as a request for a reference. Of course I can explain where it comes from. The inermost product vanishes if b is not a primitive root otherwise it is 1. Thus the second product is 1 if b is not a primitive root for all b <=a and 0 otherwise. Thus the sum is exactly one less than the first primitive root. The idea to construct it was also I think more or less like this. Find something that indicates primitive root or not and then plug it together somehow. – quid Jul 15 '14 at 15:25