Examples: Cyclic Groups and Modular Arithmetic

We prove each part in turn. The technique throughout is direct verification from definitions, together with the division algorithm and Bézout's identity, both elementary facts about $\mathbb{Z}$ that do not presuppose group theory.

(a) $\mathbb{Z}$ is a group; its subgroups are $d\mathbb{Z}$. Addition on $\mathbb{Z}$ is associative and commutative (a basic property of integer arithmetic), $0$ is an identity since $a + 0 = a$ for all $a$, and $-a$ is an inverse of $a$ since $a + (-a) = 0$. Thus $(\mathbb{Z},+)$ satisfies the group axioms. Now let $H \leq \mathbb{Z}$ be a subgroup. If $H = \{0\}$, then $H = 0\mathbb{Z}$ and we take $d = 0$. Otherwise $H$ contains some nonzero integer, and since $H$ is closed under inverses, $H$ contains a positive integer. By the well-ordering principle, the set $H \cap \mathbb{Z}_{>0}$ has a least element $d > 0$. We claim $H = d\mathbb{Z}$. Since $H$ is closed under addition and contains $d$, it contains $d, 2d, 3d, \dots$, and closed under inverses it contains $-d, -2d, \dots$; hence $d\mathbb{Z} \subseteq H$. Conversely, let $h \in H$. By the division algorithm, write $h = qd + r$ with $0 \leq r < d$. Since $h \in H$ and $qd \in d\mathbb{Z} \subseteq H$, we get $r = h - qd \in H$ (as $H$ is a subgroup, closed under addition and inverses). If $r > 0$, then $r$ is a positive element of $H$ smaller than $d$, contradicting minimality of $d$. Hence $r = 0$, so $h = qd \in d\mathbb{Z}$. Thus $H \subseteq d\mathbb{Z}$, giving $H = d\mathbb{Z}$. Uniqueness of $d \geq 0$: if $d\mathbb{Z} = d'\mathbb{Z}$ with $d, d' \geq 0$, then $d \in d'\mathbb{Z}$ forces $d' \mid d$, and symmetrically $d \mid d'$; since both are nonnegative this forces $d = d'$.

