Math 343 Elementary Number Theory Lectures 01-07 PDF

1 MATH 343 Elementary Number Theory The Textbooks: Kenneth H Rosen; Elementary Number Theory and its Applications, 6th Edition, Pearson Publishing Company, 2011. I. Niven, H. S. Zuckerman, and H. L. Montgomery, An Introduction to the The...

1 MATH 343 Elementary Number Theory The Textbooks: Kenneth H Rosen; Elementary Number Theory and its Applications, 6th Edition, Pearson Publishing Company, 2011. I. Niven, H. S. Zuckerman, and H. L. Montgomery, An Introduction to the Theory of Numbers, 5th edition, Wiley, 1991. Underwood Dudley, Elementary Number Theory, 2nd ed., Freeman and Company, 1978 Prof. Jebrel M. Habeb First Semester 2024-2025  2 Chapter 1: Integers Lecture 01 Elementary Number theory is the branch of mathematics that studies the properties of integers ℤ = {... , −2, − 1 , 0, 1 , 2,.... }, and the relationships between them. The natural numbers (positive integers) is denoted by ℤ+ = ℕ = {1, 2, 3,.... }. 𝑎 The rational numbers is denoted by ℚ = { |𝑎, 𝑏 ∈ ℤ, 𝑏 ≠ 0 }. 𝑏 The real numbers is denoted by ℝ. Clearly ℤ+ ⊆ ℤ ⊆ ℚ ⊆ ℝ. Of course, these inclusions are proper. The real number 𝑟 that is not rational is said to be irrational. We will take as known and use freely the usual properties of addition, subtraction, multiplication, division; and order for the integers ℤ. Least-Integer Principle A nonempty set of integers that is bounded below contains a smallest element. Greatest-Integer Principle A nonempty set of integers that is bounded above contains a largest element. The Well-Ordering Principle Every nonempty set of the natural numbers ℕ has a least element. So, we say that the set of positive integers ℤ+ is well ordered. However, the set of all integers ℤ is not well ordered (Why?) Divisibility Definition 1. If 𝑎 and 𝑏 are integers, we say that 𝑎 divides 𝑏 if there is an integer 𝑐 such that 𝑏 = 𝑎𝑐. We write 𝑎|𝑏. If 𝑎 divides 𝑏 we also say that 𝑎 is a divisor or factor of b and that b is a multiple of a. If 𝑎 does not divide 𝑏, we will write 𝑎 ∤ 𝑏. Example, 2|6, 12|60, 17|17, − 5|50, and 8| − 24, 17|0. 4 ∤ 2 and 3 ∤ 4. Exercise. Which integers divide zero? Does 0|0 ?  3 Example. The divisors of 6 are: ± 1, ±2, ±3, ±6. The divisors of 17 are: The divisors of 100 are: 4 2 Find all pairs of positive integers (𝑥, 𝑦), such that + = 1. 𝑥 𝑦 The End of Lecture 01  4 Chapter 1: Integers Lecture 02 (Continuation….) Divisibility Properties: Theorem 1. If 𝑎|𝑏 and 𝑏|𝑐, then 𝑎|𝑐. Proof. Exercise.  Example. Because 11|66 and 66|198, then 11|198. Theorem 2. If 𝑎, 𝑏, 𝑚, and n are integers, and if 𝑐|𝑎 and 𝑐|𝑏, then 𝑐|(𝑚𝑎 + 𝑛𝑏). Proof. Because 𝑐|𝑎 and 𝑐|𝑏, there are integers 𝑒 and 𝑓 such that 𝑎 = 𝑐𝑒 and 𝑏 = 𝑐𝑓. Hence, 𝑚𝑎 + 𝑛𝑏 = 𝑚𝑐𝑒 + 𝑛𝑐𝑓 = 𝑐(𝑚𝑒 + 𝑛𝑓). Consequently, we have 𝑐|(𝑚𝑎 + 𝑛𝑏). Example. As 3|21 and 3| 33, then 5(21) − 3(33) = 105 − 99 = 6. If 𝑚 = 𝑛 = 1 in the Theorem above, we have the following Corollary. If 𝑑|𝑎 and 𝑑|𝑏, then 𝑑| (𝑎 + 𝑏). Corollary. If 𝑑|𝑎1 , 𝑑|𝑎2 ,…, 𝑑|𝑎𝑛 , then 𝑑|(𝑐1 𝑎1 + 𝑐2 𝑎2 +... +𝑐𝑛 𝑎𝑛 ) for any integers 𝑐1 , 𝑐2 ,... , 𝑐𝑛. Exercise. Prove that if 𝑑|𝑎, then 𝑑|𝑐𝑎 for any integer 𝑐. Example. Is it possible to have 100 coins, made up of 𝑐 pennies, 𝑑 dimes, and 𝑞 quarters, be worth exactly $5.00? Solution. If it is possible, then 𝑐 + 𝑑 + 𝑞 = 100 and 𝑐 + 10𝑑 + 25𝑞 = 500. Subtract the first equation from the second and we get 9𝑑 + 24𝑞 = 400. Since 3|9 and 3|24, we have 3|9𝑑 + 24𝑞. That is 3|400. But that is impossible, so having exactly $5.00 is impossible with 100 pennies, dimes, and quarters. Exercise.  5 The End of Lecture 02  6 Chapter 1: Integers Lecture 03 (Continuation….) Greatest Common Divisors Definition 2. We say that the integer d is the greatest common divisor of the two integers a and b (written 𝑑 = 𝑔𝑐𝑑(𝑎, 𝑏) or 𝑑 = (𝑎, 𝑏)) if (i) 𝑑|𝑎 and 𝑑|𝑏, and (ii) if 𝑐|𝑎 and 𝑐|𝑏, then 𝑐 ≤ 𝑑. For example, 𝑔𝑐𝑑(2, 6) = 2 and 𝑔𝑐𝑑(3, 4) = 1. Remarks. (1) The greatest common divisor of 𝑎 and 𝑏 exists and is unique. Why? (2) 𝑔𝑐𝑑(0, 0) is not defined. Why? (3) If 𝑔𝑐𝑑(𝑎, 𝑏) is defined, then it is positive and ≥ 1. Why? Example. (1) The common divisors of 24 and 84 are : and hence 𝑔𝑐𝑑(24, 84) = 12. (2) The common divisors of 15 and 81 are and hence 𝑔𝑐𝑑(15, 81) = 3. (3) The common divisors of −17 and 289 are and hence Exercise. (1) What are (4, 14), (5, 15), and (6, 16)? (2) What is (𝑛, 1), where 𝑛 is any positive integer? What is (𝑛, 0)? What is (𝑛, 1), where 𝑛 is any negative integer? (3) If 𝑑 is a positive integer, what is (𝑑, 𝑛𝑑)? If 𝑑 and n are any integers, what is (𝑑, 𝑛𝑑)? Theorem 3. If (𝑎, 𝑏) = 𝑑, then (𝑎/𝑑, 𝑏/𝑑) = 1. Proof. Suppose that 𝑐 = (𝑎/𝑑, 𝑏/𝑑). We want to show that 𝑐 = 1. We show that 𝑐 ≤ 1 and 𝑐 ≥ 1. Since c is the greatest common divisor of two integers, we have 𝑐 ≥ 1. Now 𝑐|(𝑎/𝑑) and 𝑐|(𝑏/𝑑). So there are integers q and r such that 𝑐𝑞 = 𝑎/𝑑 and 𝑐𝑟 = 𝑏/𝑑. That is, (𝑐𝑑)𝑞 = 𝑎 and (𝑐𝑑)𝑟 = 𝑏. Hence cd is a common divisor of a and b. Thus 𝑐𝑑 ≤ 𝑑. Since d is positive, this gives 𝑐 ≤ 1. Hence 𝑐 = 1.  Definition 3. If (𝑎, 𝑏) = 1, then we will say that 𝑎 and 𝑏 are relatively prime. Example.. Because (25, 42) = 1, 25 and 42 are relatively prime.  7 Exercises. How about if 𝑛 < 0? Find the greatest common divisor of each of the following pairs of integers. a) 15, 35 b) −12, 18 Let 𝑎 be a positive integer. What is the greatest common divisor of 𝑎 and 2𝑎? What is the greatest common divisor of 𝑎 and 𝑎2 ? The End of Lecture 03  8 Chapter 1: Integers Lecture 04 (Continuation….) Theorem 4. The Division Algorithm. Given positive integers a and 𝑏, 𝑏 > 0, there exist unique integers q and r, such that 𝑎 = 𝑏𝑞 + 𝑟, with 0 ≤ 𝑟 < 𝑏 Proof. Consider the set of integers {𝑎, 𝑎 − 𝑏, 𝑎 − 2𝑏, 𝑎 − 3𝑏,... }. It contains a subset of nonnegative integers which is nonempty (Why?) and bounded below (by 0). So, from the least-integer principle, it contains a smallest element. Let it be 𝑎 − 𝑞𝑏. This number is not negative, and it is less than b, (Why?) because if it were greater than b it would not be the smallest nonnegative element in the set: 𝑎 − (𝑞 + 1)𝑏 would be. Let 𝑟 = 𝑎 − 𝑏𝑞: this construction gives us q and r, and it remains to show that they are unique. Suppose that we have found 𝑞, 𝑟 and 𝑞1 , 𝑟1 such that 𝑎 = 𝑏𝑞 + 𝑟 = 𝑏𝑞1 + 𝑟1 with 0 ≤ 𝑟 < 𝑏 and 0 ≤ 𝑟1 < 𝑏. Subtracting, we have 0 = 𝑏(𝑞 − 𝑞1 ) + (𝑟 − 𝑟1 ) Clearly 𝑏|(𝑟 − 𝑟1 ). But −𝑏 < 𝑟 − 𝑟1 < 𝑏. This implies that 𝑟 − 𝑟1 = 0 and hence 𝑟 = 𝑟1. It follows that 𝑞 − 𝑞1 = 0 too, and hence 𝑞 = 𝑞1. Therefore 𝑞 and 𝑟 are unique.  Remark. (1) The theorem is true if 𝑎 (in The Division Algorithm Theorem above) is any integer and 𝑏 ≠ 0. In this case we require 0 ≤ 𝑟 < |𝑏|. (2) a is called the dividend, b the divisor, 𝑞 the quotient and 𝑟 the remainder. Example. If 𝑎 = 133 and b = 21, then q = 6 and r = 7. If 𝑎 = −50 and b = 8, then 𝑞 = − 7 and r = 6. Exercise. What are q and r if a = 75 and b = 24? If a = 75 and b = 25? If 𝑎 = −75 and b = 25? If 𝑎 = −15 and 𝑏 = −4? If a = 23 and 𝑏 = −5? Lemma 1. If 𝑎 = 𝑏𝑞 + 𝑟, then (𝑎, 𝑏) = (𝑏, 𝑟). Proof. Let 𝑑 = (𝑎, 𝑏). Since 𝑑|𝑎 and 𝑑|𝑏 and 𝑟 = 𝑎 − 𝑏𝑞 we have 𝑑|𝑟. Thus d is a common divisor of b and r. Suppose now that c is any common divisor of b and r. Hence 𝑑 ≤ 𝑐 since 𝑐|𝑏 and 𝑐|𝑟, it follows from 𝑎 = 𝑏𝑞 + 𝑟 that 𝑐|𝑎. Thus, c is a common divisor of a and b, and hence 𝑐 ≤ 𝑑. Therefore 𝑑 = (𝑎, 𝑏) = (𝑏, 𝑟) = 𝑐.   9 Exercises. Verify that the Lemma is true when 𝑎 = 16, 𝑏 = 6, and 𝑞 = 2. The End of Lecture 04  10 Chapter 1: Integers Lecture 05 (Continuation….) Theorem 5. The Euclidean Algorithm. If 𝑎 and 𝑏 are nonnegative integers, 𝑏 ≠ 0, and 𝑎 = 𝑏𝑞 + 𝑟, 0 ≤ 𝑟 < 𝑏, 𝑏 = 𝑟𝑞1 + 𝑟1 , 0 ≤ 𝑟1 < 𝑟, 𝑟 = 𝑟1 𝑞2 + 𝑟2 , 0 ≤ 𝑟2 < 𝑟1 ,... 𝑟𝑘 = 𝑟𝑘+1 𝑞𝑘+2 + 𝑟𝑘+2 , 0 ≤ 𝑟𝑘+2 < 𝑟𝑘+1 , then for 𝑘 large enough, say 𝑘 = 𝑡, we have 𝑟𝑡−1 = 𝑟𝑡 𝑞𝑡+1 and 𝑔𝑐𝑑(𝑎, 𝑏) = 𝑟𝑡. Proof. The sequence of nonnegative integers 𝑏 > 𝑟 > 𝑟1 > 𝑟2 > ⋯. must come to an end. Eventually, one of the remainders will be zero. Suppose that it is 𝑟𝑡+1. Then 𝑟𝑡−1 = 𝑟𝑡 𝑞𝑡+1. Applying the Lemma over and over, we have (𝑎, 𝑏) = (𝑏, 𝑟) = (𝑟, 𝑟1 ) = (𝑟1 , 𝑟2 ) =... = (𝑟𝑡−1 , 𝑟𝑡 ) = 𝑟𝑡. If either 𝑎 or 𝑏 is negative, we can use the fact that (𝑎, 𝑏) = (−𝑎, 𝑏) = (𝑎, −𝑏) = (−𝑎, −𝑏).  Exercise. Calculate 𝑔𝑐𝑑(343, 280) and 𝑔𝑐𝑑(578, 442). Theorem 6. (Bezout's Theorem.) If 𝑔𝑐𝑑(𝑎, 𝑏) = 𝑑, then there are integers 𝑥 and 𝑦 such that 𝑎𝑥 + 𝑏𝑦 = 𝑑. Proof. Work the Euclidean Algorithm backward. The details are omitted.  There are two methods to find the integers 𝑥 and 𝑦 in The Euclidean Algorithm Theorem above: Method 1. Using the remainders in the Euclidean Algorithm. Example. Find x and y such that 343𝑥 + 280𝑦 = 𝑔𝑐𝑑(343, 280). Solution. Using the Euclidean Algorithm we have 343 = 280(1) + 63 280 = 63(4) + 28 63 = 28(2) + 7 28 = 7(4) + 0  11 Hence, gcd(343, 280) = 7. Now to find x and y we write the remainder of each step as the difference of the two remaining integers of the same equation. Then substitute the remainder in the previous equation in this equation and so on ….. 7 = 63 − 28(2) 7 = 63 − (2)(280 − 63(4)) = 63(9) − 280(2) 7 = 9(343 − 280) − (2)280 = 343(9) − 280(11) Hence 7 = 343(9) + 280(−11) So, we can take 𝑥 = 9 and 𝑦 = −11. Method 2. Using the quotients in the Euclidean Algorithm. Example. Find x and y such that 343𝑥 + 280𝑦 = (343, 280). Solution. Using the Euclidean Algorithm we have 343 = 280(1) + 63 280 = 63(4) + 28 63 = 28(2) + 7 28 = 7(4) + 0 Hence 𝑔𝑐𝑑(343, 280) = 7. Now to find 𝑥 and 𝑦 we use the quotients of each step as illustrated in the following table: 𝑞1 𝑞2 𝑞3 𝑞4 0 1 𝑞2 × 1 + 0 = 𝑠1 𝑞3 × 𝑠1 + 1 = 𝑠2 𝑞4 × 𝑠2 + 𝑠1 = 𝑥 0 1 𝑞1 × 1 + 0 = 𝑡1 𝑞2 × 𝑡1 + 0 = 𝑡2 𝑞3 × 𝑡2 + 𝑡1 = 𝑡3 𝑞4 × 𝑡3 + 𝑡2 = 𝑦 1 4 2 0 1 4 9=𝑥 0 1 1 5 11 = −𝑦 So, we can take 𝑥 = 9 and 𝑦 = −11. Exercises. and express the greatest common divisor of the integers as a linear combination of these integers. The End of Lecture 05  12 Chapter 1: Integers Lecture 06 (Continuation….) To illustrate the usefulness of the last Theorem, Theorem 6. (Bezout's Theorem.) If (𝑎, 𝑏) = 𝑑, then there are integers 𝑥 and 𝑦 such that 𝑎𝑥 + 𝑏𝑦 = 𝑑. Here are three corollaries. Corollary. If 𝑑|𝑎𝑏 and (𝑑, 𝑎) = 1, then 𝑑|𝑏. Proof. Since d and a are relatively prime, there are integers x and y such that 𝑑𝑥 + 𝑎𝑦 = 1. Multiplying this by b, we have 𝑑(𝑏𝑥) + (𝑎𝑏)𝑦 = 𝑏. The left-hand side is divisible by d, and so b is divisible by b.  Note that if d and a are not relatively prime in this Corollary, the conclusion is false. (Give an example) Corollary. Let (𝑎, 𝑏) = 𝑑, and suppose that 𝑐|𝑎 and 𝑐|𝑏. Then 𝑐|𝑑. Proof. Exercise.  Corollary. If 𝑎|𝑚, 𝑏|𝑚, and (𝑎, 𝑏 ) = 1, then 𝑎𝑏|𝑚. Proof. There is an integer 𝑞 such that 𝑚 = 𝑏𝑞 , and since 𝑎|𝑚 we have 𝑎|𝑏𝑞. But (𝑎, 𝑏) = 1, so we have 𝑎|𝑞. Hence there is an integer r such that 𝑞 = 𝑎𝑟, and thus 𝑚 = 𝑏𝑞 = 𝑎𝑏𝑟. Hence 𝑎𝑏|𝑚.  Theorem 7. (Lame's Theorem). The number of divisions needed to find the greatest common divisor of two positive integers using the Euclidean algorithm does not exceed five times the number of decimal digits in the smaller of the two integers. Proof. Omitted.  Exercise. Apply the Euclidean algorithm how many divisions did you need to find (a) gcd(34, 55) (b) gcd(32, 55) (c) gcd(29, 55) (d) gcd(34,1155) If 𝑝 is a prime, 𝑘 a non-negative integer and 𝑎 is an integer, then 𝑝𝑘 ||𝑎 means 𝑝𝑘 |𝑎 and 𝑝𝑘+1 ∤ 𝑎.  13 The Greatest Integer Function Definition 4. The greatest integer in a real number x, denoted by [𝑥], is the largest integer less than or equal to x. That is, [𝑥] is the integer satisfying [𝑥] ≤ 𝑥 < [𝑥] + 1. Example.We have [5/2] = 2, [−5/2] = −3, [𝜋] = 3, [−2] = −2, and = 0. Note that the greatest integer function is also known as the floor function. Lemma 2. If n is an integer, then [𝑥 + 𝑛] = [𝑥] + 𝑛 whenever 𝑥 is a real number. Proof. Let [𝑥] = 𝑚, so that 𝑚 is an integer. This implies that 𝑚 ≤ 𝑥 < 𝑚 + 1. We can add 𝑛 to this inequality to obtain 𝑚 + 𝑛 ≤ 𝑥 + 𝑛 < 𝑚 + 𝑛 + 1. This shows that 𝑚 + 𝑛 = [𝑥] + 𝑛 is the greatest integer less than or equal to 𝑥 + 𝑛. Hence, [𝑥 + 𝑛] = [𝑥] + 𝑛.  Definition 5. The fractional part of a real number 𝑥, denoted by {𝑥}, is the difference between 𝑥 and the largest integer less than or equal to 𝑥, namely, [𝑥]. That is, {𝑥} = 𝑥 − [𝑥]. Because [𝑥] ≤ 𝑥 < [𝑥] + 1, it follows that 0 ≤ {𝑥} = 𝑥 − [𝑥] < 1 for every real number 𝑥. The greatest integer in 𝑥 is also called the integral part of 𝑥 because 𝑥 = [𝑥] + {𝑥}. Example. Let 𝑎 = 1028 and 𝑏 = 34. Then 𝑎 = 𝑏𝑞 + 𝑟, with 0 ≤ 𝑟 < 𝑏, where 𝑞 = [1028/34] = 30 and 𝑟 = 1028 − [1028/34] · 34 = 1028 − 30 · 34 = 8 < 11111. Example. Let 𝑎 = − 380 and 𝑏 = 75. Then 𝑎 = 𝑏𝑞 + 𝑟 with 0 ≤ 𝑟 < 𝑏, where 𝑞 = [− 380/75] = − 6 and 𝑟 = − 380 − [− 380/75] · 75 = − 380 − (−6)75 = 70. The End of Lecture 06  14 Chapter 1: Integers Lecture 07 Exercises. (Underwood Dudley). Page 19 6. Find two different solutions of 299𝑥 + 247𝑦 = 13. Find all solutions of 299𝑥 + 247𝑦 = 13. Find all positive solutions, if any, 299𝑥 + 247𝑦 = 13. (Rosen Page 20) 25. Without multiplying all the terms, show that a) 6! 7! = 10! c) 16! = 14! 5! 2! b) l 0! =7! 5! 3! d) 9! = − 7! 3! 3! 2!. Q19/111 The End of Lecture 07