multiplicative group of integers modulo n in nLab

Contents

Contents

Definition

For n∈ℕn \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 1…p 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 r−p r−1=p r−1(p−1).\phi(p^r) = p^r - p^{r-1} = p^{r-1}(p-1).

• integers modulo n

• cyclic group

• Q/Z

 External links

• Wikipedia, Multiplicative group of integers modulo n

• Wikipedia, Euler’s totient function