2
$\begingroup$

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?

$\endgroup$
2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ The order in this case is 16. $\endgroup$ – Lubin Oct 13 '13 at 1:05
  • $\begingroup$ The order of $\mathbb{Z}_{17}$ is $17$; that was the order to which I was referring. $\endgroup$ – vadim123 Oct 13 '13 at 1:42
  • $\begingroup$ @vadim123 Can you explain why you have $\phi(\phi(17)) = 8 $? $\endgroup$ – James Lee Oct 13 '13 at 5:26
  • $\begingroup$ @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? $\endgroup$ – James Lee Oct 13 '13 at 5:33
  • $\begingroup$ You're looking for what's called a primitive root. $\phi$ denotes the Euler totient. $\phi(17)=16$ and $\phi(16)=8$. $\endgroup$ – vadim123 Oct 13 '13 at 5:48
1
$\begingroup$

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.

$\endgroup$

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.