Discrete Mathematics

Chapter 3 �The Fundamentals : Algorithms, �the Integers, and Matrices

大葉大學 資訊工程系 黃鈴玲(Lingling Huang)

3.1 Algorithms

Def 1. An algorithm is a finite sequence of precise instructions for performing a computation or for solving a problem.

• Example 1. Describe an algorithm for finding the maximum value in a finite sequence of integers.(假設給定的sequence是a₁,a₂,…,a_n)

Ch3-2

Solution : ( English language)

1. Set the temporary maximum equal to the first integer in the sequence.
2. Compare the next integer in the sequence to the temporary maximum, and if it is larger than the temporary maximum, set the temporary maximum equal to this integer.
3. Repeat the previous step if there are more integers in the sequence.
4. Stop when there are no integers left in the sequence. The temporary maximum at this point is the largest integer in the sequence.

Ch3-3

Solution : (pseudo-code)

Ch3-4

Algorithm 1. Finding the Maximum Element

​

procedure max(a₁, a₂, …, a_n : integers)

max := a₁

for i := 2 to n

if max < a_i then max := a_i

{ max is the largest element}

※ There are several properties that algorithms generally share :

• Input
• Output
• Definiteness : The steps of an algorithm must be defined precisely.
• Correctness : produce correct output values
• Finiteness : produce the desired output after a finite

number of step.

• Effectiveness
• Generality : The procedure should be applicable for all

problems of the desired form, not just for a

particular set of input values.

Ch3-5

※ Searching Algorithms

Ch3-6

Problem : Locate an element x in a list of distinct elements

a₁,a₂,…,a_n, or determine that it is not in the list.

做法 : linear search, binary search.

Algorithm 2. The linear search algorithm

​

procedure linear_search( x : integer, a₁,a₂,…,a_n: distinct integers)

i := 1

While ( i ≤ n and x≠a_i )

i := i + 1

if i ≤ n then location := i

else location := 0

{ location = j if x = a_j; location = 0 if x≠a_i, ∀i }

• 兩種search方式的概念 :

​

Linear Search : 從 a₁ 開始，逐一比對 x 是否等於 a_i，若找到則 location = i , 若到 a_n 比完後還找不到，則 location = 0。

​

Binary Search : (必須具備 a₁ < a₂ < … < a_n 的性質才能用)�(1) 每次將 list 切成兩半，( a_i , … , a_m )，(a_m+1 , … , a_j ) � 若 x > a_m 表示 x 應在右半，否則在左半。 �(2) 重覆上一步驟至 list 只剩一個元素 a_i，

若 x = a_i 則 location = i，否則 location = 0。

​

Ch3-7

Example 3. Search 19 from

a₁ a₂ a₃ a₄ a₅ a₆ a₇ a₈ a₉ a₁₀ a₁₁ a₁₂ a₁₃ a₁₄ a₁₅ a₁₆

1 2 3 5 6 7 8 10 12 13 15 16 18 19 20 22

12 13 15 16 18 19 20 22

18 19 20 22

18 19

19

Ch3-8

1. ( 切兩半 )

( 因 19 > 10，取右半 )

2. ( 再切二半 )

( 因 19 > 16，取右半 )

3. ( 再切二半 )

( 因 19 ≦19，取左半 )

4. ( 再切二半 )

( 因 19 > 18，取右半 )

5 此時只剩一個元素 a₁₄ = 19

因 19 = 19，故 location =14

Ch3-9

Algorithm 3. The Binary Search Algorithm

​

procedure binary_search( x : integer, a₁,a₂,…,a_n : increasing integers)

i :=1 { i is left endpoint of search interval }

j := n { j is right endpoint of search interval }

while i < j

begin

m :=

if x > a_m then i := m+1

else j := m

end

if x = a_i then location := i

else location := 0

{ location = i if x = a_i , location = 0 if x≠a_i , ∀i }

※ Sorting Algorithms

• Problem : Suppose that we have a list of elements, a sorting is putting these elements into a list in which the elements are in increasing order.
• eg. 7, 2, 1, 4, 5, 9 => 1, 2, 4, 5, 7, 9

d, t, c, a, f => a, c, d, f, t

