Share E-Book

A Beginners Guide to Discrete Mathematics, Second Edition (W. D. Wallis)(Z-Library)

Author

Rating 4.0 AI initial rating

Log in to rate

Mathematics
Language English

Wallis's book on discrete mathematics is a resource for an introductory course in a subject fundamental to both mathematics and computer science, a course that is expected not only to cover certain specific topics but also to introduce students to important modes of thought specific to each discipline... Lower-division undergraduates through graduate students. —Choice reviews (Review of the First Edition) Very appropriately entitled as a 'beginner's guide', this textbook presents itself as the first exposure to discrete mathematics and rigorous proof for the mathematics or computer science student. —Zentralblatt Math (Review of the First Edition) This second edition of A Beginner’s Guide to Discrete Mathematics presents a detailed guide to discrete mathematics and its relationship to other mathematical subjects including set theory, probability, cryptography, graph theory, and number theory. This textbook has a distinctly applied orientation and explores a variety of applications. Key Features of the second edition: * Includes a new chapter on the theory of voting as well as numerous new examples and exercises throughout the book * Introduces functions, vectors, matrices, number systems, scientific notations, and the representation of numbers in computers * Provides examples which then lead into easy practice problems throughout the text and full exercise at the end of each chapter * Full solutions for practice problems are provided at the end of the book This text is intended for undergraduates in mathematics and computer science, however, featured special topics and applications may also interest graduate students.

Format PDF
Size 3.6 MB
(First 20 pages)

Registered users can read the full content for free

Register as a Gaohf Library member to read the complete e-book online for free and enjoy a better reading experience.

