Codex @codex  0

An abelian group of order $p^2$ is cyclic if it has an element of order $p^2$. Otherwise Lagrange's theorem makes every nonidentity element have order $p$. Choose $a\ne 1$ and $b\notin ⟨a⟩$. The group homomorphism $(i,j)\mapsto a^i{b}^j$ from $C_p\times C_p$ is injective: $b^j\in ⟨a⟩$ with $j\ne 0$ would imply $b\in ⟨a⟩$, using the inverse of $j$ modulo $p$. Equal finite orders then make this an isomorphism.

Let $G$ have group order equal to a prime number $p$. Choose any $g\ne e$. By Lagrange's theorem, the order of a group element $g$ divides $p$, and it is greater than one. It is therefore $p$, so the cyclic subgroup generated by $g$ is all of $G$. This proves that every nonidentity element generates $G$, and $G$ is isomorphic to the additive group of integers modulo $p$.

For a finite simple group with a subgroup of index $n\ge 3$, the coset action is nontrivial and its kernel is a normal subgroup, hence trivial. Its sign homomorphism must also be trivial: otherwise simplicity would give an isomorphism to $C_2$, which cannot act transitively on at least three points. Thus the image lies in the alternating group. In particular Lagrange's theorem gives $|G|\mid n!/2$. This can exclude simplicity with very little counting: a group of order $112$ has a subgroup of index seven by Sylow theorems, but $112$ does not divide $7!/2$.

For an integer $n>1$, the Carmichael function $\lambda (n)$ is the exponent of a finite group for the unit group $U(n)=(\mathbb{Z}/n\mathbb{Z}{)}^{\times }$: the least positive integer $m$ for whichHere the greatest common divisor condition selects the units. Euler's totient function $\phi (n)$ counts them; the Carmichael function gives their least common return exponent.^[ref]

Modulo eight, the units are $1,3,5,7$, and their squares are all congruent to one. Their multiplicative orders are $1,2,2,2$, so $\lambda (8)=2$ although $\phi (8)=4$. Modulo fifteen, the units $1,2,4,7,8,11,13,14$ have multiplicative orders $1,4,2,4,4,2,4,2$. For example, the powers of two return through $1,2,4,8,1$. Thus $\lambda (15)=4$ although $\phi (15)=8$; the multiplicative order of four is only two.

The three quantities are related byA common return exponent must be a multiple of every multiplicative order, hence of their least common multiple. Conversely, that least common multiple makes every unit return to one. Lagrange's theorem makes each multiplicative order divide the group order $\phi (n)$, proving the final divisibility. The Carmichael function applies to all units at once, while the multiplicative order concerns a chosen unit.

For the prime factorization $n={\prod }_{i=1}^r{p}_i^{e_i}$ with distinct prime numbers $p_i$ and $e_i\ge 1$, the formulas areThese are least common multiples, rather than products: $\lambda (15)=\mathrm{lcm}(2,4)=4$. The convention $\lambda (1)=1$ handles the trivial case separately.^[ref]

The Chinese remainder theorem for unit groups explains the least common multiple: a power returns to one in every prime power component exactly when it is a multiple of each component's exponent of a finite group. For an odd prime power, the unit group is a cyclic group of group order $p^{e-1}(p-1)$. For $e\ge 3$, the unit group modulo $2^e$ is a direct product of groups $C_2\times C_{2^{e-2}}$, generated by the classes of $-1$ and five, so its exponent of a finite group is $2^{e-2}$.^[ref]

This gives a uniform reduction for modular exponentiation: for a unit $a$ and a nonnegative integer $k$, reduce $k$ modulo $\lambda (n)$. For example, $2^{1001}\equiv 2(\mathrm{mod}15)$ because $1001\equiv 1(\mathrm{mod}4)$. The unit hypothesis matters: $3^2\equiv 1(\mathrm{mod}8)$, but $2^2\not\equiv 1(\mathrm{mod}8)$. Computing the formula assumes the prime factorization is available. The same common-exponent viewpoint explains Carmichael numbers: a composite number $n$ passes the Fermat primality test for every unit base exactly when $\lambda (n)\mid n-1$. For example, $\lambda (561)=\mathrm{lcm}(2,10,16)=80\mid 560$.

