
# 3.1 Modulo Operation

[ "stage:draft", "article:topic", "license:ccbyncsa", "showtoc:yes" ]

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

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

Definition

Modular Arithmetic begins with a modulus "$$n$$", $$n$$ must be a member of  $$\mathbb{Z_+}$$ .

Modulus "$$n$$" divides all the integers into congruent or residue classes. These classes are determined by the remainder after division.

The modulus must always be set in advance; for example n=2, n=5, n=15.

Remainders are always $$0,\cdots, n-1.$$

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

## Properties

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

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