CHAPTER 5Number Theory1. Integers and Division1.1. Divisibility.Definition 1.1.1. Given two integers a and b we say a divides b if there is aninteger c such that b = ac. If a divides b, we write a|b. If a does not divide b, wewrite a6 | b.DiscussionExample 1.1.1. The number 6 is divisible by 3, 3|6, since 6 = 3 · 2.Exercise 1.1.1. Let a, b, and c be integers with a 6= 0. Prove that if ab|ac, thenb|c.Using this definition, we may define an integer to be even if it is divisible by 2and odd if it is not divisible by 2. This concept is one of the simplest of properties ofnumbers to define, yet it is among the most complicated of all mathematical ideas.Keep in mind that we are talking about a very restricted notion of what it means forone number to “divide” another: we can certainly divide 7 by 3 and get the rationalnumber73= 2.3333 ···, but, since the result is not an integer, we say that 3 does notdivide 7, or 36 |7. For this reason, you should avoid using fractions in any discussionof integers and integer arithmetic.1.2. Basic Properties of Divisibility.Theorem 1.2.1. For all integers a, b, and c,1. If a|b and a|c, then a|(b + c).2. If a|b, then a|(bc).3. If a|b and b|c, then a|c.Discussion1461. INTEGERS AND DIVISION 147Theorem 1.2.1 states the most basic properties of division. Here is the proof ofpart 3:Proof of part 3. Assume a, b, and c are integers such that a|b and b|c. Then bydefinition, there must be integers m and n such that b = am and c = bn. Thusc = bn = (am)n = a(mn).Since the product of two integers is again an integer, we have a|c. Exercise 1.2.1. Prove part 1 of Theorem 1.2.1.Exercise 1.2.2. Prove part 2 of Theorem 1.2.1.1.3. Theorem 1.3.1 - The Division Algorithm.Theorem 1.3.1. (Division Algorithm) Given integers a and d, with d > 0, thereexists unique integers q and r, with 0 ≤ r < d, such that a = qd + r.Notation 1.3.1. We call a the dividend, d the divisor, q the quotient, and rthe remainder.DiscussionThe division algorithm is probably one of the first concepts you learned relativeto the operation of division. It is not actually an algorithm, but this is this theorem’straditional name. For example, if we divide 26 by 3, then we get a quotient of 8 andremainder or 2. This can be expressed 26 = 3 ·8 + 2. It is a little trickier to see whatq and r should be if a < 0. For example, if we divide −26 is by 3, then the remainderis not −2. We can, however, use the equation 26 = 3 · 8 + 2 to our advantage:−26 = 3 · (−8) − 2 = [3 · (−8) − 3] − 2 + 3 = 3(−9) + 1So dividing −26 by 3 gives a quotient of −9 and remainder 1. The condition 0 ≤ r < dmakes r and q unique for any given a and d.1.4. Proof of Division Algorithm. Proof. Suppose a and d are integers, andd > 0. We will use the well-ordering principle to obtain the quotient q and remainderr. Since we can take q = a if d = 1, we shall assume that d > 1.Let S be the set of all natural numbers of the form a−kd, where k is an integer.In symbolsS = {a − kd|k ∈ Z and a −kd ≥ 0}.If we can show that S is nonempty, then the well-ordering principle will give us aleast element of S, and this will be the remainder r we are looking for. There are twocases.1. INTEGERS AND DIVISION 148Case 1: a ≥ 0. In this case, we can set k = 0 and get the element a − 0 · d = a ≥ 0of S.Case 2: a < 0. In this case, we can set k = a. Then a − kd = a − ad = a(1 − d).Since a < 0 and d > 1, a(1 − d) > 0; hence is an element of S.Thus, S 6= ∅, and so S has a least element r = a − qd for some integer q. Thus,a = qd + r and r ≥ 0. We are left to show (i) r < d and (ii) q and r are unique.(i) Suppose r ≥ d. Then r = d + r0, where 0 ≤ r0< r. Then a = qd + r =qd + d + r0= (q + 1)d + r0,so that r0= a −(q + 1)d is an element of S smaller than r. This contradicts the factthat r is the least element of S. Thus, r < d.(ii) Suppose integers q0and r0satisfy a = q0d + r0and 0 ≤ r0< d. Without loss ofgenerality, we may assume r0≥ r, so that 0 ≤ r −r0< d. Since a = q0d + r0= qd + r,r −r0= d(q0− q).This means that d divides r − r0, which implies either r − r0≥ d or r − r0= 0. Butbut we know 0 ≤ r − r0< d. Thus, r0= r, which, in turn, implies q0= q. That is, qand r are unique.1.5. Prime Numbers, Composites.Definition 1.5.1. If p is an integer greater than 1, then p is a prime numberif the only divisors of p are 1 and p.Definition 1.5.2. A positive integer greater than 1 that is not a prime numberis called composite.DiscussionPrime numbers are the building blocks of arithmetic. At the moment there areno efficient methods (algorithms) known that will determine whether a given integeris prime or find its prime factors. This fact is the basis behind many of the cryp-tosystems currently in use. One problem is that there is no known procedure thatwill generate prime numbers, even recursively. In fact, there are many things aboutprime numbers that we don’t know. For example, there is a conjecture, known asGoldbach’s Conjecture, that there are infinitely many prime pairs, that is, consecu-tive odd prime numbers, such as 5 and 7, or 41 and 43, which no one so far has beenable to prove or disprove. As the next theorem illustrates, it is possible, however, toprove that there are infinitely many prime numbers. Its proof, attributed to Euclid,is one of the most elegant in all of mathematics.Theorem 1.5.1. There are infinitely many prime numbers.1. INTEGERS AND DIVISION 149Proof. We prove the theorem by contradiction. Suppose there are only finitelymany prime numbers, say, p1, p2, ..., pn. LetN = p1p2···pn+ 1.Then N is an integer greater than each of p1, p2, ..., pn, so N cannot be prime. InExample 9, Module 3.3, we showed that N can be written as a product of primenumbers; hence, some prime p divides N. We may assume, by reordering p1, p2, ..., pn,if necessary, that p = p1. Thus N = p1a for some integer a. Substituting, we getp1a = p1p2···pn+ 1p1a − p1p2···pn= 1p1(a − p2···pn) = 1.Thus, a − p2···pnis a positive integer. Since p1is a prime number, p1> 1, and sop1(a − p2···pn) > 1.But this contradicts the equality above. 1.6. Fundamental Theorem of Arithmetic.Theorem 1.6.1. (Fundamental Theorem of …