# Lagrange’s theorem, Euler’s theorem, Fermat’s little theorem, and a short introduction to groups

A group $latex G$ in the context of math is a simple algebraic structure with a product operation $latex *$. Naturally, the operator won’t be of much use if the structure is not closed under the operation. Namely, we would like to have $latex a * b$ also in $latex G$ if both elements $latex a$ and $latex b$  are in $latex G$. Moreover, we would like to have a unit element $latex 1$ such that $latex a* 1 = a$. To make things simple (interesting), we also enforce that an inverse exist for any element in $latex G$. That is, if $latex a$ in $latex G$, we should be able to find some $latex b$ in $latex G$ such that $latex a * b= 1$. Furthermore, to ensure that the multiplication of several elements behave uniquely, we would like to have the group product to satisfy the associative rule that $latex (a*b)*c=a*(b*c)$.

As a simple example, the set of all (real) number
under the addition (plus) operation forms a group.

Consider any subset $latex H$ of a group $latex G$, that is, $latex H$ is composed of some elements of $latex G$. We will call $latex H$ is a subgroup if $latex H$ itself is a group.

Continue with our example above, the set of all
integers (positive, negative, and zero) under
the addition operation forms a subgroup (of the
set of all numbers under the same operation).

## Lagrange’s Theorem

One simple and amazing result by Lagrange is that for any finite group $latex G$ and any of its subgroup $latex H$, the size of $latex G$ has to be divisible by $latex H$. The result can be used to prove the Euler’s theorem as described later, which in turn is needed to explain the famous RSA cryptosystem.

#### Proof of Lagrange’s Theorem

The proof turns out to be very simple. Consider any element $latex a$ in $latex G$, we can create a set (known as a coset and denoted by $latex (a H)$ ) that includes the element $latex a*h$ if $latex h$ is in $latex H$. Note that it is easy to show that any two cosets $latex (aH)$ and $latex (bH)$ are identical if  $latex b^{-1}*a$ is in $latex H$, where $latex b^{-1}$ is the inverse of $latex b$. We will show this in two parts. First, we can show that $latex (a H)$ is a subset of $latex (b H)$ because for any element $latex c$ in $latex (a H)$, there exists some $latex h$ in $latex H$ such that $latex c = a*h = b* ((b^{-1}*a) *h)$. By assumption that both $latex b^{-1} * a$ and $latex h$ are in $latex H$ and thus $latex (b^{-1}*a)*h$ is in $latex H$. Therefore, $latex c$ is in $latex (b H)$ as well and so $latex (aH)$ is a subset of $latex (bH)$.

Now, let’s show that $latex (bH)$ is a subset of $latex (aH)$. Note that we can get this for free since $latex b^{-1}*a$ is in $latex H$, which itself is a group, and thus the inverse $latex a^{-1}*b$ is in $latex H$ as well (Sanity check: $latex (b^{-1}*a)*(a^{-1}*b)=1$). From the previous discussion, by just swapping$latex a$ with $latex b$, we must have $latex (bH)$ being a subset of $latex (aH)$ and thus $latex (aH)=(bH)$.

What if $latex b^{-1}*a$ is not in $latex H$? In this case, $latex (aH)$ must not share any element with $latex (bH)$. Otherwise, let say if we have $latex c$ in both $latex (aH)$ and $latex (bH)$, then this means that we should have some $latex h$ and $latex h’$ in $latex H$ such that $latex c= a*h = b*h’$ . Rearranging the terms, we have $latex b^{-1}*a=h’ * h^{-1}$, which is in $latex H$. This contradicts with our original assumption.

Finally, note that any element $latex g$ of the group $latex G$ is in the coset $latex (gH)$ since $latex g= g*1$ ($latex H$ is a group and thus has to include the unit element $latex 1$). Combining with the discussion above, all cosets of $latex H$ partition the original group $latex G$ and since all coset has the same size and is equal to the size of $latex H$, we must have the size of $latex G$ is divisible by the size of $latex H$.

## Group $latex U_n$ and Euler’s Totient function

For any positive integer $latex n \ge 2$, consider the set $latex U_n$ containing the integers  $latex k=1,\cdots,n-1$ where $latex k$ and $latex n$ are coprime, i.e., $latex k$ and $latex n$ do not share any factor. For $latex k_1, k_2$ in $latex U_n$, we can now define the group product $latex *$ that $latex k_1 * k_2$ is the remainder of $latex k_1 k_2$ divided by $latex n$. To ensure that $latex U_n$ is indeed a group, recall that we need to show the followings

1). Product operation is closed and associative
2). Unit exists
3). Inverse exists

### Cancellation rule

Note that given 1). above, and if the set is finite, we can replace the conditions 2). and 3). instead by a cancellation rule as described below

2′). Cancellation rule: if for any elements $latex a,b,c$ and $latex a * b= a*c$, then $latex b=c$.

#### Proof of cancellation rule implies existence of unit and inverse

