The Groups ℤₙ and U(n)

Two families of groups come straight out of arithmetic mod n. They will be our most-used examples, because every computation in them is quick and exact.

The group $\mathbb{Z}_{n}$. The set $\{0, 1, \dots, n - 1\}$ under addition mod $n$ is an abelian group of order $n$: the identity is $0$ and the inverse of $a$ is $n - a$ (and $-0 = 0$). Associativity comes from addition of integers.

The group $U(n)$. The set $$U(n) = \{a : 1 \le a \lt n,\ \gcd(a, n) = 1\}$$ under multiplication mod $n$ is an abelian group. Its order is Euler's $\varphi(n)$. For example $U(12) = \{1, 5, 7, 11\}$ and $U(7) = \{1, 2, 3, 4, 5, 6\}$.

Why it works

Why is $U(n)$ a group? Closure: if $\gcd(a, n) = \gcd(b, n) = 1$ and a prime $p$ divided both $ab$ and $n$, then $p$ would divide $a$ or $b$ (a prime dividing a product divides a factor), sharing a factor with $n$. So $\gcd(ab, n) = 1$, and reducing mod $n$ keeps that, since $\gcd(ab \bmod n, n) = \gcd(ab, n)$. Inverses: $\gcd(a, n) = 1$ gives integers with $ax + ny = 1$ (Bézout), so $ax \equiv 1$; reduce $x$ mod $n$, and it is coprime to $n$ too. These are the modular inverses you already know. Identity $1$, and associativity is inherited.

Worked example: List a group of units

List $U(12)$ and compute its table.

Keep the numbers below $12$ with no factor $2$ or $3$: $1, 5, 7, 11$.
$5^{2} = 25 \equiv 1$, $7^{2} = 49 \equiv 1$, $11^{2} = 121 \equiv 1$, and $5 \cdot 7 = 35 \equiv 11$, $5 \cdot 11 = 55 \equiv 7$, $7 \cdot 11 = 77 \equiv 5$.
Every element is its own inverse.

Answer: $U(12) = \{1, 5, 7, 11\}$, with $x^{2} = 1$ for every $x$.

Worked example: An inverse in $U(20)$

Find $7^{-1}$ in $U(20)$, then solve $7x = 9$ in $U(20)$.

$7 \cdot 3 = 21 = 20 + 1$, so $7^{-1} = 3$.
Multiply $7x = 9$ on the left by $3$: $x = 3 \cdot 9 = 27 \equiv 7$.
Check: $7 \cdot 7 = 49 = 40 + 9 \equiv 9$.

Answer: $7^{-1} = 3$ and $x = 7$.

The Cayley table of $U(12)$. The identity $1$ runs down the main diagonal: each element is its own inverse.

Worked example: Inverses in $\mathbb{Z}_{n}$

In $\mathbb{Z}_{9}$, find $-4$ and solve $4 + x = 2$.

$4 + 5 = 9 \equiv 0$, so $-4 = 5$.
$x = 2 + (-4) = 2 + 5 = 7$. Check: $4 + 7 = 11 \equiv 2$.

Answer: $-4 = 5$ and $x = 7$.

Common mistake

Mixing up the two groups. $\mathbb{Z}_{n}$ uses addition (identity $0$); $U(n)$ uses multiplication (identity $1$) and contains only the residues coprime to $n$. Putting $2$ into $U(12)$ breaks the group: $2y \equiv 1 \pmod{12}$ has no solution, since $2y - 1$ is odd. A quick check: $a \in U(n)$ exactly when $\gcd(a, n) = 1$.

Key idea

$\mathbb{Z}_{n}$ is $\{0, \dots, n - 1\}$ under addition mod $n$, of order $n$. $U(n)$ is the set of residues coprime to $n$ under multiplication mod $n$, of order $\varphi(n)$; inverses come from Bézout's identity.

Sources and further reading

Thomas W. Judson, Abstract Algebra: Theory and Applications (open textbook), chapter 3, Groups (section 3.1, Integer Equivalence Classes and Symmetries; section 3.2, the groups U(n))

John A. Beachy and William D. Blair, Abstract Algebra, online study guide (Northern Illinois University), section 1.4, Integers Modulo n, and section 3.1

The Groups ℤₙ and U(n)

Practice

Builds on

Leads to

Sources and further reading