10.2 Congruences and modular arithmetic
We now use our work on equivalence classes to partition \(\mathbb{Z}\). Recall that for any two integers \(a,n \in \mathbb{Z}\), \(n\neq 0\), there exists a quotient \(q\) and a remainder \(r\) such that \(a=nq+r\). Sometimes we only care about the remainder \(r\), which leads us into the following definition.
Let \(n\in\mathbb{Z}_+\). Define a relation on \(\mathbb{Z}\) via \(a\sim b\) if and only if \(a\equiv b\ \pmod{n}\). Then \(\sim\) is an equivalence relation.
Exercise.
□
Using Theorem 5.2, we can see that, given an integer \(n\), every integer \(a\) is congruent modulo \(n\) to a unique \(r\) such that \(0\leq r <n\). I.e, we partition \(\mathbb{Z}\) into exactly \(n\) congruence classes modulo \(n\) given by \([0],[1],\dots,[n-1]\) where \[[r] = \{a\in\mathbb{Z}:a\equiv r \pmod{n}\} = r+n\mathbb{Z}.\]
We write \(\mathbb{Z}/n\mathbb{Z}\) for the set of congruence classes module \(n\).
If we’re clear that we’re considering \([r]\) as an element of \(\mathbb{Z}/n\mathbb{Z}\) we’ll often simply write \(r\).Both addition and multiplication make sense modulo \(n\), by the following theorem, which is very useful in computations.
Fix \(n\in\mathbb{Z}_+\). Suppose that \(a,b,c,d\in\mathbb{Z}\) are such that \(a\equiv c\ \pmod{n}\) and \(b\equiv d\ \pmod{n}\). Then \[a+b\equiv c+d\ \pmod{n} \qquad\text{and}\qquad ab\equiv cd\ \pmod{n}.\]
By assumption, we have that \(n\mid a-c\) and \(n\mid b-d\). Hence, for some \(x,y\in\mathbb{Z}\), we have that \(a-c=nx\) and \(b-d=ny\). It follows that \[(a+b)-(c+d)=(a-c)+(b-d)= nx+ny=n(x+y).\] Since \(x+y\in\mathbb{Z}\), this means that \(n\mid((a+b)-(c+d))\), so \(a+b\equiv c+d\ \pmod{n}.\) Further, since \(a=c+nx\) and \(b=d+ny\), we have that \[ab=(c+nx)(d+ny)=cd+n(cy+dx+nxy)\] so \(ab-cd=n(cy+dx+nxy)\). Since \(cy+dx+nxy\) is an integer, we have that \(n\mid ab-cd\), so \(ab\equiv cd\ \pmod{n}.\)
□
Another consequence of Theorem 10.10 is that we can “shift” the congruence classes by a given constant \(c\in \mathbb{Z}\), i.e. the congruence classes can be given by \([c],[c+1],\dots,[c+n-1]\).
We have \((\mathbb{Z}/n\mathbb{Z},+)\) is an abelian group.
Addition on \(\mathbb{Z}/n\mathbb{Z}\) is a well-defined binary operation by Theorem 10.10. Addition \(\pmod{n}\) is associative, since \[([a]+[b])+[c]=[a+b+c]=[a]+([b]+[c]).\] The identity element is \([0]\) since \[[a]+[0]=[a]=[0]+[a]\] for any \(a\in\mathbb{Z}\). The inverse of \([a]\) is \([-a]\), since \[[a]+[-a]=[0]=[-a]+[a].\] So \((\mathbb{Z}/n\mathbb{Z},+)\) is a group. It is abelian since \([a]+[b]=[a+b]=[b+a]\) for all \(a\) and \(b\).
□
In fact, it is a cyclic group, since the following is clear.
\((\mathbb{Z}/n\mathbb{Z},+)=\langle 1\rangle\).
Since \((\mathbb{Z}/n\mathbb{Z},+)\) is cyclic, it is isomorphic to \(C_n = \langle x \rangle\). The isomorphism is \(\varphi:(\mathbb{Z}/n\mathbb{Z},+)\to C_n\) defined by \(\varphi(i) = x^i\).
This means that cyclic groups are particularly simple to understand if we know a generator, as the group operation is just addition of exponents: in a cyclic group \(G=\langle x\rangle\), \(x^ix^j=x^{i+j}\), so the group operation in an infinite cyclic group is “just like” addition of integers, and the group operation in a finite cyclic group of order \(n\) is “just like”” addition of integers \(\pmod{n}\).However, \((\mathbb{Z}/n\mathbb{Z},\times)\) is not a group, since although it is associative and has an identity element \([1]\), not every element has an inverse. For example, \([0]\) never has an inverse, and in \(\mathbb{Z}/4\mathbb{Z}\), \([2]\) does not have a multiplicative inverse.
In \(\mathbb{Z}/n\mathbb{Z}\), \([a]\) has a multiplicative inverse if and only if \(\gcd(a,n)=1\).
If \(\gcd(a,n)=1\) then Theorem 5.7 there exists \(s,t\in\mathbb{Z}\) such that \(as+nt=1\) for some . So \[as\equiv 1-nt\equiv 1\pmod{n},\] so \([a][s]=[1]\) in \(\mathbb{Z}/n\mathbb{Z}\), and so \([s]\) is a multiplicative inverse of \([a]\).
Conversely, if \(\gcd(a,n)=h>1\), and if \(as\equiv 1\pmod{n}\), then \(1=as+nq\) for some \(q\in\mathbb{Z}\). But \(h\) divides both \(a\) and \(n\), so it divides \(as+nq\). But no integer \(h>1\) divides \(1\). So there is no \(s\) such that \([s]\) is a multiplicative inverse of \(a\).□
Note that the first part of the proof is constructive and allows us to solve some congruence equations.
Find \(x \in \mathbb{Z}\) such that \(4x = 3 \pmod{7}\).
We find the inverse of \([4]\) in \(\mathbb{Z}/7\mathbb{Z}\) (which exists since \(\gcd(4,7)=1\)). We find \(s,t \in \mathbb{Z}\) such that \(4s+7t=1\). We have that
| \(k\) | \(s_k\) | \(t_k\) | Calculation | \(q_k\) | \(r_k\) |
|---|---|---|---|---|---|
| \(0\) | \(0\) | \(1\) | - | - | - |
| \(1\) | \(1\) | \(0\) | \(7=4\cdot 1+3\) | \(1\) | \(3\) |
| \(2\) | \(0-1\cdot1=-1\) | \(1-0\cdot 1=1\) | \(4=3\cdot1+1\) | \(1\) | \(1\) |
| \(3\) | \(1-(-1)\cdot1=2\) | \(0-1\cdot1 = -1\) | \(3=1\cdot3+0\) | \(3\) | \(0\) |
so \(s=2\) and \(t=-1\). So \([2]\) is the inverse of \([4]\) in \(\mathbb{Z}/7\mathbb{Z}\).
Multiply both side of \(4x \equiv 3\pmod{7}\) by \(2\), we get \(x \equiv 2\cdot 4x \equiv 2\cdot 3\equiv 6\pmod{7}\).
We can also look at solving a system of simultaneous congruence equations.
Let \(m,n\in\mathbb{Z}_+\) be co-prime. For any \(a,b\in\mathbb{Z}\), \(\exists\,x\in\mathbb{Z}\) such that \[x\equiv a\ \pmod{m} \qquad\text{ and }\qquad x\equiv b\ \pmod{n}.\] Furthermore, this \(x\) is unique modulo \(mn\). That is for \(x'\in\mathbb{Z}\), we have that \[x'\equiv a\ \pmod{m} \qquad\text{ and } \qquad x'\equiv b\ \pmod{n}\] if and only if \[x'\equiv x\ \pmod{mn}.\]
We will prove the existence of \(x\) and leave the uniqueness of \(x\) modulo \(mn\) as an exercise.
Since \(\gcd(m,n)=1\), by Theorem 5.7 we know that there exist \(s,t\in\mathbb{Z}\) such that \(ms+nt=1\). Then \[1\equiv ms+nt\equiv nt\ \pmod{m}\] and \[1\equiv ms+nt\equiv ms\ \pmod{n}.\] So let \(x=msb+nta\in \mathbb{Z}\). Then \[x\equiv msb+nta \equiv nta\equiv 1\cdot a\equiv a\ \pmod{m}\] and \[x\equiv msb+nta \equiv msb\equiv 1\cdot b\equiv b\ \pmod{n}.\]□
The above theorem is often known as the Chinese Remainder Theorem. An example of this theorem was first discussed by Sun Zi (Chinese mathematician, around 400-460) in his text Sunzi suanjing (Sun Zi’s Mathematical Manual). While Sun Zi came to the correct solution he posed in his text using the methods we would use nowadays, there is no sign that he developed a general method. Instead it was Qin Jiushao (Chinese mathematician, 1202-1261) who wrote in his text “Shushu Jiuzang” how to solve simultaneous linear congruent equations. The origin of the name “Chinese Remainder Theorem” is unclear; it arose in the west some time after a 1852 article by Wiley on the history of Chinese mathematics (however, he did not use this term).
Note that the above proof is a constructive proof, that is, it gives a way to find \(x\).
We want to find \(x\in \mathbb{Z}\) such that \(x\equiv 4\ \pmod{5}\) and \(x\equiv 7\ \pmod{8}\).
We have that \(\gcd(5,8)=1\), so we set \(x=msb+nta\), where \(a=4, m=5, b=7, n=8\) and \(s,t\) are such that \(gcd(5,8)=5s+8t\). We have that
| \(k\) | \(s_k\) | \(t_k\) | Calculation | \(q_k\) | \(r_k\) |
|---|---|---|---|---|---|
| \(0\) | \(0\) | \(1\) | - | - | - |
| \(1\) | \(1\) | \(0\) | \(8=5\cdot 1+3\) | \(1\) | \(3\) |
| \(2\) | \(0-1\cdot1=-1\) | \(1-0\cdot 1=1\) | \(5=3\cdot1+2\) | \(1\) | \(2\) |
| \(3\) | \(1-(-1)\cdot1=2\) | \(0-1\cdot1 = -1\) | \(3=2\cdot1+1\) | \(1\) | \(1\) |
| \(4\) | \(-1-2\cdot1 = -3\) | \(1-(-1)\cdot 1=2\) | \(2=1\cdot2+0\) | \(2\) | \(0\) |
One can use induction and the Fundamental Theorem of Arithmetic to prove the following generalisation of Theorem 10.14:
Let \(r\in\mathbb{Z}_+\) with \(r\ge 2\), and let \(m_1,\ldots,m_r\in\mathbb{Z}_+\) be pairwise co-prime, that is \(\gcd(m_i,m_j)=1\) for \(i,j\in\mathbb{Z}\) with \(1\le i\le r\), \(1\le j\le r\) and \(i\neq j\). Then for any \(a_1,\ldots,a_r\in\mathbb{Z}\), there exists some \(x\in\mathbb{Z}\) such that \[ x\equiv a_i\ \pmod{m_i} \] for all \(i\in\mathbb{Z}\) with \(1\le i\le r\). Further, this \(x\) is unique modulo \(m_1 m_2\cdots m_r\).
One can also think about combining all these methods together to solve simultaneous congruent equation where the coefficient in front of \(x\) is not \(1\).