Loading [MathJax]/extensions/TeX/boldsymbol.js
Skip to main content
Library homepage
 

Text Color

Text Size

 

Margin Size

 

Font Type

Enable Dyslexic Font
Mathematics LibreTexts

3.1: Modulo Operation

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

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 4.0 license and was authored, remixed, and/or curated by Pamini Thangarajah.

Support Center

How can we help?