A group 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 also in if both elements and are in . Moreover, we would like to have a unit element such that . To make things simple (interesting), we also enforce that an inverse exist for any element in . That is, if in , we should be able to find some in such that . 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 .
As a simple example, the set of all (real) number under the addition (plus) operation forms a group.
Consider any subset of a group , that is, is composed of some elements of . We will call is a subgroup if 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).
One simple and amazing result by Lagrange is that for any finite group and any of its subgroup , the size of has to be divisible by . 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 in , we can create a set (known as a coset and denoted by ) that includes the element if is in . Note that it is easy to show that any two cosets and are identical if is in , where is the inverse of . We will show this in two parts. First, we can show that is a subset of because for any element in , there exists some in such that . By assumption that both and are in and thus is in . Therefore, is in as well and so is a subset of .
Now, let’s show that is a subset of . Note that we can get this for free since is in , which itself is a group, and thus the inverse is in as well (Sanity check: ). From the previous discussion, by just swapping with , we must have being a subset of and thus .
What if is not in ? In this case, must not share any element with . Otherwise, let say if we have in both and , then this means that we should have some and in such that . Rearranging the terms, we have , which is in . This contradicts with our original assumption.
Finally, note that any element of the group is in the coset since ( is a group and thus has to include the unit element ). Combining with the discussion above, all cosets of partition the original group and since all coset has the same size and is equal to the size of , we must have the size of is divisible by the size of .
Group and Euler’s Totient function
For any positive integer , consider the set containing the integers where and are coprime, i.e., and do not share any factor. For in , we can now define the group product that is the remainder of divided by . To ensure that 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
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 and , then .
Proof of cancellation rule implies existence of unit and inverse
Since the set is finite, for any element , we must be able to find two different positive integers and such that . Without loss of generality, assume , by the cancellation rule, we can cancel some from both sides and thus immediately we have and . And by assumption 1 that the operation is closed. We have the unit element and the inverse of , , exist in the set.
as a group
Let’s verify that 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 and are in . Therefore, and are coprime and so do and . Immediately we can see that (and also its remainder of ) and cannot share any common factor and thus are coprime as well. Thus, is in and therefore the defined product is closed.
To show that the product is associative, we should verify that for any in , . Note that is defined as the remainder of divided by . That can be written as , where is some positive integer. Repeat the same procedure, we may write as for some positive integer . By a similar token, we may write as for some and . Since both and are remainders that should fall between and , this forces 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 in and assume that . We must have divisible by . Since and are coprime ( is in ), we must have divisible by . And this forces . Therefore, cancellation rule holds. And 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 and that is called the Euler’s totient function, which often is denoted as . basically counts the number of positive integers that are both coprime and smaller than . For example, if is prime and thus does not share any factors with any numbers smaller than it, then is simply .
With everything discussed so far, we can now readily show the Euler’s theorem, which states that
for any integer that is coprime with .
Or to translate it with plain English, if and do not share any factor, the remainder of divided by is .
Fermat’s little theorem
If we pick as some prime , we immediately obtain Fermat’s little theorem from Euler’s theorem since . That is,
Proof of Euler’s theorem
First, note that since and are coprime, is in . And consider the set and it is easy to see that is a subgroup of . Let say the size of is . Then, should be the minimum positive integer that satisfies (otherwise, the size of won’t be !). Now, by Lagrange’s theorem, the size of , , should be divisible by the size of , , since is a subgroup of . Thus, we should also have . Note that the unit element in the group is actually just . Therefore, the remainder of divided by is .