Simple results that are clarified by abstract algebra

Question

There are many deep results whose proofs rely heavily on the abstraction of modern algebra (e.g., the unsolvability of the quintic). But what are some simple results (i.e., results that can be proven by elementary means) that are clarified by abstraction?

For example, Fermat's little theorem is an immediate consequence of Lagrange's theorem, which is a much more illuminating proof than other proofs that don't use group theory, in my opinion. Another example is Gauss's lemma, which says that if $f$ and $g$ are primitive polynomials (with, say, integer coefficients), then $fg$ is primitive. In ring theory, Gauss's lemma can be proven by reducing modulo a prime ideal: if $fg$ is not primitive, there is a prime $p$ such that the image of $fg$ in the integral domain $(\mathbb{Z}/p\mathbb{Z})[x]$ is zero, so the image of either $f$ or $g$ in $(\mathbb{Z}/p\mathbb{Z})[x]$ is zero, and hence either $f$ or $g$ is not primitive. There is also a (rather short) elementary proof of Gauss's lemma, though I would again argue that the proof using abstract algebra is significantly more illuminating.

Answer 1

Binomial coefficients

The number theoretic fact $\binom{n+m}{n} \in \mathbb{N}$, i.e. that $n! \cdot m!$ divides $(n+m)!$, follows from Lagrange's theorem from group theory applied to the natural embedding of symmetric groups $S_n \times S_m \hookrightarrow S_{n+m}$.

What is cool about this algebraic proof is that it immediately generalizes to multinomial coefficients and also to $q$-binomial coefficients when $q$ is a prime power: $\binom{n+m}{n}_q \in \mathbb{N}$, i.e. that $[n]_q! \cdot [m]_q!$ divides $[n+m]_q!$, follows since there is a natural embedding of projective spaces $\mathbb{P}(\mathbb{F}_q^n) \times \mathbb{P}(\mathbb{F}_q^m) \hookrightarrow \mathbb{P}(\mathbb{F}_q^n \times \mathbb{F}_q^m)$.

Irrational roots

If $n > 1$ and $p$ is a prime number, then $\sqrt[n]{p}$ is irrational. This is a consequence of Eisenstein's criterion since the polynomial $X^n - p$ is irreducible over $\mathbb{Q}$ and hence has no roots.

Pythagorean triples

The classification of the rational Pythagorean triples states that the map

$\displaystyle\mathbb{Q}^2 \setminus \{(0,0)\} \to \{(a,b) \in \mathbb{Q}^2 : a^2+b^2=1\},~ (x,y) \mapsto \left(\frac{x^2 - y^2}{x^2+y^2},\frac{2xy}{x^2+y^2}\right)$

is surjective. There is a convenient proof using Hilbert's Theorem 90 from Galois theory. Namely, it implies that every element of $\mathbb{Q}(i)$ with norm $1$ is equal to $a / \overline{a}$ for some $a \in \mathbb{Q}(i)^{\times}$ (since complex conjugation generates the Galois group), and this is equivalent to the claim.

Solvability of $x^2 \equiv -1$ modulo $p$

When is the equation $x^2 \equiv -1 \bmod p$ solvable? Clearly when $p = 2$. In general, it is equivalent to the equation $x^2 = -1$ in the finite field $\mathbb{F}_p$. If we assume $p \neq 2$, this is equivalent to $x \in \mathbb{F}_p^{\times}$ and $\mathrm{ord}(x)=4$ in the multiplicative group. Since the multiplicative group is cyclic, we can "reverse Lagrange's theorem" and see that the equation is solvable iff $4$ divides $p-1$. We have therefore shown, with abstract algebra, that the equation is solvable iff $p \equiv 1 \bmod 4$.

Associativity of symmetric difference

