Group Theory 7: Congruence Modulo $n$

 In this note, we study the congruence modulo $n$, $\equiv\mod n$ on $\mathbb{Z}$ more in depth. As seen here, $\equiv\mod n$ is an equivalence relation on $\mathbb{Z}$. It turns out that $\equiv\mod n$ is more than just an equivalence relation. $\equiv\mod n$ also preserves operations $+$ and $\cdot$ on $\mathbb{Z}$. (See #1 of Problem Set 5 here) Because of this, we can define an operation $+$ on the quotient set $\mathbb{Z}/\equiv\mod n$ so that it becomes a quotient group. In general, if an equivalence relation on an algebra preserves operations, it is called a congruence relation and a congruence relation allows us to define a quotient algebra, for example, a quotient group. Let $G$ be a group and $H\leq G$. We studied the equivalence relation $\sim$ on $G$: $\forall a,b\in G$,
$$a\sim b \Longleftrightarrow ab^{-1}\in H.$$ The equivalence relation $\sim$ is a congruence relation i.e. it preserves the group operation $\cdot$ if $H$ is a normal subgroup of $G$.

Let us recall that on $\mathbb{Z}$, $a\equiv b\mod n$, we say $a$ is congruent to $b$ modulo $n$, if $n|a-b$. The equivalence class of $a$
$$[a]=\{a+nk: k\in\mathbb{Z}\}$$ is called the congruence class of $a$. By Euclid's algorithm, $\forall b\in\mathbb{Z}$, $b=qn+r$ where $0\leq r<n$. This implies that $b\equiv r\mod n$ and so $[b]=[r]$. Hence, there are exactly $n$ distinct congruence classes $[0],[1],\cdots,[n-1]$. Let
$$\mathbb{Z}_n=\{[0],[1],\cdots,[n-1]\}.$$ That is, $\mathbb{Z}_n$ is the quotient set modulo the equivalence relation $\equiv\mod n$, $\mathbb{Z}/\equiv\mod n$. Define $+$ on $\mathbb{Z}_n$: $\forall [a],[b]\in\mathbb{Z}_n$,
$$[a]+[b]:=[a+b].$$ Then $+$ is well-defined on $\mathbb{Z}_n$. What this means is that $+$ is well-defined as a function $+:\mathbb{Z}_n\times\mathbb{Z}_n\longrightarrow\mathbb{Z}_n$. In other words, if $[a]=[a']$ and $[b]=[b']$ then $[a+b]=[a'+b']$. This can be shown straightforwardly and is left for the readers as an exercise. One can readily see that $(\mathbb{Z}_n,+)$ is an abelian group. Define $\cdot $ on $\mathbb{Z}_n$: $\forall [a],[b]\in\mathbb{Z}_n$,
$$[a]\cdot[b]:=[ab].$$ Then $\cdot$ is also well-defined on $\mathbb{Z}_n$. However, $(\mathbb{Z}_n,\cdot)$ is not a group. $\forall [a]\in\mathbb{Z}_n$, $[0][a]=[0]$ and $[1]$ is the identity for the multiplication, so $[0]$ does not have a multiplicative inverse. Would the nonzero elements of $\mathbb{Z}_n$ form a group then? The answer is no. For instance, in $\mathbb{Z}_6$, $[2],[3]\ne [0]$ but $[2][3]=[6]=[0]$. Such elements like $[2]$ and $[3]$ in $\mathbb{Z}_6$ are called zero divisors. So, is there a subset of $\mathbb{Z}_n$ that forms a group under $\cdot$? The answer is affirmative. Let $\mathbb{Z}_n^\ast=\{[a]\in\mathbb{Z}_n: (a,n)=1\}$. First, note that for $[a]=[b]$, $(a,n)=1$ if and only if $(b,n)=1$. This can be proved by contrapositive. Suppose that $[a]=[b]$. Then $a\equiv b\mod n\Rightarrow a-b=nk$ for some $k\in\mathbb{Z}$. If $(b,n)=d>1$ then since $d|b$ and $ d|n$, $d|a=b+nk\Rightarrow (a,n)\ne 1$. In the same manner, it can be also shown that if $(a,n)\ne 1$ then $(b,n)\ne 1$. Recall the property that if $(a,n)=1$ and $(b,n)=1$, then $(ab,n)=1$. (# 4 of Problem Set 1 here.) This implies that $[a][b]=[ab]\in\mathbb{Z}_n^\ast$. Now suppose that $[a][b]=[a][c]$. Then
\begin{align*}
[ab]=[ac]&\Longrightarrow n|a(b-c)\\
&\Longrightarrow n|b-c\ (\mbox{since}\ (a,n)=1)\\
&\Longrightarrow [b]=[c].
\end{align*}
That is, $\mathbb{Z}_n^\ast$ has the cancellation property, so $(\mathbb{Z}_n^\ast,\cdot)$ is a group. (See # 2 of Problem Set 5 here.) In some textbooks, $\mathbb{Z}_n^\ast$ is also denoted by $U_n$. The order of $\mathbb{Z}_n^\ast$ is the number of integers $1\leq m<n$ such that $(m,n)=1$.

Definition. The Euler $\varphi$-function, $\varphi(n)$, is defined by $\varphi(1)=1$ and for $n>1$, $\varphi(n)=$ the number of positive integers $m$ with $1\leq m<n$ such that $(m,n)=1$. Hence, $|\mathbb{Z}_n^\ast|=\varphi(n)$. If $n=p$, a prime, then $\varphi(p)=p-1$.

Note that the Euler $\varphi$-function is multiplicative, namely if $(m,n)=1$, then $\varphi(mn)=\varphi(m)\varphi(n)$.

Example. $\varphi(8)=4$, $\varphi(15)=8$.

Example.
\begin{align*}
\mathbb{Z}_8^\ast&=\{[1],[3],[5],[7]\},\\
\mathbb{Z}_{15}^\ast&=\{[1],[2],[4],[7],[8],[11],[13],[14]\}.
\end{align*}

Example. $\mathbb{Z}_9^\ast=\{[1],[2],[4],[5],[7],[8]\}$.
\begin{align*}
[2]^1&=[2],\ [2]^2=[4],\ [2]^3=[8],\ [2]^4=[16]=[7],\\
[2]^5&=[32]=[5],\ [2]^6=[2][2]^5=[2][5]=[10]=[1].
\end{align*}
Hence, $\mathbb{Z}_9^\ast$ is a cyclic group $\mathbb{Z}_9^\ast=\langle[2]\rangle$.

As a summary,

Theorem. $\mathbb{Z}_n^\ast$ forms an abelian group under the product $[a][b]=[ab]$, of order $\varphi(n)$, where $\varphi(n)$ is the Euler $\varphi$-function.

Theorem. [Euler]
If $(a,n)=1$ then $a^{\varphi(n)}\equiv 1\mod n$.

Proof. Since $\mathbb{Z}_n^\ast$ is a group of order $\varphi(n)$, $[a]^{\varphi(n)}=[1]$, $\forall [a]\in\mathbb{Z}_n^\ast$. So,
$$[a^{\varphi(n)}]=[a]^{\varphi(n)}=[1]\Longrightarrow a^{\varphi(n)}\equiv 1\mod n.$$

Corollary. [Fermat]

If $p$ is a prime and $p\not | a$, then
$$a^{p-1}\equiv 1\mod p.$$
For any integer $b$, $b^p\equiv b\mod p$. This corollary is usually called Fermat's Little Theorem.

Proof. If $p$ is a prime and $p\not |a$, then $(a,p)=1$, so by the preceding theorem,
$$a^{\varphi(p)}=a^{p-1}\equiv 1\mod p$$
For any integer $b$, if $p\not b$ then
$$b^{p-1}\equiv 1\mod p\Rightarrow b^p=b^{p-1}b\equiv b\mod p,$$
since $\equiv\mod p$ preserves multiplication. One can also show that using only the definition of $\equiv\mod p$:
\begin{align*}
b^{p-1}\equiv 1\mod p &\Longrightarrow b^{p-1}-1=pk\ \mbox{for some integer}\ k\\
&\Longrightarrow b^p-b=p(bk)\\
&\Longrightarrow b^p\equiv b\mod p.
\end{align*}
If $p|b$, then $b\equiv 0\mod p\Longrightarrow b^p\equiv 0\mod p$. Hence, for any $b\in\mathbb{Z}$, $b^p\equiv b\mod p$.

Example. Compute the remainder of $8^{103}$ when it is divided by 13.

Solution. Since 13 is a prime and $13\not|8$, by Fermat's Little Theorem we have
$$8^{13-1}=8^{12}\equiv 1\mod 13.$$ Dividing 103 by 13, we obtain $103=12\cdot 8+7$. So,
\begin{align*}
8^{103}&= (8^{12})^88^7\\
&\equiv 8^7\mod 13\\
&\equiv (-5)^7\mod 13\ (8\equiv -5\mod 13)\\
&\equiv (25)^3(-5)\mod 13\\
&\equiv (-1)^3(-5)\equiv 5\mod 13\ (25\equiv -1\mod 13).
\end{align*}

Example. Show that $2^{11,213}-1$ is not divisible by 11.

Solution. Since $11$ is a prime and $11\not| 2$, by Fermat's Little Theorem we have $$2^{11-1}=2^{10}\equiv 1\mod 11.$$
$11,213=10\cdot 1,121+3$, so
\begin{align*}
2^{11,213}-1&= (2^{10})^{1,121}\cdot 2^3-1\\
&\equiv 2^3-1\mod 11\\
&\equiv 7\mod 11.
\end{align*}
Hence, when $2^{11,213}-1$ is divided by 11, the remainder is 7.

The number $11,213$ is a prime and $2^{11,213}-1$ is also a prime. In number theory, primes of the form $2^p-1$ where $p$ is a prime are called Mersenne primes.