Lecture notes on Elementary Number theory

elementary number theory and its applications solutions manual. elementary number theory a collection of problems with solutions pdf free download
WilliamsMcmahon Profile Pic
WilliamsMcmahon,United States,Professional
Published Date:20-07-2017
Your Website URL(Optional)
Comment
An Introductory Course in Elementary Number Theory Wissam Raji2 Preface These notes serve as course notes for an undergraduate course in number the- ory. Most if not all universities worldwide offer introductory courses in number theory for math majors and in many cases as an elective course. The notes contain a useful introduction to important topics that need to be ad- dressed in a course in number theory. Proofs of basic theorems are presented in an interesting and comprehensive way that can be read and understood even by non-majors with the exception in the last three chapters where a background in analysis, measure theory and abstract algebra is required. The exercises are care- fully chosen to broaden the understanding of the concepts. Moreover, these notes shed light on analytic number theory, a subject that is rarely seen or approached by undergraduate students. One of the unique characteristics of these notes is the careful choice of topics and its importance in the theory of numbers. The freedom is given in the last two chapters because of the advanced nature of the topics that are presented. Thanks to professor Pavel Guerzhoy from University of Hawaii for his contri- bution in chapter 6 on continued fraction and to Professor Ramez Maalouf from Notre Dame University, Lebanon for his contribution to chapter 8.Chapter 1 Introduction Integers are the building blocks of the theory of numbers. This chapter contains somewhat very simple and obvious observations starting with properties of inte- gers and yet the proofs behind those observations are not as simple. In this chapter we introduce basic operations on integers and some algebraic definitions that will be necessary to understand basic concepts in this book. We then introduce the Well ordering principle which states basically that every set of positive integers has a smallest element. Proof by induction is also presented as an efficient method for proving several theorems throughout the book. We proceed to define the con- cept of divisibility and the division algorithm. We then introduce the elementary but fundamental concept of a greatest common divisor (gcd) of two integers, and the Euclidean algorithm for finding the gcd of two integers. We end this chap- ter with Lame’s Lemma on an estimate of the number of steps in the Euclidean algorithm needed to find the gcd of two integers. 78 CHAPTER1. INTRODUCTION 1.1 Algebraic Operations With Integers The setZ of all integers, which this book is all about, consists of all positive and negative integers as well as 0. ThusZ is the set given by Z =f:::;4;3;2;1; 0; 1; 2; 3; 4;:::g: (1.1) While the set of all positive integers, denoted byN, is defined by N =f1; 2; 3; 4;:::g: (1.2) OnZ, there are two basic binary operations, namely addition (denoted by +) and multiplication (denoted by), that satisfy some basic properties from which every other property forZ emerges. 1. The Commutativity property for addition and multiplication a +b =b +a ab =ba 2. Associativity property for addition and multiplication (a +b) +c = a + (b +c) (ab)c = a (bc) 3. The distributivity property of multiplication over addition a (b +c) = ab +ac:1.2. THEWELLORDERINGPRINCIPLEANDMATHEMATICALINDUCTION9 In the setZ there are ”identity elements” for the two operations + and, and these are the elements 0 and 1 respectively, that satisfy the basic properties a + 0 = 0 +a =a a 1 = 1a =a for everya2Z. The setZ allows additive inverses for its elements, in the sense that for every a2Z there exists another integer inZ, denoted bya, such that a + (a) = 0: (1.3) While for multiplication, only the integer 1 has a multiplicative inverse in the sense that 1 is the only integera such that there exists another integer, denoted by 1 a or by 1=a, (namely 1 itself in this case) such that 1 aa = 1: (1.4) From the operations of addition and multiplication one can define two other operations onZ, namely subtraction (denoted by) and division (denoted by =). Subtraction is a binary operation onZ, i.e. defined for any two integers inZ, while division is not a binary operation and thus is defined only for some specific couple of integers inZ. Subtraction and division are defined as follows: 1. ab is defined bya + (b), i.e.ab =a + (b) for everya;b2Z 2. a=b is defined by the integerc if and only ifa =bc. 1.2 The Well Ordering Principle and Mathematical Induction In this section, we present three basic tools that will often be used in proving prop- erties of the integers. We start with a very important property of integers called10 CHAPTER1. INTRODUCTION the well ordering principle. We then state what is known as the pigeonhole prin- ciple, and then we proceed to present an important method called mathematical induction. 1.2.1 The Well Ordering Principle The Well Ordering Principle: A least element exist in any non empty set of pos- itive integers. This principle can be taken as an axiom on integers and it will be the key to proving many theorems. As a result, we see that any set of positive integers is well ordered while the set of all integers is not well ordered. 1.2.2 The Pigeonhole Principle The Pigeonhole Principle: Ifs objects are placed ink boxes fors k, then at least one box contains more than one object. Proof. Suppose that none of the boxes contains more than one object. Then there are at mostk objects. This leads to a contradiction with the fact that there ares objects forsk. 1.2.3 The Principle of Mathematical Induction We now present a valuable tool for proving results about integers. This tool is the principle of mathematical induction . Theorem 1. The First Principle of Mathematical Induction: If a set of positive integers has the property that, if it contains the integer k, then it also contains1.2. THEWELLORDERINGPRINCIPLEANDMATHEMATICALINDUCTION11 k + 1, and if this set contains 1 then it must be the set of all positive integers. More generally, a property concerning the positive integers that is true forn = 1, and that is true for the integern + 1 whenever it is true for the integern, must be true for all positive integers. We use the well ordering principle to prove the first principle of mathematical induction Proof. LetS be the set of positive integers containing the integer 1, and the integer k + 1 whenever it contains k. Assume also that S is not the set of all positive integers. As a result, there are some integers that are not contained inS and thus those integers must have a least element by the well ordering principle. Notice that 6= 1 since 12S. But 12S and thus using the property ofS, 2S. ThusS must contain all positive integers. We now present some examples in which we use the principle of induction. Example 1. Use mathematical induction to show that8n2N n X n(n + 1) j = : (1.5) 2 j=1 First note that 1 X 1 2 j = 1 = 2 j=1 and thus the the statement is true for n = 1. For the remaining inductive step, P n n(n+1) suppose that the formula holds forn, that is j = . We show that j=1 2 n+1 X (n + 1)(n + 2) j = : 2 j=1 to complete the proof by induction. Indeed n+1 n X X n(n + 1) (n + 1)(n + 2) j = j + (n + 1) = + (n + 1) = ; 2 2 j=1 j=1 and the result follows.12 CHAPTER1. INTRODUCTION n Example 2. Use mathematical induction to prove that n n for all positive integersn. 1 Note that 1 = 1 1 = 1. We now present the inductive step. Suppose that n nn n+1 for somen, we prove that (n + 1) (n + 1) . Note that n n n+1 (n + 1) = (n + 1)n (n + 1):n (n + 1)(n + 1) = (n + 1) : This completes the proof. Theorem 2. TheSecondPrincipleofMathematicalInduction: A set of positive integers that has the property that for every integerk, if it contains all the integers 1 throughk then it containsk + 1 and if it contains 1 then it must be the set of all positive integers. More generally, a property concerning the positive integers that is true forn = 1, and that is true for all integers up ton + 1 whenever it is true for all integers up ton, must be true for all positive integers. The second principle of induction is also known as the principle of strong induction. Also, the first principle of induction is known as the principle of weak induction. To prove the second principle of induction, we use the first principle of induc- tion. Proof. Let T be a set of integers containing 1 and such that for every positive integerk, if it contains 1; 2;:::;k, then it containsk + 1. LetS be the set of all positive integersk such that all the positive integers less than or equal tok are in T . Then 1 is inS, and we also see thatk + 1 is inS. ThusS must be the set of all positive integers. ThusT must be the set of all positive integers sinceS is a subset ofT .1.3. DIVISIBILITYANDTHEDIVISIONALGORITHM 13 Exercises n 1. Prove using mathematical induction thatn 3 for all positive integersn. P n n(n+1)(2n+1) 2 2. Show that j = . j=1 6 P n j1 2 n1 3. Use mathematical induction to prove that (1) j = (1) n(n+ j=1 1)=2. P n 3 2 4. Use mathematical induction to prove that j = n(n+1)=2 for every j=1 positive integern. P n 2 5. Use mathematical induction to prove that (2j 1) =n j=1 n 6. Use mathematical induction to prove that 2 n forn 4. 2 7. Use mathematical induction to prove thatn n forn 4. 1.3 Divisibility and the Division Algorithm We now discuss the concept of divisibility and its properties. 1.3.1 Integer Divisibility Definition 1. Ifa andb are integers such thata =6 0, then we say ”a dividesb” if there exists an integerk such thatb =ka. Ifa dividesb, we also say ”a is a factor ofb” or ”b is a multiple ofa” and we writeaj b. Ifa doesn’t divideb, we writea - b. For example 2j 4 and 7j 63, while 5- 26. Example 3. a) Note that any even integer has the form 2k for some integer k, while any odd integer has the form 2k + 1 for some integer k. Thus 2jn if n is even, while 2-n ifn is odd.14 CHAPTER1. INTRODUCTION b)8a2Z one has thataj 0. c) Ifb2Z is such thatjbja, andb =6 0, thena-b. Theorem 3. Ifa;b andc are integers such thatajb andbjc, thenajc. Proof. Sinceajb andbjc, then there exist integersk andk such thatb =k a 1 2 1 andc =k b. As a result, we havec =k k a and henceajc. 2 1 2 Example 4. Since 6j 18 and 18j 36, then 6j 36. The following theorem states that if an integer divides two other integers then it divides any linear combination of these integers. Theorem 4. If a;b;c;m and n are integers, and if c j a and c j b, then c j (ma +nb). Proof. Since cj a and cj b, then by definition there exists k and k such that 1 2 a =k c andb =k c. Thus 1 2 ma +nb =mk c +nk c =c(mk +nk ); 1 2 1 2 and hencecj (ma +nb). Theorem 4 can be generalized to any finite linear combination as follows. If ajb ;ajb ;:::;ajb 1 2 n then n X aj k b (1.6) j j j=1 for any set of integersk ; ;k 2 Z. It would be a nice exercise to prove the 1 n generalization by induction.1.3. DIVISIBILITYANDTHEDIVISIONALGORITHM 15 1.3.2 The Division Algorithm The following theorem states somewhat an elementary but very useful result. Theorem 5. TheDivisionAlgorithm Ifa andb are integers such thatb 0, then there exist unique integersq andr such thata =bq +r where 0rb. Proof. Consider the setA =fabk 0j k2 Zg. Note thatA is nonempty since for k a=b, abk 0. By the well ordering principle, A has a least elementr =abq for someq. Notice thatr 0 by construction. Now ifrb then (sinceb 0) rrb =abqb =ab(q + 1) = 0: This leads to a contradiction sincer is assumed to be the least positive integer of the formr =abq. As a result we have 0rb. We will show that q and r are unique. Suppose that a = bq +r and a = 1 1 bq +r with 0r b and 0r b. Then we have 2 2 1 2 b(q q ) + (r r ) = 0: 1 2 1 2 As a result we have b(q q ) =r r : 1 2 2 1 Thus we get that bj (r r ): 2 1 And since max(r ;r )jr rj max(r ;r ), andb max(r ;r ), then 1 2 2 1 1 2 1 2 r r must be 0, i.e. r = r . And sincebq +r = bq +r , we also get that 2 1 2 1 1 1 2 2 q =q . This proves uniqueness. 1 2 Example 5. Ifa = 71 andb = 6, then 71 = 6 11 + 5. Hereq = 11 andr = 5. Exercises 1. Show that 5j 25; 19j 38 and 2j 98.16 CHAPTER1. INTRODUCTION 2. Use the division algorithm to find the quotient and the remainder when 76 is divided by 13. 3. Use the division algorithm to find the quotient and the remainder when -100 is divided by 13. 4. Show that ifa;b;c andd are integers witha andc nonzero, such thataj b andcjd, thenacjbd. 5. Show that ifa andb are positive integers andajb, thenab. 6. Prove that the sum of two even integers is even, the sum of two odd integers is even and the sum of an even integer and an odd integer is odd. 7. Show that the product of two even integers is even, the product of two odd integers is odd and the product of an even integer and an odd integer is even. 3 8. Show that ifm is an integer then 3 dividesm m. 9. Show that the square of every odd integer is of the form 8m + 1. 10. Show that the square of any integer is of the form 3m or 3m + 1 but not of the form 3m + 2. 11. Show that ifacjbc, thenajb. 12. Show that ifajb andbja thena =b. 1.4 Representations of Integers in Different Bases In this section, we show how any positive integer can be written in terms of any positive base integer expansion in a unique way. Normally we use decimal nota- tion to represent integers, we will show how to convert an integer from decimal notation into any other positive base integer notation and vise versa. Using the1.4. REPRESENTATIONSOFINTEGERSINDIFFERENTBASES 17 decimal notation in daily life is simply better because we have ten fingers which facilitates all the mathematical operations. Notation An integera written in baseb expansion is denoted by (a) . b Theorem 6. Letb be a positive integer withb 1. Then any positive integerm can be written uniquely as l l1 m =ab +a b +::: +a b +a ; l l1 1 0 wherel is a positive integer, 0a b forj = 0; 1;:::;l anda =6 0. j l Proof. We start by dividingm byb and we get m =bq +a ; 0a b: 0 0 0 Ifq =6 0 then we continue to divideq byb and we get 0 0 q =bq +a ; 0a b: 0 1 1 1 We continue this process and hence we get q = bq +a ; 0a b; 1 2 2 2 : : : q = bq +a ; 0a b; l2 l1 l1 l1 q = b 0 +a; 0a b: l1 l l Note that the sequenceq ;q ;::: is a decreasing sequence of positive integers with 0 1 a last termq that must be 0. l Now substituting the equationq =bq +a inm =bq +a , we get 0 1 1 0 0 2 m =b(bq +a ) +a =b q +a b +a ; 1 1 0 1 1 018 CHAPTER1. INTRODUCTION Successively substituting the equations inm, we get 3 2 m = b q +a b +a b +a ; 2 2 1 0 : : : l l1 = bq +a b +::: +a b +a ; l1 l1 1 0 l l1 = ab +a b +::: +a b +a : l l1 1 0 What remains to prove is that the representation is unique. Suppose now that l l1 l l1 m =ab +a b +::: +a b +a =cb +c b +::: +c b +c l l1 1 0 l l1 1 0 where if the number of terms is different in one expansion, we add zero coeffi- cients to make the number of terms agree. Subtracting the two expansions, we get l l1 (ac )b + (a c )b +::: + (a c )b + (a c ) = 0: l l l1 l1 1 1 0 0 If the two expansions are different, then there exists 0jl such thatc =6 a . j j As a result, we get j lj b ((ac )b +::: + (a c )b + (a c )) = 0 l l j+1 j+1 j j and sinceb6= 0, we get lj (ac )b +::: + (a c )b + (a c ) = 0: l l j+1 j+1 j j We now get lj a c = (ac )b +::: + (a c )b; j j l l j+1 j+1 and as a result, bj (a c ). Since 0 a b and 0 c b, we get that j j j j a =c . This is a contradiction and hence the expansion is unique. j j1.4. REPRESENTATIONSOFINTEGERSINDIFFERENTBASES 19 Note that base 2 representation of integers is called binary representation. Bi- nary representation plays a crucial role in computers. Arithmetic operations can be carried out on integers with any positive integer base but it will not be addressed in this book. We now present examples of how to convert from decimal integer representation to any other base representation and vise versa. Example 6. To find the expansion of 214 base 3: we do the following 214 = 3 71 + 1 71 = 3 23 + 2 23 = 3 7 + 2 7 = 3 2 + 1 2 = 3 0 + 2 As a result, to obtain a base 3 expansion of 214, we take the remainders of divi- sions and we get that (214) = (21221) . 10 3 Example 7. To find the base 10 expansion, i.e. the decimal expansion, of (364) : 7 0 1 2 We do the following: 4 7 + 6 7 + 3 7 = 4 + 42 + 147 = 193. In some cases where baseb 10 expansion is needed, we add some characters to represent numbers greater than 9. It is known to use the alphabetic letters to denote integers greater than 9 in base b expansion for b 10. For example (46BC29) whereA = 10;B = 11;C = 12. 13 To convert from one base to the other, the simplest way is to go through base 10 and then convert to the other base. There are methods that simplify conversion from one base to the other but it will not be addressed in this book. Exercises20 CHAPTER1. INTRODUCTION 1. Convert (7482) to base 6 notation. 10 2. Convert (98156) to base 8 notation. 10 3. Convert (101011101) to decimal notation. 2 4. Convert (AB6C7D) to decimal notation. 16 5. Convert (9A0B) to binary notation. 16 1.5 The Greatest Common Divisor In this section we define the greatest common divisor (gcd) of two integers and discuss its properties. We also prove that the greatest common divisor of two integers is a linear combination of these integers. Two integersa andb, not both 0, can have only finitely many divisors, and thus can have only finitely many common divisors. In this section, we are interested in the greatest common divisor ofa andb. Note that the divisors ofa and that of jaj are the same. Definition 2. The greatest common divisor of two integersa andb is the greatest integer that divides botha andb. We denote the greatest common divisor of two integersa andb by (a;b). We also define (0; 0) = 0. Example 8. Note that the greatest common divisor of 24 and 18 is 6. In other words (24; 18) = 6. There are couples of integers (e.g. 3 and 4, etc...) whose greatest common divisor is 1 so we call such integers relatively prime integers. Definition 3. Two integersa andb are relatively prime if (a;b) = 1.1.5. THEGREATESTCOMMONDIVISOR 21 Example 9. The greatest common divisor of 9 and 16 is 1, thus they are relatively prime. Note that every integer has positive and negative divisors. If a is a positive divisor ofm, thena is also a divisor ofm. Therefore by our definition of the greatest common divisor, we can see that (a;b) = (jaj;jbj). We now present a theorem about the greatest common divisor of two integers. The theorem states that if we divide two integers by their greatest common divisor, then the outcome is a couple of integers that are relatively prime. Theorem 7. If (a;b) =d then (a=d;b=d) = 1. Proof. We will show that a=d and b=d have no common positive divisors other than 1. Assume thatk is a positive common divisor such thatkja=d andkjb=d. As a result, there are two positive integersm andn such that a=d =km and b=d =kn Thus we get that a =kmd and b =knd: Hencekd is a common divisor of botha andb. Also,kd d. However,d is the greatest common divisor ofa andb. As a result, we get thatk = 1. The next theorem shows that the greatest common divisor of two integers does not change when we add a multiple of one of the two integers to the other. Theorem 8. Leta;b andc be integers. Then (a;b) = (a +cb;b). Proof. We will show that every divisor ofa andb is also a divisor ofa +cb and b and vise versa. Hence they have exactly the same divisors. So we get that the greatest common divisor ofa andb will also be the greatest common divisor of a +cb andb. Letk be a common divisor ofa andb. By Theorem 4,kj (a +cb)22 CHAPTER1. INTRODUCTION and hencek is a divisor ofa+cb. Now assume thatl is a common divisor ofa+cb andb. Also by Theorem 4 we have , lj ((a +cb)cb) =a: As a result,l is a common divisor ofa andb and the result follows. Example 10. Notice that (4; 14) = (4; 14 3 4) = (4; 2) = 2. We now present a theorem which proves that the greatest common divisor of two integers can be written as a linear combination of the two integers. Theorem 9. The greatest common divisor of two integersa andb, not both 0 is the least positive integer such thatma +nb =d for some integersm andn. Proof. Assume without loss of generality thata andb are positive integers. Con- sider the set of all positive integer linear combinations ofa andb. This set is non empty sincea = 1a + 0b andb = 0a + 1b are both in this set. Thus this set has a least elementd by the well-ordering principle. Thusd =ma +nb for some integersm andn. We have to prove thatd divides botha andb and that it is the greatest divisor ofa andb. By the division algorithm, we have a =dq +r; 0rd: Thus we have r =adq =aq(ma +nb) = (1qm)aqnb: We then have thatr is a linear combination ofa andb. Since 0 r d andd is the least positive integer which is a linear combination ofa andb, thenr = 0 anda = dq. Hencedj a. Similarlydj b. Now notice that if there is a divisor c that divides botha andb. Thenc divides any linear combination ofa andb by Theorem 4. Hencecjd. This proves that any common divisor ofa andb divides d. Hencecd, andd is the greatest divisor.1.5. THEGREATESTCOMMONDIVISOR 23 As a result, we conclude that if (a;b) = 1 then there exist integersm andn such thatma +nb = 1. Definition 4. Leta ;a ;:::;a be integers, not all 0. The greatest common divisor 1 2 n of these integers is the largest integer that divides all of the integers in the set. The greatest common divisor ofa ;a ;:::;a is denoted by (a ;a ;:::;a ). 1 2 n 1 2 n Definition 5. The integersa ;a ;:::;a are said to be mutually relatively prime if 1 2 n (a ;a ;:::;a ) = 1. 1 2 n Example 11. The integers 3; 6; 7 are mutually relatively prime since (3; 6; 7) = 1 although (3; 6) = 3. Definition 6. The integersa ;a ;:::;a are called pairwise prime if for eachi6=j, 1 2 n we have (a;a ) = 1. i j Example 12. The integers 3; 14; 25 are pairwise relatively prime. Notice also that these integers are mutually relatively prime. Notice that ifa ;a ;:::;a are pairwise relatively prime then they are mutually 1 2 n relatively prime. Exercises 1. Find the greatest common divisor of 15 and 35. 2. Find the greatest common divisor of 100 and 104. 3. Find the greatest common divisor of -30 and 95. 4. Let m be a positive integer. Find the greatest common divisor of m and m + 1.24 CHAPTER1. INTRODUCTION 5. Let m be a positive integer, find the greatest common divisor of m and m + 2. 6. Show that ifm andn are integers such that (m;n) = 1, then (m+n,m-n)=1 or 2. 7. Show that ifm is a positive integer, then 3m + 2 and 5m + 3 are relatively prime. 8. Show that ifa andb are relatively prime integers, then (a+2b; 2a+b) = 1or 3. 9. Show that if a ;a ;:::;a are integers that are not all 0 and c is a positive 1 2 n integer, then (ca ;ca ;:::;ca ) =c(a ;a ;:::a ): 1 2 n 1 2 n 1.6 The Euclidean Algorithm In this section we describe a systematic method that determines the greatest com- mon divisor of two integers. This method is called the Euclidean algorithm. Lemma 1. If a and b are two integers and a = bq +r where also q and r are integers, then (a;b) = (r;b). Proof. Note that by theorem 8, we have (bq +r;b) = (b;r). The above lemma will lead to a more general version of it. We now present the Euclidean algorithm in its general form. It states that the greatest common divisor of two integers is the last non zero remainder of the successive division. Theorem 10. Leta = r andb = r be two positive integers wherea b. If we 0 1 apply the division algorithm successively to obtain that r =r q +r where 0r r j j+1 j+1 j+2 j+2 j+1

Advise: Why You Wasting Money in Costly SEO Tools, Use World's Best Free SEO Tool Ubersuggest.