Which inverse multiplicative groups modulo $n$ are cyclic or not 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?
 A: 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.  
A: 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.
A: 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.
