Taif University

College of Computers and Information Technology,

Chapter 4
Number Theory
 The Integers and Divison

 Primes

 Greatest Common Divisors

 Applications of Number Theory

 The Integers and Divison
Division
Definition: If a and b are integers with a ≠ 0, then a
divides b if there exists an integer c such that b = ac.
 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.

 If a | b, then b/a is an integer.

 If a does not divide b, we write a ∤ b.

Division

Example: Determine whether 3 | 7 and whether

3 | 12.

Solution: 3 ∤ 7 because 7/3 is not an integer. 3 | 12

because 12/3=4, which is an integer.
Properties of Divisibility
Theorem 1: Let a, b, and c be integers, where a ≠0.
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.

Proof: (i) Suppose a | b and a | c, then it follows that there are

integers s and t with b = as and c = at. Hence,
b + c = as + at = a(s + t). Hence, a | (b + c)

Corollary: If a, b, and c be integers, where a ≠0, such that a | b

and a | c, then a | mb + nc whenever m and n are integers.
Can you show how it follows easily from from (ii) and (i) of
Theorem 1?
Division Algorithm
 When an integer is divided by a positive integer, there
is a quotient and a remainder. This is traditionally
called the “Division Algorithm,” but is really a theorem.

Division Algorithm: If a is an integer and d a positive

integer, then there are unique integers q and r, with 0
≤ r < d, such that a = dq + r
 d is called the divisor.
 a is called the dividend. Definitions of Functions div
and mod
 q is called the quotient.
 r is called the remainder. q = a div d
r = a mod d
Division Algorithm
Examples:
 What are the quotient and remainder when 101 is
divided by 11?

Solution: The quotient when 101 is divided by 11 is 9 =

101 div 11, and the remainder is 2 = 101 mod 11.

 What are the quotient and remainder when −11 is

divided by 3?

Solution: The quotient when −11 is divided by 3 is −4 =

−11 div 3, and the remainder is 1 = −11 mod 3.
Congruence Relation
Definition: 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.
 The notation a ≡ b (mod m) says that a is congruent
to b modulo m.
 We say that a ≡ b (mod m) is a congruence and that m
is its modulus.
 Two integers are congruent mod m if and only if they
have the same remainder when divided by m.
 If a is not congruent to b modulo m, we write
a ≢ b (mod m)
Congruence Relation
Example: Determine whether 17 is congruent to 5
modulo 6 and whether 24 and 14 are congruent
modulo 6.

Solution:
 17 ≡ 5 (mod 6) because 6 divides 17 − 5 = 12.
 24 ≢ 14 (mod 6) since 6 divides 24 − 14 = 10 is not
divisible by 6.
 Primes
Primes
Definition: A positive 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.

Example: The integer 7 is prime because its only

positive factors are 1 and 7, but 9 is composite
because it is divisible by 3.
The Fundamental Theorem of Arithmetic
Theorem: Every positive integer greater than 1 can be
written uniquely as a prime or as the product of two or
more primes where the prime factors are written in order of
nondecreasing size.

Examples:
 100 = 2 ∙ 2 ∙ 5 ∙ 5 = 22 ∙ 52

 641 = 641

 999 = 3 ∙ 3 ∙ 3 ∙ 37 = 33 ∙ 37

 1024 = 2 ∙ 2 ∙ 2 ∙ 2 ∙ 2 ∙ 2 ∙ 2 ∙ 2 ∙ 2 ∙ 2 = 210
 Greatest Common Divisor
Greatest Common Divisor
Definition: Let a and b be integers, not both zero. The
largest integer d such that d | a and also 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).

One can find greatest common divisors of small numbers by

inspection.

Example:What is the greatest common divisor of 24 and 36?

Solution: gcd(24,36) = 12

Example:What is the greatest common divisor of 17 and 22?

Solution: gcd(17,22) = 1
Greatest Common Divisor
Definition: The integers a and b are relatively prime if their greatest
common divisor is 1.
Example: 17 and 22 are relatively prime because gcd(17, 22)=1.

Definition: The integers a1, a2, …, an are pairwise relatively prime if

gcd(ai, aj)= 1 whenever 1 ≤ i<j ≤n.

