Order of cyclic groups and the Euler phi function

Solution 1:

Suppose $\gcd(n, \phi(n)) > 1$. If $n$ is not squarefree, there exists a prime $p$ such that $p^2$ divides $n$. Then $H = \mathbb{Z}_p \times \mathbb{Z}_p$ is not cyclic and neither is $H \times \mathbb{Z}_{\frac{n}{p^2}}$. If $n$ is squarefree, there exist prime divisors $p$ and $q$ of $n$ such that $q$ divides $p-1$. Then there exists a non-abelian group $H$ of order $pq$ and $H \times \mathbb{Z}_{\frac{n}{pq}}$ is not cyclic.

The other direction is not so easy to answer, but I'll give you a few good references.

Jungnickel and Gallian give elementary proofs (or at least rough outlines for a proof) in these two papers:

Jungnickel, Dieter. On the Uniqueness of the Cyclic Group of Order $n$. Amer. Math. Monthly, Vol. 99, No. 6 (1992) JSTOR

Gallian, J. A. Moulton, David. When is $\mathbb{Z}_n$ the only group of order $n$?, Elemente der Mathematik, Vol. 48 (1993) Link to article

Pakianathan and Shankar have a paper that goes beyond cyclic numbers and gives a number theoretic characterization for abelian, nilpotent and solvable numbers too:

Pakianathan, Jonathan. Shankar, Krishnan. Nilpotent Numbers. Amer. Math. Monthly, Vol. 107, No. 7 (2000) JSTOR