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