Group Theory 7: Congruence Modulo n

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 nand 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.

Leave a Reply

Your email address will not be published. Required fields are marked *