In this lecture, we study the congruence modulo $n$, $\equiv\mod n$ on $\mathbb{Z}$. As we shall see, $\equiv\mod n$ is an equivalence relation on $\mathbb{Z}$. It is indeed more than just an equivalence relation. $\equiv\mod n$ also preserves operations $+$ and $\cdot$ on $\mathbb{Z}$. 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 preserves operations, it is called a congruence relation and a congruence relation allows us to define a quotient algebra e.g. 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.$$ It turns out that $\sim$ is a congruence relation i.e. it preserves the group operation $\cdot$ if $H$ is a normal subgroup of $G$. I am not going to talk about normal subgroups here but we will study details about this next time.

On $\mathbb{Z}$, define $a\equiv b\mod n$, we say $a$ is congruent to $b$ modulo $n$, if $n|b-a$. The 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, the $n$ classes $[0],[1],\cdots,[n-1]$ give us all the congruence classes and they are all distinct. 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 straightforward and is left for the readers. One can also 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 under multiplication, so $[0]$ does not have a multiplicative inverse. Would 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]$. 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$. Recall the property that if $(a,n)=1$ and $(b,n)=1$, then $(ab,n)=1$. This implies that $[a][b]=[ab]\in\mathbb{Z}_n^\ast$. Now suppose that $[a][b]=[a][c]$. Then
$$\begin{align*} [ab]=[ac]&\Longrightarrow ab-ac=nk\\ &\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. 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*} [1]^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. $\varphi(p)=p-1$. If $(a,p)=1$, then by the previous theorem,
$$\begin{align*} a^{p-1}\equiv 1\mod p &\Longrightarrow a^{p-1}-1=pk\\ &\Longrightarrow a^p-a=p(ak)\\ &\Longrightarrow a^p\equiv a\mod p. \end{align*}$$
If $p\not| b$, then $b^p\equiv b\mod p$. If $p|b$, then $b\equiv 0\mod p\Longrightarrow b^p\equiv 0\mod p$. So for any $b\in\mathbb{Z}$, $b^p\equiv b\mod p$.

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

Solution. Since $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}&\equiv (8^{12})^88^7\equiv 8^7\equiv (-5)^7\ (8\equiv -5\mod 13)\\ &\equiv (25)^3(-5)\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\not| 2$, by Fermat’s Little Theorem we have $2^{10}\equiv 1\mod 11$. $11,213=10\cdot 1,121+3$. So,
$$\begin{align*} 2^{11,213}-1&\equiv (2^{10})^{1,121}\cdot 2^3-1\equiv 2^3-1\\ &\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.