First I want to say that I am new and therefore not that skilled when it comes to problems in abstract algebra. I have this problem which reads:
Let $p = 19$ and consider the finite group $\mathbb{Z}^{*}_{p}$. Determine the order of every element in $\mathbb{Z}^{*}_{p}$, and list all the generators of $\mathbb{Z}^{*}_{p}$
I am not sure how to go about this problem, where to start and how would one write this down. My first impulse was to multiply each element in group and then determine it's order and if it is a generator or not, but that seems like an extremely long and painful process. I was wondering if someone has any hint or suggestion as to how I should start tackling this problem?
Best Answer
These exercises are easy and usually very short. I explain with words how to go around these types of problems. Note however that finding generators is non-trivial in general.
Finding generators is not easy and usually for those kind of exercises the only strategy is to guess. However, it is not in general extremely long and painful as you say, because as stated in the comments, a well-known fact is that $\mathbb{Z}_p^*$ is cyclic whenever $p$ is prime, so if you know about this result, you also know the probability of finding a generator by picking an element at random. It is $\frac{\text{number of generators}}{|\mathbb{Z}_p^*|}=\frac{\varphi(\varphi(p))}{\varphi(p)}=\frac{\varphi(p-1)}{p-1}$. The good news is that when $p=19$, this ratio equals $\frac{6}{18}=\frac{1}{3}$, so it shouldn't take much more than $3$ tries to find the generator. Add also the fact that this is a man-made exercise and chances are, we'll need even fewer trials! Actually I could find one in my head before writing this.
Obviously a good idea is not to pick an element at random but one that is easy to compute, say $2$. Since the divisors of $18$ are $1,2,3,6,9,18$, to check whether $2$ is a generator, note we need only check that $2^6 \not\equiv 1 \pmod{19}$ and $2^{9}\not\equiv1 \pmod{19}$ (the first inequality shows $2$ isn't of order $1,2,3$ or $6$, and the second shows it isn't of order $1,3$ or $9$, so if these are satisfied it must be of order $18$, i.e. it has to be a generator). For small numbers, this is easy to check. $2^6=64\equiv7\pmod{19}$ and $2^9=8\times7=56\equiv-1 \pmod{19}$, so $2$ has order $18$.
Now, if $k \in \{1,2,3,6,9,18\}$, it is easy to see that the elements of order $k$ are $\{2^{18j/k},\gcd(j,k)=1\}$
Therefore, according to this rule,
the elements of order $1$ are $\{2^{18}\}=\{1\}$
the elements of order $2$ are $\{2^9\}=\{18\}$
the elements of order $3$ are $\{2^6,2^{12}\}=\{7,11\}$
the elements of order $6$ are $\{2^3,2^{15}\}=\{8,12\}$
the elements of order $9$ are $\{2^2,2^4,2^8,2^{10},2^{14},2^{16}\}=\{4,16,9,17,6,5\}=\{4,5,6,9,16,17\}$
the elements of order $18$ are $\{2,2^5,2^7,2^{11},2^{13},2^{17}\}=\{2,13,14,15,3,10\}=\{2,3,10,13,14,15\}$
A quick reality-check for computations at the end is to note that there are $\varphi(k)$ elements of order $k$ (since there is a single cyclic subgroup of order $k$ and its number of generators is $\varphi(k)$), and that elements don't appear twice!