4
$\begingroup$

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?

  • 2
    I also found [The Theory of Numbers](http://www.gutenberg.org/files/13693/13693-pdf.pdf) Chapter 5 "Primitive Roots Modulo m" (by Carmichael himself) worth reading.2011-06-02

8 Answers 8

1

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.

  • 0
    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. http://math.uga.edu/~pete/4400primitiveroots.pdf.)2011-06-29
4

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.

3

Ireland, Rosen: A Classical Introduction to Modern Number Theory

3

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

2

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

2

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

  • 0
    That has the cyclicity proofs but nothing on Carmichael's function.2011-06-02
2

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

2

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.