2
$\begingroup$

I've found nothing about this in my book neither in the internet. Also the wikipedia article about inverse multiplicative modulo $n$ is poor.

So, I need prove that

$$\mathbb Z_n^*$$

is cyclic for $n = 5,9,17$ and it's not cyclic for $n = 8,20$

For the cyclic case, I tried to see if any og the groups have prime order. For example:

$$\mathbb Z_5 = \{0,1,2,3,4\} \implies \mathbb Z_5^* = \{1,2,3,4\} \implies |\mathbb Z_5^*| = 4 \ \ :($$

Also we have $|\mathbb Z_9^*|=6$ and $|\mathbb Z_{17}^*| = 14$

So none of them are prime, so I can't use the theorem.

The other technique I would try was to raise each term of $|\mathbb Z_5^*|$, for example, and see if it generates the entire group. However it would consume a lot of time even for small groups.

So, what's a good strategy to prove that $|\mathbb Z_n^*|$ is or isn't cyclic? Am I missing something important?

$\endgroup$
  • 1
    $\begingroup$ You may find this helpful. $\endgroup$ – vadim123 Jul 11 '15 at 22:38
3
$\begingroup$

I'm guessing that you are expected to just perform a bunch of multiplication to check these cases explicitly. I don't think this should be too bad.

There is a general theorem that the multiplicative group of any field is cyclic - this shows that the group of units of $\mathbb{Z}_p$ is cyclic for $p$ prime, since these are fields.

The link provided by vadim123 provides an answer to the general question of when the group of units of $\mathbb{Z}_n$ is cyclic.

| cite | improve this answer | |
$\endgroup$
3
$\begingroup$

It is easier than you think to show that a group is cyclic.

For $\mathbb Z_5$, we have $2^1\equiv 1$

$2^2\equiv 4$

$2^3\equiv 2\cdot 4\equiv 8\equiv 3$

$2^4\equiv 2\cdot 3 \equiv 6\equiv 1$

So $[2]$ generates the group. You can also show that $[3]$ does.

For a non-cyclic group, basically the task is to show that every element an some order less than the order of the original group, which is $\phi(n)$.

In $\mathbb Z_8$:

$[1]$ clearly isn't a generator

$3^2\equiv 1$

$5^2\equiv 1$

$7^2\equiv 1$

and that it. None of these elements generate $\mathbb Z_8$.

I trust it will be pretty easy to show the same for $\mathbb Z_{20}$. Just remember that the only elements of $\mathbb Z_n$ are relatively prime to $n$. If you start testing the wrong numbers it will get frustrating very quickly.

| cite | improve this answer | |
$\endgroup$
1
$\begingroup$

One way is to brute force it by checking the orders of all the elements. That said, the best way is to prove that $\mathbb{Z}_p^{\ast}$ is cyclic when $p$ is a prime. There are many proofs of this, but my favourite goes something like this :

Since it is a finite abelian group, you can write it in the form $$ \mathbb{Z}_p^{\ast} \cong \mathbb{Z}_{d_1} \times \mathbb{Z}_{d_2} \times \ldots \times \mathbb{Z}_{d_n} $$ where $d_1 \mid d_2 \ldots \mid d_n$ are natural numbers. Now consider the polynomial $x^{d_n} - 1 \in \mathbb{Z}_p[x]$. Every element of $\mathbb{Z}_p^{\ast}$ is a solution to this polynomial, but a polynomial over a field can only have as many roots as its degree. So $$ d_1d_2\ldots d_n \leq d_n \Rightarrow n=1 $$

Now for $8$, just check that all the elements of $\mathbb{Z}_8^{\ast} = \{1,3,5,7\}$ have order 2.

For $20$, note that $$ \mathbb{Z}_{20}^{\ast} \cong \mathbb{Z}_4^{\ast} \times \mathbb{Z}_5^{\ast} $$ by the Chinese Remainder theorem. But the product of two groups is cyclic only if each is cyclic and the orders are relatively prime, which is not the case here.

| cite | improve this answer | |
$\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.