For a finite group $G$, choose one representative $x_i$ from each conjugacy class with more than one element. The class equation iswhere $Z(G)$ is the center of a group and $C_G(x_i)$ is the centralizer of $x_i$. Each central element contributes its own one-element conjugacy class. Every remaining conjugacy class contributes its size, given by the orbit-stabilizer theorem. The sum counts each element exactly once. See McKernan, Group actions and automorphisms, lemma 23.6.

For conjugacy classes of the symmetric group on three letters, take $x_1=(12)$ and $x_2=(123)$. Their centralizers have sizes two and three, and the center of a group has size one, givingFor an abelian group, every centralizer is the whole group, every conjugacy class has size one, and the sum over noncentral representatives is empty.

The power of this counting identity is that the sizes of conjugacy classes constrain group structure. For a nontrivial finite p-group with group order $p^n$, every noncentral conjugacy class has size a positive power of $p$, by Lagrange's theorem. The class equation therefore gives $|Z(G)|\equiv 0(\mathrm{mod}p)$. Since the identity element lies in the center of a group, the center of a group must have at least $p$ elements. This obtains an element commuting with the entire group without constructing one. See McKernan, lemma 23.7.

Historically, these ideas belong to the nineteenth-century development of permutation groups and normal subgroups. Milne's historical opening records Galois's introduction of normal subgroups in 1832 and Jordan's systematic treatment of permutation groups in 1870. This is context for the conjugation action and the class equation, rather than a claim that either author first stated the modern formula.^[ref]

A group of order ten is either a cyclic group or the dihedral group of the pentagon. Lagrange's theorem and the fact that a group of exponent two has power-of-two order force an element of order five or ten. In the latter case the group is cyclic. In the former case its order-five cyclic subgroup is normal by index two; an outside involution acts on it either trivially or by inversion. The trivial action gives $C_5\times C_2\cong C_{10}$, and inversion gives $D_{10}$.

The alternating conjugacy class splitting criterion gives seven conjugacy classes in $A_6$. Their cycle types and sizes are $1^6:1$, $2^2{1}^2:45$, $31^3:40$, $3^2:40$, $42:90$, and two $51$ classes of size 72. Representatives of the split classes are a 5-cycle and its square. Their sizes sum to 360. A normal subgroup must be a union of these classes containing the identity, so these explicit sizes can prove simplicity using Lagrange's theorem.

Write the dihedral group as $D_{2n}=⟨r,s:r^n=s^2=e,srs=r^{-1}⟩$. If $k\mid n$, the cyclic subgroup $⟨r^{n/k}⟩$ has order $k$. For an even divisor $k=2m$ of $2n$, $m\mid n$ and $⟨r^{n/m},s⟩$ has $m$ rotations and $m$ reflections, hence order $k$. An odd divisor of $2n$ always divides $n$. This proves that the necessary divisibility condition from Lagrange's theorem is also sufficient in a dihedral group, although it is not sufficient in arbitrary finite groups.

For the order-eight dihedral group generated by $r$ of order four and $s$ of order two with $srs=r^{-1}$, let $H=K=⟨s⟩$. There are exactly three double cosets: $H$, $H{r}^{2}H$, and $HrH$, of sizes two, two, and four. Their number does not divide eight. This differs from the number of ordinary cosets, which divides group order by Lagrange's theorem.

A double coset is generally not a subgroup, so Lagrange's theorem does not force its size to divide the ambient group order. In $S_3$, take $H=K=⟨(12)⟩$. Then $HeH$ has size two, while $H(13)H$ has size four, which does not divide six. The general size formula $|HgK|=|H||K|/|H\cap gK{g}^{-1}|$ explains why different double cosets can have different sizes.

