# Generating cyclic groups

When checking to see if $\langle 2\rangle = U(25)$, why is it sufficient to check that $2^{10} \neq 1$ and $2^4 \neq 1$?

• The order of $2$ divides the size of the group
• $|U(25)|=20$, which has prime factors $2$ and $5$.

So if the order of $2$ is less than $20$, the order of $2$ would have to divide $20/2=10$ or $20/5=4$.

Alternatively, looking at possible orders for $2$:

\begin{align} \left .\begin{array}{l} |\langle 2\rangle| = 2 \\ |\langle 2\rangle| = 4 \end{array} \right \} &\implies 2^4=1 \\ \left . \begin{array}{l} |\langle 2\rangle| = 5 \\ |\langle 2\rangle| = 10 \end{array} \right \} &\implies 2^{10}=1 \\ |\langle 2\rangle| = 20 &\implies \langle 2\rangle = U(25) \\ \end{align}

I'm assuming $U(n)$ is the multiplicative group of units mod $n$? If so...

First off, at the outset there is no reason to believe that $U(n)$ is cyclic. Maybe it's true for $U(25)$. Secondly, there is no way that, even if it were cyclic, that 25 would generate it. Dwell on that for a bit.

If you conjecture that (a) $U(25)$ is cyclic and (b) in fact $2$ is a generator, then you need to check that the group-theoretic order of $2$ is equal to the order of $U(25)$. Now $U(n)$ has order $\varphi(n)$ so $U(25)$ has order $\varphi(25)=20$. Thus, you need to prove that $2$ has order $20$ in $U(25)$. This means that $2^{20}=1$ but no earlier positive power yields $1$.

You already know that $2^{20} = 1$ by Lagrange. However, if there was an earlier killer of $2$, say $2^k=1$, then $k$ would have to divide $20$ (again by Lagrange). Now you can finish your problem.

More generally

If $G$ is a group and $g \in G$ satisfies $g^n=1$, then $o(g)=n$ iff $g^{n/p}\ne1$ for all primes $p$ dividing $n$.

Indeed, if $o(g)=n$, then $g^k \ne 1$ for all $0 < k < n$.

Conversely, if $o(g)=m<n$, then $m$ divides $n$. Write $n=md$ with $d>1$ and let $p$ be a prime divisor of $d$. Write $d=pe$. Then $g^{n/p}= g^{me}=1$.