This article presents Fermat’s little theorem from a group theory perspective. This article assumes rudimentary knowledge of groups. In particular, the reader is expected to know the meaning of groups and inverses of elements.
Modular Arithmetic from Group Perspective
Definition A group is a triple where is a non-vacuous set, is an associative binary composition in and is an element of such that and . If in addition, the operator is commutative, the group is called an abelian group.
Definition A number is congruent to if
Proposition The set of numbers nonzero modulo a prime number form an abelian group with the binary operator as multiplication and as the identity element.
Proof The operator is both associative and commutative. We only need to check if every element is invertible. If an element is not invertible then the pigeonhole principle yields that there exist such that and since , from elementary number theory so but this is impossible as so every element is invertible.
Fermat’s Little Theorem
Fermat's Little Theorem (Fermat's Little Theorem) For a prime number and an integer coprime to it, that is ,
We will attempt to provide a proof of Fermat’s Theorem using group theory but this requires some sophisticated tools that we will develop before proving this theorem. First, we introduce the notion of cosets and use it to deduce Lagrange’s theorem. Then we will employ cyclic subgroups to complete the proof. A subgroup is simply a subset of a group that follows the group axioms.
Definition The order of a finite group, is the number of elements contained in .
Definition Suppose we have an arbitrary group and a non-empty subset of , then for , the right coset of in is defined as the set
Lemma All right cosets of in have the same number of elements and any two cosets of in are equal or disjoint.
Proof We can prove the first hypothesis by establishing a one-to-one correspondence between and . Observe that if then by the cancellation law, and clearly this is a surjection.
To prove the second hypothesis, suppose two cosets are not equal, then for some and our selected , then if , then and thus if then for some so . Repeating the argument in the reverse direction, we get . Therefore, .
From this lemma and the fact that each element must be in as , we can state Lagrange’s theorem.
Lagrange's Theorem The number of elements in a coset of in divides the order of . In particular, if is a subgroup of , then divides .
Definition A finite cyclic subgroup generated by is defined as where and is the order of the cyclic subgroup.
It is easy to verify that this is indeed a subgroup. We are almost ready to prove Fermat’s theorem.
Corollary If is an element in a finite group of order , then
Proof Consider the subgroup . Suppose it has order , then . By Lagrange’s theorem, and so we have
Now using the above corollary to Lagrange’s theorem, one can make out an algebraic proof of Fermat’s Little Theorem.
Proof of Fermat's Theorem Suppose , then this is trivial. Now suppose , then we can treat as a part of the multiplicative group of integers not congruent to zero modulo . This group has an order of , whence by the corollary to Lagrange’s theorem. Finally since , we can multiply on both sides without changing the result to get
A point to remark is that we have developed tools of group theory motivated to prove Fermat’s theorem, some of these results can be generalised but this would take considerable time and hence it is not pursued here.