�Discrete Mathematics (MAD101)

Lecture notes by PhuongVTM

(phuongvtm11@fe.edu.vn/

minhphuong1105.sphn@gmail.com)

​

Chapter 3:

The Integers & Algorithms

• Algorithms
• Growth of Functions
• The integers: division, primes, greatest common divisors
• Integers & Algorithm

​

1.3 The integers: số nguyên

• Definition: Let a, b ∈ℤ be integers, b ≠ 0.
• We write b ∣ a ↔ ∃ q ∈ℤ : a = q.b (↔ a/b is an integer)

Reading: a is divisible by b (a chia hết cho b)

b divides a (b chia a)

b is a factor/ divisor of a (b là nhân tử/ước của a)

a is a multiple of b (a là bội của b)

• if not, then we write b ∤ a (b does not divide a)

Example: a) 4∤ 5 b) 4∣ 8 c) 3∣ (12.n) (n ∈ℤ) d) 3∣ (3n+6) (n ∈ℤ)

Properties: Let a, b, c ∈ℤ, a ≠ 0. Then

1. a∣ b and a∣ c, then a∣ (b+c) and a∣ (b-c)
2. if a∣ b, then a∣ (b.c)
3. if a∣ b and b∣ c, then a∣ c

1.3 The integers: số nguyên

• Division Algorithm

Theorem (Euclid): Let a, d ∈ℤ , d>0. Then there exists unique q, r ∈ℤ such that

​

​

​

Notation: q: quotient (thương), r: remainder (số dư)

Example

1. 123= 6.20 +3
2. -123 = -6.20 -3 , but -3 is not the remainder of the division !

The right division is -123 = -7.20 +7

​

1.3 The integers: số nguyên

• Modular Arithmetic (Số học đồng dư)

Definition: a, b, m ∈ℤ, m >0. Then we say that a is congruent (đồng dư) to b modulo m if

a and b have the same remainder when dividing to m ↔ m∣ (a-b) ↔ a-b = k.m

Notation: a ≡ b (mod m)

Example: True or False ?

-14 ≡ 4 (mod 5) 123 ≢ 13 (mod 5) 15n - 2 ≡ 1 (mod 3) (n∈ℤ)

​

Properties:

1. a ≡ b (mod m) ⇔ ∃ k ∈ℤ : a= b+ k.m
2. If a ≡ b (mod m), then ∀c∈ℤ, a +c ≡ b +c (mod m)
3. If a ≡ b (mod m) and c ≡ d (mod m)

then a +c ≡ b +d (mod m) and ac ≡ bd (mod m)

​

1.3 The integers: số nguyên

• Modular Arithmetic (Số học đồng dư)

Example 1:

1. Find -17 mod 5 and (3⁴ mod 17)² mod 11
2. Let k∈ℤ, find (2k+1)⁴ (mod 4)
3. 8¹ºº ≡ ? (mod 7)
4. 5¹º¹ ≡ ? (mod 3)

​

Example 2:

1. List all integers n between -20 and 20 which are congruent to 1 modulo 7
2. Find all k∈ℤ such that 2k +3 ≡ -1 (mod 5)

1.3 The integers: số nguyên

• Applications of Congruences

Hashing function: Hàm băm

Use: convert large/arbitrary sized data into small integers (memory locations)

H(k)= k mod m

key: k

new key/memory location: k mod m

Example: Consider the set of keys

{100, 420, 78, 2023, 193}

H(k)= k mod 11

Compute the hashes (giá trị băm)

1.3 The integers: số nguyên

• Applications of Congruences

Hashing function: Hàm băm

Collison (xung đột):

k₁ ≠ k₂ different keys but having the same

hash value

Solution:

Use Linear Probing Function (dò tuyến tính)

h(k,i)= h(k)+i (mod m)

where i runs from 1 to m-1

( dùng hàm dò tuyến tính để tìm vị trí “trống"

đầu tiên)

1.3 The integers: số nguyên

• Applications of Congruences

Pseudo-random numbers: Số giả ngẫu nhiên

Goal: tạo ra một dãy số (xₙ) ‘trông' ngẫu nhiên (giả ngẫu nhiên) nhưng thực ra là có quy luật

Formula: Given x₀

xₙ₊₁= axₙ +b (mod m)

• Definition: The distinct ordered numbers generated by this recursive sequence is called pseudo-random numbers

Example:

1. x₀= 2 , xₙ₊₁= 3xₙ +1 (mod 6) , we have the sequence

2, 1, 4, 1, 4, 1, 4, …. —> pseudo- random numbers are 2, 1, 4

