2.4: Another Way to Work with Congruences - Equivalence Classes

\(\newcommand{\NN}{\mathbb N}\)
\(\newcommand{\RR}{\mathbb R}\)
\(\newcommand{\QQ}{\mathbb Q}\)
\(\newcommand{\ZZ}{\mathbb Z}\)
\(\newcommand{\Cc}{\mathcal C}\)
\(\newcommand{\Dd}{\mathcal D}\)
\(\newcommand{\Ee}{\mathcal E}\)
\(\newcommand{\Ff}{\mathcal F}\)
\(\newcommand{\Kk}{\mathcal K}\)
\(\newcommand{\Mm}{\mathcal M}\)
\(\newcommand{\Pp}{\mathcal P}\)
\(\newcommand{\ind}{\operatorname{ind}}\)
\(\newcommand{\ord}{\operatorname{ord}}\)

In this section, we shall consider another way to work with congruences, based upon the following:

Definition: Equivalence Relation

Let \(S\) be a set and \({}\cong{}\) a relation defined on \(S\). (That is, \(\forall x,y\in S\), the statement “\(x\cong y\)” may be true or false.) If \({}\cong{}\) satisfies the following three properties, it is called an equivalence relation:

• [Reflexivity] \(\forall x\in S\), \(x\cong x\).
• [Symmetry] \(\forall x,y\in S\), \(x\cong y\Leftrightarrow y\cong x\).
• [Transitivity] \(\forall x,y,z\in S\), \(x\cong y\) and \(y\cong z\Rightarrow x\cong z\).

If \({}\cong{}\) is an equivalence relation on the set \(S\) and \(x\in S\), then the set \([x]=\{y\in S\mid y\cong x\}\subseteq S\) is called the equivalence class of \(x\). We write \(S/ \cong \) for the set of equivalence classes in \(S\). And if \(\Cc\in S\), then any \(r\in S\) such that \(\Cc=[r]\) is called a representative of the equivalence class \(\Cc\).

Theorem \(\PageIndex{1}\)

Let \(S\) be a set and \({}\cong{}\) an equivalence relation defined on \(S\). Then

1. \(\forall x\in S,\ x\in[x]\).
2. \(\forall x,y\in S\), either \([x]=[y]\) or \([x]\cap[y]=\emptyset\), but not both.

Proof

(1): This is just the reflexivity of \({}\cong{}\).

(2): Suppose \(z\in[x]\cap[y]\). This means \(z\cong x\) and \(z\cong y\), so by symmetry \(y\cong z\) and by transitivity, \(x\cong y\).

Now if \(a\in[x]\) and \(b\in[y]\), then \(a\cong x\) and \(b\cong y\). By transitivity, \(a\cong x\cong y\cong b\). Thus \(a\in[y]\) and, by symmetry, \(b\cong x\) so \(b\in[x]\).

Therefore \([x]\subseteq [y]\) and \([y]\subseteq [x]\), and thus \([x]=[y]\).

Since the above construction only relied on the existence of some element \(z\in[x]\cap[y]\), we see that the only way we could fail to have \([x]=[y]\) is if \([x]\cap[y]=\emptyset\).

Example \(\PageIndex{1}\)

On the set \(S=\{(n,m)\mid n,m\in\ZZ, m\neq0\}\) we can define the relation \((a,b)\cong(c,d)\) if \(ad=cb\). Then \(S/ \cong\) is nothing other than the rational numbers, \(\QQ\)!

Now let us specialize the concept of equivalence class to the case of congruences:

Proposition \(\PageIndex{1}\)

Given \(n\in\NN\), the relation on \(\ZZ\) defined by \[a\cong_n b\Leftrightarrow a\equiv b\pmod{n}\] (which we shall write \(a\cong b\) if the \(n\) is clear from context) is an equivalence relation.

Definition: Congruuence Class and Integers mod

Given \(n\in\NN\) and \(a\in\ZZ\), the equivalence class of \(a\) under the above equivalence relation is called the congruence class of \(a\) mod \(n\) and is written \([a]_n\) (or, by abuse of notation, merely \([a]\) if the \(n\) is understood from the context). The set of equivalence classes \(\ZZ/\cong_n\) is called the integers mod \(n\) and is written \(\ZZ/n\ZZ\) (or, by some authors, \(\ZZ/n\) or \(\ZZ_n\)).

Theorem \(\PageIndex{2}\)

Given \(n\in\NN\), \(\ZZ/n\ZZ\) has \(n\) elements, with representatives \(0,\dots,n-1\) of these distinct equivalence classes. That is, \[\ZZ/n\ZZ = \left\{[0]_n,\dots,[n-1]_n\right\}.\]