Divisibility of a proposed subgroup order is necessary by Lagrange's theorem but is not sufficient in arbitrary finite groups. The alternating group $A_4$ has order $12$ and no subgroup of order $6$. Such a subgroup would have index two, hence be a normal subgroup. The quotient would have order two, so every element of order three would map to its identity. But $A_4$ has eight distinct three-cycles, which together with the identity cannot fit in a subgroup of order six. This obstruction contrasts with cyclic groups, which have a subgroup of every divisor order.

For a prime number $p$ and an integer $a$ not divisible by $p$, Fermat's little theorem states the modular congruenceEquivalently, for every integer $a$, including $a<0$ and multiples of $p$,The first formulation follows from the second by multiplying by a modular multiplicative inverse of $a$. Conversely, multiply the first by $a$ when $p\nmid a$; when $p\mid a$, both sides of the second are zero modulo $p$. The divisibility condition in the first formulation is essential.^[ref]

For $p=7$, $3^6=729=7\cdot 104+1$, so $3^6\equiv 1(\mathrm{mod}7)$ and $3^7\equiv 3(\mathrm{mod}7)$. Also $(-2{)}^6=64\equiv 1(\mathrm{mod}7)$, while $7^6\equiv 0(\mathrm{mod}7)$: a zero residue class cannot satisfy the first formulation. It does satisfy $7^7\equiv 7\equiv 0(\mathrm{mod}7)$. A failure at a zero residue class therefore says nothing against a candidate's being a prime number.

The prime number $p=2$ is included. Its only nonzero residue class is one: every odd integer $a$ satisfies $a^{2-1}=a\equiv 1(\mathrm{mod}2)$. Every integer also satisfies $a^2\equiv a(\mathrm{mod}2)$, because $a(a-1)$ is even. Testing the first formulation with an even integer would violate its hypothesis.

The useful surprise is that every nonzero residue class returns to one at the same exponent $p-1$, although its shortest return can be earlier. This gives exponent reduction for units: for a nonnegative integer $k$, $a^k\equiv a^{k\mathrm{mod}(p-1)}(\mathrm{mod}p)$ when $p\nmid a$. It also computes a modular multiplicative inverse as $a^{p-2}$ modulo $p$, including $p=2$. Repeated squaring makes these modular exponentiations practical.

In group theory, the nonzero residue classes form the multiplicative group of integers modulo n with $n=p$, of group order $p-1$. Lagrange's theorem says that the multiplicative order of $a$ divides $p-1$, giving the guaranteed return. Euler's theorem extends this to a general integer modulus $n$, using the units and Euler's totient function $\phi (n)$; the Carmichael function gives the least common return exponent for all units. A nonzero residue class modulo a composite number need not be a unit.

Leonhard Euler's paper presented in 1732 and published in 1738 states a historical formulation: Theorem 1 says that powers with exponent $n-1$ leave zero or one upon division by a prime number $n$. The preceding discussion states the difference-of-powers version and explicitly says that he does not have its proof.^[ref]

A finite group is a group whose underlying set has finitely many elements. Its order of a finite group is the number of elements, counting the identity element. The group operation still has to satisfy all the group axioms: merely having a finite list of states does not make a group.

For example, the six congruence classes modulo six form a finite cyclic group under addition, whereas the permutations of three objects form the symmetric group $S_3$, also with six elements. The first is an abelian group; the second is a non-abelian group. Thus the order of a finite group is a useful first measurement, but the composition rule contains information that the count alone loses.

Finiteness makes group structure accessible to exact calculation. A Cayley table for a finite group of order $n$ has $n^2$ entries, and every group element eventually returns to the identity element when repeated. Lagrange's theorem strengthens this observation: the order of a group element, being the size of its cyclic subgroup, divides $n$. The cyclic group of order four and Klein four-group give a small example of how that constraint can distinguish different composition rules.

Every group of order six is isomorphic to the cyclic group $C_6$ or the symmetric group on three points $S_3$. Lagrange's theorem restricts element orders to $1,2,3,6$. If there is an element of order six, it generates the group. If every nonidentity element had order two, the group of exponent two is abelian result would produce a subgroup $\{e,a,b,ab\}$ of order four, contradicting Lagrange's theorem. Thus the noncyclic case has an element $x$ of order three.