Since the set is finite, for any element $latex a$, we must be able to find two different positive integers $latex k$ and $latex l$ such that $latex a^k = a^l$. Without loss of generality, assume $latex k > l$, by the cancellation rule, we can cancel some $latex a$ from both sides and thus immediately we have $latex a^{k-l}=1$ and $latex a* a^{k-l-1}=1$. And by assumption 1 that the operation is closed. We have the unit element $latex a^{k-l}$ and the inverse of $latex a$, $latex a^{k-l-1}$, exist in the set.

### $latex U_n$ as a group

Let’s verify that $latex U_n$ is indeed a group by verifying that Conditions 1). and 2′). are satisfied. First, let’s show that the defined product operation is closed. Assume that $latex k_1$ and $latex k_2$ are in $latex U_n$. Therefore, $latex k_1$ and $latex n$ are coprime and so do $latex k_2$ and $latex n$.  Immediately we can see that $latex k_1 k_2$ (and also its remainder of $latex n$) and $latex n$ cannot share any common factor and thus are coprime as well. Thus, $latex k_1 * k_2$ is in $latex U_n$ and therefore the defined product is closed.

To show that the product is associative, we should verify that for any $latex k_1, k_2, k_3$ in $latex U_n$, $latex k_1 * (k_2 * k_3) = (k_1 * k_2) * k_3$. Note that $latex k_2 * k_3$ is defined as the remainder of $latex k_2 * k_3$ divided by $latex n$. That can be written as $latex k_2 * k_3 – a n$, where $latex a$ is some positive integer. Repeat the same procedure, we may write $latex k_1 * (k_2 * k_3)$ as $latex k_1 *(k_2 * k_3 – a n) – b n = k_1 * k_2 * k_3 -(a n k_1 +b) n$ for some positive integer $latex b$. By a similar token, we may write $latex k_1 * (k_2 * k_3)$ as $latex k_1 * k_2 * k_3 – (a’n k_3 + b’) n$ for some $latex a’$ and $latex b’$. Since both $latex k_1 * (k_2 * k_3)$ and $latex k_1 * (k_2 * k_3)$ are remainders that should fall between $latex 0$ and $latex n-1$, this forces $latex a n k_1 + b = a’ n_3 + b’$ and thus the two results should be identical.  Therefore,  the defined product is associative.

Finally, let’s show that the cancellation rule (2′) is satisfied. Consider $latex k_1, k_2, k_3$ in $latex U_n$ and assume that $latex k_1 * k_3 = k_2 * k_3$. We must have $latex k_1 * k_3 – k_2 * k_3 = (k_1 – k_2) * k_3$ divisible by $latex n$. Since $latex k_3$ and $latex n$ are coprime ($latex k_3$ is in $latex U_n$),  we must have $latex k_1 – k_2$ divisible by $latex n$. And this forces $latex k_1 = k_2$. Therefore, cancellation rule holds. And $latex U_n$ is indeed a group.

### Euler’s totient function and Euler’s theorem

This is a bit long article. But the end result here is pretty neat. It turns out that we have a name for the size of $latex U_n$ and that is called the Euler’s totient function, which often is denoted as $latex \phi_n$. $latex \phi_n$ basically counts the number of positive integers that are both coprime and smaller than $latex n$. For example, if $latex n$ is prime and thus does not share any factors with any numbers smaller than it, then $latex \phi_n$ is simply $latex n-1$.

With everything discussed so far, we can now readily show the Euler’s theorem, which states that

$latex a^{\phi_n} \equiv 1 \mod n$

for any integer $latex a$ that is coprime with $latex n$.

Or to translate it with plain English, if $latex a$ and $latex n$ do not share any factor, the remainder of $latex a^{\phi_n}$ divided by $latex n$ is $latex 1$.

#### Fermat’s little theorem

If we pick $latex n$ as some prime $latex p$, we immediately obtain Fermat’s little theorem from Euler’s theorem since $latex \phi_p = p-1$. That is,

$latex a^{p-1} \equiv 1 \mod p$.

#### Proof of Euler’s theorem

First, note that since $latex a$ and $latex n$ are coprime, $latex a$ is in $latex U_n$. And consider the set $latex (a)=a, a^2, a^3, \cdots$ and it is easy to see that $latex (a)$ is a subgroup of $latex U_n$. Let say the size of $latex (a)$ is $latex s_a$. Then, $latex s_a$ should be the minimum positive integer that satisfies $latex a^{s_a}=1$ (otherwise, the size of $latex (a)$ won’t be $latex s_a$!). Now, by Lagrange’s theorem, the size of $latex U_n$, $latex \phi_n$, should be divisible by the size of $latex (a)$, $latex s_a$, since $latex (a)$ is a subgroup of $latex U_n$. Thus, we should also have $latex a^{\phi_n}=1$. Note that the unit element in the group $latex U_n$ is actually just $latex 1$. Therefore, the remainder of $latex a^{\phi_n}$ divided by $latex n$ is $latex 1$.