Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It only takes a minute to sign up.
Sign up to join this community
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$.
