# 3.1: Modulo Operation

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

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

$$\newcommand{\id}{\mathrm{id}}$$ $$\newcommand{\Span}{\mathrm{span}}$$

( \newcommand{\kernel}{\mathrm{null}\,}\) $$\newcommand{\range}{\mathrm{range}\,}$$

$$\newcommand{\RealPart}{\mathrm{Re}}$$ $$\newcommand{\ImaginaryPart}{\mathrm{Im}}$$

$$\newcommand{\Argument}{\mathrm{Arg}}$$ $$\newcommand{\norm}[1]{\| #1 \|}$$

$$\newcommand{\inner}[2]{\langle #1, #2 \rangle}$$

$$\newcommand{\Span}{\mathrm{span}}$$

$$\newcommand{\id}{\mathrm{id}}$$

$$\newcommand{\Span}{\mathrm{span}}$$

$$\newcommand{\kernel}{\mathrm{null}\,}$$

$$\newcommand{\range}{\mathrm{range}\,}$$

$$\newcommand{\RealPart}{\mathrm{Re}}$$

$$\newcommand{\ImaginaryPart}{\mathrm{Im}}$$

$$\newcommand{\Argument}{\mathrm{Arg}}$$

$$\newcommand{\norm}[1]{\| #1 \|}$$

$$\newcommand{\inner}[2]{\langle #1, #2 \rangle}$$

$$\newcommand{\Span}{\mathrm{span}}$$ $$\newcommand{\AA}{\unicode[.8,0]{x212B}}$$

$$\newcommand{\vectorA}[1]{\vec{#1}} % arrow$$

$$\newcommand{\vectorAt}[1]{\vec{\text{#1}}} % arrow$$

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

$$\newcommand{\vectorC}[1]{\textbf{#1}}$$

$$\newcommand{\vectorD}[1]{\overrightarrow{#1}}$$

$$\newcommand{\vectorDt}[1]{\overrightarrow{\text{#1}}}$$

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

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

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

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



This page titled 3.1: Modulo Operation is shared under a CC BY-NC-SA license and was authored, remixed, and/or curated by Pamini Thangarajah.