Section 2 Definition 3 fussy,we can complain that we haven't defined the term two.Each of these terms- integer,divisible,and two-can be defined in terms of simpler concepts,but this is a game we cannot entirely win.If every term is defined in terms of simpler terms, we will be chasing definitions forever.Eventually we must come to a point where we say,"This term is undefined,but we think we understand what it means." The situation is like building a house.Each part of the house is built up from previous parts.Before roofing and siding,we must build the frame.Before the frame goes up,there must be a foundation.As house builders,we think of pouring the foundation as the first step,but this is not really the first step.We also have to own the land and run electricity and water to the property.For there to be water, there must be wells and pipes laid in the ground.STOP!We have descended to a level in the process that really has little to do with building a house.Yes,utilities are vital to home construction,but it is not our job,as home builders,to worry about what sorts of transformers are used at the electric substation! Let us return to mathematics and Definition 2.1.It is possible for us to define the terms integer,two,and divisible in terms of more basic concepts.It takes a great deal of work to define integers,multiplication,and so forth in terms of simpler concepts.What are we to do?Ideally,we should begin from the most basic mathematical object of all-the set-and work our way up to the integers Although this is a worthwhile activity,in this book we build our mathematical house assuming the foundation has already been formed. The symbol stands for Where shall we begin?What may we assume?In this book,we take the integers the integers.This symbol as our starting point.The integers are the positive whole numbers,the negative is easy to draw,but often whole numbers,and zero.That is,the set of integers,denoted by the letter 2.is people do a poor job. Why?They fall into the Z={.,-3,-2,-1,0,1,2,3,} following trap:They first draw a Z and then try to We also assume that we know how to add,subtract,and multiply,and we need add an extra slash.That not prove basic number facts such as 3 x 2 =6.We assume the basic algebraic doesn't work!Instead. properties of addition,subtraction,and multiplication and basic facts about order make a 7 and then an interlocking,upside-down relations(<,≤，>，and≥).See Appendix D for more details on what you may 7 to draw 2. assume. Thus,in Definition 2.1,we need not define integer or two.However,we still need to define what we mean by divisible.To underscore the fact that we have not made this clear yet,consider the question:Is 3 divisible by 2?We want to say that the answer to this question is no,but perhaps the answer is yes since 3-2 is 1. So it is possible to divide 3 by 2 if we allow fractions.Note further that in the previous paragraph we were granted basic properties of addition,subtraction,and multiplication,but not-and conspicuous by its absence-division.Thus we need a careful definition of divisible Definition 2.2 (Divisible)Let a and b be integers.We say that a is divisible by b provided there is an integer c such that bc a.We also say b divides a,or b is a factor of a,or b is a divisor of a.The notation for this is bla. This definition introduces various terms(divisible,factor,divisor,and divides) as well as the notation bla.Let's look at an example
\ The symbol Z stands for the integers. This symbol is easy to draw, but often people do a poor job. Why? They fall into the following trap: They first draw a Z and then try to add an extra slash. That doesn't work! Instead, make a 7 and then an interlocking, upside-down 7 to draw Z. Section 2 Definition 3 fussy, we can complain that we haven't defined the term two. Each of these termsinteger, divisible, and two-can be defined in terms of simpler concepts, but this is a game we cannot entirely win. If every term is defined in terms of simpler terms, we will be chasing definitions forever. Eventually we must come to a point where we say, "This term is undefined, but we think we understand what it means." The situation is like building a house. Each part of the house is built up from previous parts. Before roofing and siding, we must build the frame. Before the frame goes up, there must be a foundation. As house builders, we think of pouring the foundation as the first step, but this is not really the first step. We also have to own the land and run electricity and water to the property. For there to be water, there must be wells and pipes laid in the ground. STOP! We have descended to a level in the process that really has little to do with building a house. Yes, utilities are vital to home construction, but it is not our job, as home builders, to worry about what sorts of transformers are used at the electric substation! Let us return to mathematics and Definition 2.1. It is possible for us to define the terms integer, two, and divisible in terms of more basic concepts. It takes a great deal of work to define integers, multiplication, and so forth in terms of simpler concepts. What are we to do? Ideally, we should begin from the most basic mathematical object of all-the set-and work our way up to the integers. Although this is a worthwhile activity, in this book we build our mathematical house assuming the foundation has already been formed. Where shall we begin? What may we assume? In this book, we take the integers as our starting point. The integers are the positive whole numbers, the negative whole numbers, and zero. That is, the set of integers, denoted by the letter Z, is z = { ... ' -3, -2, -1, 0, 1, 2, 3, ... }. We also assume that we know how to add, subtract, and multiply, and we need not prove basic number facts such as 3 x 2 = 6. We assume the basic algebraic properties of addition, subtraction, and multiplication and basic facts about order relations ( <, .::::;, >, and ::::). See Appendix D for more details on what you may assume. Thus, in Definition 2.1, we need not define integer or two. However, we still need to define what we mean by divisible. To underscore the fact that we have not made this clear yet, consider the question: Is 3 divisible by 2? We want to say that the answer to this question is no, but perhaps the answer is yes since 3 --;-- 2 is 1 ~. So it is possible to divide 3 by 2 if we allow fractions. Note further that in the previous paragraph we were granted basic properties of addition, subtraction, and multiplication, but not-and conspicuous by its absence-division. Thus we need a careful definition of divisible. Definition 2.2 (Divisible) Let a and b be integers. We say that a is divisible by b provided there is an integer c such that be =a. We also say b divides a, orb is a factor of a, or b is a divisor of a. The notation for this is bla. This definition introduces various terms (divisible ,factor, divisor, and divides) as well as the notation bla. Let's look at an example
Chapter 1 Fundamentals Example 2.3 Is 12 divisible by 4?To answer this question,we examine the definition.It says that a 12 is divisible by b =4 if we can find an integer c so that 4c 12.Of course,there is such an integer,namely,c =3. In this situation,we also say that 4 divides 12 or,equivalently,that 4 is a factor of 12.We also say 4 is a divisor of 12. The notation to express this fact is 412. On the other hand,12 is not divisible by 5 because there is no integer x for which 5x 12;thus 512 is false. Now Definition 2.1 is ready to use.The number 12 is even because 2112,and we know 212 because 2 x 6 =12.On the other hand,13 is not even,because 13 is not divisible by 2;there is no integerx for which 2x =13.Note that we did not say that 13 is odd because we have yet to define the term odd.Of course,we know that 13 is an odd number,but we simply have not"created"odd numbers yet by specifying a definition for them.All we can say at this point is that 13 is not even. That being the case,let us define the term odd. Definition 2.4 (Odd)An integer a is called odd provided there is an integer x such that a=2x+1. Thus 13 is odd because we can choose x =6 in the definition to give 13 2 x 6+1.Note that the definition gives a clear,unambiguous criterion for whether or not an integer is odd. Please note carefully what the definition of odd does not say:It does not say that an integer is odd provided it is not even.This,of course,is true,and we prove it in a subsequent chapter."Every integer is odd or even but not both"is a fact that we prove. Here is a definition for another familiar concept. Definition 2.5 (Prime)An integer p is called prime provided that p>1 and the only positive divisors of p are 1 and p. For example,11 is prime because it satisfies both conditions in the definition: First,11 is greater than 1,and second,the only positive divisors of 11 are I and 11. Is 1 a prime?No.To see why,take p 1 and see if p satisfies the definition of primality.There are two conditions:First we must have p >1,and second,the only positive divisors of p are I and p.The second condition is satisfied:the only divisors of I are 1 and itself.However,p =1 does not satisfy the first condition because 1 1 is false.Therefore,1 is not a prime. We have answered the question:Is I a prime?The reason why 1 isn't prime is that the definition was specifically designed to make 1 nonprime!However,the real "why question"we would like to answer is:Why did we write Definition 2.5 to exclude 1? I will attempt to answer this question in a moment,but there is an important philosophical point that needs to be underscored.The decision to exclude the
4 Chapter 1 Fundamentals Example 2.3 Is 12 divisible by 4? To answer this question, we examine the definition. It says that a = 12 is divisible by b = 4 if we can find an integer~ so that 4c = 12. Of course, there is such an integer, namely, c = 3. In this situation, we also say that 4 divides 12 or, equivalently, that 4 is a factor of 12. We also say 4 is a divisor of 12. The notation to express this fact is 4112. On the other hand, 12 is not divisible by 5 because there is no integer x for which 5x = 12; thus 5112 is false. Now Definition 2.1 is ready to use. The number 12 is even because 2112, and we know 2112 because 2 x 6 = 12. On the other hand, 13 is not even, because 13 is not divisible by 2; there is no integer x for which 2x = 13. Note that we did not say that 13 is odd because we have yet to define the term odd. Of course, we know that 13 is an odd number, but we simply have not "created" odd numbers yet by specifying a definition for them. All we can say at this point is that 13 is not even. That being the case, let us define the term odd. Definition 2.4 (Odd) An integer a is called odd provided there is an integer x such that a= 2x + 1. Thus 13 is odd because we can choose x = 6 in the definition to give 13 = 2 x 6 + 1. Note that the definition gives a clear, unambiguous criterion for whether or not an integer is odd. Please note carefully what the definition of odd does not say: It does not say that an integer is odd provided it is not even. This, of course, is true, and we prove it in a subsequent chapter. "Every integer is odd or even but not both" is a fact that we prove. Here is a definition for another familiar concept. Definition 2.5 (Prime) An integer pis called prime provided that p > 1 and the only positive divisors of p are 1 and p. For example, 11 is prime because it satisfies both conditions in the definition: First, 11 is greater than 1, and second, the only positive divisors of 11 are 1 and 11. Is 1 a prime? No. To see why, take p = 1 and see if p satisfies the definition of primality. There are two conditions: First we must have p > 1, and second, the only positive divisors of pare 1 and p. The second condition is satisfied: the only divisors of 1 are 1 and itself. However, p = 1 does not satisfy the first condition because 1 > 1 is false. Therefore, 1 is not a prime. We have answered the question: Is 1 a prime? The reason why 1 isn't prime is that the definition was specifically designed to make 1 nonprime! However, the real "why question" we would like to answer is: Why did we write Definition 2.5 to exclude 1? I will attempt to answer this question in a moment, but there is an important philosophical point that needs to be underscored. The decision to exclude the
Section 2 Definition 5 number 1 in the definition was deliberate and conscious.In effect,the reason I is not prime is "because I said so!"In principle,you could define the word prime differently and allow the number I to be prime.The main problem with your using a different definition for prime is that the concept of a prime number is well established in the mathematical community.If it were useful to you to allow I as a prime in your work,you ought to choose a different term for your concept,such as relaxed prime or alternative prime. Now,let us address the question:Why did we write Definition 2.5 to exclude 1?The idea is that the prime numbers should form the"building blocks" of multiplication.Later,we prove the fact that every positive integer can be fac- tored in a unique fashion into prime numbers.For example,12 can be factored as 12 =2 x 2 x 3.There is no other way to factor 12 down to primes (other than rearranging the order of the factors).The prime factors of 12 are precisely 2,2. and 3.Were we to allow 1 as a prime number,then we could also factor 12 down to“primes'asl2=l×2×2x3,a different factorization. Since we have defined prime numbers,it is appropriate to define composite numbers. Definition 2.6 (Composite)A positive integer a is called composite provided there is an integer b such that 1 <b<a and bla. For example,the number 25 is composite because it satisfies the condition of the definition:There is a number b with 1 <b<25 and b25;indeed,b=5 is the only such number. Similarly,the number 360 is composite.In this case,there are several numbers b that satisfy I <b <360 and b360. Prime numbers are not composite.If p is prime,then,by definition,there can be no divisor of p between 1 and p(read Definition 2.5 carefully). Furthermore,the number 1 is not composite.(Clearly,there is no number b with 1<b<1.)Poor number 1!It is neither prime nor composite!(There is, however,a special term that is applied to the number 1-the number I is called a unit.) Recap In this section,we introduced the concept of a mathematical definition.Definitions typically have the form"An object X is called the term being defined provided it satisfies specific conditions."We presented the integers Z and defined the terms divisible,odd,even,prime,and composite. 2 Exercises 2.1.Please determine which of the following are true and which are false;use Definition 2.2 to explain your answers. a.31100. b.3199. c.-313
\ Section 2 Definition 5 number 1 in the definition was deliberate and conscious. In effect, the reason 1 is not prime is "because I said so!" In principle, you could define the word prime differently and allow the number 1 to be prime. The main problem with your using a different definition for prime is that the concept of a prime number is well established in the mathematical community. If it were useful to you to allow 1 as a prime in your work, you ought to choose a different term for your concept, such as relaxed prime or alternative prime. Now, let us address the question: Why did we write Definition 2.5 to exclude 1? The idea is that the prime numbers should form the "building blocks" of multiplication. Later, we prove the fact that every positive integer can be factored in a unique fashion into prime numbers. For example, 12 can be factored as 12 = 2 x 2 x 3. There is no other way to factor 12 down to primes (other than rearranging the order of the factors). The prime factors of 12 are precisely 2, 2, and 3. Were we to allow 1 as a prime number, then we could also factor 12 down to "primes" as 12 = 1 x 2 x 2 x 3, a different factorization. Since we have defined prime numbers, it is appropriate to define composite numbers. Definition 2.6 (Composite) A positive integer a is called composite provided there is an integer b such that 1 < b < a and bla. 2 Exercises For example, the number 25 is composite because it satisfies the condition of the definition: There is a number b with 1 < b < 25 and b 125; indeed, b = 5 is the only such number. Similarly, the number 360 is composite. In this case, there are several numbers b that satisfy 1 < b < 360 and b 1360. Prime numbers are not composite. If pis prime, then, by definition, there can be no divisor of p between 1 and p (read Definition 2.5 carefully). Furthermore, the number 1 is not composite. (Clearly, there is no number b with 1 < b < 1.) Poor number 1! It is neither prime nor composite! (There is, however, a special term that is applied to the number 1-the number 1 is called a unit.) Recap In this section, we introduced the concept of a mathematical definition. Definitions typically have the form "An object X is called the term being defined provided it satisfies specific conditions." We presented the integers Z and defined the terms divisible, odd, even, prime, and composite. 2.1. Please determine which of the following are true and which are false; use Definition 2.2 to explain your answers. a. 31100. b. 3199. c. -313
6 Chapter 1 Fundamentals d.-5-5. e.-2-7. .014. g.410. h.00. 2.2.Here is a possible alternative to Definition 2.2:We say that a is divisible by b provided 4 is an integer.Explain why this alternative definition is different from Definition 2.2. Here,different means that Definition 2.2 and the alternative definition specify different concepts.So,to answer this question,you should find integers a and b such that a is divisible by b according to one definition,but a is not divisible by b according to the other definition. 2.3.None of the following numbers is prime.Explain why they fail to satisfy Definition 2.5.Which of these numbers is composite? a.2l. b.0. C.π. d. e.-2. f.-1. 2.4.The natural numbers are the nonnegative integers;that is, The symbol stands for the natural numbers. N={0,1,2,3,.} Use the concept of natural numbers to create definitions for the following relations about integers:less than (<)less than or equal to ()greater than (>)and greater than or equal to () Note:Many authors define the natural numbers to be just the positive in-. tegers;for them,zero is not a natural number.To me,this seems unnatural The concepts positive integers and nonnegative integers are unambiguous and universally recognized among mathematicians.The term natural num- ber,however,is not 100%standardized. 2.5.A rational number is a number formed by dividing two integers a/b where The symbol stands for b0.The set of all rational numbers is denoted Q. the rational numbers. Explain why every integer is a rational number,but not all rational numbers are integers. 2.6.Define what it means for an integer to be a perfect square.For example,the integers 0,1,4,9,and 16 are perfect squares.Your definition should begin An integer x is called a perfect square provided.... 2.7.This problem involves basic geometry.Suppose the concept of distance between points in the plane is already defined.Write a careful definition for one point to be between two other points.Your definition should begin Suppose A,B.C are points in the plane.We say that C is between A and B provided.... Note:Since you are crafting this definition,you have a bit of flexibility. Consider the possibility that the point C might be the same as the point A or
1 ........ ________________ __ 6 Chapter 1 Fundamentals The symbol N stands for the natural numbers. The symbol Q stands for the rational numbers. d. -51-5. e. -21-7. f. 014. g. 410. h. 010. 2.2. Here is a possible alternative to Definition 2.2: We say that a is divisible by b provided ~ is an integer. Explain why this alternative definition is different from Definition 2.2. Here, different means that Definition 2.2 and the alternative definition specify different concepts. So, to answer this question, you should find integers a and b such that a is divisible by b according to one definition, but a is not divisible by b according to the other definition. 2.3. None of the following numbers is prime. Explain why they fail to satisfy Definition 2.5. Which of these numbers is composite? a. 21. b. 0. c. JT. d. ~- e. -2. f. -1. 2.4. The natural numbers are the nonnegative integers; that is, N={0,1,2,3, ... }. Use the concept of natural numbers to create definitions for the following relations about integers: less than ( <), less than or equal to (:S), greater than(>), and greater than or equal to(~). Note: Many authors define the natural numbers to be just the positive in-. tegers; for them, zero is not a natural number. To me, this seems unnatural !D). The concepts positive integers and nonnegative integers are unambiguous and universally recognized among mathematicians. The term natural number, however, is not 100% standardized. 2.5. A rational number is a number formed by dividing two integers a I b where b # 0. The set of all rational numbers is denoted Q. Explain why every integer is a rational number, but not all rational numbers are integers. 2.6. Define what it means for an integer to be a peifect square. For example, the integers 0, 1, 4, 9, and 16 are perfect squares. Your definition should begin An integer x is called a perfect square provided .... 2.7. This problem involves basic geometry. Suppose the concept of distance between points in the plane is already defined. Write a careful definition for one point to be between two other points. Your definition should begin Suppose A, B, C are points in the plane. We say that C is between A and B provided .... Note: Since you are crafting this definition, you have a bit of flexibility. Consider the possibility that the point C might be the same as the point A or
Section 2 Definition 7 B,or even that A and B might be the same point.Personally,if A and C were the same point,I would say that C is between A and B(regardless of where B may lie),but you may choose to design your definition to exclude this possibility.Whichever way you decide is fine,but be sure your definition does what you intend. Note further:You do not need the concept of collinearity to define berween. Once you have defined between,please use the notion of between to define what it means for three points to be collinear.Your definition should begin Suppose A,B,C are points in the plane.We say that they are collinear provided.... Note even further:Now if,say,A and B are the same point,you certainly want your definition to imply that A,B,and C are collinear. 2.8.Discrete mathematicians especially enjoy counting problems:problems that ask how many.Here we consider the question:How many positive divisors does a number have?For example,6 has four positive divisors:1,2,3, and 6. How many positive divisors does each of the following have? a.8. b.32 c.2"where n is a positive integer. d.10. e.100 f.1.000.000 g.10 where n is a positive integer. h.30=2×3×5. i.42 =2 x 3 x 7.(Why do 30 and 42 have the same number of positive divisors?) j.2310=2×3×5×7×11. k.1×2×3×4×5×6×7×8. 1.0. 2.9.An integer n is called perfect provided it equals the sum of all its divisors that are both positive and less than n.For example,28 is perfect because the positive divisors of 28 are 1,2,4,7,14,and 28.Note that 1+2+4+7+ 14=28. a.There is a perfect number smaller than 28.Find it. b.Write a computer program to find the next perfect number after 28. 2.10.At a Little League game there are three umpires.One is an engineer,one is a physicist,and one is a mathematician.There is a close play at home plate, but all three umpires agree the runner is out. Furious,the father of the runner screams at the umpires,"Why did you call her out?!" The engineer replies,"She's out because I call them as they are." The physicist replies,"She's out because I call them as I see them." The mathematician replies,"She's out because I called her out." Explain the mathematician's point of view
) \ -- Section 2 Definition 7 B, or even that A and B might be the same point. Personally, if A and C were the same point, I would say that C is between A and B (regardless of where B may lie), but you may choose to design your definition to exclude this possibility. Whichever way you decide is fine, but be sure your definition does what you intend. Note further: You do not need the concept of collinearity to define between. Once you have defined between, please use the notion of between to define what it means for three points to be collinear. Your definition should begin Suppose A, B, C are points in the plane. We say that they are collinear provided .... Note even further: Now if, say, A and B are the same point, you certainly want your definition to imply that A, B, and C are collinear. 2.8. Discrete mathematicians especially enjoy counting problems: problems that ask how many. Here we consider the question: How many positive divisors does a number have? For example, 6 has four positive divisors: 1, 2, 3, and6. How many positive divisors does each of the following have? a. 8. b. 32. c. 2n where n is a positive integer. d. 10. e. 100. f. 1,000,000. g. 1 on where n is a positive integer. h. 30 = 2 X 3 X 5. i. 42 = 2 x 3 x 7. (Why do 30 and 42 have the same number of positive divisors?) j. 2310 = 2 X 3 X 5 X 7 X 11. k. 1 X 2 X 3 X 4 X 5 X 6 X 7 X 8. I. 0. 2.9. An integer n is called perfect provided it equals the sum of all its divisors that are both positive and less than n. For example, 28 is perfect because the pos.itive divisors of 28 are 17 2, 4 7 7, 14~ and 28. Note that 1 + 2 + 4 + 7 + 14 = 28. a. There is a perfect number smaller than 28. Find it. b. Write a computer program to find the next perfect number after 28. 2.10. At a Little League game there are three umpires. One is an engineer, one is a physicist, and one is a mathematician. There is a close play at home plate, but all three umpires agree the runner is out. Furious, the father of the runner screams at the umpires, "Why did you call her out?!" The engineer replies, "She's out because I call them as they are." The physicist replies, "She's out because I call them as I see them." The mathematician replies, "She's out because I called her out." Explain the mathematician's point of view