# Lagrange's theorem and its applications

## Motivation:

It is well known that Lagrange’s theorem, an important theorem in group theory, may be used to derive Euler’s theorem which is a fundamental result in number theory. As these fundamental results were discovered separately, they suggest deep connections between group theory and number theory.

This article only requires prior knowledge of cosets, the multiplicative group of integers modulo \(n\) and Euler’s theorem.

## Cosets:

Given \(g \in G\), the left cosets of \(H\) in \(G\) are the sets obtained by multiplying each element of \(H\) by a fixed element of \(g \in G\):

\begin{equation} \forall g \in G, g \cdot H = \{g \cdot h: h \in H\} \end{equation}

so the left cosets of \(H\) in \(G\) are given by:

\begin{equation} G:H = \bigcup_{g \in G} g \cdot H \end{equation}

The right cosets are defined similarly except that the element \(g\) is a right factor, \(H \cdot g\). It follows that if \(G\) is Abelian, the right cosets equal the left cosets:

\begin{equation} \forall g \in G, g \cdot H = H \cdot g \end{equation}

but in general the group may not be Abelian.

## Lagrange’s theorem:

If \(H\) is a subgroup of a finite group \(G\), then \(\frac{|G|}{|H|}\) equals the number of left cosets of \(H\) in \(G\). It follows that:

\begin{equation} |G| = [G:H] \cdot |H| \end{equation}

## Proof:

The left cosets of \(H\) in \(G\) are the equivalence classes of an equivalence relation on \(G\). In particular,

\begin{equation} \forall x,y \in G, x \sim y \implies \exists h \in H, x = y \cdot h \end{equation}

so the number of left cosets, \([G:H]\), form a partition of \(G\).

Finally, each left coset \(gH\) has the same cardinality as \(H\) since \(x \mapsto g \cdot x\) defines a bijection from \(H\) to \(g \cdot H\). As a result we have:

\begin{equation} |G| = [G:H] \cdot |H| \end{equation}

## A corollary of Lagrange’s theorem:

In consequence of this theorem, the order of any element \(g \in G\) divides \(|G|\), the order of \(G\), since the order of \(g\) equals the order of the cyclic subgroup generated by \(g\). It follows that:

\begin{equation} g^{|G|} = e \end{equation}

In particular, given the multiplicative group of integers modulo \(n\), we have:

\begin{equation} \forall a \in \mathbb{Z}_n, a^{\phi(n)} \equiv 1 \pmod{n} \end{equation}