---
tag: 0S7495H4HM
kind: statement
role: proposition
name: Order of the group of units of Z/nZ is Euler's totient
msc: [11A07, 11A25]
uses: [0GXNHEHQNA, 0SEX9F9J5Z]
sources:
  - url: https://en.wikipedia.org/wiki/Multiplicative_group_of_integers_modulo_n
    locator: Structure
  - url: https://en.wikipedia.org/wiki/Multiplicative_group_of_integers_modulo_n
    locator: n = 9
---

## Statement

Let $n \geq 1$ be an integer.
Then the [[order|0B85S2V2DR]] of the group $(\mathbb{Z}/n\mathbb{Z})^\times$ is $\varphi(n)$.
Here $\varphi(n)$ is the number of integers $a$ with $0 \leq a \leq n - 1$ and $\gcd(a, n) = 1$.

## Remarks

The proof is a count, because the [[units of Z/nZ are the residues coprime to n|0GXNHEHQNA]].
For a prime $p$, the order is $\varphi(p) = p - 1$.
For example, $(\mathbb{Z}/9\mathbb{Z})^\times = \{1, 2, 4, 5, 7, 8\}$ has order $\varphi(9) = 6$.
With [[Lagrange's theorem|3C53TD]], this gives Euler's theorem: $a^{\varphi(n)} \equiv 1 \pmod{n}$ for each $a$ coprime to $n$.

## Explanations

### L1 human

The size of the group of units modulo $n$ is the number of residues coprime to $n$.
Euler's totient function counts exactly these residues.
So the group has $\varphi(n)$ elements.