Fundamental Theorem of Finite Abelian Groups

We argue by strong induction on $|G|$. If $G = \langle x\rangle$ there is nothing to prove: take $H = \{e\}$. So assume $\langle x \rangle \neq G$ and let $|x| = p^n$, the maximal order in $G$, so $g^{p^n} = e$ for every $g \in G$.

Step 1: choose a suitable complement candidate. Since $\langle x \rangle \neq G$, pick $y \in G \setminus \langle x\rangle$ of smallest possible order among elements outside $\langle x \rangle$; say $|y| = p^m$. We claim $y^p \in \langle x \rangle$. Indeed $y^p$ has order $p^{m-1} < p^m$, and by minimality of $m$ among orders of elements outside $\langle x\rangle$, any element of order less than $p^m$ that lies outside $\langle x \rangle$ would contradict the choice of $y$ — more precisely, $y^p$ has strictly smaller order than $y$, so if $y^p \notin \langle x \rangle$ it would be an element outside $\langle x\rangle$ of order $p^{m-1}<p^m$, contradicting minimality of $m$. Hence $y^p \in \langle x \rangle$, say $y^p = x^j$ for some integer $j$.

Step 2: adjust $y$ to get an element of order $p$ intersecting $\langle x\rangle$ trivially, outside $\langle x \rangle$. Since $y^{p^m} = e$, applying the relation repeatedly gives $x^{j p^{m-1}} = (y^p)^{p^{m-1}} = y^{p^m} = e$. As $|x| = p^n$, this means $p^n \mid j p^{m-1}$. Because $|y| = p^m \le p^n$ (maximality of $|x|$ among all elements), write $j p^{m-1} = p^n t$ for some integer $t$. We want to solve $x^i{}^{\,p} = x^{-j}$, i.e. find $i$ with $ip \equiv -j \pmod {p^n}$, so that $z := y x^{i}$ satisfies $z^p = y^p x^{ip} = x^{j + ip} = e$. Since $p^n \mid jp^{m-1}$ and $m \le n$, we get $p^{n-m+1}\mid j$ (dividing by $p^{m-1}$, valid as $m\ge 1$); in particular $p \mid j$ because $n-m+1 \geq 1$ (as $m \le n$). Write $j = p j'$. We need $ip \equiv -pj' \pmod{p^n}$, i.e. $i \equiv -j' \pmod{p^{n-1}}$, which is solvable: take $i = -j'$. Set $z = y x^{i}$. Then $z^p = e$, and $z \notin \langle x \rangle$ (since $y \notin \langle x\rangle$ and $x^i \in \langle x \rangle$, so $z \in \langle x\rangle \iff y \in \langle x \rangle$, false). Thus $z$ has order exactly $p$, lies outside $\langle x \rangle$, and $\langle z \rangle \cap \langle x \rangle = \{e\}$ because $\langle z\rangle$ has prime order $p$ and its only nontrivial elements are powers of $z$, none of which lie in $\langle x\rangle$.

Step 3: pass to the quotient and apply induction. Let $N = \langle z \rangle$, a subgroup of order $p$ with $N \cap \langle x \rangle = \{e\}$. Consider $\bar G = G/N$, an abelian $p$-group of order $|G|/p < |G|$. Let $\bar x$ be the image of $x$ in $\bar G$. Since $N \cap \langle x\rangle = \{e\}$, the map $\langle x \rangle \to \bar G$ is injective, so $\bar x$ has order $p^n$, the same as $x$. We claim $\bar x$ has maximal order in $\bar G$. Suppose some $\bar g \in \bar G$ has order $p^s$. Lift to $g \in G$; then $g^{p^s} \in N$, so $g^{p^{s+1}} \in N^p = \{e\}$ (as $|N|=p$), giving $|g| \mid p^{s+1}$, hence $|g| \le p^{n}$ by maximality of $p^n$ in $G$, hence $p^s = |\bar g| \le |g| \le p^n$. So indeed $p^n$ is the maximal order in $\bar G$, attained by $\bar x$. By the inductive hypothesis applied to $\bar G$ (which has strictly smaller order), there is a subgroup $\bar H \leq \bar G$ with

