Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.

Could you please recommend one?

share|cite|improve this question
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
up vote 2 down vote accepted

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.

share|cite|improve this answer

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.

share|cite|improve this answer

Ireland, Rosen: A Classical Introduction to Modern Number Theory

share|cite|improve this answer

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

share|cite|improve this answer

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

share|cite|improve this answer gives a proof in section 4.

share|cite|improve this answer
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.

share|cite|improve this answer

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.

Here's a link to this article on JSTOR.

share|cite|improve this answer
I wonder what would constitute a non-algebraic approach to the cyclicity of the unit group? (Edit: I clicked through to the first page of the article and apparently "algebraic" is being contrasted with "number theoretic". As an algebraic number theorist I am less than thrilled by this proposed dichotomy.) – Pete L. Clark Jun 29 '11 at 14:07
@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
sure, but is elementary number theory not algebraic? You can study it without having studied any abstract algebra, but nevertheless it is still a part of algebra. (And of course there are also proofs that are openly algebraic: see e.g. – Pete L. Clark Jun 29 '11 at 19:08

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.