• x₀= 2 , xₙ₊₁= 7xₙ +4 (mod 11), we have

2, 7, 9, 5, 6, 2, 7, 9, 5, …—-> pseudo- random numbers are 2, 7, 9, 5, 6

1.3 The integers: số nguyên

• Applications of Congruences

Classical cryptography: Mật mã

Caesar’s Encryption (mã hoá): Let k ∈ ℤ. Use the function

f(p) = p+ k mod 26 (p= 0,1,2…,25) (k: key)

to encrypt a message.

Example: Encrypt: “SEE YOU AT THE COFFEE SHOP” by using the above function with k= 3

1. assign each letter to its order in the alphabet (a number from 0 to 25)

example: A - 0, B - 1, C - 2, ….

so “SEE YOU AT THE COFFEE SHOP” will become

18 4 4 24 14 20 0 19 19 7 4 2 14 5 5 4 4 18 7 14 15

• Use the function f (p) = p+ 3 mod 26 (p= 0,1,2…,25)

21 7 7 1 17 23 3 22 21 10 7 5 17 8 8 7 7 21 10 17 18

• Translating back to words:

“ VHH BRX DW VKH FRIIHH VKRS “

1.3 The integers: số nguyên

• Applications of Congruences

Classical cryptography: Mật mã

Decryption (giải mã): Use the inverse of the encryption function (that was used to encrypt)

f⁻¹ (p) = p - k (mod m) (p=0,1,2…, 25) (k: key)

Example:

1. Decrypt the ciphertext message “MYVVC YT” with key k=5
2. Decrypt the ciphertext message “ M HSRX PMOI QEXLW ” with key k=4

APPENDIX: Alphabetical order:

0-A 1-B 2-C 3-D 4-E 5-F 6-G 7-H 8-I 9-J 10-K 11-L 12-M 13- N 14-O 15-P 16-Q 17-R 18-S 19-T 20-U 21-V 22-W 23-X 24-Y 25-Z

1.3 The integers: số nguyên

• Primes , composite integers (số nguyên tố, hợp số)

Definition:

• An integer p > 1 is a prime if it has only 2 positive factors: 1 and p.
• An integer n >0 which is not prime is called composite integer.

Example:

1. List all primes from 1 to 20 :
2. True or False ?
1. If p > 2 is a prime, then p +1 is a composite number
2. 4²º- 1 is a composite number

Factorization Theorem: If n ∈ ℕ and n >1. Then n can be uniquely factorized as

​

Where, p₁ < p₂ < ….< pₖ are primes; m₁, m₂, …, mₖ ∈ ℕ*

​

1.3 The integers: số nguyên

• Primes , composite integers (số nguyên tố, hợp số)

Example: Find the prime factorization of:

11=

396=

Question: Given n ∈ ℕ, how to check if n is prime or not ?

Theorem: If n ∈ ℕ is a composite integer, then n has a prime divisor less than or equal to

Example: 101 is a prime or not ?

Test: , so if 101 is a composite integer, it has a prime divisor p ≤ 10, which can be : 2, 3, 5, 7.

It is easy to check that 101 are not divisible by 2, 3, 5, 7. So 101 is a prime !

1.3 The integers: số nguyên

• Primes , composite integers (số nguyên tố, hợp số)

Example:

1. Prime or composite number ?
1. 251 B. 123

b) Find the prime factorization of 7007 ?

1.3 The integers: số nguyên

• Primes , composite integers (số nguyên tố, hợp số)

How many primes ?

Theorem: There are infinitely many primes (vô hạn số nguyên tố) !

Sàng Eratosthenes:

Goal: Tìm tất cả các số nguyên tố nhỏ hơn một số cho trước.

Example: List all primes that are not exceeding 50 ?

1.3 The integers: số nguyên

• Primes , composite integers (số nguyên tố, hợp số)

How many primes ?

Theorem: There are infinitely many primes (vô hạn số nguyên tố) !

Sàng Eratosthenes:

Goal: Tìm tất cả các số nguyên tố nhỏ hơn một số cho trước.

Example: List all primes that are not exceeding 50 ?

Idea:

• If n ≤ 50 and n is composite, then n has a prime divisor p ≤
• From 1 to 7, primes are: 2, 3, 5, 7

—---> In the list {1,2, …, 50}, delete all integers that are divisible by 2, 3, 5, 7, we will obtain all primes that are not exceeding 50 !

• All p primes, p ≤ 50 are: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47.

1.3 The integers: số nguyên

• Greatest Common Divisor (GCD), Least Common Multiple (LCM)

