## Section 11.2 Lagrange's Theorem and its consequences

### Subsection 11.2.1 Lagrange'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.

###### Proposition 11.16.

Let \(H\) be a subgroup of \(G\) with \(g \in G\) and define a map \(\phi:H \rightarrow gH\) by \(\phi(h) = gh\text{.}\) The map \(\phi\) is bijective; hence, the number of elements in \(H\) is the same as the number of elements in \(gH\text{.}\)

###### 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.

###### Theorem 11.17. Lagrange.

Let \(G\) be a finite group and let \(H\) be a subgroup of \(G\text{.}\) Then \(|G|/|H| = [G : H]\) is the number of distinct left cosets of \(H\) in \(G\text{.}\) In particular, the number of elements in \(H\) must divide the number of elements in \(G\text{.}\)

###### 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.

###### Corollary 11.18.

Suppose that \(G\) is a finite group and \(g \in G\text{.}\) Then the order of \(g\) must divide the number of elements in \(G\text{.}\)

###### Corollary 11.19.

Let \(|G| = p\) with \(p\) a prime number. Then \(G\) is cyclic and any \(g \in G\) such that \(g \neq e\) is a generator.

###### 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{.}\)

###### Corollary 11.20.

Let \(H\) and \(K\) be subgroups of a finite group \(G\) such that \(G \supset H \supset K\text{.}\) Then

###### Proof.

Observe that

###### Remark 11.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.

###### Proposition 11.22.

The group \(A_4\) has no subgroup of order \(6\text{.}\)

###### 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

we can conclude that \(H\) must have at least seven elements

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

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

###### Theorem 11.23.

Two cycles \(\tau\) and \(\mu\) in \(S_n\) have the same length if and only if there exists a \(\sigma \in S_n\) such that \(\mu = \sigma \tau \sigma^{-1}\text{.}\)

###### Proof.

Suppose that

Define \(\sigma\) to be the permutation

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,

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

### Subsection 11.2.2 Fermat'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.

###### Theorem 11.24.

Let \(U(n)\) be the group of units in \({\mathbb Z}_n\text{.}\) Then \(|U(n)| = \phi(n)\text{.}\)

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

###### Theorem 11.25. Euler's Theorem.

Let \(a\) and \(n\) be integers such that \(n \gt 0\) and \(\gcd(a, n) = 1\text{.}\) Then \(a^{\phi(n)} \equiv 1 \pmod{n}\text{.}\)

###### 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.

###### Theorem 11.26. Fermat's Little Theorem.

Let \(p\) be any prime number and suppose that \(p \notdivide a\) (\(p\) does not divide \(a\)). Then

Furthermore, for any integer \(b\text{,}\) \(b^p \equiv b \pmod{ p}\text{.}\)

### Subsection 11.2.3 Historical 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.

### Exercises 11.2.4 Collected 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?