Example: Determine whether the integers 10, 17 and 21 are pairwise

relatively prime.
Solution: Because gcd(10,17) = 1, gcd(10,21) = 1, and gcd(17,21) = 1,
10, 17, and 21 are pairwise relatively prime.

Example: Determine whether the integers 10, 19, and 24 are pairwise
relatively prime.
Solution: Because gcd(10,24) = 2>1, so 10, 19, and 24 are not
pairwise relatively prime.
Finding the Greatest Common Divisor
Using Prime Factorizations
 Suppose the prime factorizations of a and b are:

where each exponent is a nonnegative integer, and where all primes

occurring in either prime factorization are included in both. Then:

 This formula is valid since the integer on the right (of the equals sign)
divides both a and b. No larger integer can divide both a and b.
Example: 120 = 23 ．3 ． 5 and 500 = 22 ． 53
gcd(120,500) = 2min(3,2) 3min(1,0) 5min(1,3) = 22 30 51 = 20
 Finding the gcd of two positive integers using their prime factorizations
is not efficient because there is no efficient algorithm for finding the
prime factorization of a positive integer.
 Applications of Number Theory
Euclidean Algorithm
Euclid
(325 B.C.E. – 265 B.C.E.)
 The Euclidian algorithm is an efficient method for
computing the greatest common divisor of two integers. It
is based on the idea that gcd(a,b) is equal to gcd(a,c) when
a > b and c is the remainder when a is divided by b.
Example: Find gcd(91, 287):
 287 = 91 ∙ 3 + 14 Divide 287 by 91
 91 = 14 ∙ 6 + 7 Divide 91 by 14
 14 = 7 ∙ 2 + 0 Divide 14 by 7
Stopping
condition

gcd(287, 91) = gcd(91, 14) = gcd(14, 7) = 7

continued →
Correctness of Euclidean Algorithm
Lemma 1: Let a = bq + r, where a, b, q, and r are integers.
Then gcd(a,b) = gcd(b,r).

Proof:
 Suppose that d divides both a and b. Then d also divides a − bq = r
(by Theorem 1 of Section 4.1). Hence, any common divisor of a and
b must also be any common divisor of b and r.
 Suppose that d divides both b and r. Then d also divides bq + r = a.
Hence, any common divisor of a and b must also be a common
divisor of b and r.
 Therefore, gcd(a,b) = gcd(b,r).
gcds as Linear Combinations
Étienne Bézout
(1730-1783)
Bézout’s Theorem: If a and b are positive integers, then there exist
integers s and t such that gcd(a,b) = sa + tb.

Definition: If a and b are positive integers, then integers s and t such that
gcd(a,b) = sa + tb are called Bézout coefficients of a and b. The equation
gcd(a,b) = sa + tb is called Bézout’s identity.

 By Bézout’s Theorem, the gcd of integers a and b can be expressed in the

form sa + tb where s and t are integers. This is a linear combination with
integer coefficients of a and b.

 gcd(6,14) = (−2)∙6 + 1∙14

 Finding gcds as Linear Combinations
Example: Express gcd(252,198) = 18 as a linear combination of 252
and 198.
Solution: First use the Euclidean algorithm to show
gcd(252,198) = 18
i. 252 = 1∙198 + 54
ii. 198 = 3 ∙54 + 36
iii. 54 = 1 ∙36 + 18
iv. 36 = 2 ∙18
 Now working backwards, from iii and ii above
 18 = 54 − 1 ∙36
 36 = 198 − 3 ∙54
 Substituting the 2nd equation into the 1st yields:
 18 = 54 − 1 ∙(198 − 3 ∙54 )= 4 ∙54 − 1 ∙198
 Substituting 54 = 252 − 1 ∙198 (from i)) yields:
 18 = 4 ∙(252 − 1 ∙198) − 1 ∙198 = 4 ∙252 − 5 ∙198
continued →
Finding gcds as Linear Combinations
 This method illustrated above is a two pass method. It first
uses the Euclidian algorithm to find the gcd and then
works backwards to express the gcd as a linear combination
of the original two integers. A one pass method, called the
extended Euclidean algorithm.