Definition:

1. a, b ∈ ℤ (not both zero). The greatest common divisor of a and b is the largest integer d ∈ℤ such that d | a and d | b.

Notation: gcd(a,b)

• a, b ∈ ℤ, a, b >0. The least common multiple of a and b is the smallest positive integer m>0 such that a | m and b | m.

Notation: lcd(a,b)

Example: Find

1. gcd(5,14) and lcm(5,14)
2. gcd(18, 24) and lcm(18,24)

1.3 The integers: số nguyên

• Greatest Common Divisor (GCD), Least Common Multiple (LCM)

How to find gcd(a,b) ?

First way: Use Euclid algorithm

Lemma: If a= q.b +r, then gcd(a,b)= gcd(b,r)

Now, suppose a ≥ b > 0, we successively apply the division algorithm: Put r₀=a, r₁=b

​

​

​

​

​

​

​

Then : gcd(a,b)= gcd(r₀, r₁ )= gcd (r₁, r₂) =.... = gcd( rₙ, 0)= rₙ !

1.3 The integers: số nguyên

• Greatest Common Divisor (GCD), Least Common Multiple (LCM)

How to find gcd(a,b) ?

First way: Use Euclid algorithm

​

1.3 The integers: số nguyên

• Greatest Common Divisor (GCD), Least Common Multiple (LCM)

How to find gcd(a,b) ?

Example: Use Euclid algorithm to find gcd(252, 198)

1.3 The integers: số nguyên

• Greatest Common Divisor (GCD), Least Common Multiple (LCM)

How to find gcd(a,b), lcm(a,b) ?

Second way: Use prime factorizations of a and b

Suppose:

​

Then

​

(nhân tử chung với số mũ nhỏ nhất )

and

​

(nhân tử chung và riêng với số mũ lớn nhất)

​

1.3 The integers: số nguyên

• Greatest Common Divisor (GCD), Least Common Multiple (LCM)

How to find gcd(a,b), lcm(a,b) ?

Second way: Use prime factorizations of a and b

Example:

1. What is gcd and lcm of

b) Use prime factorization to find gcd(120, 500) and lcm(120,500)

c) What is the relation between gcd(120,500) and lcm(120,500) ?

​

1.3 The integers: số nguyên

• Greatest Common Divisor (GCD), Least Common Multiple (LCM)

Theorem: Let a, b>0 be positive integers. Then

gcd(a,b) . lcm(a,b)= a.b

—---> lcm(a,b)= (a.b) / gcd(a,b)

Definition: (số nguyên tố cùng nhau)

1. a, b ∈ ℤ, we say that a and b are relatively prime if gcd(a,b)= 1.

Notation: (a,b)= 1

• a₁, a₂…, aₙ ∈ ℤ are relatively prime if gcd(aₖ, aⱼ)= 1, for all k, j.

Example:

1. True or False ?
1. (21, 35)= 1 B. (p, q)= 1 (p, q primes, p ≠q) C. (n, n+1)= 1 (∀n ∈ ℤ)
2. Find all integers between -20 to 10 that are relatively prime with 6

1.4 Integers and Algorithms

• Representation of integers

Definition: (base b expansion)

Let b, n ∈ ℕ, b>1. Every n>0 can be written uniquely as

​

​

Where k ∈ ℕ ; 0 ≤ a₀, a₁, …, aₖ < b and aₖ ≠ 0.

Notation: (a₀a₁ … aₖ)_b : the base b expansion of n (initially in base 10)

Example: Convert into decimal expansion

1. (11001)₂= 25 (binary expansion)
2. (7016)₈ = 3598 (octal expansion)
3. (2AE0B)₁₆ (hexadecimal expansion)= 175 627

1.4 Integers and Algorithms

• Representation of integers

Base conversion: (b, n ∈ ℕ*, b >1 )

Example:

1. Find the octal expansion of (12345)₁₀ , (011 111 010 111 100)₂= (37274)_8
2. Find the binary expansion of (A8D)₁₆= (1010 1000 1101)_2 , (765)₈=
3. Find the hexadecimal expansion of (0011 1110 1011 1100)₂ =(?)_16,

(765)₈= ()_4

1.4 Integers and Algorithms

• Representation of integers

Base conversion: (b, n ∈ ℕ*, b >1 )

1.4 Integers and Algorithms

• Algorithms for Integer Operations

Addition:

Example: Add (101 001)₂ + (110 101)₂

1.4 Integers and Algorithms

• Algorithms for Integer Operations

Addition:

