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