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

A group $G$ in the context of math is a simple algebraic structure with a product operation $*$. Naturally, the operator won’t be of much use if the structure is not closed under the operation. Namely, we would like to have $a * b$ also in $G$ if both elements $a$ and $b$  are in $G$. Moreover, we would like to have a unit element $1$ such that $a* 1 = a$. To make things simple (interesting), we also enforce that an inverse exist for any element in $G$. That is, if $a$ in $G$, we should be able to find some $b$ in $G$ such that $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 $(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 $H$ of a group $G$, that is, $H$ is composed of some elements of $G$. We will call $H$ is a subgroup if $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 $G$ and any of its subgroup $H$, the size of $G$ has to be divisible by $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 $a$ in $G$, we can create a set (known as a coset and denoted by $(a H)$ ) that includes the element $a*h$ if $h$ is in $H$. Note that it is easy to show that any two cosets $(aH)$ and $(bH)$ are identical if  $b^{-1}*a$ is in $H$, where $b^{-1}$ is the inverse of $b$. We will show this in two parts. First, we can show that $(a H)$ is a subset of $(b H)$ because for any element $c$ in $(a H)$, there exists some $h$ in $H$ such that $c = a*h = b* ((b^{-1}*a) *h)$. By assumption that both $b^{-1} * a$ and $h$ are in $H$ and thus $(b^{-1}*a)*h$ is in $H$. Therefore, $c$ is in $(b H)$ as well and so $(aH)$ is a subset of $(bH)$.

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

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

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

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

For any positive integer $n \ge 2$, consider the set $U_n$ containing the integers  $k=1,\cdots,n-1$ where $k$ and $n$ are coprime, i.e., $k$ and $n$ do not share any factor. For $k_1, k_2$ in $U_n$, we can now define the group product $*$ that $k_1 * k_2$ is the remainder of $k_1 k_2$ divided by $n$. To ensure that $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 $a,b,c$ and $a * b= a*c$, then $b=c$.

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

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

### $U_n$ as a group

Let’s verify that $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 $k_1$ and $k_2$ are in $U_n$. Therefore, $k_1$ and $n$ are coprime and so do $k_2$ and $n$.  Immediately we can see that $k_1 k_2$ (and also its remainder of $n$) and $n$ cannot share any common factor and thus are coprime as well. Thus, $k_1 * k_2$ is in $U_n$ and therefore the defined product is closed.

To show that the product is associative, we should verify that for any $k_1, k_2, k_3$ in $U_n$, $k_1 * (k_2 * k_3) = (k_1 * k_2) * k_3$. Note that $k_2 * k_3$ is defined as the remainder of $k_2 * k_3$ divided by $n$. That can be written as $k_2 * k_3 - a n$, where $a$ is some positive integer. Repeat the same procedure, we may write $k_1 * (k_2 * k_3)$ as $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 $b$. By a similar token, we may write $k_1 * (k_2 * k_3)$ as $k_1 * k_2 * k_3 - (a'n k_3 + b') n$ for some $a'$ and $b'$. Since both $k_1 * (k_2 * k_3)$ and $k_1 * (k_2 * k_3)$ are remainders that should fall between $0$ and $n-1$, this forces $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 $k_1, k_2, k_3$ in $U_n$ and assume that $k_1 * k_3 = k_2 * k_3$. We must have $k_1 * k_3 - k_2 * k_3 = (k_1 - k_2) * k_3$ divisible by $n$. Since $k_3$ and $n$ are coprime ($k_3$ is in $U_n$),  we must have $k_1 - k_2$ divisible by $n$. And this forces $k_1 = k_2$. Therefore, cancellation rule holds. And $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 $U_n$ and that is called the Euler’s totient function, which often is denoted as $\phi_n$. $\phi_n$ basically counts the number of positive integers that are both coprime and smaller than $n$. For example, if $n$ is prime and thus does not share any factors with any numbers smaller than it, then $\phi_n$ is simply $n-1$.

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

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

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

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

#### Fermat’s little theorem

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

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

#### Proof of Euler’s theorem

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