# Finding primitive roots modulo $x$

I'm just starting with number theory and by now I know how to test whether a given number $$\alpha$$ is a primitive root mod $$p$$ or not. But I'm not sure yet how it works if $$\alpha$$ isn't given. I saw a small example where they ask you to find a primitive modulo $$18$$. So what was done is the following: $$\phi(18) = 6$$, so we look for an element of order 6. There are four possibilities: $$5$$, $$7$$, $$11$$ and $$13$$. Can someone explain to me what $$\phi(18) = 6$$ means and how $$5$$, $$7$$, $$11$$ and $$13$$ are of order $$6$$?

Edit: So when I know these $$4$$ possibilities, I can easily test them but I'm not sure how to arrive at these possibilities.

$$\phi (18)=6$$ means that there are six integers $$n$$ with $$1\le n \le 17$$ (we can automatically exclude $$0\equiv 18\mod 18$$) which are coprime to $$18$$ - they have no common factor with $$18$$.

These $$6$$ numbers have multiplicative inverses modulo $$18$$ and therefore form an abelian group - the multiplicative group of units modulo $$18$$. If this group is cyclic, then a primitive root modulo $$18$$ is a generator of this cyclic group.

[Note that if $$n$$ is a prime the group is always cyclic - for primes the order is $$n-1$$ - and there is always a primitive root. But if $$n=8$$ or $$n=15$$ for example the group is not cyclic.]

Now the cyclic group of order $$6$$ has just two generators. Here the six elements are $$1,5,7,11,13,17$$. We have, modulo $$18$$

$$1=1$$ has order $$1$$

$$5^2=25\equiv 7; 5^3\equiv 5\times 7\equiv 35\equiv 17\equiv -1$$

Note that it can be very useful to introduce negative numbers into the calculations to keep arithmetic simple. Now the order of an element of a group of order $$6$$ must divide the order of the group, so must be $$1,2,3,6$$ and for the element $$5$$ we have excluded $$1,2,3$$ and it follows that $$5$$ must have order $$6$$ and therefore is a primitive root. We have $$5^4\equiv 5\times -1=-5\equiv 13, 5^5\equiv 5\times 13\equiv 65\equiv 11, 5^6\equiv 5\times 11=55\equiv 1$$.

$$7^2=49\equiv 13; 7^3\equiv 7\times 13\equiv 91\equiv 1$$ so that $$7$$ has order $$3$$ and is not a primitive root.

$$11^2=121\equiv 13; 11^3\equiv 143\equiv -1$$ so that $$11$$ is a primitive root for the same reasons as $$5$$.

$$13^2=(-5)^2\equiv 25\equiv 7; 13^3\equiv 13\times 7\equiv 1$$ so $$13$$ has order $$3$$ and is not a primitive root (note how using negative numbers made this easier)

$$17^2\equiv (-1)^2\equiv 1$$ so $$17$$ has order $$2$$ and is not a primitive root.

We could have used information about the structure of the cyclic group to make this easier. In general finding primitive roots is not easy - there are methods which will help, but no ways to guarantee a quick result.

For example, here we know that $$17\equiv -1$$ has order $$2$$, and if we find an element $$a$$ of order $$3$$ before we find an element of order $$6$$ we know that multiplying an element of order $$3$$ by an element of order $$2$$ in an abelian group will give us an element of order $$6$$, so we identify $$-a$$ as a primitive root.

Here $$13$$ has order $$3$$ and $$-13\equiv 5$$ has order $$6$$. Also $$7$$ has order $$3$$ so that $$-7\equiv 11$$ has order $$6$$.