Discrete Mathematics (12) Number Theory
Discrete Mathematics (12) Number Theory
Number Theory
Session 12
Acknowledgement
Chapter 4
2
Learning Objectives
LO 2
Explain Set Theory, Fuzzy Set,
Counting method, Number Theory
and its applications
Sub Topics
4
Divisibility and Modular Arithmetic
5
Introduction
6
Division
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 ba 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. We write a∤b when a
does not divide b.
Example 1 :
Determine whether 3 ∣ 7 and whether 3 ∣ 12.
Solution:
3 ∤ 7, because 7∕3 is not an integer.
3 ∣ 12 because 12∕3 = 4.
7
Division
Example 02 :
Let n and d be positive integers. How many positive integers not
exceeding n are divisible by d?
Solution:
The positive integers divisible by d are all the integers of the form dk,
where k is a positive integer.
Hence, the number of positive integers divisible by d that do not exceed n
equals the number of integers k with 0 < dk ≤ n, or with 0 < k ≤ n∕d.
Therefore, there are ⌊n∕d⌋ positive integers not exceeding n that are
divisible by d.
8
Division
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.
9
Division
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.
Proof:
We will give a direct proof.
By part (ii) of Theorem 1 we see that
a ∣ mb and a ∣ nc
whenever m and n are integers.
By part (i) of Theorem 1 it follows that a ∣ mb + nc.
10
The Division Algorithm
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 < d, such that a = dq +
r.
Definition 2
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.
11
The Division Algorithm
Example 1:
What are the quotient and remainder when 11 is divided by 11?
Solution:
We have 11 = 11 ⋅ 9 + 2.
Hence, the quotient when 11 is divided by 11 is
9 = 11 div 11,
and the remainder is
2 = 11 mod 11.
12
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.
13
Modular Arithmetic
Example :
Determine whether 17 is congruent to 5 modulo 6 and whether 24 and 14
are congruent modulo 6.
Solution:
Because 6 divides 17 − 5 = 12, we see that 17 ≡ 5 (mod 6).
However, because 24 − 14 = 10 is not divisible by 6,
we see that 24 ≢ 14 (mod 6).
14
Modular Arithmetic
Theorem 4
Let m be a positive integer. The integers a and b are congruent modulo
m if and only if there is an integer k such that a = b + km.
Proof:
If a ≡ b (mod m), we know that m ∣ (a − b).
There is an integer k such that a − b = km, so that a = b + km.
Conversely, if there is an integer k such that a = b + km, then km = a − b.
Hence, m divides a − b, so that a ≡ b (mod m).
15
Modular Arithmetic
Theorem 5
Let m be a positive integer. If a ≡ b (mod m) and c ≡ d (mod m), then a + c
≡ b + d (mod m) and ac ≡ bd (mod m).
Proof: Example :
We use a direct proof. Because 7 ≡ 2 (mod 5)
Because a ≡ b (mod m) and c ≡ d (mod m), and 11 ≡ 1 (mod 5), it
are integers s and t with b = a + sm and d = c + follows from Theorem
tm. 5 that
Hence, 18 = 7 + 11 ≡ 2 + 1
b + d = (a + sm) + (c + tm) = (a + c) + m(s + t) =3 (mod 5)
and and that
bd = (a + sm)(c + tm) = ac + m(at + cs + stm). 77 = 7 ⋅ 11 ≡ 2 ⋅ 1 = 2
Hence, (mod 5).
a + c ≡ b + d (mod m) and ac ≡ bd (mod m).
16
Modular Arithmetic
Corollary 2
Let m be a positive integer and let a and b be integers. Then
(a + b) modm = ((a modm) + (b modm)) modm
and
ab modm = ((a modm)(b modm)) modm.
Proof:
By the definitions of modm and of congruence modulo m, we know that
a ≡(a modm) (modm) and b ≡ (b modm) (modm).
Hence, Theorem 5 tells us that
a + b ≡ (a modm) + (b modm) (modm)
and
ab ≡ (a modm)(b modm) (modm).
The equalities in this corollary follow from these last two congruences by Theorem 3.
17
Modular Arithmetic
Example:
Find the value of (193 mod 31)4 mod 23.
Solution:
First evaluate 193 mod 31. Because 193 = 6859 and 6859 = 221 ⋅ 31 + 8,
we have 193 mod 31 = 6859 mod 31 = 8.
So, (193 mod 31)4 mod 23 = 84 mod 23.
Next, note that 84 = 4096.
Because 4096 = 178 ⋅ 23 + 2,
we have 4096 mod 23 = 2.
Hence,
(193 mod 31)4 mod 23 = 2.
18
Primes and Greatest Common
Divisors
19
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.
Example :
The integer 7 is prime because its only positive factors are 1 and 7,
whereas the integer 9 is composite because it is divisible by 3.
20
Primes
Theorem 1 .
The Fundamental Theorem Of Arithmetic
Every 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
Example :
The prime factorizations of 100, 641, 999, and 1024 are given by
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 .
21
Trial Division
Theorem 2
If n is a composite integer, then n has a prime divisor less than or equal to
√n.
Proof:
If n is composite, by the definition of a composite integer, we know that it
has a factor a with 1 < a < n.
Hence, by the definition of a factor of a positive integer, we have n = ab,
where b is a positive integer greater than 1.
We will show that a ≤√n or b ≤√n. If a >√n and b >√n, then ab >√n ⋅
√n = n, which is a contradiction.
Consequently, a ≤√n orb ≤√n. Because both a and b are divisors of n, we
see that n has a positive divisor not exceeding √n.
This divisor is either prime or, by the fundamental theorem of arithmetic,
has a prime divisor less than itself. In either case, n has a prime divisor less
than or equal to √n.
22
Trial Division
Example :
Show that 101 is prime.
Solution:
The only primes not exceeding √101 are 2, 3, 5, and 7.
Because 101 is not divisible by 2, 3, 5, or 7
(the quotient of 101 and each of these integers is not an integer),
it follows that 101 is prime.
23
THE DISTRIBUTION OF PRIMES
Theroem 4.
Theprimenumbertheorem. The ratio of 𝜋(x), the number of primes not
exceeding x, and x ∕ ln x approaches 1 as x grows without bound.
(Here ln x is the natural logarithm of x.)
Definition 2
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).
Example :
What is the greatest common divisor of 24 and 36?
Solution:
25
Greatest Common Divisors and Least
Common Multiples
Definition 3
The integers a and b are relatively prime if their greatest common divisor
is 1.
Example :
The integers 17 and 22 have no positive common divisors other than 1,
so that gcd(17, 22) = 1.
Hence that the integers 17 and 22 are relatively prime.
26
Greatest Common Divisors and Least
Common Multiples
Definition 4
The integers a1, a2,…, an are pairwise relatively prime if gcd(ai, aj) = 1
whenever 1 ≤ i <j ≤ n.
Example :
Determine whether the following integers are pairwise relatively prime
a. 10, 17, and 21
b. 10, 19, and 24
Solution:
a. Because gcd(10, 17) = 1, gcd(10, 21) = 1, and gcd(17, 21) = 1, we
conclude that 10,17, and 21 are pairwise relatively prime.
b. Because gcd(10, 24) = 2 > 1, we see that 10, 19, and 24 are not pairwise
relatively prime.
27
Greatest Common Divisors and Least
Common Multiples
Definition 5 :
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).
Example :
What is the least common multiple of 23 35 72 and 24 33
Solution:
We have
lcm(23 35 72 , 24 33 ) = 2max(3, 4) 3max(5, 3) 7max(2, 0) . = 243572.
Theorem 5
Let a and b be positive integers. Then ab = gcd(a, b) ⋅ lcm(a, b).
28
The Euclidean Algorithm
Lemma 1
Let a = bq + r, where a, b, q, and r are integers. Then gcd(a, b) = gcd(b, r).
Proof:
If we can show that the common divisors of a and b are the same as the
common divisors of b and r, we will have shown that gcd(a, b) = gcd(b, r),
because both pairs must have the same greatest common divisor.
So suppose that d divides both a and b. Then it follows that d also
divides
a − bq = r .
Hence, any common divisor of a and b is also a common divisor of b and
r.
Likewise, suppose that d divides both b and r. Then d also divides bq + r
= a. Hence, any common divisor of b and r is also a common divisor of29a
The Euclidean Algorithm
Suppose that a and b are positive integers with a ≥ b. Let r0 = a and r1 = b. apply
the division algorithm, we obtain
r0 = r1 q1 + r2 0 ≤ r2 < r1,
r1 = r2 q2 + r3 0 ≤ r3 < r2,
⋅⋅⋅
rn−2 = rn−1qn−1 + rn 0 ≤ rn < rn−1,
rn−1 = rn qn.
Furthermore,
it follows from Lemma 1 that
gcd(a, b) = gcd(r0, r1) = gcd(r1, r2) = ⋯ = gcd(rn−2, rn−1)
= gcd(rn−1, rn) = gcd (rn, 0) = rn.
30
The Euclidean Algorithm
Example :
Find the greatest common divisor of 414 and 662 using the Euclidean
algorithm.
Solution:
Successive uses of the division algorithm give:
662 = 414 ⋅ 1 + 248
414 = 248 ⋅ 1 + 166
248 = 166 ⋅ 1 + 82
166 = 82 ⋅ 2 + 2
82 = 2 ⋅ 41.
Hence, gcd(414, 662) = 2, because 2 is the last nonzero remainder.
31
The Euclidean Algorithm
32
gcds as Linear Combinations
Theorem 6
Bezout’s Theorem If a and b are positive integers, then there exist
integers s and t such that gcd(a, b) = sa + tb.
Definition 6
If a and b are positive integers, then integers s and t such that
gcd(a, b) = sa + tb are called Bezout coefficients of a and b
(after ´ Etienne B´ezout, a French mathematician of the eighteenth
century). Also, the equation gcd(a, b) = sa + tb is called Bezout’s identity.
Example :
Express gcd(252, 198) = 18 as a linear combination of 252 and 198 by
working backwards through the steps of the Euclidean algorithm.
33
gcds as Linear Combinations
Solution:
To show that gcd(252, 198) = 18, the Euclidean algorithm uses these
divisions:
252 = 198 ⋅ 1 + 54
198 = 54 ⋅ 3 + 36
54 = 36 ⋅ 1 + 18
36 = 18 ⋅ 2 + 0.
We find that
18 = 54 − 1 ⋅ 36.
The second division tells us that
36 = 198 − 3 ⋅ 54.
18 = 54 − 1 ⋅ 36 = 54 − 1 ⋅ (198 − 3 ⋅ 54) = 4 ⋅ 54 − 1 ⋅ 198.
54 = 252 − 1 ⋅ 198.
18 = 4 ⋅ (252 − 1 ⋅ 198) − 1 ⋅ 198 = 4 ⋅ 252 − 5 ⋅ 198,
completing the solution.
34
gcds as Linear Combinations
Lemma 2
If a, b, and c are positive integers such that gcd(a, b) = 1 and a ∣ bc, then a ∣
c.
Proof:
Because gcd(a, b) =1, by Bezout’s theorem there are integers s and t such
that sa + tb = 1.
Multiplying both sides of this equation by c, we obtain sac + tbc = c.
By part (ii ) of that theorem, a ∣ tbc.
Because a ∣ sac and a ∣ tbc, by part (i ) of that theorem, we conclude that a
divides sac + tbc.
Because sac + tbc = c, we conclude that a ∣ c.
35
gcds as Linear Combinations
Lemma 3
If p is a prime and p ∣ a1a2⋯an, where each ai is an integer, then p ∣ ai
for some i.
Theorem 7 :
Let m be a positive integer and let a, b, and c be integers. If ac ≡ bc (mod
m) and
gcd(c,m) = 1, then a ≡ b (mod m).
Proof:
Because ac ≡ bc (mod m),m ∣ ac − bc = c(a − b). By Lemma 2, because
gcd(c,m) = 1, it follows that m ∣ a − b. We conclude that a ≡ b (mod m).
36
Solving Congruences
37
Linear Congruences
38
Linear Congruences
Solution:
Because gcd(3, 7) = 1, Theorem 1 tells us that an inverse of 3 modulo 7
exists. The Euclidean algorithm ends quickly when used to find the
greatest common divisor of 3 and 7:
7 = 2 ⋅ 3 + 1.
From this equation we see that
−2 ⋅ 3 + 1 ⋅ 7 = 1.
This shows that −2 and 1 are Bezout coefficients of 3 and 7.
We see that −2 is an inverse of 3 modulo 7.
Note that every integer congruent to −2 modulo 7 is also an inverse of 3,
such as 5, −9, 12, and so on.
39
Linear Congruences
Example 2
What are the solutions of the linear congruence 3x ≡ 4 (mod 7)?
Solution:
By Example 1 we know that −2 is an inverse of 3 modulo 7.
Multiplying both sides of the congruence by −2 shows that
−2 ⋅ 3x ≡ −2 ⋅ 4 (mod 7).
Because −6 ≡ 1 (mod 7) and −8 ≡ 6 (mod 7),
it follows that if x is a solution, then x ≡ −8 ≡ 6 (mod 7).
Assume that x ≡6 (mod 7).
Then, 3x ≡ 3 ⋅ 6 = 18 ≡ 4 (mod 7),
which shows that all such x satisfy the congruence.
We conclude that the solutions to the congruence are the integers x
such that x ≡ 6 (mod 7), namely, 6, 13, 20,… and −1, −8, −15,….
40
Fermat’s Little Theorem
Definisi 1
Let b be a positive integer. If n is a composite positive integer, and
𝑏 𝑛−1 ≡ 1 (mod n), then n is called a pseudoprime to the base b.
Definition 2
A composite integer n that satisfies the congruence 𝑏 𝑛−1 ≡ 1 (mod n) for
all positive integers b with gcd(b, n) = 1 is called a Carmichael number.
(These numbers are named after Robert Carmichael, who studied them
in the early twentieth century.)
42
Pseudoprimes
Example :
The integer 561 is a Carmichael number. Because
first 561 is composite because 561 = 3 ⋅ 11 ⋅ 17.
if gcd(b, 561) = 1, then gcd(b, 3) = gcd(b, 11) =gcd(b, 17) = 1.
it follows that 𝑏 560 ≡ 1 (mod 561) for all positive integers b with
gcd(b, 561) = 1. Hence, 561 is a Carmichael number.
43
Applications of Congruences
44
Applications of Congruences
45
1. Hashing Functions
Example :
Find the memory locations assigned by the hashing function h(k) = k mod
111 to the records of customers with Social Security numbers
a. 064212848
b. 107405723.
Solution:
a. The record of the customer with Social Security number 064212848 is
assigned to memory location 14, because
h(064212848) = 064212848 mod 111 = 14.
b. h(107405723) = 107405723 mod 111 = 14,
This location is already occupied (answer a) . But, because memory
location 15, the first location following memory location 14, is free, we
assign the record of the customer with Social Security number
107405723 to this location.
47
2. Pseudorandom Numbers
Example :
Find the sequence of pseudorandom numbers generated by the linear
congruential method with modulus m = 9, multiplier a = 7, increment c =
4, and seed x0 = 3.
Solution:
We compute the terms of this sequence by successively using the
recursively defined function xn+1 = (7xn + 4) mod 9,
beginning by inserting the seed x0 = 3 to find x1. We find that
x1 = 7x0 + 4 mod 9 = 7 ⋅ 3 + 4 mod 9 = 25 mod 9 = 7,
x2 = 7x1 + 4 mod 9 = 7 ⋅ 7 + 4 mod 9 = 53 mod 9 = 8,
x3 = 7x2 + 4 mod 9 = 7 ⋅ 8 + 4 mod 9 = 60 mod 9 = 6,
x4 = 7x3 + 4 mod 9 = 7 ⋅ 6 + 4 mod 9 = 46 mod 9 = 1,
x5 = 7x4 + 4 mod 9 = 7 ⋅ 1 + 4 mod 9 = 11 mod 9 = 2,
49
2. Pseudorandom Numbers
Solution :
x6 = 7x5 + 4 mod 9 = 7 ⋅ 2 + 4 mod 9 = 18 mod 9 = 0,
x7 = 7x6 + 4 mod 9 = 7 ⋅ 0 + 4 mod 9 = 4 mod 9 = 4,
x8 = 7x7 + 4 mod 9 = 7 ⋅ 4 + 4 mod 9 = 32 mod 9 = 5,
x9 = 7x8 + 4 mod 9 = 7 ⋅ 5 + 4 mod 9 = 39 mod 9 = 3.
50
Check Digits
51
Check Digits
Example :
Retail products are identified by their Universal Product Codes (UPCs).
The most common form of a UPC has 12 decimal digits: the first digit
identifies the product category, the next five digits identify the
manufacturer, the following five identify the particular product, and the
last digit is a check digit. The check digit is determined by the
congruence
3x1 + x2 + 3x3 + x4 + 3x5 + x6 + 3x7 + x8 + 3x9 + x10 + 3x11 + x12
≡ 0 (mod 10).
52
Check Digits
Solution:
(a) We insert the digits of 79357343104 into the congruence for UPC
check digits. This gives
3 ⋅ 7 + 9 + 3 ⋅ 3 + 5 + 3 ⋅ 7 + 3 + 3 ⋅ 4 + 3 + 3 ⋅ 1 + 0 + 3 ⋅ 4 + x12
≡ 0(mod 10).
Simplifying, we have
21 + 9 + 9 + 5 + 21 + 3 + 12 + 3 + 3 + 0 + 12 + x12 ≡ 0 (mod 10).
Hence, 98 + x12 ≡ 0 (mod 10).
It follows that x12 ≡ 2 (mod 10),
so the check digit is 2.
(b) To check whether 041331021641 is valid, we insert the digits into the
congruence these digits must satisfy. This gives
3⋅0+4+3⋅1+3+3⋅3+1+3⋅0+2+3⋅1+6+3⋅4+1
≡ 0 + 4 + 3 + 3 + 9 + 1 + 0 + 2 + 3 + 6 + 12 + 1 ≡ 4 ≢ 0 (mod 10).
Hence, 041331021641 is not a valid UPC.
53
Reference
54
Thank You