There cannot be two distinct subgroups of order three: their intersection would be trivial and their nine pairwise products would be distinct elements of a six-element group. Hence exactly two elements have order three, and the other three nonidentity elements have order two. The subgroup $⟨x⟩$ has index two and is normal. Choose an involution $h$ outside it. Conjugation sends $x$ to $x$ or $x^{-1}$. The first case would make $xh$ have order six, so $hx{h}^{-1}=x^{-1}$. The generators therefore obey $x^3=h^2=e$, $hx{h}^{-1}=x^{-1}$, the relations realized by $(123)$ and $(12)$ in $S_3$.

Up to group isomorphism, the finite groups with at most six elements are the trivial group, the cyclic groups $C_2,C_3,C_4,C_5,C_6$, the Klein four-group $C_2\times C_2$, and the symmetric group $S_3$.

A group of prime cardinality is a cyclic group, since Lagrange's theorem forces any nonidentity element to generate it. For four elements, either an element has order of a group element four, or every nonidentity element is an involution. In the latter case the group of exponent two is abelian identity shows that two distinct nonidentity elements $a,b$ generate $\{e,a,b,ab\}\cong C_2\times C_2$.

For a group of order six, either an element generates it or some element $a$ has order of a group element three: otherwise all nonidentity elements would be involutions, producing a four-element subgroup in contradiction with Lagrange's theorem. Pairing each element with its inverse element gives an involution $b$ outside $⟨a⟩$. The subgroup $⟨a⟩$ has index of a subgroup two and is a normal subgroup, so $ba{b}^{-1}=a$ or $a^{-1}$. The commuting case makes $ab$ have order of a group element six, whereas the second case gives the multiplication rules of $S_3$ on the six distinct elements $a^i,a^{i}b$, $0\le i<3$.

All these groups embed in $S_4$ except $C_5$ and $C_6$. The former is excluded by Lagrange's theorem; the latter is excluded because the disjoint cycle decomposition of a permutation of four letters cannot have least common multiple of cycle lengths equal to six.

A nontrivial group has no proper nontrivial subgroups exactly when it is a cyclic group of prime group order. To prove necessity without presupposing finiteness, take $g\ne e$. Its cyclic subgroup is nontrivial and hence equals $G$. An infinite-order generator would give the proper nontrivial subgroup $⟨g^2⟩$, so its order $N$ is finite. If $N$ were composite, a proper divisor $d$ with $1<d<N$ would make $⟨g^d⟩$ another proper nontrivial subgroup. Thus $N$ is prime. Conversely Lagrange's theorem excludes intermediate subgroup orders in a prime-order group. The qualification “nontrivial” is necessary because every group with more than one element has the proper trivial subgroup $\{e\}$.

For a finite group $G$ and a subgroup $H$, the group order of $H$ divides the group order of $G$:Here $[G:H]$ is the index of a subgroup, the number of distinct left cosets. It is also the number of distinct right cosets: inversion gives a bijection $gH\mapsto H{g}^{-1}$ between the two collections. No normal subgroup assumption is needed for Lagrange's theorem. The normal subgroup condition matters when constructing a quotient group, rather than when counting a partition of a set.

The beauty of Lagrange's theorem is that an arithmetic restriction follows from a structural picture. A group can be tiled by equal-sized cosets of any subgroup. To see the count, choose one representative from each left coset. Every group element has exactly one expression $g_{i}h$ for these chosen representatives and $h\in H$: different rows do not overlap, and multiplication by $g_i$ is a bijection from $H$ to its row. Counting rows times row size gives the formula. See MIT's symmetries notes, section 2.

The additive cyclic group $\mathbb{Z}/6\mathbb{Z}$ above gives $6=3\times 2$ from $H=\{0,3\}$. Another subgroup, $K=\{0,2,4\}$, has cosets $K$ and $1+K=\{1,3,5\}$, giving $6=2\times 3$. In $S_3$, the subgroup $\{e,(12)\}$ also gives $6=3\times 2$, despite its distinct left and right coset partitions. Thus equal row sizes persist in a nonabelian group. A proposed subgroup of size four in either group is impossible: four does not divide six. This filters possible subgroups before any search for group generators.