The symmetric difference of two subsets $A,B \subseteq X$ is defined by $A \,\Delta\, B := (A \cup B) \setminus (A \cap B)$. An elegant proof of the associativity of $\Delta$ uses the bijection $P(X) \cong \mathrm{Map}(X,\{0,1\})$ and observes that the latter is the underlying set of a $\mathbb{F}_2$-vector space $\mathrm{Map}(X,\mathbb{F}_2)$. If we pull back its addition to $P(X)$, we get $\Delta$. This way the associativity of $\Delta$ is simply a consequence of the associativity of $+$ on $\mathbb{F}_2$. But even more, we get a whole ring structure on $P(X)$ with this method (addition is $\Delta$, multiplication is $\bigcap$) and do not need to calculate anything for this.

Moebius inversion

All basic properties of the Moebius inversion are clarified by endowing the set of functions $\mathbb{N}^+ \to \mathbb{C}$ with a commutative ring structure: addition is pointwise, multiplication is $(f*g)(n) = \sum_{d ~ | ~ n } f(d) g(n/d)$. Define $\varepsilon : \mathbb{N}^+ \to \mathbb{C}$ by $\varepsilon(1)=1$ and $\varepsilon(n)=0$ for $n > 1$, this is the unit of the ring. Also define $1 : \mathbb{N}^+ \to \mathbb{C}$ to be constant $1$. The Moebius inversion formula can now be formulated as $g = 1 * f \implies f = \mu * g$. But this is an immediate consequence of $\mu * 1 = \varepsilon$ which is the definition of $\mu$.

Binomial coefficients again

If $p$ is a prime and $0 < k < p$, then $p \mid \binom{p}{k}$. Here is a proof using abstract algebra: We need to prove that $(X+1)^p = X^p + 1$ holds in the polynomial ring $\mathbb{F}_p[X]$. Both sides are monic of degree $p$, so the difference is a polynomial of degree $ < p$, and it vanishes on $\mathbb{F}_p$ by Fermat's little theorem (for which you already mentioned a group-theoretic proof), so it must be zero. This approach is also nice since a simple induction gives $(X+1)^{p^n}=X^{p^n}+1$ and hence also $p \mid \binom{p^n}{k}$ for $0 < k < p^n$.

Product rule

At least for polynomials (and thus for power series) the product rule $(f g)' = fg' + f'g$ has a nice algebraic proof using the ring of dual numbers $\mathbb{R}[\varepsilon]/\varepsilon^2$. Namely, the derivative of $f \in \mathbb{R}[T]$ is characterized (can be defined) by $f(T+ \varepsilon ) = f(T) + f'(T) \varepsilon$ in $\mathbb{R}[\varepsilon]/\varepsilon^2[T]$. This mimics the definition of the derivative in non-standard analysis. Now we calculate $$(f g)(T + \varepsilon) = f(T + \varepsilon) g(T + \varepsilon) = (f(T) + f'(T) \varepsilon) (g(T) + g'(T) \varepsilon)\\ = f(T) g(T) + f(T) g'(T) \varepsilon + f'(T) g(T) \varepsilon + \underbrace{f'(T) g'(T) \varepsilon^2}_{=0} = fg + (fg' + f'g) \varepsilon.$$

Fibonacci numbers

Binet's formula $F_n = (\varphi^n - (1-\varphi)^n)/\sqrt{5}$ for the Fibonacci numbers follows by diagonalizing the matrix $\begin{pmatrix} 1 & 1 \\ 1 & 0 \end{pmatrix}$, as is explained here. The matrix representation also implies the identities $(-1)^n = F_{n+1} F_{n-1} - F_n^2$ and $F_m F_{n+1} + F_{m-1} F_n = F_{m+n}$.

Infinitude of primes

Here is a group-theoretic proof (which I found here): Let $p$ be a prime number. We will show that there is a larger prime number. Let $q$ be a prime factor of $2^p - 1$, which means $2^p \equiv 1 \bmod q$. So $2$ has order $p$ in $\mathbb{F}_q^{\times}$, so $p \mid q-1$ by Lagrange's Theorem. Thus, $q > p$.

