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.
 A: 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$}.$$
A: 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$. 
