Hi guys, if i say 2 is a primitive root in mod 19, how can i find all the elements of order 6 in Z*19, without finding the order of each element? Thank you for the help
In general, if we have a primitive root in $\displaystyle (\mathbb{Z}_p)^{\times}$, we know this group is cyclic, and cyclic groups have some special properties.
In particular, we know that if $\displaystyle G = \langle a \rangle$, the order of $\displaystyle a^k$ is $\displaystyle \frac{|G|}{\text{gcd}(k,|G|)}$.
In this example, we have |G| = 18, so we seek k such that 18/(gcd(k,18)) = 6, so that gcd(k,18) = 3. How many such k are there?
Well, clearly k = 3 works, and of course, we need only check the following: 6,9,12,and 15. We can eliminate the even numbers straight-away, leaving just 9 and 15. Since 9|18, that leaves just 15, and indeed gcd(15,18) = 3.
So we have two such k: 3 and 15. So the elements of order 6 are precisely: 2^{3} = 8, and 2^{15} = 8^{5} = (8^{2})(8^{2})(8) = (7)(7)(8) = (7)(18) = 7(-1) = -7 = 12.