Abstract Algebra Basics

In $\mathbb Z_n$ (addition mod $n$) the element $a$ has order $\tfrac{n}{\gcd(a,n)}$: $6 \in \mathbb Z_{15}$ has order $5$. Cyclic groups of order $n$ have exactly one subgroup per divisor of $n$ ($\mathbb Z_{12}$ has $6$ subgroups) and exactly $\varphi(d)$ elements of order $d$ ($\mathbb Z_8$ has $2$ of order $4$). Consequences of Lagrange: a group of prime order is cyclic; $a^{|G|} = e$ for all $a$ — which IS Fermat–Euler when $G = (\mathbb Z/n)^\times$.

A permutation's order is the lcm of its cycle lengths — a Putnam question asks for the maximum order in $S_n$ (Landau's function) or the number of elements of a given order. Any finite subset of a group closed under the operation is a subgroup (finite cancellation forces inverses). If every element satisfies $g^2 = e$ the group is abelian. These small lemmas are quotable and graders expect them.

Over $\mathbb Z/n$ with $n$ composite that fails ($x^2 - 1$ has four roots mod $8$) — the root-count bound is a FIELD property. Wilson's theorem $(p-1)! \equiv -1$ is "pair each element with its inverse"; $x^{p-1} - 1 = \prod_{a\ne0}(x - a)$ in $\mathbb F_p[x]$ is the same fact as a polynomial identity. Frobenius $x \mapsto x^p$ is a ring homomorphism in characteristic $p$: $(a + b)^p = a^p + b^p$.

The left cosets $gH$ partition $G$: two cosets either coincide or are disjoint (if $g_1H \cap g_2H \ne \emptyset$ then $g_2^{-1}g_1 \in H$, forcing $g_1H = g_2H$), and every element lies in its own coset. Each coset has exactly $|H|$ elements (the map $h \mapsto gh$ is a bijection $H \to gH$). So $|G| = (\text{number of cosets})\cdot|H|$. $\blacksquare$ Significance: Fermat's little theorem, Euler's theorem, and "a group of prime order is cyclic" are all corollaries — Lagrange is the one group-theory proof every Putnam competitor should be able to write from memory.

If $P(a) = 0$, divide: $P(x) = (x - a)Q(x)$ with $\deg Q = \deg P - 1$ (polynomial division needs only that the leading coefficient of $x - a$ is invertible). Any other root $b \ne a$ satisfies $(b - a)Q(b) = 0$, and in a FIELD $b - a \ne 0$ is invertible, so $Q(b) = 0$. Induct on the degree. $\blacksquare$ Over $\mathbb Z/8$, $(b - a)$ can be a zero divisor ($2\cdot4 = 0$), and $x^2 - 1$ has the four roots $1, 3, 5, 7$. Significance: this is why $\mathbb F_p^\times$ is cyclic and why Lagrange interpolation works — uniqueness of polynomials from values is a field theorem.

Step 1 — the order of a permutation is the lcm of its cycle lengths, which sum to at most $10$.

Step 2 — maximize $\mathrm{lcm}$ subject to the sum: try $2 + 3 + 5 = 10$, lcm $30$; $3 + 7 = 10$, lcm $21$; $4 + 5 = 9$, lcm $20$; $1 + 2 + 3 + 4$? sum $10$, lcm $12$; $2 + 3 + 5$ wins.

Step 3 — the maximum is $30$ (Landau's function $g(10) = 30$).

Step 4 — the same reasoning gives the number of elements of order $2$ in $S_n$ (products of disjoint transpositions) and answers every "orders in $S_n$" Putnam question: it is a partition problem in disguise.

Step 1 — take $h \in H$; the powers $h, h^2, h^3, \ldots$ all lie in $H$ (closure) and $H$ is finite, so $h^i = h^j$ for some $i < j$, whence $h^{j-i} = e$: the identity is in $H$.

Step 2 — with $k = j - i \ge 1$, $h^{k-1}$ is in $H$ (it is $e$ if $k = 1$, otherwise a positive power) and $h\cdot h^{k-1} = e$: the inverse of $h$ lies in $H$.

Step 3 — closure, identity, inverses: a subgroup. $\blacksquare$ Finiteness converted "closed under multiplication" into "closed under inverses" — infinite counterexample: the positive integers inside $(\mathbb Z, +)$.

Step 1 — pair each element $g$ with its inverse $g^{-1}$. This is an involution on $G$: $(g^{-1})^{-1} = g$.

Step 2 — the elements with $g \ne g^{-1}$ fall into pairs $\{g, g^{-1}\}$, so there is an even number of them.

Step 3 — hence the number of elements with $g = g^{-1}$, i.e. $g^2 = e$, has the same parity as $|G|$: it is even.

Step 4 — the identity is one of them, so there is at least one more, $g \ne e$ with $g^2 = e$: an element of order $2$. $\blacksquare$ (This is the prime $2$ case of Cauchy's theorem.)

How to find it. Counting a set modulo $2$ by pairing its elements is the standard move when the only information is a parity; the unpaired elements are the fixed points of the pairing, and here they are exactly the solutions of $g^2 = e$.