2.2.THE DIVISION ALGORITHM 25 2.2 The Division Algorithm An application of the Principle of Well-Ordering that we will use often is the division algorithm. Theorem 2.9 Division Algorithm.Let a and b be integers,with b>0.Then there exist unique integers g and r such that a=bq+r where0≤r<b. PROOF.This is a perfect example of the existence-and-uniqueness type of proof.We must first prove that the numbers g and r actually exist.Then we must show that if g'and r' are two other such numbers,then g=g'and r=r. Eristence of q and r.Let S={a-bk:k∈Z and a-bk≥0} If 0ES,then b divides a,and we can let g=a/b and r=0.If 0,we can use the Well- Ordering Principle.We must first show that S is nonempty.If a >0,then a-b.0 S. If a <0,then a-b(2a)=a(1-26)E S.In either case S0.By the Well-Ordering Principle,S must have a smallest member,say r =a-bg.Therefore,a =bg+r,r>0. We now show that r<b.Suppose that r >b.Then a-b(q+1)=a-bq-b=r-b>0. In this case we would have a-b(q+1)in the set S.But then a-b(g+1)<a-bg,which would contradict the fact that r a-bg is the smallest member of S.So r <b.Since 0tS,r≠b and so r<b. Uniqueness of q and r.Suppose there exist integers r,r',q,and q'such that a=bg+r,0≤r<b and a=bg+r',0≤r<b. Then bg+r =ba'+r'.Assume that r'>r.From the last equation we have b(q-g)=r'-r; therefore,b must divide r'-r and 0<r'-r<r'<b.This is possible only if r-r=0. Hence,r=r'and g=g'. 口 Let a and b be integers.If b ak for some integer k,we write a b.An integer d is called a common divisor of a and b if d a and db.The greatest common divisor of integers a and b is a positive integer d such that d is a common divisor of a and b and if d' is any other common divisor of a and b,then d'd.We write d=gcd(a,b);for example, gcd(24,36)=12 and gcd(120,102)=6.We say that two integers a and b are relatively prime if gcd(a,b)=1. Theorem 2.10.Let a and b be nonzero integers.Then there exist integers r and s such that gcd(a,b)=ar+bs Furthermore,the greatest common divisor of a and b is unique. PROOF.Let S=fam +bn m,n EZ and am+bn >0. Clearly,the set S is nonempty;hence,by the Well-Ordering Principle S must have a smallest member,say d=ar +bs.We claim that d =gcd(a,b).Write a=dg+r'where 0<r'<d. If r>0,then r'=a-dq
2.2. THE DIVISION ALGORITHM 25 2.2 The Division Algorithm An application of the Principle of Well-Ordering that we will use often is the division algorithm. Theorem 2.9 Division Algorithm. Let a and b be integers, with b > 0. Then there exist unique integers q and r such that a = bq + r where 0 ≤ r < b. Proof. This is a perfect example of the existence-and-uniqueness type of proof. We must first prove that the numbers q and r actually exist. Then we must show that if q ′ and r ′ are two other such numbers, then q = q ′ and r = r ′ . Existence of q and r. Let S = {a − bk : k ∈ Z and a − bk ≥ 0}. If 0 ∈ S, then b divides a, and we can let q = a/b and r = 0. If 0 /∈ S, we can use the WellOrdering Principle. We must first show that S is nonempty. If a > 0, then a − b · 0 ∈ S. If a < 0, then a − b(2a) = a(1 − 2b) ∈ S. In either case S ̸= ∅. By the Well-Ordering Principle, S must have a smallest member, say r = a − bq. Therefore, a = bq + r, r ≥ 0. We now show that r < b. Suppose that r > b. Then a − b(q + 1) = a − bq − b = r − b > 0. In this case we would have a − b(q + 1) in the set S. But then a − b(q + 1) < a − bq, which would contradict the fact that r = a − bq is the smallest member of S. So r ≤ b. Since 0 /∈ S, r ̸= b and so r < b. Uniqueness of q and r. Suppose there exist integers r, r ′ , q, and q ′ such that a = bq + r, 0 ≤ r < b and a = bq′ + r ′ , 0 ≤ r ′ < b. Then bq+r = bq′+r ′ . Assume that r ′ ≥ r. From the last equation we have b(q−q ′ ) = r ′−r; therefore, b must divide r ′ − r and 0 ≤ r ′ − r ≤ r ′ < b. This is possible only if r ′ − r = 0. Hence, r = r ′ and q = q ′ . Let a and b be integers. If b = ak for some integer k, we write a | b. An integer d is called a common divisor of a and b if d | a and d | b. The greatest common divisor of integers a and b is a positive integer d such that d is a common divisor of a and b and if d ′ is any other common divisor of a and b, then d ′ | d. We write d = gcd(a, b); for example, gcd(24, 36) = 12 and gcd(120, 102) = 6. We say that two integers a and b are relatively prime if gcd(a, b) = 1. Theorem 2.10. Let a and b be nonzero integers. Then there exist integers r and s such that gcd(a, b) = ar + bs. Furthermore, the greatest common divisor of a and b is unique. Proof. Let S = {am + bn : m, n ∈ Z and am + bn > 0}. Clearly, the set S is nonempty; hence, by the Well-Ordering Principle S must have a smallest member, say d = ar + bs. We claim that d = gcd(a, b). Write a = dq + r ′ where 0 ≤ r ′ < d. If r ′ > 0, then r ′ = a − dq
26 CHAPTER 2.THE INTEGERS =a-（(ar+bs)q a-arq-bsq =a(1-rq)+b(-sq), which is in S.But this would contradict the fact that d is the smallest member of S.Hence, r'=0 and d divides a.A similar argument shows that d divides b.Therefore,d is a common divisor of a and b. Suppose that d'is another common divisor of a and b,and we want to show that d'd. If we let a d'h and b=d'k,then d=ar +bs d'hr+d'ks =d'(hr +ks). So d'must divide d.Hence,d must be the unique greatest common divisor of a and b. Corollary 2.11.Let a and b be two integers that are relatively prime.Then there exist integers r and s such that ar+bs =1. The Euclidean Algorithm Among other things,Theorem 2.10 allows us to compute the greatest common divisor of two integers. Example 2.12.Let us compute the greatest common divisor of 945 and 2415.First observe that 2415=945·2+525 945=525·1+420 525=420.1+105 420=105·4+0. Reversing our steps,105 divides 420,105 divides 525,105 divides 945,and 105 divides 2415. Hence,105 divides both 945 and 2415.If d were another common divisor of 945 and 2415, then d would also have to divide 105.Therefore,gcd(945,2415)=105. If we work backward through the above sequence of equations,we can also obtain numbers r and s such that 945r+2415s 105.Observe that 105=525+(-1)·420 =525+(-1).[945+(-1)·525] =2.525+(-1).945 =2.[2415+(-2).945]+(-1).945 =2.2415+(-5).945. So r =-5 and s=2.Notice that r and s are not unique,since r=41 and s=-16 would also work. To compute gcd(a,b)=d,we are using repeated divisions to obtain a decreasing se- quence of positive integers r1>r2>..>rn=d;that is, b=agi+ri a=T192+T2 T1=T2q3十T3
26 CHAPTER 2. THE INTEGERS = a − (ar + bs)q = a − arq − bsq = a(1 − rq) + b(−sq), which is in S. But this would contradict the fact that d is the smallest member of S. Hence, r ′ = 0 and d divides a. A similar argument shows that d divides b. Therefore, d is a common divisor of a and b. Suppose that d ′ is another common divisor of a and b, and we want to show that d ′ | d. If we let a = d ′h and b = d ′k, then d = ar + bs = d ′hr + d ′ ks = d ′ (hr + ks). So d ′ must divide d. Hence, d must be the unique greatest common divisor of a and b. Corollary 2.11. Let a and b be two integers that are relatively prime. Then there exist integers r and s such that ar + bs = 1. The Euclidean Algorithm Among other things, Theorem 2.10 allows us to compute the greatest common divisor of two integers. Example 2.12. Let us compute the greatest common divisor of 945 and 2415. First observe that 2415 = 945 · 2 + 525 945 = 525 · 1 + 420 525 = 420 · 1 + 105 420 = 105 · 4 + 0. Reversing our steps, 105 divides 420, 105 divides 525, 105 divides 945, and 105 divides 2415. Hence, 105 divides both 945 and 2415. If d were another common divisor of 945 and 2415, then d would also have to divide 105. Therefore, gcd(945, 2415) = 105. If we work backward through the above sequence of equations, we can also obtain numbers r and s such that 945r + 2415s = 105. Observe that 105 = 525 + (−1) · 420 = 525 + (−1) · [945 + (−1) · 525] = 2 · 525 + (−1) · 945 = 2 · [2415 + (−2) · 945] + (−1) · 945 = 2 · 2415 + (−5) · 945. So r = −5 and s = 2. Notice that r and s are not unique, since r = 41 and s = −16 would also work. To compute gcd(a, b) = d, we are using repeated divisions to obtain a decreasing sequence of positive integers r1 > r2 > · · · > rn = d; that is, b = aq1 + r1 a = r1q2 + r2 r1 = r2q3 + r3
2.2.THE DIVISION ALGORITHM 27 Tn-2 Tn-19n +Tn Tn-1 Tnqn+1. To find r and s such that ar +bs d,we begin with this last equation and substitute results obtained from the previous equations: d=Tn =Tn-2-Tn-19n =Tn-2-9n(Tn-3 -9n-1Tn-2) =-gnTn-3+(1+gngn-1)rn-2 ra+sb. The algorithm that we have just used to find the greatest common divisor d of two integers a and b and to write d as the linear combination of a and b is known as the Euclidean algorithm. Prime Numbers Let p be an integer such that p >1.We say that p is a prime number,or simply p is prime,if the only positive numbers that divide p are 1 and p itself.An integer n>1 that is not prime is said to be composite. Lemma 2.13 Euclid.Let a and b be integers and p be a prime number.If p ab,then either p a or pb. PROOF.Suppose that p does not divide a.We must show that pb.Since gcd(a,p)=1, there exist integers r and s such that ar+ps =1.So b=b(ar +ps)=(ab)r +p(bs). Since p divides both ab and itself,p must divide b=(ab)r+p(bs). 口 Theorem 2.14 Euclid.There erist an infinite number of primes. PROOF.We will prove this theorem by contradiction.Suppose that there are only a finite number of primes,say p1,p2,...,Pn.Let P=pip2...Pn+1.Then P must be divisible by some pi for 1<i<n.In this case,pi must divide P-pip2...Pn =1,which is a contradiction.Hence,either P is prime or there exists an additional prime number p pi that divides P. ☐ Theorem 2.15 Fundamental Theorem of Arithmetic.Let n be an integer such that n>1.Then n=p1p2··Pk, where p1,...,Pk are primes (not necessarily distinct).Furthermore,this factorization is unique;that is,if n=q192…9l, then k=l and the qi's are just the pi's rearranged
2.2. THE DIVISION ALGORITHM 27 . . . rn−2 = rn−1qn + rn rn−1 = rnqn+1. To find r and s such that ar + bs = d, we begin with this last equation and substitute results obtained from the previous equations: d = rn = rn−2 − rn−1qn = rn−2 − qn(rn−3 − qn−1rn−2) = −qnrn−3 + (1 + qnqn−1)rn−2 . . . = ra + sb. The algorithm that we have just used to find the greatest common divisor d of two integers a and b and to write d as the linear combination of a and b is known as the Euclidean algorithm. Prime Numbers Let p be an integer such that p > 1. We say that p is a prime number, or simply p is prime, if the only positive numbers that divide p are 1 and p itself. An integer n > 1 that is not prime is said to be composite. Lemma 2.13 Euclid. Let a and b be integers and p be a prime number. If p | ab, then either p | a or p | b. Proof. Suppose that p does not divide a. We must show that p | b. Since gcd(a, p) = 1, there exist integers r and s such that ar + ps = 1. So b = b(ar + ps) = (ab)r + p(bs). Since p divides both ab and itself, p must divide b = (ab)r + p(bs). Theorem 2.14 Euclid. There exist an infinite number of primes. Proof. We will prove this theorem by contradiction. Suppose that there are only a finite number of primes, say p1, p2, . . . , pn. Let P = p1p2 · · · pn + 1. Then P must be divisible by some pi for 1 ≤ i ≤ n. In this case, pi must divide P − p1p2 · · · pn = 1, which is a contradiction. Hence, either P is prime or there exists an additional prime number p ̸= pi that divides P. Theorem 2.15 Fundamental Theorem of Arithmetic. Let n be an integer such that n > 1. Then n = p1p2 · · · pk, where p1, . . . , pk are primes (not necessarily distinct). Furthermore, this factorization is unique; that is, if n = q1q2 · · · ql , then k = l and the qi’s are just the pi’s rearranged
28 CHAPTER 2.THE INTEGERS PROOF.Uniqueness.To show uniqueness we will use induction on n.The theorem is certainly true for n =2 since in this case n is prime.Now assume that the result holds for all integers m such that 1 m<n,and n=pP1P2·…Pk=q192·9L, where p1≤p2≤·≤Pk and q1≤q2≤·≤ql.By Lemma2.l3,p1|qi for some i=1,...,l and g I pj for somej=1,...,k.Since all of the pi's and qi's are prime,pi=qi and g1 =pj.Hence,p1=g1 since p1 <pi=q<qi=p1.By the induction hypothesis, n=p2…pk=q2…qL has a unique factorization.Hence,k=l and qi pi for i=1,...,k. Eristence.To show existence,suppose that there is some integer that cannot be written as the product of primes.Let S be the set of all such numbers.By the Principle of Well- Ordering,S has a smallest number,say a.If the only positive factors of a are a and 1,then a is prime,which is a contradiction.Hence,a aia2 where 1 <a1 a and 1 <a2 a. Neither aE S nor a2 E S,since a is the smallest element in S.So a1=p1…Pr a2=q1…9s. Therefore, a=a1a2=p1…Prq1·9s: So aS,which is a contradiction. 口 Historical Note Prime numbers were first studied by the ancient Greeks.Two important results from antiquity are Euclid's proof that an infinite number of primes exist and the Sieve of Eratos- thenes,a method of computing all of the prime numbers less than a fixed positive integer n.One problem in number theory is to find a function f such that f(n)is prime for each integer n.Pierre Fermat (1601?-1665)conjectured that 22"+1 was prime for all n,but later it was shown by Leonhard Euler (1707-1783)that 22+1=4,294,967,297 is a composite number.One of the many unproven conjectures about prime numbers is Goldbach's Conjecture.In a letter to Euler in 1742,Christian Goldbach stated the conjec- ture that every even integer with the exception of 2 seemed to be the sum of two primes: 4 =2+2,6 =3+3,8=3+5,....Although the conjecture has been verified for the numbers up through 4x 1018,it has yet to be proven in general.Since prime numbers play an important role in public key cryptography,there is currently a great deal of interest in determining whether or not a large number is prime. 2.3 Exercises 1.Prove that 12+22+.+n2=nn+1)2n+1 6 forn∈N
28 CHAPTER 2. THE INTEGERS Proof. Uniqueness. To show uniqueness we will use induction on n. The theorem is certainly true for n = 2 since in this case n is prime. Now assume that the result holds for all integers m such that 1 ≤ m < n, and n = p1p2 · · · pk = q1q2 · · · ql , where p1 ≤ p2 ≤ · · · ≤ pk and q1 ≤ q2 ≤ · · · ≤ ql . By Lemma 2.13, p1 | qi for some i = 1, . . . , l and q1 | pj for some j = 1, . . . , k. Since all of the pi ’s and qi ’s are prime, p1 = qi and q1 = pj . Hence, p1 = q1 since p1 ≤ pj = q1 ≤ qi = p1. By the induction hypothesis, n ′ = p2 · · · pk = q2 · · · ql has a unique factorization. Hence, k = l and qi = pi for i = 1, . . . , k. Existence. To show existence, suppose that there is some integer that cannot be written as the product of primes. Let S be the set of all such numbers. By the Principle of WellOrdering, S has a smallest number, say a. If the only positive factors of a are a and 1, then a is prime, which is a contradiction. Hence, a = a1a2 where 1 < a1 < a and 1 < a2 < a. Neither a1 ∈ S nor a2 ∈ S, since a is the smallest element in S. So a1 = p1 · · · pr a2 = q1 · · · qs. Therefore, a = a1a2 = p1 · · · prq1 · · · qs. So a ∈/ S, which is a contradiction. Historical Note Prime numbers were first studied by the ancient Greeks. Two important results from antiquity are Euclid’s proof that an infinite number of primes exist and the Sieve of Eratosthenes, a method of computing all of the prime numbers less than a fixed positive integer n. One problem in number theory is to find a function f such that f(n) is prime for each integer n. Pierre Fermat (1601?–1665) conjectured that 2 2 n + 1 was prime for all n, but later it was shown by Leonhard Euler (1707–1783) that 2 2 5 + 1 = 4,294,967,297 is a composite number. One of the many unproven conjectures about prime numbers is Goldbach’s Conjecture. In a letter to Euler in 1742, Christian Goldbach stated the conjecture that every even integer with the exception of 2 seemed to be the sum of two primes: 4 = 2 + 2, 6 = 3 + 3, 8 = 3 + 5, . . .. Although the conjecture has been verified for the numbers up through 4 × 1018, it has yet to be proven in general. Since prime numbers play an important role in public key cryptography, there is currently a great deal of interest in determining whether or not a large number is prime. 2.3 Exercises 1. Prove that 1 2 + 22 + · · · + n 2 = n(n + 1)(2n + 1) 6 for n ∈ N
2.3.EXERCISES 29 2.Prove that 13+23++n3=n2n+12 4 forn∈N. 3.Prove that n!2 for n >4. 4.Prove that x+4红+7z++(3n-2z=n3m-1z 2 for nE N. 5.Prove that 10m+1+10m+1 is divisible by 3 for n E N. 6.Prove that 4.102n+9.102n-1+5 is divisible by 99 for n E N. 7.Show that a1a2…amn =1 8. Prove the Leibniz rule for f(m)(),where f(m)is the nth derivative of f;that is,show that o四=2()）rag-e 9.Use induction to prove that 1+2+22+...+2m=2n+1-1 for n E N. 10.Prove that 11 1 2+++nmn+=n+ forn∈N. 11.If x is a nonnegative real number,then show that (1+x)"-1 nxc for n 0,1,2,.... 12.Power Sets.Let X be a set.Define the power set of X,denoted P(X),to be the set of all subsets of X.For example, P({a,b})={0,{a},{b},{a,b}} For every positive integer n,show that a set with exactly n elements has a power set with exactly 2n elements. 13.Prove that the two principles of mathematical induction stated in Section 2.1 are equivalent. 14.Show that the Principle of Well-Ordering for the natural numbers implies that 1 is the smallest natural number.Use this result to show that the Principle of Well-Ordering implies the Principle of Mathematical Induction;that is,show that if S C N such that l∈S and n+l∈S whenever n∈S,then S=N. 15.For each of the following pairs of numbers a and b,calculate gcd(a,b)and find integers r and s such that gcd(a,b)=ra+sb. (a)14and39 (d)471and562 (b)234and165 (e)23771and19945 (c)1739and9923 (f)-4357and3754 16.Let a and b be nonzero integers.If there exist integers r and s such that ar+bs =1, show that a and b are relatively prime
2.3. EXERCISES 29 2. Prove that 1 3 + 23 + · · · + n 3 = n 2 (n + 1)2 4 for n ∈ N. 3. Prove that n! > 2 n for n ≥ 4. 4. Prove that x + 4x + 7x + · · · + (3n − 2)x = n(3n − 1)x 2 for n ∈ N. 5. Prove that 10n+1 + 10n + 1 is divisible by 3 for n ∈ N. 6. Prove that 4 · 102n + 9 · 102n−1 + 5 is divisible by 99 for n ∈ N. 7. Show that √n a1a2 · · · an ≤ 1 n ∑n k=1 ak. 8. Prove the Leibniz rule for f (n) (x), where f (n) is the nth derivative of f; that is, show that (fg) (n) (x) = ∑n k=0 ( n k ) f (k) (x)g (n−k) (x). 9. Use induction to prove that 1 + 2 + 22 + · · · + 2n = 2n+1 − 1 for n ∈ N. 10. Prove that 1 2 + 1 6 + · · · + 1 n(n + 1) = n n + 1 for n ∈ N. 11. If x is a nonnegative real number, then show that (1+x) n−1 ≥ nx for n = 0, 1, 2, . . .. 12. Power Sets. Let X be a set. Define the power set of X, denoted P(X), to be the set of all subsets of X. For example, P({a, b}) = {∅, {a}, {b}, {a, b}}. For every positive integer n, show that a set with exactly n elements has a power set with exactly 2 n elements. 13. Prove that the two principles of mathematical induction stated in Section 2.1 are equivalent. 14. Show that the Principle of Well-Ordering for the natural numbers implies that 1 is the smallest natural number. Use this result to show that the Principle of Well-Ordering implies the Principle of Mathematical Induction; that is, show that if S ⊂ N such that 1 ∈ S and n + 1 ∈ S whenever n ∈ S, then S = N. 15. For each of the following pairs of numbers a and b, calculate gcd(a, b) and find integers r and s such that gcd(a, b) = ra + sb. (a) 14 and 39 (b) 234 and 165 (c) 1739 and 9923 (d) 471 and 562 (e) 23771 and 19945 (f) −4357 and 3754 16. Let a and b be nonzero integers. If there exist integers r and s such that ar + bs = 1, show that a and b are relatively prime