Let $H$ be the preimage of $\bar H$ under the quotient map $G \to \bar G$; so $N \le H \le G$ and $H/N = \bar H$.

Step 4: verify $G = \langle x \rangle \times H$. Intersection. If $g \in \langle x \rangle \cap H$, then $\bar g \in \langle \bar x \rangle \cap \bar H = \{\bar e\}$, so $g \in N$. But also $g \in \langle x\rangle$ and $N \cap \langle x \rangle = \{e\}$, forcing $g = e$. Hence $\langle x\rangle \cap H = \{e\}$. Sum. For any $g \in G$, $\bar g \in \bar G = \langle \bar x\rangle \bar H$, so $\bar g = \bar x^{a} \bar h$ for some integer $a$ and $\bar h \in \bar H$; lifting, $g x^{-a} h^{-1} \in N \le H$ for a preimage $h \in H$ of $\bar h$. So $g \in x^a H \cdot H = x^a H \subseteq \langle x\rangle H$. Hence $G = \langle x \rangle H$. Since $G$ is abelian, $\langle x \rangle$ and $H$ are both normal, their intersection is trivial, and their product is all of $G$; this is precisely the statement $G = \langle x \rangle \times H$ (internal direct product criterion). $\blacksquare$

(Existence of elementary divisor form, main proof.) First reduce to $p$-groups. Since $G$ is a finite abelian group, write $|G| = p_1^{a_1} \cdots p_r^{a_r}$ with distinct primes $p_i$. For each $i$ let

the $p_i$-primary component (also called the Sylow $p_i$-subgroup, though for abelian groups Sylow's theorem gives uniqueness immediately since $G_{p_i}$ is the unique subgroup of order $p_i^{a_i}$, but we do not need to invoke Sylow's theorem itself — we use a direct argument). Claim: $G = G_{p_1} \times \cdots \times G_{p_r}$. Each $G_{p_i}$ is a subgroup (closed under the group operation since $G$ is abelian, so if $g^{p_i^{a_i}} = h^{p_i^{a_i}} = e$ then $(gh)^{p_i^{a_i}} = g^{p_i^{a_i}}h^{p_i^{a_i}} = e$; inverses are similar). For any $g \in G$ of order $n \mid |G|$, write $n = \prod p_i^{b_i}$ with $b_i \le a_i$, and let $n_i = n / p_i^{b_i}$; the integers $n_1, \dots, n_r$ are coprime as a set is not quite immediate, so instead argue directly: since $|G| = \prod p_i^{a_i}$ and $g^{|G|} = e$ (Lagrange), write $|G| = m_i \cdot p_i^{a_i}$ where $m_i = \prod_{j \ne i} p_j^{a_j}$, so $\gcd(m_1, \dots, m_r) = 1$. By Bézout (extended, for $r$ integers), there exist integers $c_1, \dots, c_r$ with $\sum_i c_i m_i = 1$. Set $g_i = g^{c_i m_i}$; then $g_i^{p_i^{a_i}} = g^{c_i m_i p_i^{a_i}} = g^{c_i |G|} = e$, so $g_i \in G_{p_i}$, and

