1
$\begingroup$

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?

$\endgroup$
  • 2
    $\begingroup$ You could start by figuring out the order of $2$, and then figure out the orders of powers of $2$ $\endgroup$ – J. W. Tanner Sep 4 at 20:01
  • 3
    $\begingroup$ The group has order $18$. By a theorem in number theory it is cyclic. So first try to find a generator, then all the other elements are its powers and it will become easier. Remember that the order of each element must divide $18$ by Lagrange's theorem. Thus if you want, for example, to find the order of $2$, you don't need to compute all its powers up to $18$, but only the powers which divide $18$. $\endgroup$ – Mark Sep 4 at 20:04
1
$\begingroup$

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!

| cite | improve this answer | |
$\endgroup$
  • 1
    $\begingroup$ Thank you for the very comprehensive answer! $\endgroup$ – Rebronja Sep 5 at 7:56
1
$\begingroup$

Every element in $\Bbb Z_{19}^*\cong \Bbb Z_{18}$ has order dividing $18$. There are $\varphi(2)=1$ element of order $2$, $\varphi(3)=2$ elements of order $3$, $\varphi(6)=2$ elements of order $6$, $\varphi(9)=6$ elements of order $9$, and $\varphi(18)=6$ of order $18$.

Let's try $2$, as per the comments.

$2^2=4, 2^3=8,2^6=7$ and $2^9=512\cong-1\pmod{19}$, indicating that $2$ has order $18$ and is a primitive.

Now the other five primitives will be $2$ raised to the powers $5,7,11,13,17$, which are relatively prime to $18$. Thus we get $2^5=32\cong13\pmod{19}\,,2^7\cong14\pmod{19},2^{11}\cong15\pmod{19}\,,2^{13}\cong3\pmod{19}$ and finally $2^{17}\cong{10}\pmod{19}$ as our primitives.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ I think some of your computations are off in the end (though the reasoning is correct) $\endgroup$ – Evariste Sep 5 at 2:46
  • $\begingroup$ You're probably right. This happens when I try to do the computations mentally. @Evariste $\endgroup$ – Chris Custer Sep 5 at 2:55
  • 1
    $\begingroup$ Thanks @Evariste I think I got it now. $\endgroup$ – Chris Custer Sep 5 at 3:01

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.