
# 3.1 Modulo Operation

$$\newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} }$$

$$\newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}}$$

Definition

Let $$n$$ $$\in$$ $$\mathbb{Z_+}$$.

Define a relation " $$\equiv$$ "on $$\mathbb{Z}$$ by $$a \equiv b$$ (mod n) iff (if and only if) $$m \mid a-b$$ for all $$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 will be 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

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

## Computational aspects:

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