# Order of cyclic groups

Wikipedia says:

It is known that $(\mathbb{Z}/n\mathbb{Z})^\times$ is cyclic if and only if n is 1 or 2 or 4 or $p^k$ or $2p^k$ for an odd prime number p and k ≥ 1.

The statement seems provable given the definition and properties of the Carmichael function.

I need a reference (preferably a book) to read more on cyclic group, their order, and the Carmichael function. I tried several book (on number theory or algebra), but I couldn't find one that stated and proved the above theorem.

• You've got it backwards. The properties of the Carmichael function are provable because of this theorem. – Qiaochu Yuan Jun 2 '11 at 12:18
• Thanks @Qiaochu. I didn't know that. – M.S. Dousti Jun 2 '11 at 12:21
• I also found The Theory of Numbers Chapter 5 "Primitive Roots Modulo m" (by Carmichael himself) worth reading. – M.S. Dousti Jun 2 '11 at 14:12

This is also Theorem 2.41 in An Introduction to the Theory of Numbers (5th Edition) by Niven, Zuckerman, and Montgomery. The proof does not require Carmichael's function, though they do use Euler's totient function, defining a primitive root to be an element of multiplicative order $\phi(m)$ modulo $m$.

They first prove every prime $p$ has $\phi(p-1)$ primitive roots modulo $p$ (Theorem 2.36). Later, they show that if $p$ is a prime, then there are $\phi(\phi(p^2))$ primitive roots modulo $p^2$ (Theorem 2.39). Theorem 2.40 proves that if $p$ is an odd prime and $g$ is a primitive root modulo $p^2$, then $g$ is a primitive root modulo $p^{\alpha}$ for $\alpha\geq 2$. Then a discussion deals with the case of $p=2$, showing there are no primitive roots modulo $2^{\alpha}$ for $\alpha\geq 3$; finally, the composite numbers that are not prime powers nor twice prime powers are dealt with.

As Qiaochu points out, while the Carmichael function indicates how much the multiplicative group fails to be cyclic (when it is less than Euler's totient function), the characterization of those $n > 1$ for which the multiplicative group of $\mathbb{Z}_n$ is cyclic was done first.

The result is given in Gauss's Disquisitiones Arithmeticae, articles 52-56 and 82-89, although that precedes the terminology of groups and is thus framed in terms of congruence classes of integers and primitive roots modulo n: "In Article 56 [Gauss] states that Lambert and Euler knew of them, but that his is the first rigorous demonstration that they exist." The Wikipedia article Multiplicative group of integers modulo n gives a sketch of a modern proof using the prime powers factorization of n and the corresponding factorization of the group of units.

Once it has been worked out which prime powers n have cyclic multiplicative groups, the crux of the proof is that a product of two cyclic groups is cyclic if and only if their orders are coprime.

Ireland, Rosen: A Classical Introduction to Modern Number Theory

For full proofs, see p. 275, Theorem 9.3.5 in Bach; Shallit. Algorithmic Number Theory.

Hardy and Wright. ${}{}{}{}{}{}$

http://www.artofproblemsolving.com/Resources/Papers/MildorfNT.pdf gives a proof in section 4.

• That has the cyclicity proofs but nothing on Carmichael's function. – Bill Dubuque Jun 2 '11 at 17:14

See Chapter 4 of LeVeque's Fundamentals of Number Theory.

Here's the citation for an excellent little paper from the MAA's Mathematics Magazine that takes an algebraic approach to this problem:

David R. Guichard. When is $U(n)$ cyclic? An algebraic approach. Mathematics Magazine 72(2) (1999), 139-142.

• @Pete L. Clark: The proof that $n$ has a primitive root if and only if $n = 1, 2, 4, p^k$ or $2p^k$ for some odd prime $p$ and positive integer $k$ involves only elementary number theory. And $U(n)$ is cyclic if and only if $n$ has a primitive root. – Anononym Jun 29 '11 at 17:49