Determinants

If $A,B \in M_n(R)$ are square matrices, then $\det(AB) = \det(A) \det(B)$. Instead of calculating this directly, the best approach is to use the "coordinate free" definition of the determinant using exterior powers of modules. Namely, if $V$ is a free $R$-module of rank $n$, then $\Lambda^n(V)$ is a free $R$-module of rank $1$. Also, $\Lambda^n$ is a functor, so that every linear map $f : V \to V$ induces a linear map $\Lambda^n(V) \to \Lambda^n(V)$. Since $\Lambda^n(V) \cong R$, this is just multiplication with some ring element, the determinant $\det(f)$ of $f$. The functoriality immediately gives $\det(f \circ g) = \det(f) \cdot \det(g)$.

Vandermonde identity

Speaking of exterior powers: They satisfy the rule $$\Lambda^k(V \oplus W) \cong \bigoplus_{p=0}^{k} \Lambda^p(V) \otimes \Lambda^{k-p}(W).$$ (A quick proof uses that the functor $\Lambda^* : \mathbf{Mod}_R \to \mathbf{GradCommAlg}_R$ is left adjoint and hence preserves coproducts.) If $\dim(V)=n$, $\dim(W)=m$, by counting dimensions, we get the Vandermonde identity for binomial coefficients: $$\binom{n+m}{k} = \sum_{p=0}^{k} \binom{n}{p} \cdot \binom{m}{k-p}$$

Answer 2

My favorite example is Wilson's Congruence which states that an integer $p$ is prime iff $(p - 1)! \equiv -1 \; \mbox{mod} \; p$. I've seen at least one proof which does not rely on the language of group theory, but the proof seems more succinct when worded using facts about abelian groups:

If $A$ is an abelian group with exactly one element of order two, say $b$, then $\prod_{a \in A} a = b$. This follows because a group element is its own inverse iff it has order two or one. Applying this fact to the specific group $(\mathbb{Z}/p\mathbb{Z})^\times$ gives the desired result since $p - 1$ is the only element of order two in this group.

There are at least two other proofs of this fact using abstract algebra in pretty nice ways:

The polynomial $x^p - x$ can be shown to split into $p$ linear factors when viewed as a polynomial in $\mathbb{Z}/p\mathbb{Z}[x]$, and we have that $\prod_{i=1}^{p-1}(x - i) \equiv x^{p-1} - 1 \; \mbox{mod} \; p$. Setting $x = 0$ in this congruence gives the desired result.

The other proof uses one of the Sylow Theorems which states that the number of Sylow $p$-subgroups of a group is congruent to $1$ modulo $p$. You can deduce that the symmetric group of degree $p$ has exactly $(p - 2)!$ Sylow $p$-subgroups giving us $(p-2)! \equiv 1 \; \mbox{mod} \; p$, and the result follows by multiplying both sides by $p - 1$.

Answer 3

Here is another -- rather cute -- group-theoretic proof of

Fermat's little theorem

Fix a prime number $p$, and a positive integer $a$. Let $G$ the cyclic group generated by the $p$-cycle $ \sigma=(1,2,\dots,p)$, and let $G$ act on $X=\{1,2,\dots,a\}^p$. Stabilizers of elements of $X$ are either trivial, in which case their orbits contain $p$ elements, or else they are the whole of $G$, in which case their orbits have only one element of the form $(k,k,\dots, k)$ for one of the possible $a$ numbers between $1$ and $a$. Since the orbits partition the $a^p$ elements of $X$, we have $a+mp=a^p$ for some integer $m$, i.e. $a^p-a$ is divisible by $p$, and therefore if $a,p$ are co-prime, then also $a^{p-1}-1$ is divisible by $p$.

This proof is probably folklore. However, Stephen Kennedy published a short note in The Mathematical Gazette, (March 1994, p. 48) containing the same idea, albeit making no mention of the orbit-stabilizer theorem, which is an basic result in elementary group theory.