Introducing Modular Arithmetic via Group Theory

Mdoular arithmetic is essentially arithmetic on remainders. Recall that whenever we have two integers $m$ , $n$ with $n>0$ , there exist unique integers $d$ and $r$ , with $0\leq r < n-1$ such that $m=dn+r$ The number $r$ is the remainder.

Doing arithmetic on remainders is usually much easier than doing arithmetic on the original numbers, especially if $n$ is small. In addition, since the set of remainders is finite for any given $n$ , modular arithmetic reduces a problem on the infinite set of integers to a finite set. This observation is often useful in solving number theoretic problems, as we will see in later posts.

While modular arithmetic can be introduced in a completely elementary fashion, I will introduce this by group theory. Specifically, let $G$ is a group and $H\subseteq G$ be a subgroup. Define $G/H$ as cosets of the form $gH := \{ gh| h\in H\}$ . Observe that $gH=g'H$ if and only if $g^{-1}g'\in H$ . A subgroup $H\subseteq G$ is normal if for all $g\in G$ , $g^{-1}Hg:= \{ g^{-1}hg | h\in H\}$ equals $H$ . It is not too difficult to show that $G/H$ is a group if and only if $H$ is a normal subgroup of $G$ . The group operation is simply $gH \cdot gH=gg'H$ .

So what does this have to do with modular arithmetic? In this case, $G=(\mathbb{Z},+)$ and $H=(n\mathbb{Z},+)$ . Note that $G$ is abelian (i.e. $a+b=b+a$ for all $a,b \in G$ ). Consequently, any subgroup including $H$ is normal since $g^{-1}Hg=g^{-1}gH=H$ . Thus $\mathbb{Z}/n\mathbb{Z}$ is a group. Each integer in $\mathbb{Z}$ is represented by its remainder when divided by $n$ . Modular arithmetic is nothing other than group operation on $\mathbb{Z}/n\mathbb{Z}$ .