Procedure add( a= (aₙ₋₁aₙ₋₂…a₀)₂,b= (bₙ₋₁bₙ₋₂…b₀)₂ )

c:= 0

for j=0 to n-1

d:= ⌊(aⱼ+bⱼ+c) / 2⌋ // next carry of the next step

sⱼ:= aⱼ+bⱼ+c-2d // result bit

c:= d // update new carry to the next step

s=c // rightmost bit of the result

return (s₀sₙ₋₁sₙ₋…s₀) // the binary expansion of the sum is (ssₙ₋₁…s₀)₂

​

Question: Estimate the Big-O of the number of additions of bits required in the algorithm ?

1.4 Integers and Algorithms

• Algorithms for Integer Operations

Multiplication:

Example: Compute the product of (1010)₂ and (1100)₂

1.4 Integers and Algorithms

• Algorithms for Integer Operations

Multiplication:

Procedure multiply( a= (a₋₁a₋₂…a₀)₂,b= (b₋₁b₋₂…b₀)₂ )

for j:=0 to n-1

if bⱼ=1 then cⱼ:= a shifted j place

else cⱼ:= 0 // c₀, c₁,...,c₋₁ are partial products

p:= 0

for j:=0 to n-1

p:=p+ cⱼ

return p // p is the value of a.b

Question: Estimate the Big-O of the number of additions of bits and shifts of bits required in the algorithm?

1.4 Integers and Algorithms

• Algorithms for Integer Operations

Question: Estimate the Big-O of the number of additions of bits and shifts of bits required in the algorithm?

​

1.4 Integers and Algorithms

• Algorithms for Integer Operations

Question: Estimate the Big-O of the number of additions of bits and shifts of bits required in the algorithm?

Answer: O(n²)

1.4 Integers and Algorithms

• Algorithms for Integer Operations

Computing div and mod :

procedure division ( a: integer; d: positive integer)

q:=0

r:= |a|

while r ≥ d {quotient= number of times of successive subtractions}

begin

r:= r-d

q := q+1

end

If a<0 and r>0 then {updating remainder when a<0}

begin

r:= d-r

q := -(q+1)

end

{ q = a div d is the quotient, r=a mod d is the remainder}

1.4 Integers and Algorithms

• Algorithms for Integer Operations

Modular Exponentiation

• Use: to compute bⁿ (mod m)
• Idea: convert n to binary base : n= (aₖ₋₁…a₁a₀)₂ :

​

then compute each term (mod m) in the product by successively compute

b mod m ; b² mod m, (b²)² mod m ; ((b²)²)² mod m ,...

1.4 Integers and Algorithms

• Algorithms for Integer Operations
• Algorithm:

Procedure mod_ex ( b: integer, n=(a_k-1a_k-2…a₁a₀)₂, m: positive integer)

x:=1

power := b mod m

for i:=0 to k-1

begin

if a_i=1 then x:= (x.power) mod m

power := (power.power) mod m

end

{ x equals bⁿ mod m }

1.4 Integers and Algorithms

• Algorithms for Integer Operations

Modular Exponentiation

For example:

​

So, to compute 3¹³ mod 7, we compute

3⁰ mod 7= 1 ; 3² mod 7 = 2 ; mod 7= 2² (mod 7) = 4 ;

mod 7= 4² mod 7= 2

So 3¹³ mod 7= 1. 4. 2 (mod 7)= 1.

Here, since a₁=0, 3² mod 7 (=2) does not counted into the remainder (but still needed to compute mod 7 !

1.4 Integers and Algorithms

• Algorithms for Integer Operations

Modular Exponentiation

• Example: compute 240²⁶² (mod 14).

First, convert 262 to binary base:

262= (1 0000 0110)₂

Second: set x:=1, p:= 240 mod 14= 2

Next, compute step by step by successively taking square of p (mod 14) and x= x.p (mod 14) whenever aⱼ=1 :

​

​

​

​

So: 240²⁶² (mod 14)= 2

1.4 Integers and Algorithms

• Algorithms for Integer Operations

Modular Exponentiation

• Exercise: Using modular exponentiation to compute 150⁴⁶⁰ (mod 17)

1.4 Integers and Algorithms

• Algorithms for Integer Operations

Euclidean Algorithm

procedure gcd(a, b) { a,b: positive integers}

x:=a

y:=b

while y ≠ 0

begin

r := x mod y

x:=y

y:= r

end {gcd(a,b) is x}

PROGRAMMING PROJECT

​

PROGRAMMING PROJECT

​

PROGRAMMING PROJECT

​

Write two different algorithms to compute bⁿ (mod m), then compare their complexity.

​