## Section11.2Lagrange's Theorem and its consequences

### Subsection11.2.1Lagrange's Theorem

Our goal is to uncover the connection between the size of a group and the possible order of elements inside the group. Since the order of an element $a$ is the same as the order of the subgroup generated by $a\text{,}$ i.e., $\ord(a) = |\langle a \rangle|\text{,}$ it will be enough to find a connection between the order of a group and the orders of its subgroups.

The connection is Lagrange's theorem, stated below. It is a remarkable theorem both in terms of its content and the simplicity of its proof. The proof is a consequence of some facts about cosets, in particular, that cosets create a partition of the group into equal sized sets. We prove this fact first.

###### Proof.

We first show that the map $\phi$ is one-to-one. Suppose that $\phi(h_1) = \phi(h_2)$ for elements $h_1, h_2 \in H\text{.}$ We must show that $h_1 = h_2\text{,}$ but $\phi(h_1) = gh_1$ and $\phi(h_2) = gh_2\text{.}$ So $gh_1 = gh_2\text{,}$ and by left cancellation $h_1= h_2\text{.}$ To show that $\phi$ is onto is easy. By definition every element of $gH$ is of the form $gh$ for some $h \in H$ and $\phi(h) = gh\text{.}$

We can now easily prove Lagrange's theorem.

###### Proof.

The group $G$ is partitioned into $[G : H]$ distinct left cosets. Each left coset has $|H|$ elements; therefore, $|G| = [G : H] |H|\text{.}$

Now using the relationship between order of elements and sizes of subgroups, we arrive at our desired results.

###### Proof.

Let $g$ be in $G$ such that $g \neq e\text{.}$ Then by Corollary 11.18, the order of $g$ must divide the order of the group. Since $|\langle g \rangle| \gt 1\text{,}$ it must be $p\text{.}$ Hence, $g$ generates $G\text{.}$

Corollary 11.19 suggests that groups of prime order $p$ must somehow look like ${\mathbb Z}_p\text{.}$

###### Proof.

Observe that

\begin{equation*} [G:K] = \frac{|G|}{|K|} = \frac{|G|}{|H|} \cdot \frac{|H|}{|K|} = [G:H][H:K]\text{.} \end{equation*}
###### Remark11.21.The converse of Lagrange's Theorem is false.

The group $A_4$ has order $12\text{;}$ however, it can be shown that it does not possess a subgroup of order $6\text{.}$ According to Lagrange's Theorem, subgroups of a group of order $12$ can have orders of either $1\text{,}$ $2\text{,}$ $3\text{,}$ $4\text{,}$ or $6\text{.}$ However, we are not guaranteed that subgroups of every possible order exist. To prove that $A_4$ has no subgroup of order $6\text{,}$ we will assume that it does have such a subgroup $H$ and show that a contradiction must occur. Since $A_4$ contains eight $3$-cycles, we know that $H$ must contain a $3$-cycle. We will show that if $H$ contains one $3$-cycle, then it must contain more than $6$ elements.

###### Proof.

Since $[A_4 : H] = 2\text{,}$ there are only two cosets of $H$ in $A_4\text{.}$ Inasmuch as one of the cosets is $H$ itself, right and left cosets must coincide; therefore, $gH = Hg$ or $g H g^{-1} = H$ for every $g \in A_4\text{.}$ Since there are eight $3$-cycles in $A_4\text{,}$ at least one $3$-cycle must be in $H\text{.}$ Without loss of generality, assume that $(123)$ is in $H\text{.}$ Then $(123)^{-1} = (132)$ must also be in $H\text{.}$ Since $g h g^{-1} \in H$ for all $g \in A_4$ and all $h \in H$ and

\begin{align*} (124)(123)(124)^{-1} & = (124)(123)(142) = (243)\\ (243)(123)(243)^{-1} & = (243)(123)(234) = (142) \end{align*}

we can conclude that $H$ must have at least seven elements

\begin{equation*} (1), (123), (132), (243), (243)^{-1} = (234), (142), (142)^{-1} = (124)\text{.} \end{equation*}

Therefore, $A_4$ has no subgroup of order $6\text{.}$

In fact, we can say more about when two cycles have the same length.

###### Proof.

Suppose that

\begin{align*} \tau & = (a_1, a_2, \ldots, a_k )\\ \mu & = (b_1, b_2, \ldots, b_k )\text{.} \end{align*}

Define $\sigma$ to be the permutation