This shows $G = G_{p_1} \cdots G_{p_r}$ (product of subgroups, all normal as $G$ is abelian). For the intersection condition: if $g \in G_{p_i} \cap \prod_{j \ne i} G_{p_j}$, then $g$ has order dividing $p_i^{a_i}$ and also order dividing $\prod_{j\ne i} p_j^{a_j}$ (a product of the coprime primary components has order dividing the product of their orders, by an induction using that elements of coprime-order subgroups of an abelian group intersect trivially — since if $g$ lies in a subgroup of order dividing $m$ and one of order dividing $m'$ with $\gcd(m,m')=1$, then $|g|$ divides $\gcd(m,m')=1$, so $g=e$). Hence the intersection is trivial and $G = G_{p_1} \times \cdots \times G_{p_r}$ internally. So it suffices to decompose each $G_{p_i}$, a finite abelian $p_i$-group, into cyclic $p_i$-power factors. We do this by strong induction on the order of a finite abelian $p$-group $P$. If $|P| = 1$, take the empty product. Otherwise, let $x \in P$ have maximal order (such an element exists since $P$ is finite). By the splitting lemma above,

for some subgroup $H$ with $|H| = |P|/|x| < |P|$. By the inductive hypothesis, $H$ decomposes as a direct product of cyclic groups of $p$-power order, and adjoining $\langle x \rangle$ to this list decomposes $P$. This completes the existence part of elementary divisor form. Assembling the decompositions of $G_{p_1}, \dots, G_{p_r}$ gives the elementary divisor decomposition of $G$. $\blacksquare$

(Uniqueness of elementary divisor form.) Suppose

are two elementary divisor decompositions. First, the primary decomposition $G = \bigoplus_p G_p$ constructed above is intrinsic to $G$ (it does not depend on any choice: $G_p = \{g \in G : g \text{ has order a power of } p\}$ is forced), and under any decomposition into prime-power cyclic factors, the factors of $p$-power order must assemble (by uniqueness of primary decomposition, proven via the argument above showing $G_p$ is exactly the set of elements of $p$-power order, which is determined by $G$ alone) to give $G_p$. So it suffices to prove uniqueness for a $p$-group: if

and also

then $k = m$ and $e_i = f_i$ for all $i$. We use the standard counting invariant: for $s \geq 0$, consider the subgroup

(written additively; this is a subgroup since $P$ is abelian). For a cyclic group $\mathbb{Z}/p^e$, we have $|p^s (\mathbb{Z}/p^e)| = p^{\max(e-s,0)}$, since multiplication by $p^s$ on $\mathbb{Z}/p^e\mathbb{Z}$ has image of size $p^e / \gcd(p^e, p^s) = p^{\max(e-s,0)}$. Since $|p^s(A \times B)| = |p^s A|\cdot|p^s B|$ for a direct product, we get from the first decomposition

and from the second

Since $|p^s P|$ is an invariant of $P$ alone (not of the decomposition), these two expressions are equal for every $s \geq 0$:

Define $a_s = \#\{i : e_i > s\}$ (equivalently, a strictly decreasing count) — more precisely, define for each $s\ge 0$ the quantity $A(s) = \sum_i \max(e_i-s,0)$; this is exactly the number of lattice points $\#\{(i,t) : 1\le t\le e_i,\ t > s\}$, i.e. $A(s) = \sum_{t > s} r(t)$ where $r(t) = \#\{i : e_i \ge t\}$. In particular $A(s-1) - A(s) = r(s)$ for $s \geq 1$ (taking $A(-1)$ formally if needed, or just $s\ge 1$), i.e.

By $(\ast)$, $A(s)$ is the same function whether computed from the $e_i$'s or the $f_j$'s, so $r(s) = \#\{i : e_i \ge s\}$ equals $\#\{j : f_j \ge s\}$ for every $s \geq 1$. Two partitions (the multiset $\{e_i\}$ and the multiset $\{f_j\}$, both consisting of positive integers) with the same number of parts $\ge s$ for every $s \ge 1$ are identical as multisets: taking $s=1$ gives $k = m$ (total number of parts), and comparing the counts $r(s)$ for consecutive $s$ recovers exactly how many $e_i$ equal each value, which must match the corresponding count for $f_j$. Hence sorting both in decreasing order, $e_i = f_i$ for all $i = 1, \dots, k = m$. This proves uniqueness of the elementary divisors. $\blacksquare$

Existence. Given the elementary divisor decomposition of $G$, group the prime-power cyclic factors by prime: for each prime $p$ dividing $|G|$, let the elementary divisors at $p$ be $p^{e_{p,1}} \ge p^{e_{p,2}} \ge \cdots \ge p^{e_{p,k_p}}$ (possibly $k_p=0$ if $p$ does not occur). Let $k = \max_p k_p$, and for $1 \le i \le k$ define

where the product runs over all primes $p$ occurring in $G$'s factorization, with the convention $e_{p,i} = 0$ (contributing factor $p^0=1$) if $p$ has fewer than $i$ elementary divisors, and we index so that $d_1$ uses the smallest elementary divisor at each prime (i.e. reindex $i=1,\dots,k$ from smallest to largest so that $d_1 \mid d_2 \mid \cdots \mid d_k$; concretely list each prime's exponents in increasing order $e_{p,1}\le e_{p,2}\le\cdots$, pad shorter lists with zeros on the left, and multiply across primes column by column). Since for a fixed $i$, the exponents $e_{p,i}$ range over distinct primes $p$, the Chinese Remainder Theorem gives