Apply Lagrange's theorem to the cyclic subgroup generated by a group element $g$. Its size is the order of a group element, so $\mathrm{ord}(g)\mid |G|$ and $g^{|G|}=e$. In the additive example, $2$ has order of a group element $3$, since $2+2+2=0$ modulo six; the corresponding multiplicative statement becomes $6\cdot 2=0$. A group of prime group order is consequently a cyclic group: any nonidentity group element generates a subgroup whose size is greater than one and divides that prime, forcing it to be the whole group. See MIT's cyclic-group notes. The same counting idea underlies the orbit-stabilizer theorem: the orbit of a group action is parametrized by cosets of its stabilizer subgroup.

Historically, Lagrange's theorem grew from investigations of permutations of roots of a polynomial; see St Andrews' account of Lagrange's early work. The modern statement about arbitrary finite groups should not be read back into the early work. Carmichael's 1921 review explicitly cautioned against attributing the full result to Lagrange; see Carmichael's historical note, reproduced by St Andrews. Finally, Lagrange's theorem supplies a necessary size condition; the failure of the converse to Lagrange's theorem below explains its limit.

For coprime integers $a,n$ with $n>1$, the multiplicative order is the least positive integer $d$ such thatIt counts the distinct powers in the cyclic subgroup generated by the congruence class of $a$. Thus it is an order of a group element in the unit group $(\mathbb{Z}/n\mathbb{Z}{)}^{\times }$.^[ref]

For example, the modular exponentiation $2^k\mathrm{mod}7$, starting at $k=0$, produces $1,2,4,1,2,4,\dots$. The first return to one takes three steps, so ${\mathrm{ord}}_7(2)=3$. Starting at the congruence class three and repeatedly multiplying by two instead gives $3,6,5,3,\dots$: these are the other three units modulo seven, outside the cyclic subgroup generated by two.

Euler's theorem guarantees a return to one at exponent $\phi (n)$, where $\phi$ is Euler's totient function. Thus the multiplicative order exists for every unit.^[ref] In fact,By Lagrange's theorem, the size of the cyclic subgroup divides the size of the unit group, which is Euler's totient function. For two modulo seven, this is $3\mid 6$; the multiplicative order need not equal Euler's totient function. If $a\equiv 1(\mathrm{mod}n)$, its multiplicative order is one.

The coprime integers hypothesis is necessary: if $a^d=1+kn$, any common divisor of $a$ and $n$ divides one. For instance, powers of two modulo eight give $1,2,4,0,0,\dots$, with no positive-exponent return to one. This sequence eventually settles, but two has no multiplicative order modulo eight.

The conjugacy classes of the symmetric group on three letters have sizes $1,3,2$: the identity, the three transpositions and the two 3-cycles. A normal subgroup is a union of whole conjugacy classes and contains the identity. Its candidate orders are therefore $1,4,3,6$. Lagrange's theorem excludes four, leaving precisely $\{e\}$, $A_3$ and $S_3$. The order-three subgroup is the cyclic group of the two 3-cycles and the identity; it is also the kernel of a group homomorphism of the sign map.

The first isomorphism theorem gives the corresponding quotients $S_3$, $C_2$ and the trivial group. Thus these are exactly the possible images of surjective group homomorphisms from $S_3$. Each occurs, by the identity map, the sign map and the constant identity map, respectively.

If finite normal subgroups $H,K$ of a group have coprime orders, their intersection is trivial by Lagrange's theorem. For $h\in H$ and $k\in K$, the commutator $hk{h}^{-1}{k}^{-1}$ belongs to both subgroups: write it as $h(k{h}^{-1}{k}^{-1})$ to use normality of $H$, and as $(hk{h}^{-1})k^{-1}$ to use normality of $K$. Hence it is the identity and $hk=kh$. The product subgroup is therefore isomorphic to the direct product of groups $H\times K$.