Proof

Given \(n\in\NN\) and \(a\in\ZZ\), the Division Algorithm tells us there is a unique pair \(q,r\in\ZZ\) such that \(a=qn+r\) and \(0\le r<n\). Note that \(a\equiv r\pmod{n}\) or, equivalently, \(a\in[r]\). Thus every \(a\in\ZZ\) is an element of a unique equivalence class \([r]\) for \(r\in\{0,\dots,n-1\}\). Since each such \(r\in[r]\), uniquely!, the equivalence classes \([0],\dots,[n-1]\) are all distinct.

The remarkable thing about these \(\ZZ/n\ZZ\) is that we can do much of the usual integer arithmetic in them; in fact, sometimes we can do a bit more than the usual.

Given \(n\in\NN\) and \(\Cc,\Dd\in\ZZ/n\ZZ\), define \(\Cc+\Dd=[a+b]\) and \(\Cc\cdot\Dd=[a\cdot m]\) where \(a\) and \(b\) are any representatives of the congruence classes \(\Cc\) and \(\Dd\), respectively.

Theorem \(\PageIndex{3}\)

The operations \({}+{}\) and \({}\cdot{}\) on \(\ZZ/n\ZZ\) are well-defined. That is, they are independent of the choices of representatives of the congruence classes.

Proof

Say \(n\in\NN\) and \(\Cc,\Dd\in\ZZ/n\ZZ\). Let \(a,p,b,q\in\ZZ\) be such that \(\Cc=[a]=[p]\) and \(\Dd=[b]=[q]\). Then \(p\equiv a\pmod{n}\) and \(q\equiv b\pmod{n}\). But then Theorem 2.1.1 tells us that \(a+b\equiv p+q\pmod{n}\) and \(a\cdot b\equiv p\cdot q\pmod{n}\), so \([a+b]=[p+q]\) and \([a\cdot b]=[p\cdot q]\). This means that \(\Cc+\Dd\) can be defined either as \([a+b]\) or as \([p+q]\) and it will be the same thing, as asserted, and likewise for \(\Cc\cdot\Dd\).

These new operations are quite nice:

Theorem \(\PageIndex{4}\)

Given \(n\in\NN\), the addition and multiplication on \(\ZZ/n\ZZ\)

1. are commutative and associative;
2. multiplication distributes over addition;
3. both operations have an identity – \([0]\) for addition and \([1]\) for multiplication;
4. every element of \(\ZZ/n\ZZ\) has an additive inverse – the inverse of \([a]\) is \([-a]\) (or \([n-a]\), another name for the same thing); and
5. an element \([a]\in\ZZ/n\ZZ\) has a multiplicative inverse \([a]^{-1}\) if and only if \(\gcd(a,n)=1\); this inverse is unique when it exists.

Proof

Left to the reader. Note the last point is basically Corollary 2.2.1 restated in the language of congruence classes.

We can also restate many of our other, earlier results beside just Corollary 2.2.1 in terms of congruence classes. Most of these shall be left to the reader, but here is one example:

Theorem \(\PageIndex{5}\)

Given \(a,b\in\ZZ\) and \(n\in\NN\), let \(d=\gcd(a,n)\). Consider the equation \[[a]\cdot x = [b]\] where \(x\in\ZZ/n\ZZ\). Then

1. If \(d\nmid b\), there are no solutions.
2. If \(d\mid b\), this equation has exactly \(d\) solutions in \(\ZZ/n\ZZ\).

Proof

Left to the reader; this is really just Theorem 2.2.2 stated differently.

Exercise \(\PageIndex{1}\)

When the rational numbers \(\QQ\) are described as in Example 2.4.1, we define addition by \([(n,m)]+[(p,q)]=[(nq+mp,mq)]\) and multiplication by \([(n,m)]\cdot[(p,q)]=[(np,mq)]\), where \(n,m,p,q\in\ZZ\) and neither \(m\) nor \(q\) is \(0\). Prove a version of Theorem 2.4.3 for this version of \(\QQ\).

1. What are the additive and multiplicative identities in this \(\QQ\)? Does every element (or nearly every element) of \(\QQ\) have an additive and multiplicative inverse – if so, give a formula for those inverses; if not, why not?
2. Restate the Chinese Remainder Theorem in terms of congruence classes and equations in various \(\ZZ/n\ZZ\)’s rather than congruences.
3. Prove the statements in this section which have proofs “left to the reader.”
4. State and prove congruence class versions of any results about congruences from sections 2.1 and 2.2 which do not have versions in this section.