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