Introduction + Chapter 1 - Number Theory (Part 1).pdf

BSSE 21043 - Mathematics for Software Engineering II Prof. N. G. J. Dias Senior Professor Department of Computer Systems Engineering Faculty of Computing and Technology University of Kela...

BSSE 21043 - Mathematics for Software Engineering II Prof. N. G. J. Dias Senior Professor Department of Computer Systems Engineering Faculty of Computing and Technology University of Kelaniya Kelaniya Contents Basic concepts in Number Theory - Principle of number theory and Modulo arithmetic Fundamentals of Graph Theory - Different types of graphs and their properties. Algebraic Structures - Fundamentals of Groups, Rings, Integral domains and Fields Applications of Combinatorics. Applications - Applications in number theory and graph theory in software engineering. 29 July 2024 NGJDias@FCT-UoK 2 Evaluation End of Semester Examination – 60% Mid Semester Examination – 20% Assignments (02) – 20% 29 July 2024 NGJDias@FCT-UoK 3 References Johnsonbaugh, R., (2007), “Discrete Mathematics”, 6th Edition, Pearson Education India. Rosen, K. H., (2003), “Discrete Mathematics and Its Applications”, 5th Edition, McGraw- Hill, New York. Lipschutz, S., (1976), “Discrete Mathematics”, McGraw-Hill, New York. Nachman, L. J., (1978), “Fundamental Mathematics”, John Wiley, New York. Trudeau, R. J., (1994), “Introduction to Graph Theory”, 2nd Edition, Dover Publications. Baumslag, B. and Chandler, B., (1968), “Schaum's Outline of Group Theory”, 1st Edition, McGraw-Hill. 29 July 2024 NGJDias@FCT-UoK 4 Chapter 1 – Number Theory Prof. N. G. J. Dias Senior Professor Department of Computer Systems Engineering Faculty of Computing and Technology University of Kelaniya Kelaniya 1.1 Introduction The part of mathematics devoted to the study of the set of integers and their properties is known as number theory. In this chapter we will develop some of the important concepts of number theory including many of those used in computer science. We will first introduce the notion of divisibility of integers, which we use to introduce modular arithmetic. We will introduce the concept of greatest common divisors and study the Euclidean algorithm for computing them. We will discuss prime numbers, the positive integers that have only 1 and themselves as positive divisors. We will prove that there are infinitely many primes; the proof is considered to be one of the most beautiful proofs in mathematics. 29 July 2024 NGJDias@FCT-UoK 6  We will introduce the fundamental theorem of arithmetic, a key result which tells us that every positive integer has a unique factorization into primes. We will explain how to solve linear congruences, as well as systems of linear congruences, which we solve using the famous Chinese remainder theorem. Finally, this chapter introduces several important applications of number theory. 29 July 2024 NGJDias@FCT-UoK 7 1.2 The Integers and Division 1.2.1 Integers An integer is colloquially defined as a number that can be written without a fractional component. For example, 21, 4, 0, and -2048 are integers, while 9.75, 51.2 , and 2 are not. The set of integers consists of zero (0), the positive integers (1, 2, 3, … ), also called the natural numbers, and the negative integers (-1, -2, -3, … ). The set of integers is often denoted by ℤ, and is given by ℤ = {⋯ , −3, −2, −1, 0, 1, 2, 3, ⋯ }. We denote the set of natural numbers by ℕ, i.e., ℕ = {1, 2, 3, ⋯ }. 29 July 2024 NGJDias@FCT-UoK 8 1.2.2 Elementary Properties of Integers Arithmetic Properties of Integers The following simple rules (laws) concerning the addition (+) and multiplication (∙) on integers are assumed: 1. If 𝑎, 𝑏 ∈ ℤ, then 𝑎 + 𝑏 ∈ ℤ. (Closure under addition) 2. If 𝑎, 𝑏 ∈ ℤ, then 𝑎 ∙ 𝑏 ∈ ℤ. (Closure under multiplication) 3. If 𝑎, 𝑏 ∈ ℤ, then 𝑎 + 𝑏 = 𝑏 + 𝑎. (Commutativity of addition) 4. If 𝑎, 𝑏 ∈ ℤ, then 𝑎 ∙ 𝑏 = 𝑏 ∙ 𝑎. (Commutativity of multiplication) 5. If 𝑎, 𝑏, 𝑐 ∈ ℤ, then 𝑎 + (𝑏 + 𝑐) = (𝑎 + 𝑏) + 𝑐. (Associativity of addition) 6. If 𝑎, 𝑏, 𝑐 ∈ ℤ, then 𝑎 ∙ (𝑏 ∙ 𝑐) = (𝑎 ∙ 𝑏) ∙ 𝑐. (Associativity of multiplication) 7. There exists an element 0 ∈ ℤ such that for all 𝑎 ∈ ℤ, 𝑎 + 0 = 𝑎. (Existence of an additive identity) The element 0 is called the additive identity. 29 July 2024 NGJDias@FCT-UoK 9  8. There exists an element 1 ∈ ℤ such that for all 𝑎 ∈ ℤ, 𝑎 ∙ 1 = 𝑎. (Existence of an multiplicative identity) The element 1 is called the multiplicaitive identity. 9. For every 𝑎 ∈ ℤ, there exists 𝑏 ∈ ℤ such that 𝑎 + 𝑏 = 0. (Existence of an additive inverse) This integer 𝑏 is called the additive inverse of 𝑎 and is denoted by −𝑎, i.e., 𝑏 = −𝑎. 10. If 𝑎, 𝑏, 𝑐 ∈ ℤ and 𝑐 ≠ 0, then 𝑎 ∙ 𝑐 = 𝑏 ∙ 𝑐 implies 𝑎 = 𝑏. (Cancellation Law) 11. If 𝑎, 𝑏, 𝑐 ∈ ℤ, then 𝑎 ∙ 𝑏 + 𝑐 = 𝑎 ∙ 𝑏 + 𝑎 ∙ 𝑐. (Distributive Law) 29 July 2024 NGJDias@FCT-UoK 10  Remark Property 9 allows us to define the usual subtraction on integers as follows: 𝑎 − 𝑏 = 𝑎 + (−𝑏), i.e., subtracting 𝑏 from 𝑎 is defined to be adding additive inverse of 𝑏 to 𝑎. Using these basic properties of integers, we can prove other properties of integers, as in the following set of theorems. 29 July 2024 NGJDias@FCT-UoK 11  Theorem 1 The additive identity in ℤ is unique, that is, 0 is the only element satisfying Property 7. Proof: Let 𝑒 ∈ ℤ be another additive identity in ℤ such that 𝑎 + 𝑒 = 𝑎 for all 𝑎 ∈ ℤ. In particular, this is true for 𝑎 = 0, so 0 + 𝑒 = 0. --- (1) Also, 0 + 𝑒 = 𝑒 + 0 (By commutativity of addition) = 𝑒 --- (2) (Since 0 is an additive identity) From (1) and (2), we get 𝑒 = 0. So, any integer satisfying Property 7 is necessarily 0. 29 July 2024 NGJDias@FCT-UoK 12  Theorem 2 Given 𝑎 ∈ ℤ, its additive inverse is unique, i.e., there exists unique 𝑏 ∈ ℤ such that 𝑎 + 𝑏 = 0. Proof: Let 𝑏, 𝑐 ∈ ℤ be two additive inverses of the given element 𝑎 ∈ ℤ. Then 𝑎 + 𝑏 = 0 and 𝑎 + 𝑐 = 0. Adding 𝑏 to both sides of the second equation gives (𝑎 + 𝑐) + 𝑏 = 0 + 𝑏 = 𝑏, since 0 is the additive identity. (𝑎 + 𝑐) + 𝑏 = 𝑏 ⇒ 𝑎 + 𝑐 + 𝑏 = 𝑏, (by associative law) ⇒ 𝑎 + 𝑏 + 𝑐 = 𝑏, (by commutative law) ⇒ (𝑎 + 𝑏) + 𝑐 = 𝑏, (by associative law) ⇒ 0 + 𝑐 = 𝑏, (by the assumption) ⇒ 𝑐 = 𝑏. (since 0 is the additive identity) Thus, the additive inverses of a given integer is unique. 29 July 2024 NGJDias@FCT-UoK 13  Theorem 3 Let 𝑎, 𝑏 and 𝑐 be integers. Then (i) 𝑏 + 𝑎 = 𝑐 + 𝑎 ⇒ 𝑏 = 𝑐. (ii) 𝑎 + 𝑏 = 𝑎 + 𝑐 ⇒ 𝑏 = 𝑐. Proof: (i) Suppose 𝑎, 𝑏 and 𝑐 be integers such that 𝑏 + 𝑎 = 𝑐 + 𝑎. Then 𝑏 + 𝑎 = 𝑐 + 𝑎 ⇒ (𝑏 + 𝑎) + −𝑎 = (𝑐 + 𝑎) + (−𝑎), (adding −𝑎 to both sides) ⇒ 𝑏 + (𝑎 + −𝑎 ) = 𝑐 + (𝑎 + −𝑎 ), (by associative laws) ⇒ 𝑏 + 0 = 𝑐 + 0, (by additive inverse) ⇒𝑏=𝑐 (since 0 is the additive identity) 29 July 2024 NGJDias@FCT-UoK 14  Hence, 𝑏 + 𝑎 = 𝑐 + 𝑎 ⇒ 𝑏 = 𝑐. (ii) Suppose 𝑎 + 𝑏 = 𝑎 + 𝑐. By the commutative law, we have 𝑎 + 𝑏 = 𝑏 + 𝑎 and 𝑎 + 𝑐 = 𝑐 + 𝑎. Therefore, 𝑎 + 𝑏 = 𝑎 + 𝑐 ⇒ 𝑏 + 𝑎 = c + 𝑎. Hence, using part (i) above, we can conclude that 𝑏 = 𝑐. 29 July 2024 NGJDias@FCT-UoK 15  Theorem 4 For all integer 𝑎 ∈ ℤ, 𝑎 ∙ 0 = 0 = 0 ∙ 𝑎. Proof: Let 𝑎 be an integer. Then 𝑎 ∙ 0 + 0 = 𝑎 ∙ 0, (since 0 is the additive identity) ⇒ 𝑎 ∙ 0 + 0 = 𝑎 ∙ (0 + 0), (since 0 is the additive identity) ⇒𝑎∙0+0=𝑎∙0+𝑎∙0 (by distributive law) We now apply Theorem 3 to conclude that 𝑎 ∙ 0 = 0. Moreover, by the commutative law, 0 ∙ 𝑎 = 𝑎 ∙ 0 and so 0 ∙ 𝑎 = 0. 29 July 2024 NGJDias@FCT-UoK 16  Theorem 5 For all 𝑎 ∈ ℤ, −𝑎 = (−1) ∙ 𝑎. Proof: First we will show that (−1) ∙ 𝑎 is an additive inverse of 𝑎. 𝑎 + −1 ∙ 𝑎 = 1. 𝑎 + −1 ∙ 𝑎, (since 1 is the multiplicative identity and by commutativity) = (1 + −1 ). 𝑎, (by distributive law) = 0. 𝑎, (by additive inverse) = 0. (by Theorem 4) That is, (−1) ∙ 𝑎 is an additive inverse of 𝑎. By the uniqueness of additive inverses (Theorem 2), the result follows, i.e., −𝑎 = (−1) ∙ 𝑎. 29 July 2024 NGJDias@FCT-UoK 17  Theorem 6 For all 𝑎 ∈ ℤ, − −𝑎 = 𝑎. Proof: Let 𝑎 ∈ ℤ. Then by the inverse property, −𝑎 + 𝑎 = 0. --- (1) Now −𝑎 ∈ ℤ. We apply the inverse property on −𝑎. Therefore, −𝑎 + − −𝑎 = 0. --- (2) Hence, from (1) and (2) we have −𝑎 + − −𝑎 = −𝑎 + 𝑎. We can now apply Theorem 3 to conclude that − −𝑎 = 𝑎. 29 July 2024 NGJDias@FCT-UoK 18  Theorem 7 If 𝑎 and 𝑏 are two integers such that 𝑎 ∙ 𝑏 = 0, then either 𝑎 = 0 or 𝑏 = 0. Proof: Suppose 𝑎 and 𝑏 are integers such that 𝑎 ≠ 0 and 𝑎 ∙ 𝑏 = 0. Then 𝑎 ∙ 𝑏 = 0. 𝑎 ∙ 𝑏 = 0 ⇒ 𝑎 ∙ 𝑏 = 𝑎 ∙ 0, (by Theorem 4) ⇒ 𝑏 = 0. (by the cancellation law) Exercise Let 𝑎 and 𝑏 be integers. Show that (i) −𝑎 ∙ 𝑏 = − 𝑎 ∙ 𝑏 = 𝑎 ∙ (−𝑏), (ii) −𝑎 ∙ −𝑏 = 𝑎 ∙ 𝑏. 29 July 2024 NGJDias@FCT-UoK 19  Definition 1 – Ordering on Integers Given two integers 𝑎 and 𝑏, we say that 𝑎 is less than 𝑏, written 𝑎 < 𝑏, if there exists a 𝑐 ∈ ℕ such that 𝑏 = 𝑎 + 𝑐. We also write 𝑏 > 𝑎 and say that 𝑏 is greater than 𝑎. If 𝑎 < 𝑏 or 𝑎 = 𝑏, we write 𝑎 ≤ 𝑏 and read as 𝑎 is less than or equal to 𝑏 ; similarly 𝑎 ≥ 𝑏 means that either 𝑎 > 𝑏 or 𝑎 = 𝑏. The relations and ≥ are called inequalities in order to distinguish them from the relation = of equality. We also note that 𝑎 is positive if and only if 𝑎 > 0, and 𝑎 is negative if and only if 𝑎 < 0. 29 July 2024 NGJDias@FCT-UoK 20  Ordering Properties of Integers 1. If 𝑎, 𝑏 > 0, then 𝑎 + 𝑏 > 0. (Closure of “> 0” under addition) 2. If 𝑎, 𝑏 > 0, then 𝑎 ∙ 𝑏 > 0. (Closure of “> 0” under multiplication) 3. For any two integers 𝑎, 𝑏 ∈ ℤ, exactly one of the following holds: 𝑎 < 𝑏, 𝑎 = 𝑏 or 𝑎 > 𝑏. (Law of Trichotomy) 4. For any integer 𝑎, 𝑎 ≤ 𝑎. 5. Let 𝑎 and 𝑏 be integers. If 𝑎 ≤ 𝑏 and 𝑏 ≤ 𝑎, then 𝑎 = 𝑏. 6. Let 𝑎, 𝑏 and 𝑐 be integers. If 𝑎 < 𝑏 and 𝑏 < 𝑐, then 𝑎 < 𝑐. 7. Suppose 𝑎 < 𝑏, and let 𝑐 be any integer. Then (i) 𝑎 + 𝑐 < 𝑏 + 𝑐 (ii) 𝑎𝑐 < 𝑏𝑐 if 𝑐 > 0 and 𝑎𝑐 > 𝑏𝑐 if 𝑐 < 0. 29 July 2024 NGJDias@FCT-UoK 21  8. Let 𝑎, 𝑏, 𝑐 and 𝑑 be integers. If 𝑎 < 𝑏 and 𝑐 < 𝑑, then 𝑎 + 𝑐 < 𝑏 + 𝑑. 9. Let 𝑎, 𝑏 and 𝑐 be integers. If 0 ≤ 𝑎 < 𝑏 and 0 ≤ 𝑐 < 𝑑, then 𝑎𝑐 < 𝑏𝑑. 10. Let 𝑎 and 𝑏 be integers. If 𝑎 < 𝑏, then −𝑏 < −𝑎. 11. For any integer 𝑎, 0 ≤ 𝑎2. 12. Let 𝑎 and 𝑏 be integers. If 𝑎𝑏 = 1, then either 𝑎 = 𝑏 = 1 or 𝑎 = 𝑏 = −1. Note: Properties 1 , 2, and 6 – 10 hold if each < is replaced with ≤. Exercise: Try to prove above properties using the definition of ordering of integers. 29 July 2024 NGJDias@FCT-UoK 22 1.3 Divisibility 1.3.1 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 2. Definition 2 If 𝑎 and 𝑏 are integers with 𝑎 ≠ 0, we say that 𝑎 divides 𝑏 if there is an integer 𝑐 such that 𝑏 = 𝑎𝑐. When 𝑎 divides 𝑏 we say that 𝑎 is a factor of 𝑏 and that 𝑏 is a multiple of 𝑎. The notation 𝑎|𝑏 denotes that 𝑎 divides 𝑏. We write 𝑎 ∤ 𝑏 when 𝑎 does not divides 𝑏. 29 July 2024 NGJDias@FCT-UoK 23  Remark: We can express 𝑎 | 𝑏 using quantifiers as ∃𝑐 ∈ ℤ. 𝑎𝑐 = 𝑏, where the universe of discourse is the set of integers. Example 1: Determine whether 3|7 and whether 3|12. 7 Solution: We see that 3 ∤ 7, because is not an integer. On the other hand, 3 12 3|12 because = 3. 4 29 July 2024 NGJDias@FCT-UoK 24 Example 2: Let 𝑛 and 𝑑 be positive integers such that 𝑑 ≤ 𝑛. How many positive integers not exceeding 𝑛 are divisible by 𝑑? Solution: The positive integers divisible by 𝑑 are all the integers of the form 𝑑𝑘, where 𝑘 is a positive integer. Hence, the number of positive integers divisible by 𝑑 that do not exceed 𝑛 equals the number of integers 𝑘 with 0 < 𝑑𝑘 < 𝑛, or with 0 < 𝑘 ≤ 𝑛/𝑑. Therefore, there are 𝑛/𝑑 positive integers not exceeding 𝑛 that are divisible by 𝑑. Remark: 1|𝑎 and 𝑎|𝑎 for all 𝑎 ∈ ℤ. Some of the basic properties of divisibility of integers are given in the following Theorem 8. 29 July 2024 NGJDias@FCT-UoK 25  Theorem 8 Let 𝑎, 𝑏, and 𝑐 be integers, where 𝑎 ≠ 0. Then (i) if 𝑎|𝑏 and 𝑎|𝑐, then 𝑎|(𝑏 + 𝑐); (ii) if 𝑎|𝑏, then 𝑎|𝑏𝑐 for all integers 𝑐; (iii) if 𝑎|𝑏 and 𝑏|𝑐 , then 𝑎|𝑐. Proof: (i) Suppose that 𝑎|𝑏 and 𝑎|𝑏. Then, from the definition of divisibility, it follows that there are integers 𝑠 and 𝑡 with 𝑏 = 𝑎𝑠 and 𝑐 = 𝑎𝑡. Hence, 𝑏 + 𝑐 = 𝑎𝑠 + 𝑎𝑡 = 𝑎 𝑠 + 𝑡 = 𝑎𝑢, where 𝑢 = 𝑠 + 𝑡 ∈ ℤ. Therefore, 𝑎|(𝑏 + 𝑐). 29 July 2024 NGJDias@FCT-UoK 26  (ii) Suppose that 𝑎|𝑏. Then, from the definition of divisibility, it follows that there is an integer 𝑠 with 𝑏 = 𝑎𝑠. Then 𝑏𝑐 = (𝑎𝑠)𝑐 = 𝑎(𝑠𝑐) = 𝑎𝑢, where 𝑢 = 𝑠𝑐 ∈ ℤ. Therefore, 𝑎|𝑏𝑐. (iii) Suppose that 𝑎|𝑏 and 𝑏|𝑐. Then, from the definition of divisibility, it follows that there are integers 𝑠 and 𝑡 with 𝑏 = 𝑎𝑠 and 𝑐 = 𝑏𝑡. Then 𝑐 = 𝑏𝑡 = 𝑎𝑠 𝑡 = 𝑎 𝑠𝑡 = 𝑎𝑢, where 𝑢 = 𝑠𝑡 ∈ ℤ. Therefore, 𝑎|𝑐. 29 July 2024 NGJDias@FCT-UoK 27  Corollary 1: If 𝑎, 𝑏, and 𝑐 be integers, where 𝑎 ≠ 0, such that 𝑎|𝑏 and 𝑎|𝑐, then 𝑎|𝑚𝑏 + 𝑛𝑐 whenever 𝑚 and 𝑛 are integers. Proof: By part (ii) of Theorem 8 we see that 𝑎|𝑚𝑏 and 𝑎|𝑛𝑐 whenever 𝑚 and 𝑛 are integers. By part (i) of Theorem 8 it follows that 𝑎|𝑚𝑏 + 𝑛𝑐. 29 July 2024 NGJDias@FCT-UoK 28 1.3.2 Primes Every integer greater than 1 is divisible by at least two integers, because a positive integer is divisible by 1 and by itself. Positive integers that have exactly two different positive integer factors are called primes. Definition 3 – Prime Numbers An integer 𝑝 greater than 1 is called prime if the only positive factors of 𝑝 are 1 and 𝑝. A positive integer that is greater than 1 and is not prime is called composite. 29 July 2024 NGJDias@FCT-UoK 29  Remark 1. The integer 1 is not prime, because it has only one positive factor. 2. 2 is the only even prime number (why?). 3. Note also that an integer 𝑛 is composite if and only if there exists an integer 𝑎 such that 𝑎|𝑛 and 1 < 𝑎 < 𝑛. That is, if an integer 𝑛 is composite then 𝑛 = 𝑎𝑏 where 1 < 𝑎, 𝑏 < 𝑛. Example 1: The integer 7 is prime because its only positive factors are 1 and 7, whereas the integers 6 = 2 ∙ 3 and 15 = 3 ∙ 5 are composite because they have factors other than 1 and themselves. Example 2: The numbers 21, 24 and 1729 are not primes, but each can be written as a product of primes as follows. 21 = 3 ∙ 7, 24 = 2 ∙ 2 ∙ 2 ∙ 3 = 23 ∙ 3, 1729 = 7 ∙ 13 ∙ 19. 29 July 2024 NGJDias@FCT-UoK 30  The primes are the building blocks of positive integers, as the fundamental theorem of arithmetic shows. Theorem 9 (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. Proof: Can be proved using strong induction. Example The prime factorizations of integers 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. 29 July 2024 NGJDias@FCT-UoK 31  Theorem 10 If 𝑛 is a composite integer, then 𝑛 has a prime divisor less than or equal to 𝑛. Proof: If 𝑛 is composite, by the definition of a composite integer, we know that it has a factor 𝑎 with 1 < 𝑎 < 𝑛. Hence, by the definition of a factor of a positive integer, we have 𝑛 = 𝑎𝑏, where 𝑏 is a positive integer greater than 1. We will show that 𝑎 ≤ 𝑛 or 𝑏 ≤ 𝑛. If 𝑎 > 𝑛 and 𝑏 > 𝑛, then 𝑎𝑏 > 𝑛 ∙ 𝑛 = 𝑛, which is a contradiction. Consequently, 𝑎 ≤ 𝑛 or 𝑏 ≤ 𝑛. Because both 𝑎 and 𝑏 are divisors of 𝑛, we see that 𝑛 has a positive divisor not exceeding 𝑛. This divisor is either prime or, by the fundamental theorem of arithmetic, has a prime divisor less than itself. In either case, 𝑛 has a prime divisor less than or equal to 𝑛. 29 July 2024 NGJDias@FCT-UoK 32  From Theorem 10, it follows that an integer is prime if it is not divisible by any prime less than or equal to its square root. This leads to the brute-force algorithm known as trial division. To use trial division we divide 𝑛 by all primes not exceeding 𝑛 and conclude that 𝑛 is prime if it is not divisible by any of these primes. Example: Show that 101 is prime. 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. 29 July 2024 NGJDias@FCT-UoK 33  Because every integer has a prime factorization, it would be useful to have a procedure for finding this prime factorization. Consider the problem of finding the prime factorization of 𝑛. Begin by dividing 𝑛 by successive primes, starting with the smallest prime, 2. If 𝑛 has a prime factor, then by Theorem 10 a prime factor 𝑝 not exceeding 𝑛 will be found. So, if no prime factor not exceeding 𝑛 is found, then 𝑛 is prime. 𝑛 Otherwise, if a prime factor 𝑝 is found, continue by factoring. 𝑝 𝑛 Note that has no prime factors less than 𝑝. 𝑝 𝑛 Again, if has no prime factor greater than or equal to 𝑝 and not exceeding its 𝑝 square root, then it is prime. 𝑛 Otherwise, if it has a prime factor 𝑞, continue by factoring. 𝑝𝑞 This procedure is continued until the factorization has been reduced to a prime. 29 July 2024 NGJDias@FCT-UoK 34 Example: Find the prime factorization of 7007. To find the prime factorization of 7007, first perform divisions of 7007 by successive primes, beginning with 2. None of the primes 2, 3, and 5 divides 7007. 7007 However, 7 divides 7007, with = 1001. 7 Next, divide 1001 by successive primes, beginning with 7. 1001 It is immediately seen that 7 also divides 1001, because = 143. 7 Continue by dividing 143 by successive primes, beginning with 7. 143 Although 7 does not divide 143, 11 does divide 143, and = 13. 11 Because 13 is prime, the procedure is completed. It follows that, 7007 = 7 · 1001 = 7 · 7 · 143 = 7 · 7 · 11 · 13. Consequently, the prime factorization of 7007 is 7 ∙ 7 ∙ 11 ∙ 13 = 72 ∙ 11 ∙ 13. 29 July 2024 NGJDias@FCT-UoK 35 Example: Find all prime numbers less than 100. Every composite number less than 100 must have a prime divisor, less than 100 = 10. Since 2,3,5,7 are all primes less than 10, we need only to check each integer less than 100 divisible by these primes. Write the odd numbers greater than 7 which are not divisible by 3 and not ending with 5. They are, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 49, 53, 59, 61, 67, 71, 73, 77, 79, 83, 89, 91, 97. Now cross each integer divisible by 7. (i.e. 49, 77, 91) The remaining 21 numbers together with 2,3,5 and 7 are the primes less than 100. 29 July 2024 NGJDias@FCT-UoK 36  Theorem 11: There are infinitely many prime numbers. Proof: We will prove this theorem using a proof by contradiction. We assume that there are only finitely many primes, 𝑝1 , 𝑝2 , ⋯ , 𝑝𝑛. Let 𝑄 = 𝑝1 𝑝2 ⋯ 𝑝𝑛 + 1. Clearly 𝑄 is an integer larger than any of the primes 𝑝1 , 𝑝2 , ⋯ , 𝑝𝑛 , so it doesn’t equal one of them. Since 𝑝1 , 𝑝2 , ⋯ , 𝑝𝑛 constitute all primes 𝑄 can’t be prime. That is 𝑄 is composite. Therefore, by the fundamental theorem of arithmetic, 𝑄 can be written as the product of two or more of our finitely many primes 𝑝1 , 𝑝2 , ⋯ , 𝑝𝑛. That is 𝑄 has a prime divisor. Let us consider it as 𝑝𝑚 (with 1 ≤ 𝑚 ≤ 𝑛) and 𝑝𝑚 |𝑄. Since 𝑝𝑚 |𝑄 and 𝑝𝑚 |𝑝1 𝑝2 ⋯ 𝑝𝑛 , we have 𝑝𝑚 |𝑄 − 𝑝1 𝑝2 ⋯ 𝑝𝑛 , i.e., 𝑝𝑚 |1. 29 July 2024 NGJDias@FCT-UoK 37  This is a contradiction and so 𝑄 is divisible by some other prime. Therefore, there are infinitely many prime numbers. Remark: If 2𝑛 − 1 is prime, then 𝑛 is also prime. 29 July 2024 NGJDias@FCT-UoK 38 1.4 The Division Algorithm The following fundamental property of arithmetic is essentially a restatement of the result of long division. Theorem 12 (Division Algorithm) Let 𝑎 be an integer and 𝑑 be a positive integer. Then there are unique integers 𝑞 and 𝑟, with 0 ≤ 𝑟 < 𝑑, such that 𝑎 = 𝑑𝑞 + 𝑟. Remark: Theorem 12 is not really an algorithm. (Why not?) Nevertheless, we use its traditional name. Definition 4 In the equality given in the division algorithm, 𝑑 is called the divisor, 𝑎 is called the dividend, 𝑞 is called the quotient, and 𝑟 is called the remainder. This notation is used to express the quotient and remainder: 𝑞 = 𝑎 𝑑𝑖𝑣 𝑑, 𝑟 = 𝑎 𝑚𝑜𝑑 𝑑. 29 July 2024 NGJDias@FCT-UoK 39 Example 1 What are the quotient and remainder when 101 is divided by 11? We have 101 = 11 ∙ 9 + 2. Hence, the quotient when 101 is divided by 11 is 9 = 101 𝑑𝑖𝑣 11 and the remainder is 2 = 101 𝑚𝑜𝑑 11. Example 2 What are the quotient and remainder when −11 is divided by 3? We have −11 = 3 −4 + 1. Hence, the quotient when −11 is divided by 3 is −4 = −11 𝑑𝑖𝑣 3 and the remainder is 1 = −11 𝑚𝑜𝑑 3. Note that the remainder cannot be negative. Consequently, the remainder in Example 2 is not −2, even though −11 = 3 −3 − 2, because 𝑟 = −2 does not satisfy 0 ≤ 𝑟 < 3. 29 July 2024 NGJDias@FCT-UoK 40  Remark: Note that both 𝑎 𝑑𝑖𝑣 𝑑 and 𝑎 𝑚𝑜𝑑 𝑑 for a fixed 𝑑 are functions on the set of integers. Furthermore, when 𝑎 is an integer and 𝑑 is a positive integer, we have 𝑎 𝑑𝑖𝑣 𝑑 = 𝑎/𝑑 and 𝑎 𝑚𝑜𝑑 𝑑 = 𝑎 − 𝑑. Note that the integer 𝑎 is divisible by the integer 𝑑 if and only if the remainder is zero when 𝑎 is divided by 𝑑. Remark: A programming language may have one, or possibly two, operators for modular arithmetic, denoted by mod (in BASIC, Maple, Mathematica, EXCEL, and SQL), % (in C, C++, Java, and Python), rem (in Ada and Lisp), or something else. Be careful when using them, because for 𝑎 < 0, some of these operators return 𝑎 − 𝑚 𝑎/𝑚 instead of 𝑎 𝑚𝑜𝑑 𝑚 = 𝑎 − 𝑚 𝑎/𝑚. Also, unlike 𝑎 𝑚𝑜𝑑 𝑚𝑎, some of these operators are defined when 𝑚 < 0, and even when 𝑚 = 0. 29 July 2024 NGJDias@FCT-UoK 41 1.5 Greatest Common Divisors and Least Common Multiples 1.5.1 Greatest Common Divisor The largest integer that divides both of two integers is called the greatest common divisor of these integers. Definition 5 Let 𝑎 and 𝑏 be integers, not both zero. The largest integer 𝑑 such that 𝑑|𝑎 and 𝑑|𝑏 is called the greatest common divisor of 𝑎 and 𝑏. The greatest common divisor of 𝑎 and 𝑏 is denoted by gcd(𝑎, 𝑏). The greatest common divisor of two integers, not both zero, exists because the set of common divisors of these integers is nonempty and finite. One way to find the greatest common divisor of two integers is to find all the positive common divisors of both integers and then take the largest divisor. 29 July 2024 NGJDias@FCT-UoK 42 Example 1 What is the greatest common divisor of 24 and 36? The positive common divisors of 24 and 36 are 1, 2, 3, 4, 6, and 12. Hence, gcd 24,36 = 12. Similarly, gcd 12, −18 = 6, gcd 12, −16 = 4, , gcd 14,49 = 7. Example 2 What is the greatest common divisor of 17 and 22? The integers 17 and 22 have no positive common divisors other than 1, so that gcd 17,22 = 1. Because it is often important to specify that two integers have no common positive divisor other than 1, we have the following Definition 6. 29 July 2024 NGJDias@FCT-UoK 43  Definition 6 The integers 𝑎 and 𝑏 are relatively prime if their greatest common divisor is 1. Example By Example 2 above, it follows that the integers 17 and 22 are relatively prime, because gcd 17,22 = 1. Because we often need to specify that no two integers in a set of integers have a common positive divisor greater than 1, we make Definition 7. Definition 7 The integers 𝑎1 , 𝑎2 , ⋯ , 𝑎𝑛 are pairwise relatively prime if gcd 𝑎𝑖 , 𝑎𝑗 = 1 whenever 1 ≤ 𝑖 < 𝑗 ≤ 𝑛. 29 July 2024 NGJDias@FCT-UoK 44 Example Determine whether the integers 10, 17, and 21 are pairwise relatively prime and whether the integers 10, 19, and 24 are pairwise relatively prime. 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. Because gcd 10,24 = 2 > 1, we see that 10, 19, and 24 are not pairwise relatively prime. 29 July 2024 NGJDias@FCT-UoK 45  Another way to find the greatest common divisor of two positive integers is to use the prime factorizations of these integers. Suppose that the prime factorizations of the positive integers 𝑎 and 𝑏 are 𝑎 𝑎 𝑎 𝑏 𝑏 𝑏 𝑎 = 𝑝1 1 𝑝2 2 ⋯ 𝑝𝑛 𝑛 and 𝑏 = 𝑝1 1 𝑝2 2 ⋯ 𝑝𝑛𝑛 , where each exponent is a nonnegative integer, and where all primes occurring in the prime factorization of either 𝑎 or 𝑏 are included in both factorizations, with zero exponents if necessary. Then gcd 𝑎, 𝑏 is given by min(𝑎1 ,𝑏1 ) min(𝑎2 ,𝑏2 ) min(𝑎𝑛 ,𝑏𝑛 ) gcd 𝑎, 𝑏 = 𝑝1 𝑝2 ⋯ 𝑝𝑛 , where min(𝑥, 𝑦) represents the minimum of the two numbers 𝑥 and 𝑦. 29 July 2024 NGJDias@FCT-UoK 46 Example 1 The prime factorizations of 120 and 500 are 120 = 23 ∙ 3 ∙ 5 and 500 = 22 ∙ 53 , the greatest common divisor is gcd 120,500 = 2min(3,2) × 3min(1,0) × 5min(1,3) = 22 × 30 × 51 = 20. Example 2 Find the greatest common divisor of the two numbers 32 ∙ 5 ∙ 74 and 23 ∙ 3 ∙ 5 (given in their prime factorization form). gcd 32 ∙ 5 ∙ 74 , 23 ∙ 3 ∙ 5 = gcd 20 ∙ 32 ∙ 51 ∙ 74 , 23 ∙ 31 ∙ 51 ∙ 70 = 2min(0,3) × 3min(2,1) × 5min(1,1) × 7min(4,0) = 20 × 31 × 51 × 70 = 15. 29 July 2024 NGJDias@FCT-UoK 47  Properties of Greatest Common Divisor 1. For any integer 𝑎, we have gcd 1, 𝑎 = 1. 2. For integers 𝑎 and 𝑏, not both zero gcd 𝑎, 𝑏 = gcd(𝑏, 𝑎). 3. For any prime 𝑝, we have gcd 𝑝, 𝑎 = 𝑝 if 𝑝|𝑎, and gcd 𝑝, 𝑎 = 1 if 𝑝 ∤ 𝑎. 4. Suppose 𝑎 is positive. Then 𝑎|𝑏 if and only if gcd 𝑎, 𝑏 = 𝑎. 5. If 𝑥 > 0, then gcd 𝑎𝑥, 𝑏𝑥 = 𝑥 ∙ gcd(𝑎, 𝑏). 𝑎 𝑏 6. If 𝑑 = gcd(𝑎, 𝑏), then gcd , = 1. 𝑑 𝑑 7. For any integer 𝑥, gcd 𝑎, 𝑏 = gcd(𝑎, 𝑏 + 𝑎𝑥). 29 July 2024 NGJDias@FCT-UoK 48 1.5.2 Least Common Multiple Definition 8 The least common multiple of the positive integers 𝑎 and 𝑏 is the smallest positive integer that is divisible by both 𝑎 and 𝑏. The least common multiple of 𝑎 and 𝑏 is denoted by lcm(𝑎, 𝑏). A way to find the least common multiple of two positive integers is to use the prime factorizations of these integers. Suppose that the prime factorizations of the positive integers 𝑎 and 𝑏 are 𝑎 𝑎 𝑎 𝑏 𝑏 𝑏 𝑎 = 𝑝1 1 𝑝2 2 ⋯ 𝑝𝑛 𝑛 and 𝑏 = 𝑝1 1 𝑝2 2 ⋯ 𝑝𝑛𝑛 , here each exponent is a nonnegative integer, and where all primes occurring in the prime factorization of either 𝑎 or 𝑏 are included in both factorizations, with zero exponents if necessary. 29 July 2024 NGJDias@FCT-UoK 49  Then lcm(𝑎, 𝑏) is given by max(𝑎1 ,𝑏1 ) max(𝑎2 ,𝑏2 ) max(𝑎𝑛 ,𝑏𝑛 ) lcm 𝑎, 𝑏 = 𝑝1 𝑝2 ⋯ 𝑝𝑛 , where max(𝑥, 𝑦)represents the maximum of the two numbers 𝑥 and 𝑦. Example What is the least common multiple of 23 35 72 and 24 33 ? We have lcm 23 35 72 ,24 33 = 2max(2,4) 3max(5,3) 7max(2,0) = 24 35 72. Exercise Find the gcd and lcm of: (i) 32 and 72, (ii) 117 and 273 (iii) 73 and 245 (iv) 84 and 1254. 29 July 2024 NGJDias@FCT-UoK 50  Properties of Least Common Multiple 1. For any integer 𝑎, we have lcm 1, 𝑎 = 1. 2. For positive integers 𝑎 and 𝑏, lcm 𝑎, 𝑏 = lcm(𝑏, 𝑎). 3. For any prime 𝑝 and for any positive integer 𝑎, we have lcm 𝑝, 𝑎 = 𝑎 if 𝑝|𝑎, and gcd 𝑝, 𝑎 = 𝑎𝑝 if 𝑝 ∤ 𝑎. 4. Suppose 𝑎 and 𝑏 are positive integers. Then 𝑎|𝑏 if and only if lcm 𝑎, 𝑏 = 𝑏. The following Theorem 13 gives the relationship between the greatest common divisor and least common multiple of two integers. It can be proved using the formulae we have derived for these quantities. Theorem 13 Let 𝑎 and 𝑏 be positive integers. Then 𝑎𝑏 = gcd(𝑎, 𝑏) ∙ lcm(𝑎, 𝑏). Proof: The proof of this theorem is left as Exercise. 29 July 2024 NGJDias@FCT-UoK 51 1.6 The Euclidean Algorithm 1.6.1 Introduction Computing the greatest common divisor of two integers directly from the prime factorizations of these integers is inefficient. The reason is that it is time-consuming to find prime factorizations. We will give a more efficient method of finding the greatest common divisor, called the Euclidean algorithm. This algorithm has been known since ancient times and it is named after the ancient Greek mathematician Euclid. This algorithm consists of repeatedly applying the division algorithm (long division). Before describing the Euclidean algorithm, we illustrate the algorithm with an example. 29 July 2024 NGJDias@FCT-UoK 52 1.6.2 An Example for Illustration Find gcd(91,287). - First, divide 287, the larger of the two integers, by 91, the smaller, to obtain 287 = 91 ∙ 3 + 14. --- (1) Any divisor of 91 and 287 must also be a divisor of 287 − 91 ∙ 3 = 14. Also, any divisor of 91 and 14 must also be a divisor of 287 = 91 ∙ 3 + 14. Hence, the greatest common divisor of 91 and 287 is the same as the greatest common divisor of 91 and 14. This means that the problem of finding gcd(91,287) has been reduced to the problem of finding gcd(91,14). - Next, divide 91 by 14 to obtain 91 = 14 ∙ 6 + 7. --- (2) 29 July 2024 NGJDias@FCT-UoK 53  Because any common divisor of 91 and 14 also divides 91 − 14 ∙ 6 = 7 and any common divisor of 14 and 7 divides 91, it follows that gcd 91,14 = gcd(14,7). Continue by dividing 14 by 7, to obtain 14 = 7 ∙ 2. --- (3) Because 7 divides 14, it follows that gcd 14,7 = 7. Since, gcd 91,287 = gcd 91,14 = gcd 14,7 = 7, the original problem has been solved. Furthermore, by working backwards from equation (2) to (1) in turn we see that 7 = 91 + (−6) ∙ 14 (by (2)) = 91 + −6 ∙ 287 + −3 ∙ 91 (by (1)) = −6 ∙ 287 + 19 ∙ 91 So that, gcd 287,91 = 𝑥 ∙ 287 + 𝑦 ∙ 91, where 𝑥 = −6 and 𝑦 = 19. 29 July 2024 NGJDias@FCT-UoK 54  In other words, we have been able, by using the succession of divisions, to express the gcd of 287 and 91 as a sum of multiples of these two integers. Now we can describe how the Euclidean algorithm works in generality. We will use successive divisions to reduce the problem of finding the greatest common divisor of two positive integers to the same problem with smaller integers, until one of the integers is zero. 29 July 2024 NGJDias@FCT-UoK 55 1.6.3 Determining the gcd The Euclidean algorithm is based on the following result about greatest common divisors and the division algorithm. Lemma 1 Let 𝑎 and 𝑏 be positive integers such that 𝑎 = 𝑏𝑞 + 𝑟, where 0 ≤ 𝑟 < 𝑏. Then gcd 𝑎, 𝑏 = gcd(𝑏, 𝑟). Proof: If we can show that the common divisors of 𝑎 and 𝑏 are the same as the common divisors of 𝑏 and 𝑟, we will have shown that gcd 𝑎, 𝑏 = gcd(𝑏, 𝑟), because both pairs must have the same greatest common divisor. So suppose that 𝑑 divides both 𝑎 and 𝑏. Then it follows that 𝑑 also divides 𝑎 − 𝑏𝑞 = 𝑟 (from Theorem 8 of Section 1.3). 29 July 2024 NGJDias@FCT-UoK 56  Hence, any common divisor of 𝑎 and 𝑏 is also a common divisor of 𝑏 and 𝑟. Likewise, suppose that 𝑑 divides both 𝑏 and 𝑟. Then 𝑑 also divides 𝑏𝑞 + 𝑟 = 𝑎. Hence, any common divisor of 𝑏 and 𝑟 is also a common divisor of 𝑎 and 𝑏. Consequently, gcd 𝑎, 𝑏 = gcd(𝑏, 𝑟). 29 July 2024 NGJDias@FCT-UoK 57 1.6.4 Euclidean Algorithm for Finding the gcd We now describe the Euclidean algorithm for computing the greatest common divisor 𝑑 of the two positive integers 𝑎 and 𝑏, and will also describe how to express 𝑑 in the form 𝑑 = 𝑠𝑎 + 𝑡𝑏, for some integers 𝑠 and 𝑡. Suppose that 𝑎 and 𝑏 are positive integers with 𝑎 ≥ 𝑏. By the division algorithm, there exist integers 𝑞1 and 𝑟1 such that 𝑎 = 𝑏𝑞1 + 𝑟1 , 0 ≤ 𝑟1 < 𝑏. Now consider 𝑏 and 𝑟1. If 𝑟1 ≠ 0, then by the division algorithm, there exist integers 𝑞2 and 𝑟2 such that 𝑏 = 𝑟1 𝑞2 + 𝑟2 , 0 ≤ 𝑟2 < 𝑟1. Next consider 𝑟1 and 𝑟2. 29 July 2024 NGJDias@FCT-UoK 58  If 𝑟2 ≠ 0, then by the division algorithm, there exist integers 𝑞3 and 𝑟3 such that 𝑟1 = 𝑟2 𝑞3 + 𝑟3 , 0 ≤ 𝑟3 < 𝑟2. We continue this process. Therefore, we obtain 𝑎 = 𝑏𝑞1 + 𝑟1 , 0 ≤ 𝑟1 < 𝑏. --- (1) If 𝑟1 ≠ 0, 𝑏 = 𝑟1 𝑞2 + 𝑟2 , 0 ≤ 𝑟2 < 𝑟1. --- (2) If 𝑟2 ≠ 0, 𝑟1 = 𝑟2 𝑞3 + 𝑟3 , 0 ≤ 𝑟3 < 𝑟2. --- (3) If 𝑟3 ≠ 0, 𝑟2 = 𝑟3 𝑞4 + 𝑟4 , 0 ≤ 𝑟4 < 𝑟3. --- (4) If 𝑟4 ≠ 0, 𝑟3 = 𝑟4 𝑞5 + 𝑟5 , 0 ≤ 𝑟5 < 𝑟4. --- (5) ⋮ ⋮ ⋮ ⋮ 29 July 2024 NGJDias@FCT-UoK 59  Now the remainders 𝑟1 , 𝑟2 , 𝑟3 , ⋯ , form the following decreasing sequence of nonnegative integers: 𝑎 ≥ 𝑏 > 𝑟1 > 𝑟2 > 𝑟3 ⋯ ≥ 0. Because 𝑏 is a fixed positive integer, we must encounter the remainder 0 after a finite number of steps. Suppose the process terminates after (𝑛 + 1) steps. Then we have, 𝑟𝑛−2 = 𝑟𝑛−1 𝑞𝑛 + 𝑟𝑛 , 0 ≤ 𝑟𝑛 < 𝑟𝑛−1. --- (n) 𝑟𝑛−1 = 𝑟𝑛 𝑞𝑛+1. Now the repeated application of Lemma 1 yields gcd 𝑎, 𝑏 = gcd 𝑏, 𝑟1 = gcd 𝑟1 , 𝑟2 = gcd 𝑟2 , 𝑟3 = ⋯ = gcd 𝑟𝑛−1 , 𝑟𝑛. Because 𝑟𝑛−1 = 𝑟𝑛 𝑞𝑛+1 , it follows that gcd(𝑟𝑛−1 , 𝑟𝑛 ) = 𝑟𝑛. Hence, gcd 𝑎, 𝑏 = 𝑟𝑛. Thus, the greatest common divisor is the last nonzero remainder in the sequence of divisions. 29 July 2024 NGJDias@FCT-UoK 60  Next we show how to find integers 𝑠 and 𝑡 such that gcd 𝑎, 𝑏 = 𝑠𝑎 + 𝑡𝑏. Again consider the equations (1) to (n) derived above. From equation (1), 𝑟1 = 𝑎 − 𝑏𝑞1 = 𝑠1 𝑎 + 𝑡1 𝑏, where 𝑠1 = 1 and 𝑡1 = −𝑏. From equation (2), 𝑟2 = 𝑏 − 𝑟1 𝑞2 = 𝑏 − 𝑎 − 𝑏𝑞1 𝑞2 = −𝑞2 𝑎 + 1 + 𝑞1 𝑞2 𝑏 = 𝑠2 𝑎 + 𝑡2 𝑏, where 𝑠2 = −𝑞2 and 𝑡2 = 1 + 𝑞1 𝑞2. From equation (3), 𝑟3 = 𝑟1 − 𝑟2 𝑞3 = 𝑎 − 𝑏𝑞1 − (𝑠2 𝑎 + 𝑡2 𝑏)𝑞3 = 1 − 𝑠2 𝑞3 𝑎 + −𝑞1 − 𝑡2 𝑞3 𝑏 = 𝑠3 𝑎 + 𝑡3 𝑏, where 𝑠3 = 1 − 𝑠2 𝑞3 and 𝑡3 = −𝑞1 − 𝑡2 𝑞3. 29 July 2024 NGJDias@FCT-UoK 61  From equation (4), 𝑟4 = 𝑟2 − 𝑟3 𝑞4 = 𝑠2 𝑎 + 𝑡2 𝑏 − (𝑠3 𝑎 + 𝑡3 𝑏)𝑞4 = 𝑠2 −𝑠3 𝑞4 𝑎 + 𝑡2 − 𝑡3 𝑞4 𝑏 = 𝑠4 𝑎 + 𝑡4 𝑏, where 𝑠4 = 𝑠2 −𝑠3 𝑞4 and 𝑡4 = 𝑡2 − 𝑡3 𝑞4. From equation (5), 𝑟5 = 𝑟3 − 𝑟4 𝑞5 = 𝑠3 𝑎 + 𝑡3 𝑏 − (𝑠4 𝑎 + 𝑡4 𝑏)𝑞5 = 𝑠3 −𝑠4 𝑞5 𝑎 + 𝑡3 − 𝑡4 𝑞5 𝑏 = 𝑠5 𝑎 + 𝑡5 𝑏, where 𝑠5 = 𝑠3 −𝑠4 𝑞5 and 𝑡5 = 𝑡3 − 𝑡4 𝑞5. Continuing in this way, from equation (n), 𝑟𝑛 = 𝑟𝑛−2 − 𝑟𝑛−1 𝑞𝑛 = 𝑠𝑛−2 𝑎 + 𝑡𝑛−2 𝑏 − (𝑠𝑛−1 𝑎 + 𝑡𝑛−1 𝑏)𝑞𝑛 = 𝑠𝑛−2 −𝑠𝑛−1 𝑞𝑛 𝑎 + 𝑡𝑛−2 − 𝑡𝑛−1 𝑞𝑛 𝑏 = 𝑠𝑎 + 𝑡𝑏 where 𝑠 = 𝑠𝑛−2 −𝑠𝑛−1 𝑞𝑛 and 𝑡 = 𝑡𝑛−2 − 𝑡𝑛−1 𝑞𝑛. Thus, gcd 𝑎, 𝑏 = 𝑟𝑛 = 𝑠𝑎 + 𝑡𝑏, for some integers 𝑠 and 𝑡. 29 July 2024 NGJDias@FCT-UoK 62  In other words, gcd(𝑎, 𝑏) can be expressed as a linear combination gcd 𝑎, 𝑏 = 𝑠𝑎 + 𝑡𝑏 of 𝑎 and 𝑏 with integer coefficients 𝑠 and 𝑡. Example: Find the greatest common divisor of 414 and 662 using the Euclidean algorithm and express the greatest common divisor as a linear combination of 414 and 662. Successive uses of the division algorithm give: 662 = 414 ∙ 1 + 248 --- (1) 414 = 248 ∙ 1 + 166 --- (2) 248 = 166 ∙ 1 + 82 --- (3) 166 = 82 ∙ 2 + 2 --- (4) 82 = 2 ∙ 41 + 0. Hence, gcd 414,662 = 2, because 2 is the last nonzero remainder. 29 July 2024 NGJDias@FCT-UoK 63  By working backwards from equation (4) to (1) in turn we see that 2 = 166 − 82 ∙ 2 (by (4)) = 166 − (248 − 166 ∙ 1) ∙ 2 (by (3)) = 166 ∙ 3 − 248 ∙ 2 = 414 − 248 ∙ 1 ∙ 3 − 248 ∙ 2 (by (2)) = 414 ∙ 3 − 248 ∙ 5 = 414 ∙ 3 − (662 − 414 ∙ 1) ∙ 5 (by (1)) = 8 ∙ 414 + −5 ∙ 662 Thus, gcd 414,662 = 2 = 𝑠 ∙ 414 + 𝑡 ∙ 662, where 𝑠 = 8 and 𝑡 = −5. Exercise: Find the gcd of the following pairs of integers. 1. 376 and 140 2. 540 and 168 3. 5917 and 1403 Answers: 4,12,61 29 July 2024 NGJDias@FCT-UoK 64 1.6.5 gcds as Linear Combinations An important result we will use throughout the remainder of this section is that the greatest common divisor of two integers 𝑎 and 𝑏 can be expressed in the form 𝑠𝑎 + 𝑡𝑏, where 𝑠 and 𝑡 are integers. In other words, gcd(𝑎, 𝑏) can be expressed as a linear combination gcd 𝑎, 𝑏 = 𝑠𝑎 + 𝑡𝑏 of 𝑎 and 𝑏 with integer coefficients 𝑠 and 𝑡. We state this fact as following Theorem 13. Theorem 14 (Bézout’s Theorem) If a and b are positive integers, then there exist integers 𝑠 and 𝑡 such that gcd 𝑎, 𝑏 = 𝑠𝑎 + 𝑡𝑏. Proof: We have proved this in Section 1.6.4. 29 July 2024 NGJDias@FCT-UoK 65  Definition 9 If 𝑎 and 𝑏 are positive integers, then integers 𝑠 and 𝑡 such that gcd 𝑎, 𝑏 = 𝑠𝑎 + 𝑡𝑏 are called Bézout coefficients of 𝑎 and 𝑏. Also, the equation gcd 𝑎, 𝑏 = 𝑠𝑎 + 𝑡𝑏 is called Bézout’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. 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. Using the next-to-last division (the third division), we can express gcd 252,198 = 18 as a linear combination of 54 and 36. 29 July 2024 NGJDias@FCT-UoK 66  We find that 18 = 54 − 1 ∙ 36. The second division tells us that 36 = 198 − 3 ∙ 54. Substituting this expression for 36 into the previous equation, we can express 18 as a linear combination of 54 and 198. We have 18 = 54 − 1 ∙ 36 = 54 − 1 ∙ 198 − 3 ∙ 54 = 4 ∙ 54 − 1 ∙ 198. The first division tells us that 54 = 252 − 1 ∙ 198. Substituting this expression for 54 into the previous equation, we can express 18 as a linear combination of 252 and 198. We conclude that 18 = 4 ∙ 252 − 1 ∙ 198 − 1 ∙ 198 = 4 ∙ 252 + (−5) ∙ 198, completing the solution. 29 July 2024 NGJDias@FCT-UoK 67  Corollary 2 The two positive integers 𝑎 and 𝑏 are relatively prime if and only if 𝑠𝑎 + 𝑡𝑏 = 1 for some integers 𝑠 and 𝑡. Proof: Suppose that, the two positive integers 𝑎 and 𝑏 are relatively prime. Hence from Theorem 14 (Bézout’s theorem), there exist integers 𝑠 and 𝑡 such that 1 = 𝑠𝑎 + 𝑡𝑏. Conversely, assume that 1 = 𝑠𝑎 + 𝑡𝑏 for some integers 𝑠 and 𝑡. Let 𝑑 = gcd(𝑎, 𝑏). Then 𝑑|𝑎 and 𝑑|𝑏. This implies that, 𝑑|(𝑠𝑎 + 𝑡𝑏), by Theorem 8 part (iii), and so 𝑑|1. Because 𝑑 > 0 and 𝑑|1, it follows that 𝑑 = 1, and so 𝑎 and 𝑏 are relatively prime. 29 July 2024 NGJDias@FCT-UoK 68  Theorem 15 If 𝑎, 𝑏 and 𝑐 are positive integers such that gcd 𝑎, 𝑏 = 1 and 𝑎|𝑏𝑐, then 𝑎|𝑐. Proof: Because gcd 𝑎, 𝑏 = 1, by Corollary 2 there are integers 𝑠 and 𝑡 such that 𝑠𝑎 + 𝑡𝑏 = 1. Multiplying both sides of this equation by 𝑐, we obtain 𝑠𝑎𝑐 + 𝑡𝑏𝑐 = 𝑐. We can now use Theorem 8 of Section 1.3 to show that 𝑎|𝑐. By part (ii) of that theorem, 𝑎|𝑡𝑏𝑐. Because 𝑎|𝑠𝑎𝑐 and 𝑎|𝑡𝑏𝑐, by part (i) of that theorem, we conclude that 𝑎 divides 𝑠𝑎𝑐 + 𝑡𝑏𝑐. Because 𝑠𝑎𝑐 + 𝑡𝑏𝑐 = 𝑐, we conclude that 𝑎|𝑐𝑎, completing the proof. 29 July 2024 NGJDias@FCT-UoK 69  Theorem 16 If 𝑝 is a prime and 𝑝|𝑎𝑏, where 𝑎 and 𝑏 are integers, then either 𝑝|𝑎 or 𝑝|𝑏. Proof: Suppose 𝑝 is a prime and 𝑝|𝑎𝑏. Consider 𝑝 and 𝑎. There are two choices: Either 𝑝|𝑎 or 𝑝 ∤ 𝑎. If 𝑝|𝑎,then the required result is true. Now assume that 𝑝 ∤ 𝑎. Because 𝑝 is prime, the only positive divisors of 𝑝 are 1 and 𝑝. It follows that, gcd 𝑝, 𝑎 = 1. Hence, by Corollary 2, there exit integers 𝑠 and 𝑡 such that 1 = 𝑠𝑝 + 𝑡𝑎. Multiplying both sides by 𝑏, we get 𝑏 = 𝑠𝑝𝑏 + 𝑡𝑎𝑏. --- (1) 29 July 2024 NGJDias@FCT-UoK 70  Now since, 𝑝|𝑎𝑏, there is an integer 𝑘 such that 𝑎𝑏 = 𝑝𝑘. Using this in equation (1) we deduce that 𝑏 = 𝑠𝑝𝑏 + 𝑡𝑝𝑘 = 𝑝 𝑠𝑏 + 𝑡𝑘 = 𝑝𝑥, where 𝑥 = 𝑠𝑏 + 𝑡𝑘 ∈ ℤ. So, 𝑝|𝑏. This completes the proof. Theorem 16 is restricted to only two integers 𝑎 and 𝑏. It can be generalized as follows. Corollary 3 If 𝑝 is a prime and 𝑝|𝑎1 𝑎2 ⋯ 𝑎𝑛 , where each 𝑎𝑖 is an integer, then 𝑝|𝑎𝑖 for some 𝑖. 29 July 2024 NGJDias@FCT-UoK 71