Show that a cyclic group of order $n$ has $n-1$ generators iff $n$ is prime.

Question

Show that a cyclic group of order $n$ has $n-1$ generators iff $n$ is prime.

I did the following proof yet not sure if this is correct or if there is an easier proof:

$$\implies$$ Let $C_n = \langle g\rangle_{g^n=e}$ have $(n-1)$ generators. To show $n$ is prime. For contradiction, suppose $n$ is not prime. Then $$n=ab, \ 2\leq a,b, \leq n-1 \\ \implies C_n=\langle g\rangle_{g^{ab}=e} $$ By Lagrange's Theorem, $C_n$ can have elements of order $a $ or $b$. Consider $g^a \in C_n$. Now $(g^a)^b=e$ and since $b<n$ then $g^a $ is not a generator of $C_n$. Similarly, $g^b $ is not a generator of $C_n$. Also, $e$ does not generate $C_n$ neither. So $C_n$ can have a maximum of $n-3$ generators which is a contradiction, hence $n$ is prime.

$$\impliedby$$ Let $n$ be prime. To show $C_n $ has $n-1$ generators. Now $C_n = \langle g\rangle_{g^n=e}$ I prove that $$\forall m \in \mathbb N , m\leq n-1, \ (g^m)^n = e \ $$ and whenever $$l \in \mathbb N,\ l<n, (g^m)^l\neq e $$ Proof: Since $$|C_n| =n \\ \forall g \in C_n, g^{|G|} =e \\ \implies (g^m)^n =e$$

Considering the case $(g^m)^l$, suppose for contradiction that $$(g^m)^l=e\\ \text{but } g^n =e \ \text{and } n \text{ is prime} \\ \implies g^{ml}=g^n=e \\ \implies n | ml \\ \implies n | m \text{ or } n|l $$ But $n>m$ and $n>l$ which is a contradiction. So $(g^m)^l \neq e \forall l<n$. I.e. $C_n$ has $n-1$ generators.

Answer 1

In the $\implies$ part, to conclude at most $n-3$ generators, you would have to show that $1, g^a, g^b$ are all distinct.
It is easy to show that $g^a \neq 1 \neq g^b$ since $a, b < n.$

However $g^a \neq g^b$ is not necessary, so you cannot conclude "at most $n-3$ generators". (Take $n = 4$, for example.)

However, the same idea does show that the group has at most $n-2$ generators and that is sufficient to conclude.

---

Minor note: When you assume $n$ is not prime for the sake of contradiction, $n = 1$ is also a possibility. (Which does trivially lead to a contradiction.)

---

The $\impliedby$ part looks fine except for a minor abuse of notation. You have written

$$\forall {\color{red}g} \in C_n, {\color{red}g}^{|G|} = e.$$

Since you've already fixed $g$ to be a generator, so you should use a separate variable in place of ${\color{red}g}$.

Answer 2

Your proof is a bit confusing but it looks valid, it could do with some streamlining. You don't need to use Lagrange's theorem for the first part, the fact that $n$ = $ab$ is enough. Here is how I would solve this: Let $G$ be cyclic with order $n$.

Suppose $n$ is prime, let $g \in G$ such that $g \neq e$ and let $m = |g|$. By Lagrange's theorem $m | n$, so $m = 1$ or $m = n$. The group generated by $g$ contains the distinct elements $g,e$ so $m=1$ is impossible, thus $m = n$, and $g$ generates the group.

If $G$ has $n-1$ generators and $n = ab$ for $1 < a,b < n$ then the group generated by $g^a$ has at most $b$ elements since $(g^a)^b = g^n = e$, so $g^a$ cannot generate $G$. Since $e$ also does not generate $G$, there are at most $n-2$ generators, contradiction.