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

Leave a Reply

Your email address will not be published. Required fields are marked *