group generators of $(\mathbb Z_{17}-\{0\},\times)$

How to find generators of $(\mathbb Z_{17}-\{0\},\times)$?

Is there a faster way to find generators than trying every element in the group?

I know that for additive group, if a number say m is relatively prime to n (in this case 17), then it's a generator of that group. Do we have something like this for multiplicative group?

You can read details about this here. You get a generator when the order, in this case $17$, is either a prime power or twice a prime power. There's no really good way to find a generator except trial and error; however there are $\phi(\phi(17))=8$ of them, so in this case it shouldn't take too long.

• The order in this case is 16. – Lubin Oct 13 '13 at 1:05
• The order of $\mathbb{Z}_{17}$ is $17$; that was the order to which I was referring. – vadim123 Oct 13 '13 at 1:42
• @vadim123 Can you explain why you have $\phi(\phi(17)) = 8$? – James Lee Oct 13 '13 at 5:26
• @vadim123 I think I get why it's 8 now. But how do you know to this formula to find the number of quadratic nonresiduals? – James Lee Oct 13 '13 at 5:33
• You're looking for what's called a primitive root. $\phi$ denotes the Euler totient. $\phi(17)=16$ and $\phi(16)=8$. – vadim123 Oct 13 '13 at 5:48

Since the order of that group is a power of $2$, all you need to do is find a number that is not a quadratic residue modulo $17$

$$\left(\frac{3}{17}\right) = -1,$$

so $3$ is a generator.