(b) $\mathbb{Z}/n\mathbb{Z}$ is a well-defined group of order $n$ under addition. Equivalence relation. Reflexivity: $n \mid (a - a) = 0$. Symmetry: if $n \mid (a-b)$ then $n \mid (b-a) = -(a-b)$. Transitivity: if $n \mid (a-b)$ and $n \mid (b-c)$ then $n \mid ((a-b)+(b-c)) = a - c$. So congruence mod $n$ is an equivalence relation. Exactly $n$ classes. By the division algorithm, every integer $a$ can be written $a = qn + r$ with $0 \leq r < n$, so $a \equiv r \pmod n$, i.e. $[a]_n = [r]_n$ for some $r \in \{0, \dots, n-1\}$. This shows every class equals one of $[0]_n, \dots, [n-1]_n$. These $n$ classes are pairwise distinct: if $0 \leq r < r' \leq n-1$ and $[r]_n = [r']_n$, then $n \mid (r' - r)$, but $0 < r' - r < n$, impossible. Hence $\mathbb{Z}/n\mathbb{Z}$ has exactly $n$ elements. Well-definedness of $+$. Suppose $[a]_n = [a']_n$ and $[b]_n = [b']_n$, i.e. $n \mid (a - a')$ and $n \mid (b-b')$. We must check $[a+b]_n = [a'+b']_n$, i.e. $n \mid ((a+b) - (a'+b'))$. Indeed,

a sum of two multiples of $n$, hence itself a multiple of $n$. So the class $[a+b]_n$ depends only on the classes of $a$ and $b$, not on the particular representatives chosen; the operation is well-defined. Group axioms. Associativity: $([a]_n + [b]_n) + [c]_n = [(a+b)+c]_n = [a+(b+c)]_n = [a]_n + ([b]_n+[c]_n)$, using associativity of integer addition. Identity: $[a]_n + [0]_n = [a+0]_n = [a]_n$. Inverse: $[a]_n + [-a]_n = [0]_n$. Thus $(\mathbb{Z}/n\mathbb{Z}, +)$ is a group, and it has order $n$ by the previous paragraph.

(c) Multiplication is well-defined but not a group operation. Well-definedness. Suppose $n \mid (a-a')$ and $n \mid (b - b')$; write $a' = a + sn$, $b' = b + tn$ for integers $s,t$. Then

so $a'b' - ab = n(at+bs+stn)$ is a multiple of $n$. Hence $[a'b']_n = [ab]_n$, so $[a]_n[b]_n := [ab]_n$ is well-defined. Failure to be a group. The operation is associative and commutative (inherited from $\mathbb{Z}$) and has identity $[1]_n$. However, for $n \geq 2$, the class $[0]_n$ satisfies $[0]_n \cdot [b]_n = [0]_n$ for every $b$, which is never $[1]_n$ since $[0]_n \neq [1]_n$ (as $n \nmid 1$ when $n \geq 2$). So $[0]_n$ has no multiplicative inverse, and $(\mathbb{Z}/n\mathbb{Z}, \cdot)$ fails the inverse axiom; it is not a group. (For composite $n$, other nonzero classes also fail to have inverses, as part (d) will show precisely.)

(d) Units are exactly the classes coprime to $n$, and they form a group of order $\varphi(n)$. $(\Rightarrow)$ Suppose $[a]_n$ is a unit, so there is $b$ with $[a]_n[b]_n = [1]_n$, i.e. $n \mid (ab - 1)$, i.e. $ab - 1 = kn$ for some integer $k$, i.e.

Let $d = \gcd(a,n)$. Since $d \mid a$ and $d \mid n$, $d$ divides $ab - kn = 1$, forcing $d = 1$. Hence $\gcd(a,n) = 1$. $(\Leftarrow)$ Suppose $\gcd(a,n) = 1$. By Bézout's identity, there exist integers $b, k$ with

(Bézout's identity is a standard consequence of the Euclidean algorithm applied to $a$ and $n$, established independently of group theory.) Then $ab - 1 = -kn$ is a multiple of $n$, so $[a]_n[b]_n = [ab]_n = [1]_n$. Thus $[a]_n$ has inverse $[b]_n$, i.e. $[a]_n$ is a unit. This proves the equivalence: $[a]_n$ is a unit $\iff \gcd(a,n) = 1$. Note this characterization is well-defined on classes: if $a \equiv a' \pmod n$ then $\gcd(a,n) = \gcd(a',n)$, since $a' = a + tn$ implies any common divisor of $a,n$ divides $a'$ and vice versa. $(\mathbb{Z}/n\mathbb{Z})^\times$ is a group. Multiplication restricted to units is closed: if $\gcd(a,n) = \gcd(b,n) = 1$, then $\gcd(ab, n) = 1$ (a prime dividing both $ab$ and $n$ would have to divide $a$ or $b$, contradicting coprimality with $n$), so $[a]_n[b]_n = [ab]_n$ is again a unit. Associativity and commutativity are inherited from $(\mathbb{Z}/n\mathbb{Z}, \cdot)$. The identity $[1]_n$ is a unit ($\gcd(1,n)=1$) and lies in $(\mathbb{Z}/n\mathbb{Z})^\times$. Every unit has an inverse by definition, and that inverse is itself a unit (if $[a]_n[b]_n = [1]_n$ then $[b]_n[a]_n = [1]_n$ too, by commutativity, so $[b]_n$ is a unit). Hence $(\mathbb{Z}/n\mathbb{Z})^\times$ satisfies all group axioms. Order $\varphi(n)$. By definition, $\varphi(n)$ counts the integers $a \in \{1, \dots, n\}$ with $\gcd(a,n) = 1$. Every residue class mod $n$ has a unique representative in $\{0, 1, \dots, n-1\}$ (shown in part (b)), or equivalently in $\{1, \dots, n\}$ (replacing representative $0$ by $n$, since $\gcd(0,n) = n$ and $\gcd(n,n)=n$ agree, and this does not affect the coprimality count as neither is coprime to $n$ unless $n=1$). By the characterization just proved, the classes that are units correspond exactly to representatives coprime to $n$, of which there are $\varphi(n)$ by definition. Hence $|(\mathbb{Z}/n\mathbb{Z})^\times| = \varphi(n)$. $\blacksquare$