\begin{align*} \sigma( a_1 ) & = b_1\\ \sigma( a_2 ) & = b_2\\ & \vdots\\ \sigma( a_k ) & = b_k\text{.} \end{align*}

Then $\mu = \sigma \tau \sigma^{-1}\text{.}$

Conversely, suppose that $\tau = (a_1, a_2, \ldots, a_k )$ is a $k$-cycle and $\sigma \in S_n\text{.}$ If $\sigma( a_i ) = b$ and $\sigma( a_{(i \bmod k) + 1}) = b'\text{,}$ then $\mu( b) = b'\text{.}$ Hence,

\begin{equation*} \mu = ( \sigma(a_1), \sigma(a_2), \ldots, \sigma(a_k) )\text{.} \end{equation*}

Since $\sigma$ is one-to-one and onto, $\mu$ is a cycle of the same length as $\tau\text{.}$

### Subsection11.2.2Fermat's and Euler's Theorems

The Euler $\phi$-function is the map $\phi : {\mathbb N } \rightarrow {\mathbb N}$ defined by $\phi(n) = 1$ for $n=1\text{,}$ and, for $n \gt 1\text{,}$ $\phi(n)$ is the number of positive integers $m$ with $1 \leq m \lt n$ and $\gcd(m,n) = 1\text{.}$

From Proposition 2.4, we know that the order of $U(n)\text{,}$ the group of units in ${\mathbb Z}_n\text{,}$ is $\phi(n)\text{.}$ For example, $|U(12)| = \phi(12) = 4$ since the numbers that are relatively prime to 12 are 1, 5, 7, and 11. For any prime $p\text{,}$ $\phi(p) = p-1\text{.}$ We state these results in the following theorem.

The following theorem is an important result in number theory, due to Leonhard Euler.

###### Proof.

By Theorem 11.24 the order of $U(n)$ is $\phi(n)\text{.}$ Consequently, $a^{\phi(n)} = 1$ for all $a \in U(n)\text{;}$ or $a^{\phi(n)} - 1$ is divisible by $n\text{.}$ Therefore, $a^{\phi(n)} \equiv 1 \pmod{n}\text{.}$

If we consider the special case of Euler's Theorem in which $n = p$ is prime and recall that $\phi(p) = p - 1\text{,}$ we obtain the following result, due to Pierre de Fermat.

### Subsection11.2.3Historical Note

Joseph-Louis Lagrange (1736–1813), born in Turin, Italy, was of French and Italian descent. His talent for mathematics became apparent at an early age. Leonhard Euler recognized Lagrange's abilities when Lagrange, who was only 19, communicated to Euler some work that he had done in the calculus of variations. That year he was also named a professor at the Royal Artillery School in Turin. At the age of 23 he joined the Berlin Academy. Frederick the Great had written to Lagrange proclaiming that the “greatest king in Europe” should have the “greatest mathematician in Europe” at his court. For 20 years Lagrange held the position vacated by his mentor, Euler. His works include contributions to number theory, group theory, physics and mechanics, the calculus of variations, the theory of equations, and differential equations. Along with Laplace and Lavoisier, Lagrange was one of the people responsible for designing the metric system. During his life Lagrange profoundly influenced the development of mathematics, leaving much to the next generation of mathematicians in the form of examples and new problems to be solved.

### Exercises11.2.4Collected Homework

###### 1.

The Euler $\phi$-function is the function that, on input $n\text{,}$ gives the number of positive integers less than and relatively prime to $n\text{.}$ (That is, $\phi(n)$ is the number of $m$ with $1 \le m \lt n$ and $\gcd(m,n) = 1$). We also define $\phi(1) = 1\text{.}$ Let's explore some properties of this function

###### (a)

If $p$ is prime, what is $\phi(p)\text{?}$ Explain how you know.

###### (b)

Compute the following values of the function by brute force (list and count the numbers less than $n$ relatively prime to $n$): $\phi(6)\text{,}$ $\phi(10)\text{,}$ $\phi(14)\text{,}$ $\phi(15)\text{,}$ and $\phi(21)\text{.}$

###### (c)

All of the inputs in the previous task were the product of two primes. Conjecture a formula for $\phi(pq)$ where $p$ and $q$ are distinct primes.

###### (d)

Does your formula also make sense for $\phi(p^2)\text{?}$ Does it work for $\phi(ab)$ where $a$ and $b$ are not primes?