Equivalence relations and partitions Equivalence classes modulo n Residue systems

Logic and Discrete Mathematics

Section 5.6
Equivalence Classes Modulo n
Residue Systems

Slides version: January 2015

Equivalence relations and partitions Equivalence classes modulo n Residue systems

Equivalence Relations

Let R be a binary relation on a set A. Then R is called

1. reflexive if R(a, a) for all a ∈ A;
2. symmetric if R(a, b) implies R(b, a), for all a, b ∈ A;
3. transitive if R(a, b) and R(b, c) implies R(a, c), for all
a, b, c ∈ A.

Definition
A relation R is an equivalence relation, if it is reflexive,
symmetric, and transitive.
Equivalence relations and partitions Equivalence classes modulo n Residue systems

Partitions

Definition
A partition of a set X is a family of non-empty and pairwise
disjoint subsets of X , the union of which is X . The sets in a
partition are called clusters of the partition.
Equivalence relations and partitions Equivalence classes modulo n Residue systems

Partitions vs. Equivalence Relations

Every partition P of a set X naturally defines an equivalence

relation ∼P on X as follows:
for every a, b ∈ X , a ∼P b iff a and b belong to the same cluster
of P.
Definition
Let ∼ be an equivalence relation in a set X and x ∈ X . The set
[[x]]∼ = {y ∈ X | x ∼ y } is called the equivalence class of x
with respect to ∼ .
Equivalence relations and partitions Equivalence classes modulo n Residue systems

Partitions vs. Equivalence Relations (2)

Lemma
Let ∼ be an equivalence relation in a set X . Then:
1. If x, y ∈ X and y ∈ [[x]]∼ then [[x]]∼ = [[y ]]∼ .
2. The family {[[x]]∼ | x ∈ X } is a partition of X .

Thus, equivalence relations and partitions are two sides of the

same coin.
Equivalence relations and partitions Equivalence classes modulo n Residue systems

The integers modulo n

Denote ‘congruence modulo n’ by ≡n .

The equivalence class of x with respect to ≡n will be denoted
by [[x]]n and will be called the equivalence class of x modulo n.
So:
[[x]]n = [[y ]]n iff x ≡ y (mod n).

For instance, [[3]]5 = {. . . , −7, −2, 3, 8, 13, . . .}.

Equivalence relations and partitions Equivalence classes modulo n Residue systems

The integers modulo n

Denote ‘congruence modulo n’ by ≡n .

The equivalence class of x with respect to ≡n will be denoted
by [[x]]n and will be called the equivalence class of x modulo n.
So:
[[x]]n = [[y ]]n iff x ≡ y (mod n).

For instance, [[3]]5 = {. . . , −7, −2, 3, 8, 13, . . .}.

Equivalence relations and partitions Equivalence classes modulo n Residue systems

The integers modulo n

Denote ‘congruence modulo n’ by ≡n .

The equivalence class of x with respect to ≡n will be denoted
by [[x]]n and will be called the equivalence class of x modulo n.
So:
[[x]]n = [[y ]]n iff x ≡ y (mod n).

For instance, [[3]]5 = {. . . , −7, −2, 3, 8, 13, . . .}.

Equivalence relations and partitions Equivalence classes modulo n Residue systems

The integers modulo n

Denote ‘congruence modulo n’ by ≡n .

The equivalence class of x with respect to ≡n will be denoted
by [[x]]n and will be called the equivalence class of x modulo n.
So:
[[x]]n = [[y ]]n iff x ≡ y (mod n).

For instance, [[3]]5 = {. . . , −7, −2, 3, 8, 13, . . .}.

Equivalence relations and partitions Equivalence classes modulo n Residue systems

The set Zn of integers modulo n

The set
Zn = {[[x]]n | x ∈ Z}
is called the set of integers modulo n.
Zn has precisely n different elements: [[0]]n , [[1]]n ..., [[n − 1]]n .
Hereafter we will denote them by [0]n , [1]n ..., [n − 1]n , i.e.

Zn = {[0]n , [1]n ..., [n − 1]n }.

Thus,
[[x]]n = [a]n iff a = (x rem n).

For example: [[−7]]5 = [3]5 , [[42]]7 = [0]7 .

Equivalence relations and partitions Equivalence classes modulo n Residue systems

The set Zn of integers modulo n

The set
Zn = {[[x]]n | x ∈ Z}
is called the set of integers modulo n.
Zn has precisely n different elements: [[0]]n , [[1]]n ..., [[n − 1]]n .
Hereafter we will denote them by [0]n , [1]n ..., [n − 1]n , i.e.

Zn = {[0]n , [1]n ..., [n − 1]n }.

Thus,
[[x]]n = [a]n iff a = (x rem n).

For example: [[−7]]5 = [3]5 , [[42]]7 = [0]7 .

Equivalence relations and partitions Equivalence classes modulo n Residue systems

The set Zn of integers modulo n

The set
Zn = {[[x]]n | x ∈ Z}
is called the set of integers modulo n.
Zn has precisely n different elements: [[0]]n , [[1]]n ..., [[n − 1]]n .
Hereafter we will denote them by [0]n , [1]n ..., [n − 1]n , i.e.

Zn = {[0]n , [1]n ..., [n − 1]n }.

Thus,
[[x]]n = [a]n iff a = (x rem n).

For example: [[−7]]5 = [3]5 , [[42]]7 = [0]7 .

Equivalence relations and partitions Equivalence classes modulo n Residue systems

The set Zn of integers modulo n

The set
Zn = {[[x]]n | x ∈ Z}
is called the set of integers modulo n.
Zn has precisely n different elements: [[0]]n , [[1]]n ..., [[n − 1]]n .
Hereafter we will denote them by [0]n , [1]n ..., [n − 1]n , i.e.

Zn = {[0]n , [1]n ..., [n − 1]n }.

Thus,
[[x]]n = [a]n iff a = (x rem n).

For example: [[−7]]5 = [3]5 , [[42]]7 = [0]7 .

Equivalence relations and partitions Equivalence classes modulo n Residue systems

The set Zn of integers modulo n

The set
Zn = {[[x]]n | x ∈ Z}
is called the set of integers modulo n.
Zn has precisely n different elements: [[0]]n , [[1]]n ..., [[n − 1]]n .
Hereafter we will denote them by [0]n , [1]n ..., [n − 1]n , i.e.

Zn = {[0]n , [1]n ..., [n − 1]n }.

Thus,
[[x]]n = [a]n iff a = (x rem n).

For example: [[−7]]5 = [3]5 , [[42]]7 = [0]7 .

Equivalence relations and partitions Equivalence classes modulo n Residue systems

The set Zn of integers modulo n

The set
Zn = {[[x]]n | x ∈ Z}
is called the set of integers modulo n.
Zn has precisely n different elements: [[0]]n , [[1]]n ..., [[n − 1]]n .
Hereafter we will denote them by [0]n , [1]n ..., [n − 1]n , i.e.

Zn = {[0]n , [1]n ..., [n − 1]n }.

Thus,
[[x]]n = [a]n iff a = (x rem n).

For example: [[−7]]5 = [3]5 , [[42]]7 = [0]7 .

Equivalence relations and partitions Equivalence classes modulo n Residue systems

The set Zn of integers modulo n

The set
Zn = {[[x]]n | x ∈ Z}
is called the set of integers modulo n.
Zn has precisely n different elements: [[0]]n , [[1]]n ..., [[n − 1]]n .
Hereafter we will denote them by [0]n , [1]n ..., [n − 1]n , i.e.

Zn = {[0]n , [1]n ..., [n − 1]n }.

Thus,
[[x]]n = [a]n iff a = (x rem n).

For example: [[−7]]5 = [3]5 , [[42]]7 = [0]7 .

Equivalence relations and partitions Equivalence classes modulo n Residue systems

The set Zn of integers modulo n

The set
Zn = {[[x]]n | x ∈ Z}
is called the set of integers modulo n.
Zn has precisely n different elements: [[0]]n , [[1]]n ..., [[n − 1]]n .
Hereafter we will denote them by [0]n , [1]n ..., [n − 1]n , i.e.

Zn = {[0]n , [1]n ..., [n − 1]n }.

Thus,
[[x]]n = [a]n iff a = (x rem n).

For example: [[−7]]5 = [3]5 , [[42]]7 = [0]7 .

Equivalence relations and partitions Equivalence classes modulo n Residue systems

The set Zn of integers modulo n

The set
Zn = {[[x]]n | x ∈ Z}
is called the set of integers modulo n.
Zn has precisely n different elements: [[0]]n , [[1]]n ..., [[n − 1]]n .
Hereafter we will denote them by [0]n , [1]n ..., [n − 1]n , i.e.

Zn = {[0]n , [1]n ..., [n − 1]n }.

Thus,
[[x]]n = [a]n iff a = (x rem n).

For example: [[−7]]5 = [3]5 , [[42]]7 = [0]7 .

Equivalence relations and partitions Equivalence classes modulo n Residue systems

Modular arithmetic
[[x]]n = [[y ]]n iff x and y leave the same remainders modulo n.
There are precisely n possible remainders modulo n :

0, 1, ..., n − 1
Zn has precisely n different elements:

[[0]]n , [[1]]n ..., [[n − 1]]n .

Thus:

Zn = {[0]n , [1]n ..., [n − 1]n }.

[[x]]n ⊕n [[y ]]n = [[x + y ]]n ,

and
[[x]]n n [[y ]]n = [[x.y ]]n .
Equivalence relations and partitions Equivalence classes modulo n Residue systems

Example

In Z6 :
[2]6 ⊕6 [5]6 = [[2 + 5]]6 = [[7]]6 = [1]6 ;
[3]6 6 [4]6 = [[3.4]]6 = [[12]]6 = [0]6 .
Equivalence relations and partitions Equivalence classes modulo n Residue systems

Basic laws of modular arithmetic

Theorem
In every Zn :

1. ⊕ is commutative and associative;

2.  is commutative and associative;

3.  is distributive over ⊕, i.e.:

[a]n  ([b]n ⊕ [c]n ) = ([a]n  [b]n ) ⊕ ([a]n  [c]n ).

4. [a]n ⊕ [0]n = [a]n ;

5. [a]n  [0]n = [0]n ;

6. [a]n  [1]n = [a]n .

Equivalence relations and partitions Equivalence classes modulo n Residue systems

Basic laws of modular arithmetic

Theorem
In every Zn :

1. ⊕ is commutative and associative;

2.  is commutative and associative;

3.  is distributive over ⊕, i.e.:

[a]n  ([b]n ⊕ [c]n ) = ([a]n  [b]n ) ⊕ ([a]n  [c]n ).

4. [a]n ⊕ [0]n = [a]n ;

5. [a]n  [0]n = [0]n ;

6. [a]n  [1]n = [a]n .

Equivalence relations and partitions Equivalence classes modulo n Residue systems

Basic laws of modular arithmetic

Theorem
In every Zn :

1. ⊕ is commutative and associative;

2.  is commutative and associative;

3.  is distributive over ⊕, i.e.:

[a]n  ([b]n ⊕ [c]n ) = ([a]n  [b]n ) ⊕ ([a]n  [c]n ).

4. [a]n ⊕ [0]n = [a]n ;

5. [a]n  [0]n = [0]n ;

6. [a]n  [1]n = [a]n .

Equivalence relations and partitions Equivalence classes modulo n Residue systems

Basic laws of modular arithmetic

Theorem
In every Zn :

1. ⊕ is commutative and associative;

2.  is commutative and associative;

3.  is distributive over ⊕, i.e.:

[a]n  ([b]n ⊕ [c]n ) = ([a]n  [b]n ) ⊕ ([a]n  [c]n ).

4. [a]n ⊕ [0]n = [a]n ;

5. [a]n  [0]n = [0]n ;

6. [a]n  [1]n = [a]n .

Equivalence relations and partitions Equivalence classes modulo n Residue systems

Basic laws of modular arithmetic

Theorem
In every Zn :

1. ⊕ is commutative and associative;

2.  is commutative and associative;

3.  is distributive over ⊕, i.e.:

[a]n  ([b]n ⊕ [c]n ) = ([a]n  [b]n ) ⊕ ([a]n  [c]n ).

4. [a]n ⊕ [0]n = [a]n ;

5. [a]n  [0]n = [0]n ;

6. [a]n  [1]n = [a]n .

Equivalence relations and partitions Equivalence classes modulo n Residue systems

Basic laws of modular arithmetic

Theorem
In every Zn :

1. ⊕ is commutative and associative;

2.  is commutative and associative;

3.  is distributive over ⊕, i.e.:

[a]n  ([b]n ⊕ [c]n ) = ([a]n  [b]n ) ⊕ ([a]n  [c]n ).

4. [a]n ⊕ [0]n = [a]n ;

5. [a]n  [0]n = [0]n ;

6. [a]n  [1]n = [a]n .

Equivalence relations and partitions Equivalence classes modulo n Residue systems

Basic laws of modular arithmetic

Theorem
In every Zn :

1. ⊕ is commutative and associative;

2.  is commutative and associative;

3.  is distributive over ⊕, i.e.:

[a]n  ([b]n ⊕ [c]n ) = ([a]n  [b]n ) ⊕ ([a]n  [c]n ).

4. [a]n ⊕ [0]n = [a]n ;

5. [a]n  [0]n = [0]n ;

6. [a]n  [1]n = [a]n .

Equivalence relations and partitions Equivalence classes modulo n Residue systems

Residue Systems – Definition

Given a positive integer n, a set of integers {x1 , . . . , xn } is

called a complete residue system modulo n if for every integer
y there is exactly one xi such that xi is a residue of y modulo n,
i.e. y ≡ xi (mod n).
The complete residue system modulo n {0, 1, 2, . . . , n − 1} is
called the primary residue system modulo n.
Thus, a complete residue system modulo n contains exactly
one representative of every equivalence class modulo n.
Equivalence relations and partitions Equivalence classes modulo n Residue systems

New Residue Systems from Old

Lemma
For any positive integer n :
1. n integers form a complete residue system modulo n if and
only if no two of them are congruent modulo m.
2. If {x1 , . . . , xn } is a complete residue system modulo n then
for any integer a, {x1 + a, . . . , xn + a} is a complete
residue system modulo n, too.
3. If {x1 , . . . , xn } is a complete residue system modulo n then
for any integer a, {ax1 , . . . , axn } is a complete residue
system modulo n iff gcd(a, n) = 1.
Equivalence relations and partitions Equivalence classes modulo n Residue systems

Reduced Residue Systems

Given a positive integer n, a reduced residue system modulo n

is the subset of any complete residue system modulo n,
consisting only of those integers that are relatively prime to n.
Equivalence relations and partitions Equivalence classes modulo n Residue systems

Multiplicative inverses in Zn
For any element [a]n ∈ Zn :
[a]n ⊕ [n − a]n = [n − a]n ⊕ [a]n = [0]n ,
i.e. [n − a]n is an additive inverse of [a]n in Zn .
An element [b]n is a multiplicative inverse of [a]n in Zn if

[a]n  [b]n = [1]n .

Does every element of Zn have a multiplicative inverse?

Theorem
[a]n has a multiplicative inverse in Zn iff gcd(a, n) = 1.
E XAMPLE . In Z6 : [5]6 has a multiplicative inverse (which?)
but [4]6 does not have one.

Corollary
Given an integer n > 1, the element [a]n ∈ Zn has a
multiplicative inverse for every 0 < a < n iff n is prime.
Equivalence relations and partitions Equivalence classes modulo n Residue systems

Multiplicative inverses in Zn
For any element [a]n ∈ Zn :
[a]n ⊕ [n − a]n = [n − a]n ⊕ [a]n = [0]n ,
i.e. [n − a]n is an additive inverse of [a]n in Zn .
An element [b]n is a multiplicative inverse of [a]n in Zn if

[a]n  [b]n = [1]n .

Does every element of Zn have a multiplicative inverse?

Theorem
[a]n has a multiplicative inverse in Zn iff gcd(a, n) = 1.
E XAMPLE . In Z6 : [5]6 has a multiplicative inverse (which?)
but [4]6 does not have one.

Corollary
Given an integer n > 1, the element [a]n ∈ Zn has a
multiplicative inverse for every 0 < a < n iff n is prime.
Equivalence relations and partitions Equivalence classes modulo n Residue systems

Multiplicative inverses in Zn
For any element [a]n ∈ Zn :
[a]n ⊕ [n − a]n = [n − a]n ⊕ [a]n = [0]n ,
i.e. [n − a]n is an additive inverse of [a]n in Zn .
An element [b]n is a multiplicative inverse of [a]n in Zn if

[a]n  [b]n = [1]n .

Does every element of Zn have a multiplicative inverse?

Theorem
[a]n has a multiplicative inverse in Zn iff gcd(a, n) = 1.
E XAMPLE . In Z6 : [5]6 has a multiplicative inverse (which?)
but [4]6 does not have one.

Corollary
Given an integer n > 1, the element [a]n ∈ Zn has a
multiplicative inverse for every 0 < a < n iff n is prime.
Equivalence relations and partitions Equivalence classes modulo n Residue systems

Multiplicative inverses in Zn
For any element [a]n ∈ Zn :
[a]n ⊕ [n − a]n = [n − a]n ⊕ [a]n = [0]n ,
i.e. [n − a]n is an additive inverse of [a]n in Zn .
An element [b]n is a multiplicative inverse of [a]n in Zn if

[a]n  [b]n = [1]n .

Does every element of Zn have a multiplicative inverse?

Theorem
[a]n has a multiplicative inverse in Zn iff gcd(a, n) = 1.
E XAMPLE . In Z6 : [5]6 has a multiplicative inverse (which?)
but [4]6 does not have one.

Corollary
Given an integer n > 1, the element [a]n ∈ Zn has a
multiplicative inverse for every 0 < a < n iff n is prime.
Equivalence relations and partitions Equivalence classes modulo n Residue systems

Multiplicative inverses in Zn
For any element [a]n ∈ Zn :
[a]n ⊕ [n − a]n = [n − a]n ⊕ [a]n = [0]n ,
i.e. [n − a]n is an additive inverse of [a]n in Zn .
An element [b]n is a multiplicative inverse of [a]n in Zn if

[a]n  [b]n = [1]n .

Does every element of Zn have a multiplicative inverse?

Theorem
[a]n has a multiplicative inverse in Zn iff gcd(a, n) = 1.
E XAMPLE . In Z6 : [5]6 has a multiplicative inverse (which?)
but [4]6 does not have one.

Corollary
Given an integer n > 1, the element [a]n ∈ Zn has a
multiplicative inverse for every 0 < a < n iff n is prime.
Equivalence relations and partitions Equivalence classes modulo n Residue systems

Multiplicative inverses in Zn
For any element [a]n ∈ Zn :
[a]n ⊕ [n − a]n = [n − a]n ⊕ [a]n = [0]n ,
i.e. [n − a]n is an additive inverse of [a]n in Zn .
An element [b]n is a multiplicative inverse of [a]n in Zn if

[a]n  [b]n = [1]n .

Does every element of Zn have a multiplicative inverse?

Theorem
[a]n has a multiplicative inverse in Zn iff gcd(a, n) = 1.
E XAMPLE . In Z6 : [5]6 has a multiplicative inverse (which?)
but [4]6 does not have one.

Corollary
Given an integer n > 1, the element [a]n ∈ Zn has a
multiplicative inverse for every 0 < a < n iff n is prime.
Equivalence relations and partitions Equivalence classes modulo n Residue systems

Multiplicative inverses in Zn
For any element [a]n ∈ Zn :
[a]n ⊕ [n − a]n = [n − a]n ⊕ [a]n = [0]n ,
i.e. [n − a]n is an additive inverse of [a]n in Zn .
An element [b]n is a multiplicative inverse of [a]n in Zn if

[a]n  [b]n = [1]n .

Does every element of Zn have a multiplicative inverse?

Theorem
[a]n has a multiplicative inverse in Zn iff gcd(a, n) = 1.
E XAMPLE . In Z6 : [5]6 has a multiplicative inverse (which?)
but [4]6 does not have one.

Corollary
Given an integer n > 1, the element [a]n ∈ Zn has a
multiplicative inverse for every 0 < a < n iff n is prime.