3.1: Modulo Operation

Definition: Modulo

Let \(m\) \(\in\) \(\mathbb{Z_+}\).

\(a\) is congruent to \(b\) modulo \(m\) denoted as \( a \equiv b (mod \, n) \), if \(a\) and \(b\)  have the remainder when they are divided by \(n\), for  \(a, b \in \mathbb{Z}\).

Example \(\PageIndex{1}\):

Suppose \(n= 5, \) then the possible remainders are \( 0,1, 2, 3,\) and \(4,\) when we divide any integer by \(5\).

Is \(6 \, \equiv 11 (mod \, 5)\)? Yes, because \(6\) and \(11 \) both belong to the same congruent/residue class \(1\). That is to say when \(6\) and \(11\) are divided by \(5\) the remainder is \(1.\)

Is \(7 \equiv 15(mod \, 5)\)? No, because \(7\) and \(15\) do not belong to the same congruent/residue class. Seven has a remainder of \(2,\) while \(15\) has a remainder of \( 0, \) therefore \(7 \) is not congruent to \( 15 (mod \, 5)\). That is \(7 \not \equiv 15(mod \, 5)\).

Example \(\PageIndex{2}\): Clock arithmetic

Find \(18:00\), that is find \(18 (mod \, 12)\).

Solution

\(18 mod(12) \equiv 6\). 6 pm.

Properties

Let \(n \in \mathbb{Z_+}\). Then

Theorem 1 :

Two integers \(a \) and \(b\) are said to be congruent modulo \( n\), \(a \equiv b (mod \, n)\), if all of the following are true:

a) \(m\mid (a-b).\)

b) both \(a\) and \(b \) have the same remainder when divided by \(n.\)

c) \(a-b= kn\), for some \(k \in \mathbb{Z}\).

NOTE: Possible remainders of \( n\) are \(0, ..., n-1.\)

Reflexive Property

Theorem 2:

The relation " \(\equiv\) " over \(\mathbb{Z}\) is reflexive.

Proof: Let \(a \in \mathbb{Z} \).

Then \(a-a=0(n)\), and \( 0 \in \mathbb{Z}\).

Hence \(a \equiv a (mod \, n)\).

Thus congruence modulo n is Reflexive.

Symmetric Property

Theorem 3:

The relation " \(\equiv\) " over \(\mathbb{Z}\) is symmetric.

Proof: Let \(a, b \in \mathbb{Z} \) such that \(a \equiv b\) (mod n).

Then \(a-b=kn, \) for some \(k \in \mathbb{Z}\).

Now \( b-a= (-k)n \) and \(-k \in \mathbb{Z}\).

Hence \(b \equiv a(mod \, n)\).

Thus the relation is symmetric.

Antisymmetric Property

Is the relation " \(\equiv\) " over \(\mathbb{Z}\) antisymmetric?

Counter Example: \(n\) is fixed

choose: \(a= n+1, b= 2n+1\), then

\(a \equiv b(mod \, n)\) and \( b \equiv a (mod \, n)\)

but \( a \ne b.\)

Thus the relation " \(\equiv\) "on \(\mathbb{Z}\) is not antisymmetric.

Transitive Property

Theorem 4 :

The relation " \(\equiv\) " over \(\mathbb{Z}\) is transitive.

Proof: Let \(a, b, c \in\) \(\mathbb{Z}\), such that \(a \equiv b (mod n)\) and \(b \equiv c (mod n).\)

Then \(a=b+kn, k \in\) \(\mathbb{Z}\) and \(b=c+hn, h \in\) \(\mathbb{Z}\).

We shall show that \(a \equiv c (mod \, n)\).

Consider \(a=b+kn=(c+hn)+kn=c+(hn+kn)=c+(h+k)n, h+k \in\) \(\mathbb{Z}\).

Hence \(a \equiv c (mod \, n)\).

Thus congruence modulo \(n\) is transitive.

Theorem 5:

The relation " \(\equiv\) " over \(\mathbb{Z}\) is an equivalence relation.

Modulo classes

Let . The relation \( \equiv \) on by \( a \equiv b \) if and only if , is an equivalence relation. The Classes of have the following equivalence classes:

.

 

Example of writing equivalence classes:

Example \(\PageIndex{3}\):

The equivalence classes for \(( mod \, 3 )\) are (need to show steps):

.

.

.

 

Computational aspects:

Finding "mod 5"

%%python3
print( "integer  integer mod 5")
for i in range(30):
    print(i, "       ", i%5)

Code \(\PageIndex{1}\) (Python):

%%python3