nLab multiplicative group of integers modulo n




For nn \in \mathbb{N}, the group of units of the ring of integers modulo n

(/n) × \left( \mathbb{Z}/n \right)^\times

is typically called the multiplicative group of integers modulo nn.

This consists of all those elements k/nk \in \mathbb{Z}/n which are represented by coprime integers to nn. It is typically denoted /n *\mathbb{Z}/n ^\ast.

Euler totient function

The cardinality |(/n) ×|{|(\mathbb{Z}/n)^\times|} is often denoted ϕ(n)\phi(n) (after Leonhard Euler), and ϕ\phi is known as the Euler totient function.

The function ϕ\phi is multiplicative in the standard number theory sense: ϕ(mn)=ϕ(m)ϕ(n)\phi(m n) = \phi(m)\phi(n) is mm and nn are coprime. This is a corollary of the Chinese remainder theorem?, which asserts that the canonical ring map

/mn/m×/n\mathbb{Z}/m n \to \mathbb{Z}/m \times \mathbb{Z}/n

is an isomorphism if m,nm, n are coprime. Thus, if n=p 1 r 1p k r kn = p_1^{r_1} \ldots p_k^{r_k} is the prime factorization of nn, we have

ϕ(n)=ϕ(p 1 r 1)ϕ(p k r k).\phi(n) = \phi(p_1^{r_1}) \ldots \phi(p_k^{r_k}).

Furthermore, as /p r\mathbb{Z}/p^r is a local ring with maximal ideal p(/p r)p(\mathbb{Z}/p^r), the cardinality of the group of units is

ϕ(p r)=p rp r1=p r1(p1).\phi(p^r) = p^r - p^{r-1} = p^{r-1}(p-1).

Last revised on December 28, 2022 at 12:18:42. See the history of this page for a list of all contributions to it.