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$.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy