U-3, CH-3

NUMBER THEORY
Division
When one integer is divided by a second nonzero integer, the quotient may or may
not be an integer.
For example, 12/3 = 4 is an integer, whereas 11/4 = 2.75 is not.
This leads to Definition 1.

DEFINITION 1: If a and b are integers with a ≠ 0, we say that a divides b if

there is an integer c such that b = ac, or equivalently, if𝑏𝑎 is an integer. When a
divides b we say that a is a factor or divisor of b, and that b is a multiple of a. The
notation a | b denotes that a divides b.

THEOREM 1 :
Let a, b, and c be integers, where a ≠ 0.
Then
(i) if a | b and a | c, then a | (b + c);
(ii) if a | b, then a | bc for all integers c;
(iii) if a | b and b | c, then a | c.

COROLLARY 1: If a, b, and c are integers, where a ≠ 0.

such that a | b and a | c, then a | mb + nc whenever m and n are integers

THEOREM 2: THE DIVISION ALGORITHM: Let a be an integer and d a

positive integer. Then there are unique integers q and r, with 0 ≤ r

In the equality given in the division algorithm, d is called the divisor, a is called the
dividend, q is called the quotient, and r is called the remainder.
This notation is used to express the quotient and remainder:
q = a div d, r = a mod d.
Remark: When a is an integer and d is a positive integer, we have a div d = a/d
and a mod d = a − d.
Modular Arithmetic:
DEFINITION 3: If a and b are integers and m is a positive integer, then a is
congruent to b modulo m if m divides a − b. We use the notation a ≡ b (mod m) to
indicate that a is congruent to b modulo m. We say that a ≡ b (mod m) is a
congruence and that m is its modulus (plural moduli). If a and b are not congruent
modulo m, we write a ≢ b (mod m)

THEOREM 3: Let a and b be integers, and let m be a positive integer. Then a ≡ b

(mod m) if and only if a mod m = b mod m.
• The set of all integers congruent to an integer a modulo m is called the
congruence class of a modulo m.

COROLLARY 2:
Let m be a positive integer and let a and b be integers. Then (a + b) mod m = ((a
mod m) + (b mod m)) mod m and
ab mod m = ((a mod m)(b mod m)) mod m

Arithmetic Modulo m:
We can define arithmetic operations on Zm, the set of nonnegative integers less
than m, that is, the set {0, 1,...,m − 1}. In particular, we define addition of these
integers, denoted by +m by
a +m b = (a + b) mod m,
where the addition on the right-hand side of this equation is the ordinary addition
of integers, and
we define multiplication of these integers, denoted by ·m by
a ·m b = (a · b) mod m
The operations +m and ·m are called addition and multiplication modulo m and
when we use these operations, we are said to be doing arithmetic modulo m
Primes
DEFINITION 1 :An integer p greater than 1 is called prime if the only positive
factors of p are 1 and p. A positive integer that is greater than 1 and is not prime is
called composite
Greatest Common Divisors and Least Common Multiples :
The largest integer that divides both of two integers is called the greatest common
divisor of these integers.
DEFINITIONS :
• Let a and b be integers, not both zero. The largest integer d such that d | a and d |
b is called the greatest common divisor of a and b. The greatest common divisor
of a and b is denoted by gcd(a, b)
• The integers a and b are relatively prime if their greatest common divisor is 1.
• The integers a1, a2,...,an are pairwise relatively prime if gcd(ai, aj ) = 1
whenever 1 ≤ i< j ≤n.
• gcd(a, b) = p1 min(a1, b1) p2 min(a2, b2) ··· pn min(an, bn)

DEFINITION : The least common multiple of the positive integers a and b is

the smallest positive integer that is divisible by both a and b. The least common
multiple of a and b is denoted by lcm(a, b).
• lcm(a, b) = p1 max(a1, b1) p2 max(a2, b2) ··· pn max(an, bn)
THEOREM : Let a and b be positive integers.
Then ab = gcd(a, b) · lcm(a, b).

The Euclidean Algorithm:

LEMMA 1: Let a = bq + r, where a, b, q, and r are integers. Then gcd(a, b) =
gcd(b, r).
 U-2, CH- 1
PARTIAL ORDERING
Partial ordering:
A relation R on a set S is called a partial ordering or partial order if it is reflexive,
antisymmetric, and transitive.
A set S together with a partial ordering R is called a partially ordered set, or poset,
and is denoted by (S, R) or (S,≼ ).
Members of S are called elements of the poset.

Example: Show that the divisibility relation ′ / ′ is a partial ordering on the set of
positive integers.
Solution: Let Z + be the set of positive integers.
Since (i). a/a for all a ∈ Z + , / is reflexive.
(ii). a/b and b/a ➙ a = b, / is antisymmetric.
(iii). a/b and b/c ➙ a/c, / is transitive.
It follows that / is a partial ordering on Z + and (Z + , /) is a poset.

Comparability:
The elements a and b of a poset (S, ≼) are called comparable if either a ≼ b or
b ≼ a.
When a and b are elements of S such that neither a ≼ b nor b ≼ a, a and b are
called incomparable.

DEFINITION : If (S, ≼) is a poset and every two elements of S are comparable,

S is called a totally ordered or linearly ordered set, and ≼ is called a total order or a
linear order. A totally ordered set is also called a chain.

Example: The poset (Z, ≤) is totally ordered, because a ≤ b or b ≤ a whenever a and

b are integers.
Example: The poset (Z+, |) is not totally ordered because it contains elements that
are incomparable, such as 5 and 7.
Well-ordered set:
(S, ≼ ) is a well-ordered set if it is a poset such that ≼ is a total ordering and
every nonempty subset of S has a least element.
Product order:
Let (A, ≼ 1) be a poset with a1,a2 ∈ A such that a1 ≼ a2 and let (B, ≼ 2) be a poset
with b1,b2 ∈ B such that b1 ≼ b2. Then the order ≼ on AxB defined by (a1, b1)
≼ (a2, b2) is called product order. (AxB, ≼ ) is a poset.

Lexicographic order:
The product order (a1, b1) ≼ (a2, b2) on AxB is called Lexicographic order if
i) a1< a2
Or
ii) a1= a2 and b1< b2
Lexicographic ordering of strings:
Consider the strings a1a2 ...am and b1b2 ...bn on a partially ordered set S. Suppose
these strings are not equal. Let t be the minimum of m and n. The definition of
lexicographic ordering is that the string a1a2 ...am is less than b1b2 ...bn if and only if
(a1, a2,..., at) ≺ (b1, b2,..., bt ),
Or
(a1, a2,..., at) = (b1, b2,..., bt ) and m < n.
Hasse Diagram:
It is used for the representation of a partial order ≼ on a set X.
• Elements of X are represented by vertices.
• If x,y ∈ X and y is a immediate successor of x, then y is placed at higher
level than x.
• x and y are joined
Maximal and Minimal elements:
An element of a poset is called maximal if it is not less than any element of the
poset. That is, a is maximal in the poset (S, ≼ ) if there is no b ∈ S such that a ≺ b.
Similarly, an element of a poset is called minimal if it is not greater than any
element of the poset. That is, a is minimal if there is no element b ∈ S such that b
≺ a.
• If there is an element in a poset that is greater than every other element. Such an
element is called the greatest element. That is, a is the greatest element of the
poset (S, ≼ )if b ≼ a for all b ∈ S. The greatest element is unique when it exists
 •Likewise, an element is called the least element if it is less than all the other
elements in the poset. That is, a is the least element of(S, ≼ )if a ≼ b for all b ∈ S.
The least element is unique when it exists

Upper and Lower Bounds:

Let (S, ≼ ) be a partially ordered set and let A ⊆ S . Any element x ∈ S is called an
upper bound for A if for all a ∈ A, a ≤ x.
Similarly, any element x ∈ S is called a lower bound for A if for all a ∈ A, x ≤ a.

•Let (S, ≤) be a partial ordered set and let A ⊆ S. An element x ∈ S is a least

upper bound or supremum for A if x is an upper bound for A and x ≤ y where y
is any upper bound for A.
Similarly, the the greatest lower bound for A is an element x ∈ P such that x is a
lower bound and y ≤ x for all lower bounds y.
**************************************
 U-1, CH-3
RELATIONS
Introduction:
Cartesian product:
Let A and B be sets. The cartesian product of A and B, denoted AxB in the set of
all ordered pairs(a,b) where a∈ A and b∈ B. Hence AxB={(a,b)|a∈ A and b∈ B}

Binary relation
Let A and B be sets. A binary relation from A to B is a subset of A × B.

• We use the notation aRb to denote that (a, b) ∈ R. Moreover, when (a, b) belongs
to R, a is said to be related to b by R.

DEFINITION :A relation on a set A is a relation from A to A.

In other words, a relation on a set A is a subset of A × A.

Note:
•The number of possible relations from set A of m elements to set B of n elements
is 2mn .
• Largest possible relation is AxB.
• Smallest possible relation is {}

Definition :The set of all first elements in a relation is called the domain of the
relation R and the set of second elements in a relation is called range of R.
•Range is a subset of Co-domain.

Properties of relations:
1) Reflexive relation: A relation R on a set A is called reflexive, if (a, a) ∈
R ,∀ a ∈ A.
2) Irreflexive relation: A relation R on a set A is called irreflexive, if (a, a) ∉
R , ∀ a ∈ A.
3) Symmetric relation: A relation R on a set A is called symmetric, if (a, b) ∈
R then(b, a) ∈ R whenever, ∀ a, b ∈ A.
4) Antisymmetric relation: A relation R on a set A is called antisymmetric, if
(a, b) ∈ R and (b, a) ∈ R, then a = b ,∀ a, b ∈ A.
5) Asymmetric relation: A relation R on a set A is called asymmetric relation,
if (a, b) ∈ R then (b, a)∉ R , ∀ a,b ∈ A.
6) Transitive relation: A relation R on a set A is called transitive, if (a, b) ∈ R
and (b, c) ∈ R, then (a, c) ∈ R, ∀ a, b, c ∈ A

Equivalence relation:
A relation on a set A is called an equivalence relation if it is reflexive, symmetric,
and transitive
Eg: If A={1,2,3} and R= {(1,1), (2,2), (3,3), (1,2), (2,1)}
Here R is an equivalence relation

Compatibility relation:
A relation R on a set A is said to be a compatibility relation if it is reflexive and
symmetric. Clearly, all equivalence relations are compatibility relations. A
compatibility relation is sometimes denoted by ≈.

Composition of binary relation:

Let R be a relation from A to B and S be a relation from B to C. Then a relation
written as R ◦ S is called a composite relation of R and S where R◦S = {(a, c)| a ∈
A, c ∈ C, and there exists b ∈ B with (a, b) ∈ R and (b, c) ∈ S }.
The operation of obtaining R◦S from R and S is called Composition of relations.

Relation Matrix
Let R be a relation from A = {a1, a2,...,am} to B = {b1, b2,...,bn}.Then the relation
matrix of R is defined as MR = [mij ], where
mij = {1, if (ai, bj) ∈ R
{ 0, if(ai, bj) ∉ R.
Properties of relation matrix:
(i). A relation R is reflexive, if the matrix diagonal elements are 1.
(ii). A relation R is irreflexive, if the matrix diagonal elements are 0.
(iii). A relation R is symmetric, if the transpose of relation matrix is equal to its
original relation matrix. i.e., MR = (MR)T .
(iv). A relation R is antisymmetric, then its matrix is such that if mij = 1 then mji =
0 for i ≠j.

Graph of a relation:
Digraph:
A directed graph, or digraph, consists of vertices (or nodes) connected by directed
edges (or arcs).
The vertex a is called the initial vertex of the edge (a, b), and the vertex b is called
the terminal vertex of this edge.
An edge of the form (a, a) is represented using an arc from the vertex a back to
itself. Such an edge is called a loop.
Properties :
(i). If a relation is reflexive, then there must be a self loop at each node.
(ii). If the relation is irreflexive, then there is no self loop at any node.
(iii). If a relation is symmetric, then there is a closed loop between two nodes.
 (iv). If a relation is antisymmetric, then there is no closed loop between two nodes
(v). If a relation is asymmetric, then there is no self loop or no closed loop between
two nodes.
•Indegree vertex is the number of edges terminating at the vertex.
• Outdegree vertex is the number of edges leaving the vertex.

**********************************************
 U-2, CH-2
FUNCTIONS
Function:
Let A and B be nonempty sets. A function f from A to B is an assignment of
exactly one element of B to each element of A.
We write f (a) = b if b is the unique element of B assigned by the function f to the
element a of A. If f is a function from A to B, we write f : A → B.
Remark: Functions are sometimes also called mappings or transformations.
• If f (a) = b, we say that b is the image of a and a is a preimage of b.
• If f is a function from A to B, we say that A is the domain of f and B is the
codomain of f.
•The range, or image, of f is the set of all images of elements of A.
Also, if f is a function from A to B, we say that f maps A to B.

Q: How many functions are possible?

Ans: nm
Q: How many relations which are not functions?
Ans: 2mn - nm

DEFINITION :
Let f1 and f2 be functions from A to R. Then f1 + f2 and f1f2 are also functions from
A to R defined for all x ∈ A by
(f1 + f2)(x) = f1(x) + f2(x),
(f1f2)(x) = f1(x)f2(x)
Types of Functions
1) One-to-one (Injective/ Injunction):
A mapping f : X → Y is called one-to-one if distinct elements of X are mapped
into distinct elements of Y , i.e., f is one-to-one if f(x1) = f(x2) ➙ x1 = x2 for x1,
x2 ∈ X.
Eg:
 2)Onto or Surjective function:
If f : X → Y is onto, then each element of Y is an image of atleast one element of
X.
i.e., ∀ y ∈ Y, ∃ x such that f(x) = y.
• In onto function, range of f =Codomain
Eg:

3) Bijective function/one-to-one correspondence

A mapping f : X → Y is called bijective if it is both one-to-one and onto. Such a
mapping is also called a one-to-one correspondence between X and Y .
4)Identity function:
Let X be any set and f be a function such that f : X → X is defined by f(x) = x for
all x ∈ X. Then, f is called the identity function or identity transformation on X. It
can be denoted by I or Ix.
Note: The identity function is both one-to-one and onto.
5) Constant function:
A function f : X → Y is called constant function if every element of is assigned to
the same element. i.e., f(x) = b
6) Composition of function:
Let f : X → Y and g : Y → Z be two functions. Then the composition of f and g
denoted by g ◦ f, is the function from X to Z defined as
(g ◦ f)(x) = g(f(x)), for all x ∈ X.
• g ° f(x) ≠ f ° g(x)

7) Inverse function:
Let f : X → Y be a bijective function. The inverse function of f is the function that
assigns to an element y ∈ Y the unique element x∈ X such that f (x) = y. The
inverse function of f is denoted by f −1. Hence, f −1(y) = x when f (x) = y.
 • A one-to-one correspondence is called invertible because we can define an
inverse of this function. A function is not invertible if it is not a one-to-one
correspondence, because the inverse of such a function does not exist.
• If f : X → Y and g : Y → X be such that g ◦ f = Ix and f ◦ g = Iy, then f and g
are both invertible. Furthermore, f −1 = g and g −1 = f

Example: Let f : R → R be given by f(x) = x 3 − 2. Find f −1 .

Solution: (i) First we shall show that f is one-to-one:
Let x1, x2 ∈ R such that f(x1) = f(x2)
➙ x1 3 − 2 = x23 − 2
➙ x1 3 = x23
➙ x1 = x2
∴ f is one-to-one.
To show that f is onto:
f(x)=y
➙ x3 -2 = y
➙ x 3 = y+2
➙ x= 3√𝑦 + 2
Given y ∈ R(codomain), there exists an element x = 3√𝑦 + 2 ∈ R
∴ f is onto
➙ f is invertible
f(x)=y
f( 3√𝑦 + 2)=y
and f −1 (y) = 3√𝑦 + 2.

**********************************************