Lagrange’s theorem

Lagrange’s theorem is a useful theorem in group and number theory. I will state and prove Lagrange’s theorem, and use it to prove Euler’s theorem.

Lagrange’s theorem: Suppose that $G$ is a group with a subgroup $S$ . Then the order of $S$ divides the order of $G$ .

Proof: Label the elements in $S$ as $s_{1}, s_{2}, ..., s_{n}$ , with $s_{k_{1}} \neq = s_{k_{2}}$ whenever $k_{1} \neq = k_{2}$ . Now consider the set ${a s_{1}, a s_{2}, ..., a s_{n}}$ that is obtained by left-multiplying all the elements in $S$ by some element $a \in G$ . Note that this set, which I’ll denote as $a S$ , is not necessarily a group since it will not contain the identity element $e$ in case $g^{- 1} \neq \in S$ . I now claim that

For every $a \in G$ , $a S$ contains the same number of elements as $S$
For every $a, b \in G$ , where have either $a S = b S$ or $a S \cap b S = \emptyset$

The first claim is easy to see, since $s_{k_{1}} \neq = s_{k_{2}}$ implies $a s_{k_{1}} \neq = a s_{k_{2}}$ . For the second claim, suppose that $a s_{k_{1}} = b s_{k_{2}}$ with $k_{1} \neq = k_{2}$ . It follows that $a^{- 1} b = s_{k_{1}} s_{k_{2}}^{- 1}$ . Since $s_{k_{1}} s_{k_{2}}^{- 1} \in S$ , this is impossible if $a^{- 1} b \neq \in S$ , so in this case we have $a S \cap b S = \emptyset$ . Otherwise, we have $a s_{k_{1}} s_{k_{2}}^{- 1} = b$ . It follows that $a S = a (s_{k_{1}} s_{k_{2}}^{- 1} S) = (a s_{k_{1}} s_{k_{2}}^{- 1}) S = b S$ . Note that $s_{k_{1}} s_{k_{2}}^{- 1} S = S$ , since $s_{k_{1}}, s_{k_{2}}^{- 1} \in S$ , and multiplication of a group by an element in the group just permutes the elements.

We can conclude that we can divide $G$ in a number of sets with no overlap, all with $n$ number of elements. So $n$ must divide the order in $G$ . $□$

As a corollary, we can now easily prove Euler’s theorem.

Euler’s theorem: *Suppose that $g$ is an element of the group $G$ , which has order $n$ . Then

g^{n} = e

where $e$ is the identity element.*

Proof: Consider the sequence $e, g, g^{2}, ...$ . Suppose that $g^{m}$ is the first element that occurs earlier in the sequence. Suppose that $g^{m} = g^{m^{'}}$ for some $m^{'} < m$ . Then $g^{m - m^{'}} = e$ . If $m^{'} > 0$ this is a contradiction, since in this case $m - m^{'} < m$ , but $g^{m - m^{'}} = e$ occurs earlier in the sequence. So it follows that $m^{'} = 0$ and $g^{m} = e$ . Now ${e, g, g^{2}, ..., g^{m - 1}}$ is a subgroup of $G$ with order $m$ . By Lagrange’s theorem, we have that $m$ is a divisor of $n$ , so $\frac{n}{m}$ is a positive integer number. Now we have

g^{n} = (g^{m})^{\frac{n}{m}} = e^{\frac{n}{m}} = e

$□$