(using the standard fact that $\mathbb{Z}/mn\mathbb{Z} \cong \mathbb{Z}/m\mathbb{Z}\times \mathbb{Z}/n\mathbb{Z}$ when $\gcd(m,n)=1$, applied repeatedly). Rearranging the direct product of all the prime-power cyclic factors of $G$ by this column grouping and applying CRT column-by-column shows

Because for each prime $p$ the exponents were listed in increasing order (padding with $0$, i.e. factor $1$, for missing columns on the low end), we get $e_{p,1}\le e_{p,2}\le\cdots\le e_{p,k}$ for every $p$, hence $d_i \mid d_{i+1}$ for all $i$ (each prime's contribution to $d_i$ divides its contribution to $d_{i+1}$). Discard any $d_i = 1$ from the start of the list (they contribute a trivial factor). This proves existence of the invariant factor decomposition. Uniqueness. Suppose $G \cong \mathbb{Z}/d_1 \times \cdots \times \mathbb{Z}/d_k$ with $d_1 \mid \cdots \mid d_k$, all $d_i \ge 2$. Factor each $d_i = \prod_p p^{e_{p,i}}$ into prime powers; by CRT, $\mathbb{Z}/d_i \cong \prod_p \mathbb{Z}/p^{e_{p,i}}$ (again with $e_{p,i}=0$ meaning that prime is absent, contributing a trivial factor). Expanding all $k$ factors this way yields an elementary divisor decomposition of $G$. Since $d_i \mid d_{i+1}$, for every prime $p$ we have $e_{p,i} \le e_{p,i+1}$ (a prime power divides another times something coprime only if the exponent doesn't decrease — precisely, $d_i \mid d_{i+1}$ implies $p^{e_{p,i}} \mid d_{i+1}$, and since $p^{e_{p,i+1}}$ is the full $p$-part of $d_{i+1}$, we need $e_{p,i}\le e_{p,i+1}$). By the uniqueness of elementary divisors already proven, the multiset $\{p^{e_{p,i}} : i=1,\dots,k,\ e_{p,i}>0\}$ for each fixed $p$ is an isomorphism invariant of $G$, hence determined. Since the sequence $e_{p,1}\le \cdots \le e_{p,k}$ is the sorted list of these exponents padded with zeros to length $k$ (where $k$ is also forced, being the number of invariant factors, matching the largest number of elementary divisors at any single prime — if this padding is done consistently to the same length $k$ for every prime, which is required for the $d_i$ to multiply correctly), the exponents $e_{p,i}$ are uniquely recovered for each $p$ and each $i$, hence each $d_i = \prod_p p^{e_{p,i}}$ is uniquely recovered. This proves uniqueness of the invariant factors. $\blacksquare$