• 解法有很多，此處僅介紹 : bubble sort (氣泡排序法)，及 insertion sort (插入排序法)。
• Bubble Sort 概念 : 設原 list 為 a₁,…,a_n。
• 從a₁,a₂開始，向後兩兩比較，若a_i > a_i+1 則交換，當檢查完 a_n 時，a_n 必定是最大數。
• 再從 a₁,a₂ 開始向後比較，若a_i > a_i+1 則交換，此時只需檢查到 a_n-1 即可。
• 依此類推。

Ch3-10

• Example 4. Use the bubble sort to put 3, 2, 4, 1, 5 into increasing order.
• Sol :

Ch3-11

3

2

4

1

5

First pass (i=1) :

2

3

4

1

5

2

3

4

1

5

2

3

1

4

5

Second pass (i=2) :

Third pass (i=3) :

Fourth pass (i=4) :

1

2

3

4

5

Ch3-12

Algorithm 4 The Bubble Sort� procedure bubble_sort (a₁,…,a_n )

for i := 1 to n−1

for j := 1 to n−i

if a_j > a_j+1 then interchange a_j and a_j+1

{ a₁,a₂,…,a_n is in increasing order }

• Insertion Sort 的概念 :
• 從 j = 2 開始，將 a_j 插入已排序好的 a₁,…,a_j−1間的位置，使得 a₁,…,a_j 都由小 → 大排好。
• j 逐次遞增，重複上一步驟至做完。

Ch3-13

• Example 5. Use insertion sort to sort 3, 2, 4, 1, 5
• Sol :
• (j=2時，a₁=3可看成已經排序好的數列，此時要插入a₂) :

3 < 2 ⇒ 2, 3 交換 ⇒ 2, 3, 4, 1, 5

• (j=3時，a₁,a₂已經排序好，此時要插入a₃) :

4 > 2, 4 > 3 ⇒ 4的位置不變 ⇒ 2, 3, 4, 1, 5

• (j=4時，a₁,a₂ ,a₃已經排序好，此時要插入a₄) :

1 < 2 ⇒ 將 1 插在最前面 ⇒ 1, 2, 3, 4, 5

• (j=5時，a₁,a₂ ,a₃ ,a₄已經排序好，此時要插入a₅) :

5 > 1, 5 > 2, 5 > 3, 5 > 4 ⇒ 5不變 ⇒ 1, 2, 3, 4, 5

Ch3-14

a₁ a₂ a₃ a₄ a₅

Ch3-15

Algorithm 5 The Insertion Sort �procedure insertion_sort ( a₁,…,a_n : real numbers with n ≥ 2 )

for j := 2 to n

begin

i := 1 � while a_j > a_i

i := i + 1

m := a_j

for k := 0 to j – i – 1

a_j−k := a_j−k−1

a_i := m

end

{ a₁,a₂,…,a_n are sorted }

( Exercise : 3, 9, 13, 23, 35, 39 )

找出 a_j 應插入的位置�最後a_i−1 < a_j <= a_i

將 a_i, a_i+1, …, a_j−1�全部往右移一格

3.2 The Growth of Functions

• To analyze the practicality of the program, we need to understand how quickly the function (number of operations used by this algorithm) grows as n (number of input elements) grows.
• eg. sort n objects
• Alg. 1 : n²次計算
• Alg. 2 : 8n次計算

Ch3-16

better!

Def 1. ( Big-O notation )

Let f and g be functions from the set of integers to the set of real numbers. We say that f (x) is O(g(x)) if there are constants C and k such that

| f (x) | ≤ C | g(x) |

whenever x > k . ( read as “f (x) is big-oh of g(x)” )

Ch3-17

Example 1. Show that f (x) = x²+2x+1 is O(x²)

Sol : Since

x²+2x+1 ≤ x²+2x²+x² = 4x²

whenever x > 1 , it follows that f (x) is O(x²)

(take C = 4 and k =1 )

另法：

If x > 2, we see that

x²+2x+1 ≤ x²+x²+x² = 3x²

( take C = 3 and k = 2 )

​

Ch3-18

Figure 2. The function f (x) is O(g(x))

​

​

​

​

​

​

Example 1(補充). Show that f (n)= n ²+2n +2 is O(n³)

Sol : Since

n²+2n+2 ≤ n³+n³+n³ = 3n³

whenever n > 1, we see that f (n) is O(n³) � ( take C = 3 and k = 1 )

Ch3-19

Note. The function g is chosen to be as small as possible.