Page 1
(This page has no text content)
Page 2
(This page has no text content)
Page 3
W.D. Wallis A Beginner’s Guide to Discrete Mathematics Second Edition
Page 4
W.D. Wallis Department of Mathematics Southern Illinois University Carbondale, IL 62901 USA wdwallis@siu.edu ISBN 978-0-8176-8285-9 e-ISBN 978-0-8176-8286-6 DOI 10.1007/978-0-8176-8286-6 Springer New York Dordrecht Heidelberg London Library of Congress Control Number: 2011940047 Mathematics Subject Classification (2010): 05-01, 05Axx, 05Cxx, 60-01, 68Rxx, 97N70 1st edition: © Birkhäuser Boston 2003 2nd edition: © Springer Science+Business Media, LLC 2012 All rights reserved. This work may not be translated or copied in whole or in part without the written permission of the publisher (Springer Science+Business Media, LLC, 233 Spring Street, New York, NY 10013, USA), except for brief excerpts in connection with reviews or scholarly analysis. Use in connection with any form of information storage and retrieval, electronic adaptation, computer software, or by similar or dissimilar methodology now known or hereafter developed is forbidden. The use in this publication of trade names, trademarks, service marks, and similar terms, even if they are not identified as such, is not to be taken as an expression of opinion as to whether or not they are subject to proprietary rights. Printed on acid-free paper Springer is part of Springer Science+Business Media (www.birkhauser-science.com)
Page 5
For Nathan
Page 6
Preface This text is a basic introduction to those areas of discrete mathematics of interest to students of mathematics. Introductory courses on this material are now standard at many colleges and universities. Usually these courses are of one semester’s duration, and usually they are offered at the sophomore level. Very often this will be the first course where the students see several real proofs. The preparation of the students is very mixed, and one cannot assume a strong back- ground. In particular, the instructor should not assume that the students have seen a linear algebra course, or any introduction to number systems that goes beyond col- lege algebra. In view of this, I have tried to avoid too much sophistication, while still retain- ing rigor. I hope I have included enough problems so that the student can reinforce the concepts. Most of the problems are quite easy, with just a few difficult exercises scattered through the text. If the class is weak, a small number of sections will be too hard, while the instructor who has a strong class will need to include some supple- mentary material. I think this is preferable to a book at a higher mathematical level, one that scares away the weaker students. Readership While the book is primarily directed at mathematics majors and minors, this material is also studied by computer scientists. The face of computer science is changing due to the influence of the internet, and many universities will also require a second course, with more specialized material, but those students also need the basics. Another developing area is the course on mathematical applications in the mod- ern world, aimed at liberal arts majors and others. Much of the material in those courses is discrete. I do not think this book should even be considered as a text for such a course, but it could be a useful reference, and those who end up teaching such a course will also find this text useful. Discrete mathematics is also an elective
Page 7
viii Preface topic for mathematically gifted students in high schools, and I consulted the Indiana suggested syllabus for such courses. Outline of Topics The first two chapters include a brief survey of number systems and elementary set theory. Included are discussions of scientific notation and the representation of num- bers in computers; topics that were included at the suggestion of computer science instructors. Mathematical induction is treated at this point although the instructor could defer this until later. (There are a few references to induction later in the text, but the student can omit these in a first reading.) I introduce logic along with set theory. This leads naturally into an introduction to Boolean algebra, which brings out the commonality of logic and set theory. The latter part of Chapter 3 explains the application of Boolean algebra to circuit theory. I follow this with a short chapter on relations and functions. The study of rela- tions is an offshoot of set theory, and also lays the foundation for the study of graph theory later. Functions are mentioned only briefly. The student will see them treated extensively in calculus courses, but in discrete mathematics we mostly need basic definitions. Enumeration, or theoretical counting, is central to discrete mathematics. In Chap- ter 5 I present the main results on selections and arrangements, and also cover the binomial theorem and derangements. Some of the harder problems here are rather challenging, but I have omitted most of the more sophisticated results. Counting leads naturally to probability theory. I have included the main ideas of discrete probability, up to Bayes’ theorem. There was a conscious decision not to include any real discussion of measures of central tendency (means, medians) or spread (variance, quartiles) because most students will encounter them elsewhere, e.g., in statistics courses. Graph theory is studied, including Euler and Hamilton cycles and trees. This is a vehicle for some (easy) proofs, as well as being an important example of a data structure. Matrices and vectors are defined and discussed briefly. This is not the place for algebraic studies, but matrices are useful for studying other discrete objects, and this is illustrated by a section on adjacency matrices of relations and graphs. A number of students will never study linear algebra, and this chapter will provide some founda- tion for the use of matrices in programming, mathematical modeling, and statistics. Those who have already seen vectors and matrices can skip most of this chapter, but should read the section on adjacency matrices. Chapter 9 is an introduction to cryptography, including the RSA cryptosystem, together with the necessary elementary number theory (such as modular arithmetic and the Euclidean algorithm). Cryptography is an important application area and is a good place to show students that discrete mathematics has real-world applications.
Page 8
Preface ix Moreover, most computer science majors will later be presented with electives in this area. The level of mathematical sophistication is higher in parts of this chapter than in most of the book. The final chapter is about voting systems. This topic has not been included in very many discrete mathematics texts. However, voting methods are covered in many of the elementary applied mathematics courses for liberal arts majors, and they make a nice optional topic for mathematics and computer science majors. Perhaps I should explain the omissions rather than the inclusions. I thought the study of predicates and quantifiers belonged in a course on logic rather than here. I also thought lattice theory was too deep, although it would fit nicely after the section on Boolean forms. There is no section on recursion and recurrence relations. Again, this is a deep area. I have actually given some problems on recurrences in the induction section, but I thought that a serious study belongs in a combinatorics course. Similarly, the deeper enumeration results, such as counting partitions, belong in higher-level courses. Another area is linear programming. This was once an important part of dis- crete mathematics courses. But, in recent years, syllabi have changed. Nowadays, somewhat weaker students are using linear programming, and there are user-friendly computer packages available. I do not think that it will be on the syllabus of many of the courses at which this book is aimed. Problems and Exercises The book contains a large selection of exercises, collected at the end of sections. There should be enough for students to practice the concepts involved. Most are straightforward; in some sections there are one or two more sophisticated questions at the end. A number of worked examples, called Sample Problems, are included in the body of each section. Most of these are accompanied by a Practice Exercise, de- signed primarily to test the reader’s comprehension of the ideas being discussed. It is recommended that students work all the Practice Exercises. Complete solutions are provided for all of them, as well as brief answers to the odd-numbered problems from the sectional exercise sets. Gender In many places a mathematical discussion involves a protagonist—a person who flips a coin or deals a card or traverses a road network. These people used to be exclusively male in older textbooks. In recent years this has rightly been seen to be inappropriate. Unfortunately this has led to frequent repetitions of nouns—“the player’s card” rather than “his card”—and the use of the ugly “he or she.”
Page 9
x Preface I decided to avoid such problems by a method that was highly appropriate to this text: I flipped a coin to decide whether a character was male or female. If the reader detects an imbalance, please blame the coin. There were two exceptions to this rule. Cryptographers traditionally write about messages sent from Alice (A) to Bob (B), so I followed this rule in discussing RSA cryptography. And in the discussion of the Monty Hall problem, the game show host is male, in honor of Monty, and the player is female for balance. Acknowledgments My treatment of discrete mathematics owes a great deal to many colleagues and mathematicians in other institutions with whom I have taught or discussed this ma- terial. Among my influences are Roger Eggleton, Ralph Grimaldi, Dawit Haile, Fred Hoffman, Bob McGlynn, Nick Phillips, Bill Sticka, and Anne Street, although some of them may not remember why their names are here. I am grateful for the constant support and encouragement of the staff at Birkhäuser. Carbondale, USA W.D. Wallis
Page 10
Contents 1 Properties of Numbers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 1.1 Numbers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 1.2 Sums . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9 1.3 Bases . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15 1.4 Scientific Notation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20 1.5 Arithmetic in Computers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24 2 Sets and Data Structures . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31 2.1 Propositions and Logic . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31 2.2 Elements of Set Theory . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38 2.3 Proof Methods in Set Theory . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45 2.4 Some Further Set Operations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 52 2.5 Mathematical Induction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 57 3 Boolean Algebras and Circuits . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 67 3.1 Boolean Algebra . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 67 3.2 Boolean Forms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 73 3.3 Finding Minimal Disjunctive Forms . . . . . . . . . . . . . . . . . . . . . . . . . . . 79 3.4 Digital Circuits . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 86 4 Relations and Functions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 93 4.1 Relations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 93
Page 11
xii Contents 4.2 Some Special Kinds of Relations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 100 4.3 Functions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 105 5 The Theory of Counting . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 113 5.1 Events . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 113 5.2 Unions of Events . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 121 5.3 One-to-One Correspondences and Infinite Sets . . . . . . . . . . . . . . . . . . 129 5.4 Arrangement Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 133 5.5 Selections . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 140 5.6 The Binomial Theorem and Its Applications . . . . . . . . . . . . . . . . . . . . 151 5.7 Some Further Counting Results . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 156 6 Probability . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 165 6.1 Probability Measures . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 166 6.2 Repeated Experiments . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 177 6.3 Counting and Probability . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 185 6.4 Conditional Probabilities . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 191 6.5 Bayes’ Formula and Applications . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 203 7 Graph Theory . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 215 7.1 Introduction to Graphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 215 7.2 The Königsberg Bridges; Traversability . . . . . . . . . . . . . . . . . . . . . . . . 222 7.3 Walks, Paths, and Cycles . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 232 7.4 Distances and Shortest Paths . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 236 7.5 Trees . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 243 7.6 Hamiltonian Cycles . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 252 7.7 The Traveling Salesman Problem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 257 8 Matrices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 263 8.1 Vectors and Matrices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 263 8.2 Properties of the Matrix Product . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 271 8.3 Systems of Linear Equations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 277
Page 12
Contents xiii 8.4 More About Linear Systems and Inverses . . . . . . . . . . . . . . . . . . . . . . 284 8.5 Adjacency Matrices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 291 9 Number Theory and Cryptography . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 297 9.1 Some Elementary Number Theory . . . . . . . . . . . . . . . . . . . . . . . . . . . . 297 9.2 Modular Arithmetic . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 303 9.3 An Introduction to Cryptography . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 310 9.4 Substitution Ciphers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 317 9.5 Modern Cryptography . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 323 9.6 Other Cryptographic Ideas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 329 9.7 Attacks on the RSA System . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 333 10 The Theory of Voting . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 339 10.1 Simple Elections . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 339 10.2 Multiple Elections . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 350 10.3 Fair Elections . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 359 10.4 Properties of Electoral Systems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 369 Solutions to Practice Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 379 Answers to Selected Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 409 Index . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 423
Page 13
1 Properties of Numbers When we study numbers, many of the problems involve continuous properties. Much of the earliest serious study of mathematics was in geometry, and one essential prop- erty of the real world is that between any two points there is a line segment that is continuous and infinitely divisible. All of calculus depends on the continuous nature of the number line. Some of the most famous difficulties of Greek mathematics in- volved the existence of irrational numbers and the fact that between any two real numbers one can always find another number. But the discrete properties of numbers are also very important. The decimal nota- tion in which we usually write numbers depends on properties of the number 10, and we can also study the (essentially discrete) features of representations where other positive whole numbers take the role of 10. When we write the exact value of a number, or an approximation to its value, we use only the ten integers 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, together with the decimal point. When numbers are represented in a computer, only integers are used. So it is impor- tant to understand the discrete properties of numbers to talk about their continuous properties. 1.1 Numbers Sets and Number Systems All of discrete mathematics—and, in fact, all of mathematics—rests on the founda- tions of set theory and numbers. In this first section we remind you of some basic definitions and notations. Further properties of numbers will be explored in the rest of this chapter; sets will be discussed further in Chapter 2. We use the word set in everyday language: a set of tires, a set of saucepans. In mathematics you have already encountered various sets of numbers. We shall use W.D. Wallis, A Beginner’s Guide to Discrete Mathematics, DOI 10.1007/978-0-8176-8286-6_1, © Springer Science+Business Media, LLC 2012
Page 14
2 1 Properties of Numbers set to mean any collection of objects, provided only that there is a well-defined rule, called the membership law, for determining whether a given object belongs to the set. The individual objects in the set are called its elements or members and are said to belong to the set. If S is a set and s is one of its elements, we denote this fact by writing s ∈ S, which is read as “s belongs to S” or “s is an element of S.” The notation S ⊆ T means that every member of S is a member of T : x ∈ S ⇒ x ∈ T . Then S is called a subset of T . This definition allows for the possibility that S = T , and, in fact, a set is considered to be a subset of itself. If S ⊆ T , but S = T we say S is a proper subset of T and write S ⊂ T . One way of defining a set is to list all the elements, usually between braces; thus the set of the first three members of the English alphabet is {a, b, c}. If S is the set consisting of the numbers 0, 1, and 3, we could write S = {0, 1, 3}. We write {1, 2, . . . , 16} to mean the set of all whole numbers from 1 to 16. This use of a string of dots is not precise, but is usually easy to understand. Another method is the use of the membership law of the set: for example, since the numbers 0, 1, and 3 are precisely the numbers that satisfy the equation x3 − 4x2 + 3x = 0, we could write the set S as S = { x : x3 − 4x2 + 3x = 0 } or S = { x|x3 − 4x2 + 3x = 0 } (“the set of all x such that x3 − 4x2 + 3x = 0”). Whole numbers are called integers, and integral means “being an integer,” so the set of whole numbers from 1 to 16 is {x : x integral, 1 ≤ x ≤ 16}. Sample Problem 1.1. Write three different expressions for the set with elements 1 and −1. Solution. Three possibilities are {1,−1}, {x : x2 = 1}, and “the set of square roots of 1.” There are others. Practice Exercise. Write three different expressions for the set with elements 1, 2, and 3. Some sets of numbers are so important that special names are given to them. The set of all integers, or whole numbers, is denoted Z. With this notation, the set {1, 2, . . . , 16} can be written {x : x ∈ Z, 1 ≤ x ≤ 16}.
Page 15
1.1 Numbers 3 The positive integers or natural numbers, usually denoted Z + or N, are the inte- gers greater than 0. Another important set of integers is the set Z 0 of nonnega- tive integers. We sometimes write Z + = {1, 2, 3, . . .}, Z0 = {0, 1, 2, 3, . . .}, and Z = {. . . ,−3,−2,−1, 0, 1, 2, 3, . . .}. The use of a string of three dots without a terminating number (called an ellipsis) is understood to mean that the set continues without end. Such sets are called infinite (as opposed to finite sets like {0, 1, 3}). The number of elements in a finite set S is called the order of S and is denoted |S|; for example, if S = {0, 1, 3} then |S| = 3. The rational numbers Q consist of all fractions whose denominator is not 0: Q = { p q : p ∈ Z, q ∈ Z, q = 0 } . Equivalently, it can be shown that Q is the set of all numbers with a repeating or terminating decimal expansion. Examples are 1 2 = 0.5, −12 5 = −2.4, 3 7 = 0.428571428571 . . . . In the last example, the digit string 428571 repeats forever, and we usually indicate this by writing 3 7 = 0.428571. The denominator q cannot be zero. In fact, division by zero is never possible. This is not an arbitrary rule, but rather it follows from the definition of division. When we write x = p q , we mean “x is the number that, when multiplied by q, gives p.” What would x = 2/0 mean? There is no number that, when multiplied by 0, gives 2. Similarly, x = 0/0 would be meaningless. In this case there are suitable numbers x, in fact, every number will give 0 when multiplied by 0, but we want a uniquely defined answer. Different decimal expansions do not always mean different numbers. The excep- tion is an infinite string of 9’s. These can be rounded up: 0.9 = 1, 0.79 = 0.8, and so on. We prove a small theorem that illustrates this fact. Theorem 1. 0.9 = 1. Proof. Suppose x = 0.9. Then 10x = 9.9 = 9 + 0.9 = 9 + x. So 9x = 9 and x = 1. The integers are all rational numbers, and, in fact, they are the rational numbers with numerator 1. For example, 5 = 5/1.
Page 16
4 1 Properties of Numbers Each rational number has as infinitely many representations as a ratio. For exam- ple, 1/2 = 2/4 = 3/6 = · · · . The final number system we shall use is the set R of real numbers, consisting of all numbers that are decimal expansions. Not all real numbers are rational; one easy example is √ 2. In fact, if n is any natural number other than a perfect square (one of 1, 4, 9, 16, . . .), then √ n is not rational. Another important number that is not rational is the ratio π of the circumference of a circle to its diameter. The number systems satisfy Z + ⊆ Z ⊆ Q ⊆ R. Rational numbers that are not integers are called proper fractions, and real numbers that are not rational are called irrational numbers. When a < b, the set of all real numbers x such that a < x < b is called an open interval and denoted (a, b); we write [a, b] for the set of all real numbers x with a ≤ x ≤ b] (a closed interval). Similarly, [a, b) = {x : x ∈ R, a ≤ x, b}, and (a, b] is an interval that contains b but not a. The notations Z + and Z 0, mentioned previously, can be extended to the other number systems: for example, R+ is the set of positive real numbers. It is also useful to discuss number systems with the number 0 omitted from them, especially when division is involved. We denote this with an asterisk: for example, Z∗ is the set of nonzero integers. Factors and Divisors When x and y are integers, we use the phrase “x divides y” and write x|y to mean “there is an integer z such that y = xz,” and we say x is a divisor of y. Thus 2 divides 6 (because 6 = 2 · 3), −2 divides 6 (because 6 = (−2) · (−3), 2 divides −6 (because −6 = 2 · (−3)). Some students get confused about the case y = 0, but according to our definition x divides 0 for any nonzero integer x. We define the factors of a positive integer x to be the positive divisors of x (negative divisors are not called factors so −2 is not a factor of 6). If x divides both y and z, we call x a common divisor of y and z. Among the common divisors of y and z there is naturally a greatest one, called (not surprisingly) the greatest common divisor of y and z, and denoted (y, z). If (y, z) = 1, y and z are called coprime or relatively prime. For example, (4, 10) = 2, so 4 and 10 are not coprime; (4, 9) = 1, so 4 and 9 are coprime. In the latter example we also say 4 is relatively prime to 9. A prime number is a positive integer x other than 1 whose only factors are 1 and x. The first few primes are 2, 3, 5, 7, 11, and 13. The number 1 is excluded and is called a unit. Theorem 2. The set of all prime numbers is infinite.
Page 17
1.1 Numbers 5 Proof. Suppose the number of primes is finite. Then there will be some positive inte- ger n such that there exist exactly n primes. Suppose the primes are p1, p2, . . . , pn. Now consider the number x = p1 × p2 × · · · × pn + 1. Clearly, dividing x by p1 would leave a remainder of 1, and similarly for the other pi ; so x is not divisible by any of p1, p2, . . . , pn. Either it is prime, or its prime divisors are outside the set of all primes—but the latter case is impossible. So the assumption that the number of primes is finite must be false. Any positive integer x can be written as a product x = x1 × x2 × · · · × xk, where the xi are all primes. So every positive integer is the product of prime factors. For example, 36 is the product 2 × 2 × 3 × 3. We usually collect all the equal factors and use an exponent, so we write 36 = 22 × 32. This prime factor decomposition is unique: for example, if 2a3b5c = 2x3y7z, it must be true that a = x, b = y, and c and z are both zero. We shall look at this further in Section 9.1. Sample Problem 1.2. Use the prime factor decomposition to find the greatest common divisors of each of the following numbers with 224: 16, 53, 63, 84, 97. Solution. 224 = 25 · 7, and 16 = 24, 53 is prime, 63 = 32 · 7, 84 = 22 · 3 · 7, 97 is prime. So (16, 224) = 16, (53, 224) = 1, (63, 224) = 7, (84, 224) = 28, and (97, 224) = 1. Practice Exercise. Use the prime factor decomposition to find (72, 84) and (56, 42). Exponents and Logarithms If x is a positive integer, bx is the product of x copies of b: bx = b × b × · · · × b (x factors). In this expression b is called the base and x the exponent. It is easy to deduce such properties as bxby = bx+y, ( bx )y = bxy, (ab)x = axbx. Negative exponents are handled by defining b−x = 1 bx , and also b0 = 1 whenever b is nonzero. The multiplication rule leads us to define b 1 x to be the xth root of b. (When x is even, we take the positive root for positive b and say b 1 x is not defined for negative b.)
Page 18
6 1 Properties of Numbers Sample Problem 1.3. Express the following in the simplest form—as decimal numbers if possible: (612)0, ( x3)5 , ( x4)0 , (−10)−4, 1 10−2 . Solution. (612)0 = 1 (b0 = 1 for any b); (x3)5 = x3·5 = x15; (x4)0 = 1 (again, b0 = 1 for any b, or you could also argue that (x4)0 = x4·0 = x0 = 1); (−10)−4 = 1 (−10)4 = 1 (−1)4·104 = 1 104 = 0.0001; 1 10−2 = 102 = 100. Practice Exercise. Do the same to 115, 05, ( x−1)0 , x6 x3 , (−2)−1, 1 5−2 . Sample Problem 1.4. Express in the simplest possible form, with positive expo- nents: 1 x−4 ; u−2 v−3 3a2)(5a−3). Solution. 1 x−4 x−4)−1 = x(−4)·(−1) = x4; u−2 v−3 = (u−2)(v−3)−1 = u−2v3 = v3 u−2 ; ( 3a2)(5a−3) = 3 · 5 · a2 · a−3 = 15a−1 = 15 a . Practice Exercise. Express in the simplest possible form, with positive expo- nents: t−2 t−3 ; y5−2, ( 4x−2)(3x4). The process of taking powers can be inverted. The logarithm of x to base b, or logb x, is defined to be the number y such that by = x. Clearly logb x is not defined if b is 1 (if x = 1, any y would be suitable, and if x = 1, no y would work). Sample Problem 1.5. What are log2 8 and log16 4? Solution. 23 = 8, so log2 8 = 3. √ 16 = 16 1 2 = 4, so log16 4 = 1 2 . Practice Exercise. What are log3 9, log5 125 and log4 2? Several properties of logarithms follow from the elementary properties of expo- nents. In particular
Page 19
1.1 Numbers 7 logb uv = logb u + logb v, logb ( u−1) = − logb u, logb ( xy ) = y logb x, logb 1 = 0 for any b. Theorem 3. For any x and any base b, x = logb bx . Proof. By definition, u = b logb u. Putting u = bx we have bx = b(logb bx). So comparing the exponents, x = logb bx . Sample Problem 1.6. Evaluate 125log5 2. Solution. 125log5 2 = ( 53)log5 2 = 53 log5 2 = 5log5 23 = 5log5 8 = 8. Practice Exercise. Evaluate log3(9 √ 3)5. Absolute Value, Floor, and Ceiling The absolute value or modulus of the number x, which is written |x|, is the nonneg- ative number equal to either x or −x. For example, |5.3| = 5.3, |−7.2| = 7.2. (Do not confuse this with the notation for set order.) The floor x of x is the largest integer not greater than x. If x is an integer, x = x. Some other examples are 6.1 = 6, −6.1 = −7. It is easy to deduce the following properties: (1) x = n if and only if n is an integer and n ≤ x < n + 1. (2) If x is nonnegative, then x equals the integer part of x. If x is negative and nonintegral, then x is one less than the integer part of x. (3) If n and k are integers, then k divides n if and only if n k = n k . The ceiling x is defined analogously as the smallest integer not less than x. Sample Problem 1.7. What are 6.3, 7.2 , −2.4 , |3.4|, |−3.4|? Solution. 6, 8,−2, 3.4, 3.4.
Page 20
8 1 Properties of Numbers Practice Exercise. What are 2.6, −1.7, 4.8 , −4 , |3.1|, |−4.4|? Exercises 1.1 Are the given statements true or false in Exercises 1 to 10? 1. 3 ∈ {2, 3, 4, 6}. 2. 4 /∈ {2, 3, 4, 6}. 3. 5 ∈ {2, 3, 4, 6}. 4. {3, 2} = {2, 3}. 5. {1, 2} ∈ {1, 2, 3}. 6. {1, 2} = {1, 2, 3}. 7. 5 ∈ {1, 3, 4, 7}. 8. 6 /∈ {1, 3, 4, 7}. 9. 4 ∈ {1, 3, 4, 7}. 10. {1, 3} = {1, 2, 3}. In Exercises 11 to 15, write the list of all members of the set. 11. {x : x is a month whose name starts with J}. 12. {x : x is an odd integer between −6 and 6}. 13. {x : x is a letter in the word “Mississippi”}. 14. {x : x is an even positive integer less than 12}. 15. {x : x is a color on the American flag}. 16. Which of the following are true? (i) All natural numbers are integers. (ii) All integers are natural numbers. 17. For each of the following numbers, to which of the sets Z +, Z, Q, R does it belong? (i) −2.13, (ii) √ 5, (iii) √ 4, (iv) 2π , (v) 1.834, (vi) 2 + √ 2. 18. For each of the following numbers, to which of the sets Z +, Z, Q, R does it belong? (i) 1.308, (ii) 1.3, (iii) −7, (iv) √ 3, (v) 10,508, (vi) 1 − √ 7. In Exercises 19 to 27, list all the factors of the number. 19. 36. 20. 50. 21. 72. 22. 61. 23. 63. 24. 24. 25. 29. 26. 70. 27. 48.
The above is a preview of the first 20 pages. Register to read the complete e-book.

Recommended for You

Loading recommended books...
Failed to load, please try again later

Tip the Site

Scan the WeChat Pay or Alipay code to tip. No login required.

WeChat Pay
Alipay
← Back to List