# 3.1 Modulo Operation

- Page ID
- 7454

\( \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:

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