Example 5. How can big-O notation be used to estimate the sum of the first n positive integers?

( i.e., )

​

Sol :

1 + 2 + 3 + … + n ≤ n + n + … + n = n²

∴ is O(n²), taking C =1 and k =1.

Ch3-20

Theorem 1.� Let f (x) = a_nxⁿ+a_n−1xⁿ⁻¹+…+a₁x+a₀

where a₀, a₁, …, a_n are real numbers.

Then f (x) is O(xⁿ).

Example 6. Give big-O estimates for f (n) = n!

Sol :

n! = 1⋅2 ⋅ 3 ⋅ … ⋅ n ≤ n ⋅ n ⋅ … ⋅ n = nⁿ

∴ n! is O(nⁿ) , taking C =1 and k =1.

Ch3-21

Theorem 2,3 Suppose that f₁(x) is O(g₁(x)) and f₂(x) is O(g₂(x)), then � (f₁+f₂)(x) is O(max(|g₁(x)|, |g₂(x)|)),

(f₁ f₂)(x) is O(g₁(x) g₂(x)).

Example 7. (see Figure 3) �常見function的成長速度由小至大排列：� 1 < log n < n < n log n < n² < 2ⁿ < n!

​

Exercise 7,11,19

​

Exercise 19(c) : f (n) = (n!+2ⁿ)(n³+log(n²+1))

≤ (n!+n!)(n³+n³)

= 4n³⋅n!

∴ f (n) is O(n³⋅n!) 取 C = 4, k = 3

Ch3-22

3.3 Complexity of Algorithms

Q : How can the efficiency of an algorithm be

analyzed ?

Ans : (1) time (2) memory

Def :

• Time complexity : an analysis of the time required to solve a problem of a particular size.

(評量方式 : 計算 # of operations，如 “comparison”次數，�“加法” 或 “乘法” 次數等)

• Space complexity : an analysis of the computer memory required to solve a problem of a particular size. (通常是資料結構探討的範圍)

Ch3-23

Example 1. Describe the time complexity of Algorithm 1.

Ch3-24

Algorithm 1. ( Find Max )

procedure max(a₁,…,a_n : integers)

max := a₁

for i := 2 to n

if max < a_i then max := a_i

​

{ max is the largest element }

Sol : (計算 # of comparisons)

�i 值一開始 = 2

逐次加一，並比較是否>n.

當 i 變成 n+1 時

因比 n 大，故結束 for 迴圈。

∴ 共有 n 次 comparison

​

共有 n−1 次 comparison

​

故整個演算法共做 2n−1 次

comparison

其 time complexity 為 O(n).

Example 2. Describe the time complexity of the linear search algorithm.

Ch3-25

Sol : ( 計算 # of comparisons )

(Case 1) 當 x = a_i for some i ≤ n 時

此行只執行 i 次，故此行共2i次比較

加上if，共計 2i +1次 comparisons.

(Case 2) 當 x ≠ a_i for all i 時

此行執行 n 次後

第 n + 1 次時 i = n + 1 > n 即跳出

∴共計 2n+2 次 comparisons

由(1)、(2)取 worst-case � 演算法的 time complexity為 O(n)

Example 4. Describe the average-case performance of the linear search algorithm, assuming that x is in the list.

Ch3-26

Sol : ( 計算 “平均比較次數” )�

已知當 x = a_i 時，共需 2i + 1 次比較.

( by Example 2 )

x = a₁,a₂, …, 或 a_n 的機率都是 1/n.

∴平均比較次數 (即期望值)

= ( x = a₁ 的比較次數 ) × ( x = a₁ 的機率 )

+ ( x = a₂ 的比較次數 ) × ( x = a₂ 的機率 )

+ …

+ ( x = a_n 的比較次數 ) × ( x = a_n 的機率 )

= 3 × 1/n + 5 × 1/n + … + ( 2n+1) × 1/n

= ( 3+5+…+(2n+1)) / n

​

= / n = n + 2

​

∴average-case的time complexity為O(n)

Alg. 2 ( Linear Search )

procedure ls ( x,a₁,…,a_n)

i := 1

While ( i ≤ n and x ≠a_i )

i := i +1

if i ≤ n then location := i

else location := 0

Example 3. Describe the time complexity of the binary search algorithm.

Ch3-27

Sol : 設 n = 2^k 以簡化計算

(若 n < 2^k，其比較次數必小於等 � 於 n = 2^k 的情況)

因while迴圈每次執行後

整個 list 會切成兩半

故最多只能切 k 次

就會因 i = j 而跳出迴圈

∴共比較 2k+2 次

�time complexity 為 �O(k) = O(log n)

Example 5. What is the worst-case complexity of the bubble sort in terms of the number of comparisons made ?

Ch3-28

procedure bubble_sort ( a₁,…,a_n )

for i := 1 to n −1

for j := 1 to n – i

if a_j > a_j+1 then � interchange a_j and a_i+1

{ a₁,…,a_n is in increasing order }

Sol : 共 n−1 個 pass

第 i 個 pass 需 n – i 次比較

∴共計

(n−1)+(n−2)+…+1

= 次比較

∴ O(n²)

​

Note 1. 不管何種 case 都需做 次比較。

​

Note 2. For 迴圈所需比較次數通常會省略，因此Example 5,6 不再考慮。

• Example 6. What is the worst-case complexity of the insertion sort in terms of the number of comparisons made ?

​

Ch3-29

procedure insertion_sort ( a₁,…,a_n )

for j := 2 to n

begin

i := 1

while a_j > a_i

i := i +1

m := a_j

for k := 0 to j − i −1

a_j−k := a_j−k−1

a_i := m

end

{ a₁,…,a_n are sorted }

Sol :

做最多次比較的情況如下：

在考慮 a_j 時

a₁ < a₂ < … < a_j−1 < a_j

此時共做 j 次比較

​

故共計

2+3+…+n = −1 次比較

​

⇒ O(n²)

(即 worst case 是 a₁ < a₂ < … < a_n)

Table 1. Commonly Used Terminology

​

Ch3-30

Exercise : 7,8,13

3.4 The integers and division

※探討一些 Number Theory 的基本觀念

Def 1. a,b : integers, a≠0.

a divides b (denote a | b) if ∃c∈Z , b=ac .� (a : a factor of b, b : a multiple of a)� (a b if a does not divide b)

Corollary 1. If a,b,c ∈Z and a | b , a | c.

then a | mb+nc whenever m,n∈Z

Def 2. In the quality a = dq + r with 0 ≤ r < d, d is called the divisor (除數), a is called the dividend (被除數), �q is called the quotient (商數), and r is called the remainder (餘數).�⇒ q = a div d, r = a mod d

Ch3-31

Def 3. If a,b∈Z, m∈Z⁺, then

a is congruent (同餘) to b modulo m if m | (a−b).

(denote a≡b (mod m)).

Thm 4. Let m∈Z⁺, a,b∈Z.

a≡b (mod m) iff ∃k∈Z, s.t. a=b+km.

Thm 5. Let m∈Z⁺, a,b∈Z.

If a≡b (mod m) and c≡d (mod m),� then a+c≡b+d (mod m) and ac≡bd (mod m).

​

Ch3-32

3.5 Primes and Greatest Common Divisors

Def 1. p∈Z⁺ −{1} is called prime (質數) ^� if a p, ∀1<a< p, a∈Z⁺. �p is called composite (合成數) otherwise.

Thm 1. (The fundamental theorem of arithmetic)

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.

Example 2.

The prime factorization (因數分解) of 100 is 2²5².

Ch3-33

Thm 3. There are infinitely many primes.�Pf. 假設質數只有n個：p₁, p₂, …, 及 p_n，� 令Q = p₁p₂…p_n+1, 因 p₁, …, p_n 都不整除Q，得證。

※目前為止所知最大的質數是2^p −1的形式, where p is prime. 稱為 Mersenne primes (梅森質數).

Example 5. 2²−1=3, 2³−1=7, 2⁵−1=31 are primes,� but 2¹¹−1=2047=23×89 is not a prime.

Def 2. gcd ( greatest common divisor )

Def 3. relatively prime (互質)

Def 5. lcm ( least common multiple )

Ch3-34

Exercise 14. How many zeros are there at the end of 100! ?

Sol : 計算1×2 × 3 × … × 100=10^k × m, where 10 m

∵ 10=2 × 5，又2的次數必定比5多

∴ 計算1 × 2 × 3 × … × 100=5^k × n, where 5 n

∵ 5,10,15,20,…,100才有因數5,� 而25,50,75,100有因數25

∴ k=24 ⇒ 共有24個0

Ch3-35

Homework : 試寫一alg.

求出 ≤ n 的所有質數

3.6 Integers and Algorithms

※The Euclidean Algorithm (輾轉相除法求 gcd )

Example : Find gcd(91,287)

Sol:

287 = 91 ⋅ 3 + 14�

91 = 14 ⋅ 6 + 7

14 = 7 ⋅ 2

∴ gcd(91,287) = 7

Lemma 1 Let a = bq + r, where a, b, q, and r ∈Z.�Then gcd(a, b) = gcd (b, r).

Ch3-36

if x|91 & x|287 ⇒ x|14

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

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

gcd (14,7) = 7

Ch3-37

Algorithm 6. ( The Euclidean Algorithm)

procedure gcd ( a, b : positive integers)

x := a

y := b

while y≠0

begin

r := x mod y ( if y > x then r = x)

x := y

y := r

end

{ gcd (a, b) = x }

eg. 求 gcd (6,12)

​

x = 6

y = 12

while y≠0

r = 6 mod 12 =6

x = 12

y = 6

while y≠0

r = 12 mod 6 = 0

x = 6

y = 0

while y = 0 , end.

∴ gcd (6,12) = 6

Exercise : 23,25

3.7 Applications of Number Theory

Ch3-38

Theorem 1.

If a and b are positive integers, then there exist integers s and t such that gcd(a,b) = sa+tb.

gcd(a,b) can be expressed as a linear combination �with integer coefficients of a and b.

※將gcd(a,b) 寫成a 跟 b的線性組合： �The extended Euclidean Algorithm

Ch3-39

Example 1 Express gcd(252, 198) =18 as a linear combination of 252 and 198.

Sol:

252 = 1 ⋅ 198 + 54

198 = 3 ⋅ 54 + 36

54 = 1 ⋅ 36 + 18

36 = 2 ⋅ 18

∴ gcd(252, 198) = 18 �

18 = 54 – 1 ⋅ 36

36 =198 – 3 ⋅ 54

54 =252 – 1 ⋅ 198

18 = 54 – 1 ⋅ 36

⇒

= 54 – 1 ⋅ (198 – 3 ⋅ 54 )

= 4 ⋅ 54 – 1 ⋅ 198

= 4 ⋅ (252 – 1 ⋅ 198) – 1 ⋅ 198

= 4 ⋅ 252 – 5 ⋅ 198

Exercise : 1(g)

Ch3-40

Lemma 1.

If a, b and c are positive integers such that gcd(a,b) = 1 and a | bc, then a | c.

Lemma 2.

If p is a prime and p | a₁a₂…a_n, where each a_i is an integer, then p | a_i for some i.

Q: 何時可以讓 ≡ 的左右同除以一數後還成立呢？

另, 14 ≡ 8 (mod 3), 同除以2後, 7 ≡ 4 (mod 3)成立

Ch3-41

Theorem 2.

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).

※ Linear Congruences

A congruence (同餘式) of the form ax ≡ b (mod m), where�m is a positive integer, a and b are integers, and x is a �variable, is called a linear congruence.

How can we solve the linear congruence ax ≡ b (mod m)?

Ch3-42

Theorem 3.

If a and m are relatively prime integers and m>1, then an inverse of a modulo m exists. �Furthermore, this inverse is unique modulo m.

Proof. (existence) (unique的部分是exercise)

By Thm 1, because gcd(a, m) = 1, �there exist integers s and t such that sa + tm =1.

⇒ sa + tm ≡ 1 (mod m).

Because tm ≡ 0 (mod m),

sa ≡ 1 (mod m),

⇒ s is an inverse of a modulo m.

Ch3-43

Example 3 Find an inverse of 3 modulo 7.

Sol. � Because gcd(3, 7) = 1, find s, t such that 3s + 7t =1.

⇒ −2 is an inverse of 3 modulo 7.

⇒ 7 = 2 ⋅ 3 + 1

⇒ 1 = −2 ⋅ 3 + 1 ⋅ 7

(Note that every integer congruent to −2 modulo 7

is also an inverse of 3, such as 5, −9, 12, and so on. )

Exercise : 5

Ch3-44

Example 4 What are the solutions of the linear �congruence 3x ≡ 4 (mod 7)?

Sol. � By Example 3 ⇒ −2 is an inverse of 3 modulo 7

⇒ If x is a solution, then x ≡ −8 ≡ 6 (mod 7).

⇒ −2 ⋅ 3x ≡ −2 ⋅ 4 (mod 7)

Because −6 ≡ 1 (mod 7), and −8 ≡ 6 (mod 7),

We need to determine whether every x with x ≡ 6 (mod 7)�is a solution. Assume x ≡ 6 (mod 7), then� 3x ≡ 3 ⋅ 6 = 18 ≡ 4 (mod 7).

Therefore every such x is a solution: � x = 6, 13, 20, …, and −1, −8, −15, ….

Exercise : 11

將 3x ≡ 4 (mod 7) 左右同乘 −2

⇒ −6x ≡ −8 (mod 7)

⇒ 3 ⋅ (−2) ≡ 1 (mod 7)

Example 5. 孫子算經 :「某物不知其數，三三數之餘二，五五數之餘三，七七數之餘二，問物幾何 ?」 (又稱為「韓信點兵」問題)

i.e. x ≡ 2 (mod 3)

x ≡ 3 (mod 5) x = ?

x ≡ 2 (mod 7)

Ch3-45

Theorem 4. (The Chinese Remainder Theorem)

Let m₁,m₂,…,m_n be pairwise relatively prime positive integers �and a₁, a₂, …, a_n arbitrary integers. Then the system

x ≡ a₁ (mod m₁)�x ≡ a₂ (mod m₂)

:�x ≡ a_n (mod m_n)

has a unique solution modulo m = m₁m₂…m_n.�(即有一解 x, where 0≤ x < m , 且所有其他解 mod m都等於 x)

The Chinese Remainder Theorem (中國餘數定理)

Proof of Thm 4:

Let M_k = m / m_k ∀ 1≤ k ≤ n

∵ m₁, m₂,…, m_n are pairwise relatively prime

∴ gcd (M_k , m_k) = 1

⇒ ∃ integer y_k s.t. M_k y_k ≡ 1 (mod m_k)

( by Thm. 3)

⇒ a_k M_k y_k ≡ a_k (mod m_k) , ∀ 1 ≤ k ≤ n

Let x = a₁ M₁ y₁+a₂ M₂ y₂+…+a_n M_n y_n

∵ m_i | M_j , ∀i ≠ j

∴ x ≡ a_k M_k y_k ≡ a_k (mod m_k) ∀ 1≤ k ≤ n

x is a solution.

All other solution y satisfies y ≡ x (mod m_k).

Ch3-46

x ≡ a₁ (mod m₁)�x ≡ a₂ (mod m₂)

:�x ≡ a_n (mod m_n)

m = m₁m₂…m_n

Example 6. (Solve the system in Example 5)

Let m = m₁m₂m₃ = 3⋅5⋅7 = 105

M₁ = m / m₁ = 105 / 3 = 35 (也就是m₂m₃)

M₂ = m / m₂ = 105 / 5 = 21

M₃ = m / m₃ = 105 / 7 = 15

​

​

35 ≡ 2 (mod 3) ⇒ 35 × 2 ≡ 2 × 2 ≡ 1 (mod 3)

​

21 ≡ 1 (mod 5) ⇒ 21 × 1 ≡ 1 (mod 5)

​

15 ≡ 1 (mod 7) ⇒ 15 × 1 ≡ 1 (mod 7)

​

∴ x = a₁M₁y₁ + a₂M₂y₂ + a₃M₃y₃

= 2 × 35 × 2 + 3 × 21 × 1 + 2 × 15 × 1 = 233 ≡ 23 (mod 105)

∴ 最小的解為23，其餘解都等於 23+105t for some t∈Z⁺

Ch3-47

M₁

y₁

x ≡ 2 (mod 3)

x ≡ 3 (mod 5) x = ?

x ≡ 2 (mod 7)

找 y₁ 使得M₁y₁ = 1 (mod 3)

Exercise 18. Find all solutions to the system of congruences x ≡ 2 (mod 3)

x ≡ 1 (mod 4)

x ≡ 3 (mod 5)

Sol :

a₁=2 , a₂=1 , a₃=3,

m₁=3 , m₂=4 , m₃=5 m=3×4×5=60

M₁=20 , M₂=15 , M₃=12

20≡2 (mod 3) ⇒ 20×2≡1 (mod 3)

15≡3 (mod 4) ⇒ 15×3≡1 (mod 4)

12≡2 (mod 5) ⇒ 12×3≡1 (mod 5)

∴ x = 2×20×2+1×15×3+3×12×3

= 80+45+108=233≡53 (mod 60)

Ch3-48

Ch3-49

※ 補充：(when m_i is not prime)

Ex 20. Find all solutions, if any, to the system of �congruences.

x≡5 (mod 6)

x≡3 (mod 10)

x≡8 (mod 15)

Sol. Rewrite the system as the following:

x ≡ 1 (mod 2)

x≡2 (mod 3)

i.e.,

x≡1 (mod 2)

x≡2 (mod 3) …

x≡3 (mod 5)

Exercise : 做完此題

x ≡ 1 (mod 2)

x ≡ 2 (mod 3)

x≡3 (mod 5)

x≡3 (mod 5)

Ch3-50

※ 補充：(when m_i is a prime power)

Ex 21. Find all solutions, if any, to the system of �congruences.

x≡7 (mod 9)

x≡4 (mod 12)

x≡16 (mod 21)

Sol. Rewrite the system as the following:

x≡7 (mod 9) (不能拆！)

�x≡0 (mod 4)

i.e.,

x≡7 (mod 9) (此式取代 x≡1 (mod 3) 式子)

x≡0 (mod 4) …

x≡2 (mod 7)

x≡1 (mod 3)

x≡1 (mod 3)

x≡2 (mod 7)

Ch3-51

Computer Arithmetic with Large Integers

Suppose that m₁,m₂,…,m_n be pairwise relatively prime integers �greater than or equal to 2 and let m = m₁m₂ …m_n.�By the Chinese Remainder Theorem, we can show that an �integer a with 0 ≤ a < m can be uniquely represented by the�n-tuple (a mod m₁, a mod m₂, …, a mod m_n).

Example 7 What are the pairs used to represent the nonnegative�integers x<12 when they are represented by the order pair�(x mod 3, x mod 4)?

Sol � 0=(0, 0), 1=(1, 1), 2=(2, 2), 3=(0, 3), 4=(1, 0), 5=(2, 1),

6=(0, 2), 7=(1, 3), 8=(2, 0), 9=(0, 1), 10=(1, 2), 11=(2, 3).

Exercise : 37

Ch3-52

To perform arithmetic with larger integers, we select�moduli (modulus的複數) m₁,m₂,…,m_n, where�each m_i is an integer greater than 2, �gcd(m_i, m_j)=1 whenever i ≠ j, and �m=m₁m₂…m_n is greater than the result of �the arithmetic operations we want to carry out.

Ch3-53

Example 8 Suppose that performing arithmetic with integers �less than 100 on a certain processor is much quicker than doing �arithmetic with larger integers. We can restrict almost all our �computations to integers less than 100 if we represent integers�using their remainders modulo pairwise relatively prime integers �less than 100.

For example, 99, 98, 97, and 95 are pairwise relatively prime.�every nonnegative integer less than 99×98×97×95 = 89403930�can be represented uniquely by its remainders when divided by�these four moduli.

E.g., 123684 = (33, 8, 9, 89), and 413456 = (32, 92, 42, 16)

123684 + 413456 = (33, 8, 9, 89) + (32, 92, 42, 16)� = (65 mod 99, 100 mod 98, 51 mod 97, 105 mod 95) � = (65, 2, 51, 10)

Use Chinese Remainder Thm to find this sum ⇒ 537140.

Ch3-54

Theorem 5 (Fermat’s Little Theorem)

If p is prime and a is an integer not divisible by p, then� a ^p−1 ≡ 1 (mod p)

Furthermore, for every integer a we have� a ^p ≡ a (mod p)

Exercise 27(a) Show that 2³⁴⁰ ≡ 1 (mod 11) �by Fermat’s Little Theorem and noting that 2³⁴⁰ = (2¹⁰)³⁴.

Proof 11 is prime and 2 is an integer not divisible by 11.

⇒ 2¹⁰ ≡ 1 (mod 11)

⇒ 2³⁴⁰ ≡ 1 (mod 11) by Thm 5 of Sec. 3.4� (a ≡ b (mod m) and c ≡ d (mod m)� ⇒ ac ≡ bd (mod m) )

Exercise : Compute 5²⁰⁰³ (mod 7)