The Algebraic Foundations of Mathematics - Beaumont. [PDF]

Zitiervorschau

THE ALGEBRAIC FOUNDATIONS OF MATHEMATICS

This book is in the ADDISON-WESLEY SERIES I N INTRODUCTORY COLLEGE MATHEMATICS

Consulting Editors

RICHARD S. PIETERS

GAILS. YOUNG

THE ALGEBRAIC FOUNDATIONS OF MATHEMATICS ROSS A . BEAUMOXT and

RICHARD S. PIERCE Department of Mathematics University of Washington

ADDISOK-WESLEY

PUBLISHING

READING, MASSACHUSETTS

COMPANY, INC.

PALO ALTO

LONDON

Copyright @ 1963 ADDISON-WESLEY PUBLISHING COMPANY, INC. Printed in the United States U;r; Arnerica ALL RIGHTS RESERVED. THIS BOOK, OR PARTS THEREOF, MAY NOT B E REPRODUCED I N ANY FORM WITHOUT WRITTEN PERMISSION OF THE PUBLISHERS.

Library of Congress Catalog Card No. 623-8895

PREFACE This book is an offspring of two beliefs which the authors have held for many years: it is worthwhile for the average person to understand what rnathematics is al1 about; it is impossible to learn much about mathematics without doing mathematics. The first of these convictions seems to be accepted by most educated people. The second opinion is less widely held. Mathematicians teaching in liberal arts colleges and universities are often under pressure from their colleagues in the humanities and social sciences to offer short courses which will painlessly explain mathematics to students with varying backgrounds who are seeking a broad, liberal education. The extent to which such courses do not exist is a credit to the good sense of professional mathematicians. Mathematics is a big and difficult subject. I t embraces a rigid method of reasoning, a concise form of expression, and a variety of new concepts and viewpoints which are quite different from those encountered in everyday life. There is no such thing as "descriptive7' mathematics. In order to find answers to the questions "What is mathematics?" and "What do mathematicians do?", it is necessary to learn something of the logic, the language, and the philosophy of mathematics. This cannot be done by listening to a few entertaining lectures, but only by active contact with the content of real mathematics. I t is the authors' hope that this book will provide the means for this necessary contact. For most people, the road from marketplace arithmetic to the border of real mathematics is long and steep. I t usually takes severa1 years to make this journey. Fortunately, because of the improving curriculum in high schools, many students are completing the elementary mathematics included in algebra, geometry, and trigonometry before entering college, so that as college freshmen they can begin to appreciate the attractions of sophisticated mathematical ideas. Many of these students have even been exposed to the new programs for school mathematics which introduce modern mathematical ideas and methods. Too often, such students are shunted into a college algebra or elementary calculus course, where the main emphasis is on mathematical formalism and manipulation. Any enthusiasm for creative thinking which a student may carry into college will quickly be blunted by such a course. It is often claimed that the manipulative skills acquired in elementary algebra and calculus are what a student needs for the application of mathematics to science and engineering, and indeed to the practica1 problems of life. Although not altogether wrong, this argument overlooks the obvious fact that in almost any situation, the ability to use mathematical technique and reasoning is more valuable than the ability to manipulate and calculate accurately. v

vi

PREFACE

Elementary college algebra and calculus courses usually cultivate manipulation a t the expense of logical reasoning, and they give the student almost no idea of what mathematics is really like. It is often painfully evident to an instructor in, say, a senior leve1 course in abstract algebra that the average mathematics major in his class has a very distorted idea of the nature of mathematics. The object of this book is to present in a form suitable for student consumption a small but important part of real mathematics. I t is concerned with topics related to the principal number systems of mathematics. The book treats those topics of algebra which are basic for advanced studies in mathematics and of fundamental importance for al1 working mathematicians. This is the reason t,hat we have entitled our book "The Algebraic Foundations of Mathematics. " In accord with the philosophy that students should be taught mathematics by exposing them to the mathematics of professional mathematicians, the book should be useful not only to students majoring in mathematics, but also to adequately prepared students of any speciality. Since mathematics is a logical science, it is appropriate that any book on real mathematics should emphasize mathematical proofs. The student who masters the technique and acquires the habit of mathematical proof is well on his way toward understanding the nature of mathematics. Such a mastery is hard to achieve, but it is within the reach of a large percentage of the college population. This book is not intended to be an easy one. I t is not meant for the college freshman with minimum preparation from high school. An apt student with three years of high school mathematics should be able to study most parts of the book with profit, but his progress may not be rapid. Appropriate places for the use of this book include: a freshman course to replace the standard precalculus college algebra for students who will progress to a rigorous treatment of calculus, a terminal course for liberal arts students with a good background in mathematics, an elementary honors course for mathematics majors, a course to follow a traditional calculus course to develop maturity, and a refresher course for high school mathematics teachers. The book is written in such a way that the law of diminishing returns will not set in too quiekly. That is, enough difficult material is included in most sections and chapters so that even the best students will be challenged. The student of more modest ability should keep this in mind in order to combat discouragement. Some sections digress from the main theme of the book. These are designated by a "star." For the most part, starred sections can be omitted without loss of continuity, although it may be necessary to refer to them for definitions. It should be emphasized that the starred sections are not the most difficult parts of the book. On the contrary, much of the material

vii

PREFACE

in these sections is very elementary. A star has been attached to just those sections which are not sufficiently important to be considered indispensable, but which are still too interesting to omit. The complete book can be covered in a two semester or three quarter course meeting three hours per week. The following table suggests how the book can be used for shorter courses. Course

Time required

Chapter

College algebra

1 Semester, 3 hours 1 Quarter, 5 hours

1 (Omit 1-3, 1-5, and starred sections) 2 (Omit starred sections) 4 (Omit 4-1) 5 (Omit starred sections) 6 (Omit 6-1, 6-4, 6-5) 7 (Omit 7-1, 7-2, 7-3, 7-6, and starred sections) 8 9 (Omit starred section) 10 (Omit 10-4)

Development of the classical number systems

1 Semester, 3 hours 1 Quarter, 5 hours

1 through 8 (Omit starred sections)

Theory of equations

1 Semester, 2 hours 1 Quarter, 3 hours

Elementary theory of numbers

1 Semester, 2 hours 1 Quarter, 3 hours

4 5 6 8 9 10

(Omit 4-1, 4-3, 4-5, 4-6) (Omit starred sections) (Omit 6-1, 6-4, 6-5) (Omit starred section) (Omit 10-3, 10-4)

1 (Omit starred sections) 2 (Omit starred sections) 4 5

Above all, this book represents an effort to show college students some of the real beauty of mathernatics. The appreciation of mathematical beauty is not like the enjoyment of literature, music, and other art forms. I t requires serious effort and hard study. I t is much more difficult for a mathematician to explain his triumphs and masterpieces than for any other kind of artist or scientist. Consequently, most mathematicains do not try to interpret their work to the general public, but only communicate with

viii

PREFACE

colleagues having similar interests. For this reason, a mathematician is often considered to be a rather aloof person who lives partly in this world and partly in some other mysterious realm. This is in fact a fairly accurate conception. However, the door to the world of mathematics is never locked, and anyone who will make the effort can enjoy the beauties of an intellectual domain which comes closer to aesthetic perfection than any other science. Acknowledgements. Writing a textbook is not a routine chore. Without the help of many people, we might never have finished this one. We are particularly indebted to Professors C. W. Curtis, R. A. Dean, and H. S. Zuckerman, who read most of the manuscript of this book, and gave us many valuable suggestions. Our publisher, Addison-Wesley, has watched over our work from beginning to end with remarkable patience and benevolence. The swift and expert typing of Mary Pierce is sincerely appreciated. Finally, we are grateful to many friends for sincere encouragement during the last two years, and especially to our wives, who have lived with us through these trying times.

Seattle, Washington January 1963

1-1 1-2 1-3 1-4 1-5 "1-6 *1-7

Sets . . . . . . . . . . . . . . The cardinal number of a set . . . . . . . The construction of sets from given sets . . . . . . . . . . . . The algebra of sets Further algcbra of sets . General rules of operation Measures on sets . . . . . . . . . . . . . . Properties and esamples of measures

. . . . . . . .

2-1 2-2 2-3 *2-4 2-5 *2-6

Proof by induction . . . . . . . . The binomial theorem . . . . . . . Generalizations of the induction principlc . S h e technique of induction . . . . . Inductive properties of the natural numbcrs Inductive definitions . . . . . . .

3-1 3-2 3-3

. . . The definition of numbers Operations with the natural numbers The ordcring of the natural numbers

4-1 4-2 4-3 4 4 4-5 4-6

Construction of the integers . . . . . . . . Rings Generalized sums and products Integral domains . . . . Thc ordering of the integers . Properties of order . . . .

5-1 5-2 5-3 *5-4 *5-5 5-6 5-7 *5-8 6-1 6-2 6-3

.

.

. .

. .

. .

. .

.

.

.

.

. .

. .

. .

. .

. . . . . . . . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

.

.

.

.

.

.

. . . . . . . . .

.

.

.

.

.

.

.

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . S h e division algorithm Greatest common divisor . . . . . . . . . . . . . . . The fundamental theorem of arithmetic . . . . . . . . . . . More about primes Applications of the fundamental theorem of arithmetic . . . . . . . . . . . . . . Congruences . . . . . . . . . . . Linear congruences The theorems of Fermat and Euler . . . . . . .

. . . Basic properties of the rational numbcrs . . . . . . . . . . . . . Fields The characteristic of integral domains and fields . ix

. . . . . . . .

. . . . . . . .

. . . . . . . . . . . .

CONTENTS

X

6-4 6-5 7-1 7-2 7-3 7-4 7-5 7-6 "7-7 "7-8 *7-9 *7-10

Equivalence relations . The construction of & .

. .

. .

. .

. .

Development of the real numbers . . . . . . The coordinate line Dedekind cuts . . . . . . . . Construction of the real numbers The completeness of the real numbers Properties of complete ordered fields Infinite sequences . . . . . . Infinite series . . . . . . . Decimal representation . . . . Applications of decimal representations

. .

. . . . . . . 213 . . . . . . . 218

. .

. .

. .

. .

. .

. .

. . . .

.

.

.

.

.

.

.

.

. .

. .

. .

. .

. .

. .

. .

. .

.

.

.

.

.

.

.

.

. . .

. . .

. . .

. . .

. . .

. . .

. . .

. . .

. . . . . . . .

8-1 8-2 8-3 8-4

The construction of the complesnumbers . . . Comples conjugates and the absolute value in C . The geometrical representation of complex numbers Polar representation . . . . . . . . .

9-1 9-2 9-3 9-4 9-5 9-6 9-7 9-8 "9-9 9-10 9-1 1 9-12

Algebraic equations . . . . . . . . . Polynomials . . . . . . . . . . . The division algorithm for polynomials . . . . Greatest common divisor in F[x] . . . . . . The unique factorization theorem for polynomials Derivatives . . . . . . . . . . . . The roots of a polynomial . . . . . . . The fundamental theorem of algebra . . . . The solution of third- and fourth-degree equations Graphs of real polynomials . . . . . . . Sturm's theorem . . . . . . . . . . Polynomials with rational coefficients . . . .

10-1 10-2 10-3 10-4

Polynomialsinseveralindeterminates . Systems of linear equations . . . . The algebra of matrices . . . . . The inverse of a square matrix . . .

. . . . 286 . . . . 291 . 298 . . . . 303

. . . . . . . . . . . . . . . . . . . . . . . . . . . .

394 410 428 443

INTRODUCTION

As we explained in the preface, the purpose of this book is to exhibit a small, but significant and representative, part of the world of mathematics. The selection of a principal subject for this project poses difficulties similar to those which a blind man faces when he tries to discover the shape of an elephant by means of his "sense of feel." Only a few aspects of the subject are within reach, and it is necessary to exercise care to be sure the part examined is truly representative. We might select some important unifying concept of modern mathematics, such as the notion of a group, and explore the ramifications of this idea. Alternatively, an older and perhaps familiar topic can be examined in depth. I t is this last more conservative program which will be followed. We will study the principal number systems of mathematics and some of the theories related to them. An attempt will be made to answer the question "what are numbers?" in a way which meets the standards of logical precision demanded in modern mathematics. This program has certain dangers. Familiarity with ordinary numbers hides subtle difficulties which must be overcome before it is even possible to give an exact definition of them. Checking the details in the construction of the various number systems is often tedious, especially for a student who does not see the point of this effort. On the other hand, the end products of this work, the real and complex number systems, are objects of great usefulness and importance in mathematics. Moreover, the development of these systems offers an opportunity to exhibit a wide variety of mathematical techniques and ideas, so that the student is exposed to a representative cross section of mathematics. I t is customary in technical books to te11 the reader what he will need to know in order to understand the text. A typical description of such requirements in mathematical textbooks runs as follows: "This book has no particular prerequisites. However, the reader will need a certain amount of mathematical maturity. " Usually such a statement means that the book is written for graduate students and seasoned mathematicians. Our prerequisites for understanding this book are more modest. The reader should have successfully completed two years of high-school algebra and a year of geometry. The geometry, although not an absolute prerequisite, will be very helpful. For certain topics in the chapters on the complex numbers and the theory of equations, a knowledge of the rudiments of trigonometry is assumed. We do not expect that the reader will have much "mathe1

2

INTRODUCTION

matical maturity." Indeed, one of the main purposes of this book is to put the reader in touch with mature mathematics. Some of the obstacles which a beginning student of mathematics faces seem more formidable than they reafly are. With a little encouragement almost any intelligent person can become a better mathematician than he would imagine possible. The purpose of the remainder of this introduction is to provide some encouraging words on a variety of subjects. I t is hoped that our discussion will smooth the reader's way throughout the book. We suggest that this material be read quickly, then referred to later as it is needed. The number systems. There are five principal number systems in mathematics: the natural numbers: 1, 2, 3, 4, etc.; the integers: 0, 1, -1, 2, -2, 3, -3, etc.; the rational numbers: 0, 1, -1, +, -+,-$, -3, 3, -3, etc.; the real numbers:O, 1, *, -*, 4,-4,a, 3 - $'a,etc.;and the complez numbers: 0, 1, i, 1 G,T S,etc. With the possible exception of the complex numbers, each of these systems should be familiar. Indeed, the study of these number systems is the principal subject of arithmetic courses in elementary school and of algebra courses in high school. Of course, the names of these systems may not be familiar. For exarnple, the integers are sometimes called whole numbers, and the rational numbers are often referred to as fractions. In this book the number systems will be considered at two levels. On the one hand, we will assume at least a superficial knowledge of numbers, and use them in examples from the first chapter on. On the other hand, Chapters 3, 4, 6, 7, and 8 each present a critica1 study of one of these systems. The reader has two alt,ernatives. He can either skim the material in these chapters, relying on the knowledge of numbers which he already possesses, or he can study these chapters in detail. The latter road is longer and more tedious, but it leads to a very solid foundation for advanced courses in mathematical analysis. Variables. If a single event can be called the beginning of modern mathematics, then it may possibly be the introduction of variables as a systematic notational device. This innovation, due largely to the French inathematician Francois Vihta (1540-1603), occurred about 1590. Without variables, mathematics would not have progressed very far beyond what we now think of as its "beginnings." By using variables it is possible to express complicated properties of numbers in a very simple way. Basic laws of operation, such as

m, +

z+ y =y+z

and

+

x + (y+z) = (x-ky) i-2,

can be stated without using the variables x, y, and z, but the resulting statements lack the clarity of these algebraic identities. For example,

the statement that "the product of a number by the sum of two other ilumbers is equal to the sum of the product of the first number by the secoild with the product of the first number by the third" is more simply and clearly-expressed by the identity

More complicated laws would be almost impossible to stat*ewithout using variables. The reader who doubts this should try to express in words the relatively simple identity

The variables which are encountered in high-school algebra courses usually range over systems of numbers; that is, it is intended that these variables stand for real numbers, rational numbers, or perhaps only for integers. However, variable symbols are often useful in other contexts. For example, the symbols 1and m in the statement "if 1and m are two different nonparallel lines, then 1 and m have exactly one point in common" are variables, representing arbitrary lines in a plane. In this book variables will be used to denote many kinds of objects. However, in al1 cases, a variable is a symbol which represents an unspecified member of some definite collection of objects, such as numbers, points, or lines. The given collection is called the range of the variable, and a particular object in the range is called a value of the variable. The notations used for variables in mathematical literature often puzzle students. In the simplest cases, the letters of the alphabet are used as variable symbols. However, some mathematical statements involve a very large number of variables, and in some cases, even infinitely many. To accommodate the need for many variables, letter symbols with subscripts are usually employed, for example, xl, x2, x7, y3, 215, a2, b7, etc. Sometimes double subscripts are more convenient than single ones. Thus, , ~ etc.~ Variable symbols are we find expressions such as x l , ~~, 7 x2~,52, often used to denote a subscript on a variable letter. For instance xi, y,, ak, zi,j, etc. In these cases, the variable subscript is usually assumed to stand for a natural number, or possibly an integer. Mathematical language. One of the difficulties in learning mathematics is the language barrier. Not only must the student master many new concepts and the riames of these concepts, but he must also learn numerous abbreviations and symbols for common words. Except for the use of abbreviations, the grammar of mathematics is the same as that of the language in which it is written.

4

INTRODUCTION

A sentence in mathematical writing is any expression which is a meaningful assertion, either true or false. According to this definition, such formulas as 2 . ' -2 - 2, 1=2, 1 1 2,

and expressions which have the form of sentences, except that variables occur in place of the subject or object; for example, "x is an integer" and "2 divides n." Expressions such as these are called sentential functions. They have the property that substituting numerical values (or whatever objects the variables represent) for the variables converts them into sentences. For instance, by suitable substitutions for x and y, the sentential function x y = 1 is transformed into the sentences

+

+

I t makes no sense to ask whether or not a formula such as x y = 1 is true. For some values of x and y it is true; for others it is not. On the other hand, the formula x y=y x has the property that every substitution of numbers for x and y leads to a true sentence. Such a sentential function is usually called an identity. Sentential functions which are not formulas may also have the property of being true for al1 values of the variables occurring in them. For example, the statement x" has this property of universal validity, provided "either x < y, or y that it is understood that x and y are variables which range over real numbers. A sentential function which is true for al1 values of the variables in it is said to be identically true or identically valid (the adjective "identically is sometimes omitted) . Implications. Many beginning students of mathematics have trouble understanding the idea of logical implication. As many as one-half of al1 statements in a mathematical proof may be implications, that is, of the form " p implies q," where p and q are sentences or sentential functions.

+


O and -1 < O. If the implication "p implies q" and its converse "q implies p" are both true, then the statements p and q are said to be equivalent. In practice, the notion of equivalence of p and q is most frequently applied when p and q are sentential functions. For example, if x and y are variables which range over numbers, then the formulas x = y 1=y 1 are equivalent, since "x = y implies x 1=y 1" and x and "x 1= y 1 implies x = y" are identically valid. There are various ways of saying that two statements p and q are equivalent. Most of these forms are derived from the terminology for implications. Severa1 examples are given in Table 2.

+

+ +

+ +

+

+

INTRODUCTION

TABLE3 P

Q

not p

not q

p implies q

not q implies not p

true

true

false

false true

false true true

f alse

true false true

true

true

false true true

true

false false

false

false true true

Contrapositive and inverse. In addition to the implication "p implies q" and its converse "q implies p," two other implications can be forrned using p and q. These are "not q implies not p" and "not p implies not q." The implication "not q implies not p" is called the contrapositive of "p implies q," while "not p implies not q" is called the inverse of ('p implies q." For example, the contrapositive of the statement "if x = 1, then x is an integer " is the implication "if x is not an integer, then x is not equal to l." I t is easy to see that the contrapositive of "p implies q" is true under exactly the same circumstances that this implication is itself true. The most convincing way to demonstrate this fact is to make a table listing al1 of the possible combinations of truth values of any two sentences p and q, together with the corresponding truth or falsity of " p implies q" and its contrapositive (Table 3). The entries in the fifth column of Table 3 are determined by the combinations of true and false in the first two columns, while the entries of the last column are determined from the combinations which occur in the third and fourth columns. Of course, the entries of the third column are just the opposite of those in the first column, and a similar relation exists between the fourth and second columns. The fact that an implication is logically the same as its contrapositive is often very useful in mathematical proofs. Sometimes, rather than proving a statement of the form "p implies q," it is easier to prove the contrapositive "not q implies not p." This is logically acceptable. Also, if we wish to prove that p and q are equivalent, that is, " p implies q" and "q implies p " are valid, it is permissible to establish that "p implies q" and "not p implies not q. " This is because "not p implies not q" is the contrapositive of "q implies p. " However, beware ; it is not correct to claim that if p implies q and not q implies not p, then p is equivalent to q. DeJinitions. Simple mathematical proofs often consist of nothing more than showing that the conditions of some definition are satisfied. Kevertheless, beginning students frequently find such arguments difficult to understand. Consider, for example, the problem of showing that 222 is

INTRODUCTION

From this we can infer such formulas as

The logical structure of a mathematical proof may have one of two forms. The direct proof starts from certain axioms or definitions, and proceeds by application of logical rules to the required conclusion. The second method, the so-called indirect proof, is perhaps less familiar, even though it is often used unconsciously in everyday thinking. The indirect proof begins by assuming "hat the statement to be proved is false. Then, using this assumption, together with the appropriate axioms and definitions, a contradiction of some kind is obtained by means of a logical argument. From this contradiction it is inferred that the statement originally assumed to be false must actually be true. For example, let us show by an indirect proof that there is no largest natural iiumber. This proof uses three general properties of numbers, which, for our purposes can be considered as axioms: 1 is a natural iiumber; (a) if n is a natural iiumber, theii n 1; (b) n < n (c) if n < m, then n 2 m is impossible. Our indirect proof begins with the assumption that the statement to be proved is false, that is, we assume that there is a largest natural number. Let this number be deiioted by n. To say that n is the largest natural number means two things: (i) n is a natural number; (ii) if m is a natural number, then n m. Applying the rule of detachment to (a) aiid (i) gives (iii) n 1 is a natural number. Substituting n 1 for m in (ii), we obtain (iv) if n 1 is a natural number, then n n 1. The rule of detachment can nolv be applied to (iii) and (iv) to conclude that (v) n 2 n 1. 1 for m iii (c) gives However, substituting n (vi) if n < n 1, then n n 1 is impossible. This, together with (b) and the rule of detachmeiit yields (vii) n 2 n 1 is impossible. The statements (v) and (vii) provide the contradiction which completes this typical indirect proof. In spite of the elementary character of the logic used by mathematicians, it is a matter of experience that understanding proofs is the most difficult aspect of mathematics. Most people, mathematiciaiis included, must work hard to follow a difficult proof. The statements follow each other relent-

+

+

>

+ + + + + +

> +

+

> +

10

INTRODUCTION

lessly. Each step requires logical justification, which may not be easy to find. The result of this labor is only the beginning. After the step-by-step correctness of t,he argument has been checked, it is necessary to go on and find the mathematical ideas behind the proof. Truly, real mathematics is not easy.

CHAPTER 1

SET THEORY 1-1 Sets. The notion of a set enters into al1 branches of modern mathematics. Algebra, analysis, and geometry borrow freely from elementary set theory and its terminology. Indeed, al1 of mathematics can be founded on the theory of sets. As is to be expected, an idea with such a wide range of application is quite simple, and any intelligent person can learn enough about set theory for most useful applications of the subject. The central idea of set theory is that of dealing with a collection of objects as an individual thing. Mathematics is not alone in using this idea, and many occurrences of it are found in everyday experience. Thus, for example, one speaks of the Smith family, meaning the collection of people consisting of John Smith, his wife Mary, and their son William. Also, if we referred to Mrs. Smith's wardrobe, we would be treating as a single thing the collection of individual pieces of clothing belonging to Mrs. Smith. The mathematical use of this device of lumping things together into a single entity differs from common usage only in the frequency and systematic manner of its application.

DEFINITION 1-1.1. A set is an entity consisting of a collection of objects. * Two sets are considered to be the same if they contain exactly the same objects. When this is the case, we say that the sets are equal. The objects belonging to a set are called the elements of the set. A set is usually determined by some property which the elements of the set have in common. In the example given above, the property of being a. piece of clothing belonging to Mrs. Smith defines the set which we cal1 Mrs. Smith's wardrobe. I t should be emphasized that in thinking of a collection of objects as a set, no account is takeil of the arrangement of the objects or any relations between them. Thus, for example, a deck of

* This statement cannot be considered as a mathematical definition of the terni "set." I n mathematics, a definition is supposed to completely identify the object being defined. Here we have only supplied the synonym "collection" for the less familiar term "set," The problem of finding a satisfactory mathematical definition is far more difficult than it might seem. The uncritical use of sets can lead to contradictions which are avoided only by imposing restrictions on the naive concept of a set, Finding a definition of "set" which is free from contradictions and which satisfies al1 mathematical needs has for 75 years been a central problem of the logical foundations of mathematics. Fortunately, these difficult aspects of set theory can be ignored in almost al1 mathematical applications of the theory. 11

12

SET THEORY

[CHAP.1

52 cards, considered as a set, remains the same whether it is in its original package or is shuffled and distributed into four bridge hands.

EXAMPLE 1. The set consisting of the numbers O and 1. EXAMPLE 2. The set of numbers which are roots of the equation x2 - x = 0. EXAMPLE 3. The set of numbers which are roots of the equation " x

x2 = o. EXAMPLE 4. The set of numbers a on the real line (Fig. 1-1) which satisfy -1 5 a 5 l.

EXAMPLE 5. The set of al1 numbers x/2, where x is a real number which satisfies -2 5 x 5 2. EXAMPLE 6. The set of al1 points a t a distance less than one from a point p in some plane. EXAMPLE 7. The set of al1 points inside a circle of radius one with center a t the point p in the plane of the preceding example. EXAMPLE 8. The set of al1 circles with center a t the point p in the plane of Example 6. EXAMPLE 9. The set consisting of ¿he single number O. EXAMPLE10. The set which contains no objects whatsoever.

According to our definition of equality of sets, we see that the sets of Examples 1, 2, and 3 are the same. Although O occurs as a so-called double root of the equation x 3 - x 2 = O in Exaniple 3, only its presence or absence matters when speaking of the set of roots. The sets of Exanlples 4 and 5 are the same, as are those of Examples 6 arid 7. If we consider a circle to be the same thing as the set of al1 of its poiiits, then the eleineiits of the set of Example 8 are themselves sets. Sets of sets will be studied more thoroughly in Section 1-5. The set described in Example 9 contains a single element. Such sets are quite common. I t is conventional to regard such a set as an eiltity which is different from the eleinent which is its only member. Even in ordinary conversation this distinctioii is often made. If Robert Brown is a bachelor with no known rclsttions, then we would say that the Brown family consists of one meniber, but we would not say that Mr. Brown consists of oiie nlember. The reader may feel that the set of Example 10 does not satisfy the description given in

1-11

13

SETS

Definition 1-1.1. However, it is customary in mathcmatics to interpret the term "collcction" i11 such a ivay that this ~iotionincludes the collection of no objects. Actiially, thc sct containing no elements arises quite naturally in many situations. For instante, in consideriiig thc scts of real numbers which are roots of algebraic equatioris, it ~voilldbe awkjvard to makc a special rase for equations like x2 1 = O, ivhich has no real roots. 13ecause of its importailcc, thc set coiitaiilirig no elemcilts has a special namc, thc empty set, and it is rcprcscntcd by a special symbol, a. When it is neccssary to cal1 atteiltioii to the fuct that a set A is not the empty set, then ve will say that A is nonempty. Oiie reason that set theory is used in so many brailches of mathcmatics is thc versatility of its notation. As aiiyoiie ~ v h ohas studied elcmentary algebra might expect, thc, letters of the alphabet are used to rcpresent sets. 111 this book, sets will be represeiitcd by capital letters, and the elements of sets ~ i l usually l bc represeiitcd by small letters. Thc statemeiit that an object a is an elemeiit of a set A is symbolized by

+

We rcad thc cxpression a E A as "a is in A," or sometimes, "a in A." To give a specific example, lct, A be t,he set of roots of the equation x2 - x = O (Example 2). Theii

IVe often wish to cxpress the fact t,hat an object is not contained in a certaiii set. If a is not an element of t,he set A, \ve writc

and rcad this cxpressioii "a is iiot in A . " Thus if A again is the set of Examplc 2, wc would havc 2 4 A, 3 4 A, 4 4 A, etc. I t \vas mentioned earlier that a set is ofteri dcfincd by some property possessed by its elements. There is a very uscful ilotatioiial device iri set theory which gives a standard method of symbolizing thc sct of al1 objects having a certain property. For instaiice, the sets of Kxamples 2 and 4 are respcct ivcly writtcn {2-~z2-x=0],

and

{al-l5a A . If A is iiot a subset of B, ~ v cwritc A g R or B 2 A .

EXAMPLE 1l . The set of al1 even integers, 23 = (0, &2, &4, . . .), is a proper subsct of the sct Z of al1 intcgers. EXAMPLE 12. The set of a11 poirits a t distance Iess than one from a point p in a plane P is a proper subset of the set of points of P a t distance less than or equal to oiie f r o n ~p.

16

SET THEORY

EXAMPLE 13. {O, 1) C (O, 1, 2, 4). EXAMPLE 14. (a10 < a 5 1) C {a10 5 a EXAMPLE 15. Q, E A for every set A .

5

1).

The reader should carefully check to see that in each of these examples the condition of Definition 1-1.2 is satisfied. The fact that Q, is a subset of every set may seem straiige. However, it is certainly true according to our definitions: every element of is an element of A, or in other words, no element of can be found which is not in A. Since Q, has no elements, this condition is certainly satisfied. The inclusion relation has three properties which, although direct consequences of our definition, are quite important. The first of these has already been noted. THEOREM 1-1.3. For any sets A, B, and C, (a) A E A , (b) if A c B and B 5 A, then A = B, (c) if A E B and B S C, then A E C.

Proof. We will prove property (b) in detail, leaving the proof of (c) t o the reader. If A c B and B E A , then every element of A is an element of B and every element of B is an element of A. That is, A and B contain exactly the same elements. Thus, by Definition 1-1.1, A = B. Certain sets occur so frequently in mathematical work that it is convenient to use particular symbols to designate them throughout any mathematical paper or book. An example is the practice of denoting the empty set by the symbol a. In this book, the number systems of mathematics, considered as sets, will occur repeatedly. We therefore adopt the f ollowing conventions :

N designates the set of al1 natural numbers : (1, 2, 3, . . .) ; Z designates the set of al1 integers: {. . . , -3, -2, -1,0, 1, 2, 3, . . .) ; Q designates the set of al1 rational numbers: (albja E 2, b E N) ; R designates the set of al1 real numbers. This notation, though not universal, would be recognized by most modern mathematicians. Throughout this book, the letters N, 2 , Q, and R will not be used to denote any set other than the corresponding ones listed above. I n mathematical literature, a considerable amount of variation in notation can be found. The terminology and symbolism introduced in this section will be used in the remainder of this book, but it is by no means

1-11

17

SETS

universal. F o r t h e reader's coiivenience, \ve list some common alternative termii~ology. Set : class, ensemble, aggregate, collect ion. Element of a set: member of a set, poiiit of a set. E m p t y set : void set, vaciious set, null set, zero set. CP: o, A. a ~ A : A 3 a . a 4 A : ~ E ' A , ~ E A , A ~ ~ . (*]*) : (* : *), [*)*], [* : *l.

l. Using the set builder form, write expressions for the follon-ing sets. (a) The set of al1 even integers. (b) The set of al1 integers which are divisible by five. (c) The set of al1 integers which leave a remainder of one mhen divided by five. (d) The set of al1 rational numbers greater than five. (e) The set of al1 points in space which are inside a sphere with center a t the point p and radius r . (f) The set of solutions of the equation x3 - 2x2 - x 2 = 0. 2. Te11 in words what sets are represented by the following expressions. (a) {x E NIx > 10) (b) {x E QIX - 3 E N) ( 4 ( 5 , 6 , 7, . . -1 (4 {a, b, , Y, 2 ) (e) { X ~ X = y2 z2, y E R, z E R, x2 - y2 = (x - y)(x y)) 3. Describe the following sets by listing their elements. (a) {xIx2 = 1) (b) {x1x2 - 2x = 0) 1 = O) (c) {x1x2 - 2x 4. List the following collections of sets. (a) The sets {a, b, c), where a, b, and c are natural numbers less than or equal to 3. (b) The sets {a2 a 1), where a is a natural number less than or equal to 5 . (c) The three element sets (a, b, c), where a, b, and c are integers between -2 and 4. 5. State al1 inclusion relations which exist between the folloñing sets: N, 2, Q, R, the set of al1 even integers, {n(n = m2, m E Z), {zjx = y2, y E Q), { X ~ X = y2 - n, y E R, n E 2). 6. Prove Theorem 1-1.3(c). 7. Prove that if A B, B C C, then A C C, and if A C B and B G C, then A c C.

+

+

+

+

+ +

18

SET THEORY

[CHAP.

1

1-2 The cardinal number of a set. The simplest and most important classification of sets is given by the distinction between finite and infinite sets. Returning to the examples considered in Section 1-1, the set of Examples 1, 2, and 3, and the sets of Examples 8 and 9 are finite, while the sets of Examples 4 through 7 are infinite. Note that the empty set @ is considered to be finite. I t is not altogether easy to explain the difference between a finite and an infinite set, although almost everyone with some experieiice learns to distinguish finite from infinite sets. Roughly speaking, a finite set is either the empty set, or a set in which we can designate a first element, a second element, a third element, and so on, until at some stage we reach an nth element and find that there are no more left. Of course, the number n of elements in the set may be one, two, three, four, . . . , a million, or any natural number whatsoever. A set is said to be infinite if it is not finite, that is, if its elements cannot be counted. Examples of infinite sets are the set N of al1 natural numbers, the set Z of al1 integers, the set Q of al1 rational numbers, the set R of al1 real numbers, etc. These examples show that some of the most important sets encountered in mathematics are infinite. If A is a finite set, it is meaningful to speak of the number of elements of A. This number is called the cardinal number (or cardinality) of the set A. We will use the notation iA 1 to designate the cardinal number of A . As examples,

0

,

l

a

=

l(O,1,4)1=3.

I t was remarked above that the empty set 4> is regarded as being finite: Since @ has no elements, it is natural to say that the cardinality of (P is zero. Thus, in symbols, (@l = 0. There are many synonyms for the expression "cardinal number of A." Besides the term "cardinality of A," which we have already mentioned, one finds such expressions as "power of A " and "potency of A. " The notation IA( for the cardinal number of the set A is not universal either. The symbolism A is perhaps even more common (but difficult to print and type), and such expressions as card A or N(A) can also be found. These descriptions of finite and infinite sets, and of the cardinal number of a finite set are too vague to be called mathematical definitions. Moreover, we have not said anything about the cardinal numbers of sets which are not finite. The first man to systematically study the cardinal number concept for arbitrary sets (both finite and infinite) was Georg Cantor (1845-1918). His researches have had a profound influence on al1 aspects of modern mathematics. In the remainder of this section, we will examine one of Cantor's most important ideas, and see in particular how it enables as to explain the concept of a finite set in more exact terms.

1-21

19

THE CARDINAL KUMBER OF A SET

DEFINITION 1-2.1. A pairing between the elements of two sets A and B such that each element of A is matched with exactly one element of B, and each element of B is matched with exactly one element of A , is called a one-to-one correspondence between A and B. The reader should study the following examples to be sure that he fully understands the meaning of the fundamental concept defined in Definition 1-2.1.

EXAMPLE1. Let A = (1, 2, 31, and B = (a, b, e]. Then there are six possible one-to-one correspondences between -4 and B: 1

5

a

2 b

3

1

5

5

c

2

3

1

5

5 5 5

b c a

2

3

c a b

3

1 2 3

1 2 3

5 5 5

1

2

5 5 5

5 5 5

b a c

a

c

b

c b a

EXAMPLE2. It is impossible to obtain a one-to-one correspondence between the set A = (1, 2, 3) and the set B = (1, 2). No matter how we try to pair , and B, we find that more than one element of A must off the elements of 4 correspond to a single element of B. If 1 t, 1 and 2 t, 2, then 3 must correspond 1, the element 1 E B to 1 or 2 in B. I n the correspondence 1 t, 1, 2 t, 2, 3 is paired with both 1 E A and 3 E A, so that the correspondence is not one-toone. A similar situation occurs in al1 possible correspondences between A and B. The more general fact that there is no one-to-one correspondence between (1, 2, 3, . . . , m) and (1, 2, 3, . . . , n) if m < n is also true. This can be proved using the properties of the natural numbers, which will be discussed in the next two chapters. EXAMPLE3. There is a one-to-one correspondence bet.c~-eenthe set Z = (. . . , -3, -2, -1, 0, 1, 2, 3, . . .) of al1 integers and the set N = (1, 2, 3, . . .) of al1 natural numbers. The elements of Z and N can be paired off as follows:

Note that in order to construct a one-to-one correspondence between Z and N, not al1 of the numbers of N can be paired with themselves. Otherwise, we would use up al1 of N and have nothing left to associate with O, -1, -2, . . . .

Usiiig Defiiiitioii 1-2.1, we caii clarify the notioil of a fiiiite set.

DEFINITION 1-2.2. Let A be a set and let n be a natural number. Then the cardinal iliimber of A is n if there is a one-to-oiie correspondence between A and the set (1, 2, 3, . . . , n), consisting of the first n natural

20

SET THEORY

[CHAP.

1

numbers. A set A is Jinite if A = @, or there is a natural number n such that the cardinal number of A is n. Otherwise A is called in$nite. This definition is no more than a careful restatement of the informal descriptions of finite and infinite sets, and their cardinal numbers, which were given a t the beginning of this chapter. The usual practice of writing a finite set in the form {al, az, a3,

, a,)

(without repetition)

exhibits the one-to-one correspondence between A and (1, 2, 3, . . . , n), namely, a l a 2 a3 . . . a,

Cantor observed that it is possible to say when two sets A and B have the same number of elements, without referring to the exact number of elements in A and B. This idea is illustrated in the following example. Suppose that in a certain mathematics class, every chair in the room is occupied and no students are standing. Then without counting the number of students and the number of chairs, it can be asserted that the number of students in the class is the same as the number of chairs in the room. The reason is obvious; there is a one-to-one correspondence between the set of al1 students in the class and the set of al1 chairs in the room.

DEFINITION 1-3.3. Two sets A and B are said to have the same cardinal number, or the same cardinality, or to be equivalent if there exists a one-to-one correspondence between A and B. By Example 1, the two sets {1,2,3) and {a, b, c ) have the same cardinality. By Example 3, so do the sets N and 2. However, according to Example 2, the sets {1,2, 3) and (1,2) do not have the same cardinal number . In accordance with Definition 1-2.3, the existence of any one-to-one correspondence between A and B is enough to guarantee that A and B have the same cardinal number. As in Example 1, there may be many one-to-one correspondences between A and B.

,

EXAMPLE 4. Every set *4 is equivalent to itself, since a ++ a for a E A is obviously a one-to-one correspondence of A with itself. If A contains more than one element, then there are other ways of defining a one-to-one correspondence of A with itself. For example, let L4 = (1, 2). Then there are two one-to-one correspondences of A with itself : 1 * 1, 2 t, 2 and 1 * 2, 2 o 1. Any oneto-one correspondence of a set with itself is called a permutation of the set.

1-21

THE CARDINAL KUMBER OF A SET

21

If A = {al, a2, . . . , a,) and B = {bl, b2, . . . , b,) are finite sets which both have the cardinal number n, then there is a one-to-one correspondence between A and B :

so that A and B are equivalent in the sense of Definition 1-2.3. That is, if A and B are finite sets, then A and B are equivalent if 1 A 1 = 1 BI. The important fact to observe about Definition 1-2.3 is that it applies to infinite as well as finite sets. One of Cantor's most remarkable discoveries was that infinite sets can have different magnitudes, that is, in some sense, certain infinite sets are "bigger than" others. To appreciate this fact requires some work. Example 3 has already illustrated the fact that infinite sets which seem to have different magnitudes may in fact have the same cardinality. An even more striking example of this phenomenon is the following one.

EXAMPLE 5 . The set iV of natural numbers has the same cardinality as the set F = (m/nlm E N, n E N) of al1 positive rational numbers. This can be seen with the aid of a dia.gram as in Fig. 1-2. By following the indicated path, each fraction will eventually be passed. If we number the fractions in the order that they are encountered, which are equal to numbers which have skipping fractions like S, 2, S, and

2,

22

SET THEORY

[CHAP.

1

been ~reviouslypassed, 1%-eget the desired one-to-one correspondence between N and F:

Cantor showed that many important collections of numbers have the same cardinality as the set N of al1 natural numbers. For example, this is true for the set d of al1 real algebraic numbers, that is, real numbers r which are solutions of an equation of the form

where no, ni, . . . , nk-1, n k are any integers. The set A includes al1 rational numbers, since m / n is a root of the equation nx - m = O; A also includes numbers like

d2,4%)4 3 , a,. . . .

Judging from these examples, one might guess that al1 infinite sets have the same cardinality. But this is not the case. Cantor proved that it is impossible to give a pairing between N and the set R of al1 real numbers. Later, we will be able to present Cantor's proof that these sets do not have the same cardinal numbers. The fact that the set A of real algebraic numbers has the same cardinality as N and the result that R and N do not have the same cardinal numbers together imply that R # A . That is, there are real numbers which are not solutions of any equation

with no, nl, . . . , nk-l, nk integers. This interesting fact is by no means evident. I t is fairly hard to exhibit such a real number, but Cantor's results immediately imply that they do exist. Although Cantor's work on the theory of sets was highly successful in many ways, it raised numerous new and difficult problems. One of these ranks among the three most famous unsolved problems in mathematics (the other two: the Fermat conjecture, which we will describe in Chapter 5 , and the Riemann hypothesis, urhich is too technical t o explain in this book.) Cantor posed the problem of urhether or not there is some set S of real numbers whose cardinality is different from both the cardinality of N and the cardinality of R. The conjecture that no such set S exists

1-21

THE CARDINAL NUMBER OF A SET

23

is known as the continuum hypothesis. I t was first suggested in 1878, and to date, it has been neither proved nor disproved. An infinite set is called denumerable if it has the same cardinality as the set N of al1 natural numbers. If S is denumerable, then it is possible to pair off the elements of S with the numbers 1 , 2 , 3 , . . . . Thus, the elements can be labeled a l , a2, a3, . . . , where a, is the symbol which stands for the element corresponding to the number n. Hence, if S is denumerable, then S can be written {al, a2, a3, . . .), with the elements of S listed in the form of a sequence. The converse statement is also true. That is, a set which can be designat,ed {al, a2, a3, . . .) is denumerable (or possibly finite, since distinct symbols might represent the same element of S). As we have shown in this section, the set of al1 integers and the set of al1 positive rational numbers are examples of denumerable sets. We conclude this section by listing for future reference the following important propert'ies of the equivalence of sets. (1-2.4). Let A, B, and C be arbitrary sets. Then (a) A is equivalent to A ; (b) if A is equivalent to B, then B is equivalent to A; and (c) if A is equivalent to B and B is equivalent to C, then A is equivalent to C. I t has already been noted in Example 4 that (a) is satisfied. Property (b) follows from the fact that the definition of a one-to-one correspondence is symmetric. That is, if A and B are interchanged in Definition 1-2.1, the definition says the same thing as before. Thus, a one-to-one correspondence between A and B is a one-to-one correspondence between B and A. The proof of (c) is left as an exercise for the reader (see Problem 8).

l. State which of the following sets are finite.

(a) {(x, Y,z>lxE (0, 1, 2)) Y E (3, 41, 2 E (0, 2,411 (b) ( X ~EXZ, x < 5 ) (e) {xlx E N, x2 - 3 = 0) (d) (x1x E Q, O < x < 1)

2. What is the cardinal number of the following finite sets? (b) {nln E 2, n2 5 86) (a) {nln E N, n < 1000) (d) (nln E N, n3 5 27) (e) (n21n E Z, n2 5 36) (e) {n31n.E N, n3 27) 3. Let A = (1, 2, 3, 4) and B = (a, b, c, d). List al1 one-to-one correspondences between -4 and B.




2

> +

Let us next consider Example 2 : If a -1, then (1 a)n 1 na. This example is somewhat different from the first one, since it has the form of a mathematical theorem, rather than a mathematical identity. As in the case of Example 1, the statement of Example 2 can be considered to be an abbreviation for an infinite sequence of statements:

If a If a If a

2. -1, 2 -1, 2 -1,

> 1 + a. + > 1 f2a. + > 1 + 3a.

then (1 + a ) then (1 a ) 2 then (1 a)3

In these statements, a represents an arbitrary real number, and we re-1 in each statement. Clearly, the first of these statements quire a is true. Let us try to proceed as in Example 1, using the nth statement of the sequence to prove the following statement. Assume then that -1, we have 1 a 2 0. Therefore, (1 a)" 1 na. Since a multiplying each side of the assumed inequality by 1 a preserves the direction of the inequality and gives

>

+

> +

>

+

+

Since a2 2 O for every real number a, it follows that

Combining these two inequalities gives the desired result,

I n this example, the argument needed to pass from statement n to statement n 1 is somewhat more complicated than the corresponding proof in Example 1. Nevertheless, it achieves the same end: from the truth of the first statement (n = l ) , the truth of the second statement (n = 2) follows; from the truth of the second statement, the truth of the third statement (n = 3) follows; and so on. Eventually every statement of the sequence is proved. Let us review the methods which we have used to prove the statements given in Examples 1 and 2. I t should be evident that both proofs follow the same outline. That outline, stated in general terms, is the principie of induction. The statements in Examples 1 and 2 involve an arbitrary natural number n. Thus, in both cases, we are presented with the problem of proving

+

2-11

57

PROOF BY INDUCTION

al1 of the statements in an infinite sequence P1, P2,P3,. . . of mathematical assertions. The procedure which we followed to prove these statements in the examples consisted of two steps. First, we observed that the first statement P1 of the sequence is true. Then we showed that for any n, it is possible to construct a proof of the statement Pn+l,based on the assumption that P, is true. This deduction of Pn+lfrom P, took the form of an ordinary mathematical argument (using logic and known mathematical facts). The number n occurred throughout the proof as a variable. For example, we could have substituted a number like 23 for each occurrence of n in the proof to obtain a deduction of Ps4 from P23. From these two steps in both Examples 1 and 2, it was concluded that al1 the statements were true. These conclusions were special cases of what is called the principle of mathematical induction. (2-1.1). Principle of mathematical induction. Let P1,P2,P3, . . . be a sequence of statements. Suppose that (a) P1 is true, and (b) for any n, if P, is true, then P,+l is true. Then al1 of the statements P1, Ps, P3,. . . are true. By assumption (a), P1 is true. By assumption (b) in the case n = 1, if P1is true, then P2is true. Thus P2is true. By (b) in the case n = 2, if P2is true, then P3is true. Thus P3is true. We can continue indefinitely in this way. Since any statement of the sequence will ultimately be reached, it follows that every one of the statements is true. To apply the principle of induction in making a mathematical proof, it is necessary to establish that conditions (a) and (b) are satisfied. The proof of (a) is usually called the basis of the induction while the proof of (b) is called the induction step. In carrying out the proof of the induction step, it may be assumed throughout the argument that the statement P, is true. This is called the induction hypothesis. I t should be noted however that the validity of the induction step does not necessarily depend on the truth of P,. For example, if P, is the 1)2 assertion "n2 n is odd," then Pn+l is the statement "(n (n 1) is odd." Since (n 1)2 (n 1) = n2 n 2(n l ) , it follows that if P, is true, then so is Pn+l(because the sum of an odd number and an even number is odd). That is, condition (b) is satisfied. However, P, is actually false for every n E N, since n2 n = n(n l), and a t least one of the natural numbers n or n 1 is even. Another aspect of the proof of the induction step which should be emphasized is that n must represent an arbitrary natural number (that is, a variable) throughout the argument. This is essential because the fact that P, implies P,+l is applied successively with n = 1, 2, 3, . . . .

+

+

+

+ +

+

+ +

+ + +

+

+

58

MATHEMATICAL INDUCTION

2

[CHAP.

EXAMPLE 4. We prove Theorem 1-6.4 (Example 3). The proof is a typical application of mathematical induction to establish a mathematical theorem. The statement to be proved for the basis step is the following: If {Al} is a pairwise disjoint collection of sets, then m(A1) = m(A1). This is obviously true. To prove the induction step, we make the induction hypothesis P,: If (Al, A2,

..

- 7

An)

is a pairwise disjoint collection of sets in S, then m(A1 U A2 U . m(A1) rn(*42) m(A,). The statement which has to be P,+i: If {Al, A2, . . . , A,, An+l) is a pairwise disjoint collection S, then m(A1 U A2 U U 14, U An+l) = m(A1) m(A2) . . m(A,+l). Note that by the definition of pairwise disjointness, if

+ +

+

U An) = proved is of sets in m(A,)

+ +

+

is a pairwise disjoint collection, then so is (Al, A2, . . . , A,}. tion hypothesis can be applied to obtain

+

Thus the induc-

Consequently, m(Ai) -4- m(Aa)

3-

4- m ( 4 4

+ m(An+l) =

m(A1 U A2 U

U A,)

+ m(A,+i).

+

We would like to conclude that m(Al U A2 U U A,) m(A,+l) = This conclusion is justified by Definition m(A1 U A2 U U A, U A,+i). 1-6.3, provided that A l U A2 U U A, and A,+l are disjoint. However by Theorem 1-5.4, An+i

n ( A l U A2 U

U A,)

(An+i n A l ) U (A,+l ri A2) U = @ U @ U . . . ~ =@ a, =

. U ( A , + ~n A,)

since {Al, A2, . . . , A,, ,4,+1) is a pairwise disjoint collection. Thus, we have shown that the truth of P,+l follows from the truth of P,. By the principle of induction, this proves Theorem 1-6.4.

1. Use mathematical induction to prove the following identities. (2n - 1) = n2 (a) 1 + 3 + 5 + - - . + s ~ ( n 1)(2n 1) (b) 1 2 + 2 2 + 3 2 + - . - + n 2 = 1 (2n 1 ) 2 = +(n 1)(2n 1)(2n (c) l 2 32 52 l6 z6 36 (-i),-'n6 (d)

+ + + + + + +

+

+

+

+

+ 3)

2-11

PROOF BY INDUCTION

2. Use mathematical induction to prove the following identities.

3. Use mathematical induction to prove the following identities. (a)

(1 2 . 312 - ( 2 . 3 . 4)2

+ ( 3 . 4 - 5)2 -

+ (-Un-'[n(n + l)(n + 2)12 L

(b)

4. Use (a) (b) (c)

( 1 . 2 - 3 . . . r ) + [ 2 . 3 . 4 . - . (r+ 1)]+[3.4-5.e. (r+ 2)]+.-[n(n 2) (n -01

+ + +

+

mathematical induction to prove the following identities. 1+2+22+.**+2n-1 = 2"-1 n(+ln-l = 4 - (n 2) (+) "-l 1 2(+) 3(+)2 3 + 33 + 35 + . . . + 32-1 = 3s(9" - 1)

+

+

+

+ +

5. Use mathematical induction to prove the following identities. (a)

1 -1

-(

1-

)

(

1-

1

)

1 n+1

= ---

6. Let t be any real number different from 1. Use mathematical induction to prove the following identities.

(a)

i+t+t2+...+tn-'

tn - 1 t -1

= -

MATHEMATICAL INDUCTION

[CHAP.

2

7. Use mathematical induction to prove the following inequalities. (b) 2fl+3 < ( n + 3)! (a) n < 2, r ) !, where r E N. (c) n ! r ! < (n 8. Prove that for al1 natural numbers m and n, m(m 1) . (m n - 1) is a multiple of n. 9. Prove by mathematical induction that if O al 5 1, O 5 a2 5 1, . . . , ( 1 - a,) 2 1 - al - a2 - a,. O 5 a , 5 l , t h e n ( l - a l ) ( l - a2)

+

+

+




I t is important to show that inductive definitions give uniquely determined objects 0, for every natural number n. That is, we would llke to know that there exists a sequence 01, 0 2 , . . . , O,, . . . of objects such that O, satisfies C, for every n 5 k, and 0, satisfies K for n > k, and that if Oí, OS, . . . , O;, . . . is any sequence of objects such that 0; satisfies Cn for n 5 Ic, and 0; satisfies K for n > k, then Oi = 01, 0; = 0 2 , . . . , 0; = O, . . . . This can be proved using the induction principle for the natural numbers (2-5.1).

THEOREM 2-6.1. Suppose that Cl, C2, . . . , Ck, and K are conditions having the properties stated in (1) and (2) above. Then there is a unique sequence 01,02,. . . , O,, . . . of objects such that O, satisfies Cn for n 5 k, and 0, satisfies K for n > k. Proof. Let S be the set of al1 natural numbers m such that there are unique objects 01, 02,. . . , Om with the properties that for n 5 m and n 5 Ic, O, satisfies C,, and for Ic < n _< m, O, satisfies K (provided m > k). Then 1, 2, . . . , and k are in S, since by ( l ) , conditions C1, C2, . . . ! Ck, respectively, determine unique objects 01, 02, . . . , Ok. Suppose that some m 2 k belongs to S. Then by (2), there is a unique object satisfying K. Therefore there are unique objects 01, 0 2 , . . . , Om, such that O,(n 5 m 1) satisfies C, for n 5 Ic, and 0, satisfies K for n > k. Thus m 1 E S. Hence, S satisfies the conditions of (2-5.1), and therefore every natural number is in S. This means that there is a unique sequence 01, 02,. . . , O,, . . . of objects such that O, satisfies C, for n 5 k , and 0, satisfies K for n > k.

+

+

As one might expect, if objects 0, are defined inductively, then mathematical induction is an important tool for establishing the properties of these objects. We illustrate this fact by obtaining an estimate of the size of the Fibonacci numbers. Let a be a positive real number satisfying 1 a = a2. Then a is a solution of the equation x2 - x - 1 = O. By the formula for the roots of a quadratic equation, the solutions of this equation are i ( 1 6 ) and s ( 1 - fi).Of the solutions, only the first is positive. Thus, a = +(1 6 ) . In particular, a > 1. Hence, u1 = 1 < a and u2 = 1 < a < a2. Make the induction hypothesis that u, < am for al1

+

+

+

2-61

81

INDUCTIVE DEFINITIONS

5 n. Then

m

Thus by the principle of induction we conclude that u, < a", for al1 n. Note that although we do not know an explicit formula for the number u,, we can nevertheless find some of its properties. This is typical of objects which are defined inductively:

1. Using the inductive definition of Example 1, prove that

and if O

< x < y, then O < xn < y".

2. Give an inductive definition for the sums in Problems l(a), 2(a), 3(a), and 4(a) of Section 2-1. 3. Give an inductive definition of n! 4. Give an inductive definition of nx (the operation of adding x to itself n times), and prove that this is the sarne as the operation of multiplying x by n. 5. List the first 50 terms of the Fibonacci sequence. 6. Show that no two consecutive terms of the Fibonacci sequence are divisible by the same natural number greater than one.

7. I n the Fibonacci sequence ul, u2, . . . , u,. n is a multiple of 3 and that u, is odd otherwise. an

8. In the Fibonacci sequence ul, u2, where a = + ( l d5).

< u,+2,

+

+

. . , show that

. . . , u,, . . . , show

u, is even if

that for al1 n,

9. Let a = + ( l d 5 ) and b = +(1 - 4 5 ) . Prove that if u, is the nth term of the Fibonacci sequence, then u, = (1/2/5) (an - bn). 10. Let the sequence vi,

v2, 03,

. . . be defined inductively by

List the first 25 terms of this sequence. Show by induction that for any natural numbers m and n, 2um+, = umvn unvm, where ui, u2, . . . , U,, . . . is the Fibonacci sequence.

+

CHAPTER 3

THE NATURAL NUMBERS 3-1 The definition of numbers. If you were to ask a person with an average education to define mathematics, his answer might be "the science of numbers. " Although this definition does not convey much information, it would be hard to find a more concise description of mathematics. Almost al1 of mathematics is concerned directly or indirectly with ordinary numbers. For this reason, it is important to examine carefully the concept of number, a notion which up to now has been taken for granted. What are numbers? This is a question of concern to both mathematicians and philosophers. Many answers have been gjven, but none can be considered to be final. However, 19th century mathematical research has shown that the common number systems (the integers, rational numbers, real numbers, and complex numbers) can al1 be constructed from the natural numbers. The question "What are numbers?" is therefore replaced by the apparently simpler problem "What are natural numbers? " In this chapter, we will discuss the natural numbers. In later chapters, the integers, rational numbers, real numbers, and complex numbers will be studied in turn. We will concentrate on the basic properties of each number system, and discuss the extent to which these properties determine the system. The intuitive idea of the various kinds of numbers which students develop in school will be critically examined. Finally, we will indicate the processes by which the integers are formally constructed from the natural numbers, the rational numbers are obtained from the integers, the real numbers are defined from the rationals, and the complex numbers are constructed from the real numbers. I t is important for advanced mathematics students to go through the constructions of these number systems in detail, but students a t an elementary leve1 will find the process long and tedious. I t is better for beginners to concentrate on understanding the definitions and why they are made. The text which follows aims to present a guide toward such understanding. A complete development of the number systems will be given in the form of problems, and interested students are invited to work out the details for themselves. The concept of a natural number was developed over a period of many centuries as a tool for counting the objects in sets. That is, the natural numbers were introduced as labels to designate the property shared by sets of equal cardinality (in the sense introduced by Cantor, see Section 1-2). Thus, when two traders of ancient Egypt agreed to exchange

3- 11

THE DEFISITION

OF XUMBERS

83

three camels for seven wives, it was essential that both understood how many items he would have to give up and how many he would receive. This understanding could be achieved, for example, by means of "counters, " that is, collections of stones from which sets of small cardinality might be formed in the palm of the hand. I+om very early times, numbers have been treated as concrete objects, rather than the names of properties of sets. I n fact, this fictitious viewpoint was essential for the creation and development of mathematics. I t was not until the 19th century that mathematicians started wondering how to justify the existence of numbers. One of the earliest attempts to define the natural numbers as objects was made by the German mathematician Gottlob E'rege (1848-1925) in a book on the foundations of arithmetic, published in 1893. Basing his work on Cantor's set theory, Frege defined the cardinal number of a set A to be the class of al1 sets which are equivalent to A by Cantor's definition of equivalence (see Definition 1-2.3). According to Frege's definition, the cardinal number of {O, 1) is the class of a11 sets {al, a2), where a l and a2 are distinct objects. Similarly, the cardinal number of (1, 11, 111) is the class of al1 sets {al, a2, a3), where a l , a*, and a3 are distinct elements. The natural numbers are defined to be the cardinal numbers offinite sets. Thus, the number "2" is a set, namely, the set of al1 pairs of distinct objects. Frege's definition of the natural numbers is therefore based on two concepts: the notion of a finite set, and the definition of the cardinal number of an arbitrary set. I n Section 1-2, it was taken for granted that the natural numbers existed, and that their properties were well known. Thus, it made sense in Definition 1-2.2 to define a set to be finite if it was equivalent to (1, 2, . . . , n) for some natural number n. This definition cannot be used if the natural numbers are defined as in Frege's program, using the concept of a finite set. This difficulty can be avoided by defining a set A to be finite if and only if there is no one-to-one correspondence betiveen A and a proper subset* of A . I t turned out that there was a more serious flaw in the second notion which enters into Frege's definition of the natural numbers. Unless handled with great care, the concept of the class of al1 sets which are equivalent to a given set A leads to perplexing logical contradictions. Exactly how much care is needed to avoid these contradictions is somewhat uncertain even now. Thus, the definition of the cardinal number of an arbitrary set which Frege used is unacceptable, and therefore so is his construction of the natural numbers.

* I t is possible to give a convincing argument that this definition of a finite set agrees with the intuitive idea of such a set. For examplc, see The Foundations oj ~Jiathematicsb y R. L. 1j7ilder, pp. 62-71. TViley (1952)) New York.

84

THE NATURAL XUMBERS

[CHAP.

3

A more satisfactory definition of the natural numbers was given by John von Neumann (1903-1957) in 1923. von Neumann observed that any standard sequence of sets, containing what we would intuitively recognize as 1, 2, 3, 4, . . . elements, respectively, can be adopted as the sequence of natural numbers. He showed that a convenient choice for this standard sequence is

These particular sets* are now usually called Jinite ordinal numbers. The elements of each such ordinal number n are the empty set, and al1 ordinal numbers which precede n. Usually, the number O (zero) is included among the ordinal numbers. If this is done, then according to von Neumann's definition, O would have to be the empty set, since is the only set which contains no elements. With this convention, the definition of finite ordinal numbers is very natural: n is the set of al1 ordinal numbers which precede it. In this book, we will consider O to be an ordinal number, but not a natural number. This convention simplifies certain statements concerning the arithmetic of N, for example, the cancellation law of multiplication. In order to develop some of von Neumann's theory of the natural numbers, we must give an exact definition of these objects. The method by which the natural numbers can be generated is clear: and =

{a, 1, 2,

. . . ,n

-

1) U {n) = n U (n).

Starting with 1 = {a), we obtain successively

u

=

{a)

3 = 2 U (2)

=

{a, 1) U (2)

=

1

u

(1)

2

(1)

=

{a, 1) =

=

(a, {a)),

{a, 1,2) =

{a, (a;,, {a, (al-)),

and so on. Every natural number is ultimately obtained by this process.

* The reader should remember the convention discussed in Section 1-1 that an object a is to be distinguished from the set {a) whose only element is a. Thus, 1 = (a) # a , and 2 = (a, {a)) Z {a, a ) = {a) = 1, etc.

3-11

THE DEFIXITIOS

OF NUMBEHS

85

DEFINITION 3-1.1. (a) ( n. (d) I'rove these cases (see 3-3.5). (e) I'rove al1 other cases, eithcr dircctly or by reducing them to the cases treated in (d).] .

8. Gsing Dcfinition 4-1 .5, prove that if c and d are intcgers, and c # O, d # 0, then c d # O. llsing this fact together with the distributive law (4-1.6e) and the result of Problem 6, prove (4-1.6~).

+ +

+ +

9. Prove the associativc law of additiori a (b c) = (a b) c. [Hints: (a) Cse (4-1.4~) to prove the law in al1 cases in which a t least one of a, b, or c is zero. (b) Enunlerate thc eight possible cases in which none of a, b, or c is zero. a = -a, and use this fact together with the distributive (c) Prove that (-1) law to reduce these eight cases to thc three cases: (i) k+ (m+ n) = (k+ m) n, and (iii) k [(-m) n] = (m n) = [(-k) m] n, (ii) (-lc) [k (-m)] n. (d) Complete the proof outlined in Example 2 of case (ii). (e) Give the proof of case (iii) .]

+

+ + +

+ +

+

+

+

4-2 Rings. Starting with the properties of addition and multiplication given in (4-1.4) and (4-1.6), it is possible to develop many useful facts about the integers. However, as t,he reader may have noticed, the system of rational numbers and the real number system also satisfy the identities listed in (4-1.4) and (4-1.6). Therefore, if we prove a theorem about the integers using only the facts contained in (4-1.4) and (4-1.6), the samc theorem should be true for the rational numbcrs and real numbers. There is oiie trouble with this usefiil observation. In order to carry a theorem which has been stated and proved for the integers over to the real or rational numbers, it is necessary to examine the proof of the theorem to be sure that it uses only properties which can be deduced from (4-1.4) and (4-1.6). Mathematicians have solvcd this problem by a simple but powerful idea. They have introduced a new term, "integral domain," to describe al1 systems on tzrhich are defined tmo operations (called addition and multiplication) satisfying al1 of the laws given in (4-1.4) and (4-1.6). Then, if a theorem can be deduced from the properties listed in (4-1.4) and (4-1.6), it is a theorem about integral domains, meaning that it is true for every system ~vhichsatisfies (4-1.4) and (4-1.6). In particular, it is true for the integers, rational numbers, and real numbers. 111this section, ure deal with systems which are defined by a set of axioms, without concern for thc nature of the particular systems under consideration. Such a viewpoint is called abstract. There are several advantages (other than the possible economy of being able to treat many systems a t

4-21

RINGS

107

once) to be gained by an abstract approach t o mathematics. One of them is that in working with an axiomatically defined object, rather than a specific one, there is a n economy of ideas and concepts. Al1 of the superfluous notions and facts are thrown away, and our concentration is focused on the essential features of the object which we are studying. The abstract axiomatic approach to problems and theories has become a dominant feature of modern mathematics. hloreover this viewpoint is gaining importance in physical and social sciences. Anyone who wants to know what is current in science, particularly mathemat,ics, must become acqiiainted with abstraction. Instead of considering integral domains immediately, we introduce a more general concept,.

DEFISITIOS 4-2.1. A ring is a set A oii which are defined two biiiary operations x y and x y (called nddition and multiplication), and a unary opcration -x (called negation), such that A contains among its elements a particular one O (called the xero* of A ) , and the following idcntities hold for al1 .r, y, and x in :

+

(a) (b) (c) (d) (e) (f) (g)

x + y = y +x; x (y 2 ) = (.r y) 2; x o = x; x (-2) = 0; x (y x) = (x y) x; 2) = (.c . y) -.t(x 2); x (y ( x + y ) . x = (x.2) (y-2).

+ +

+ +

+ +

+

+

I t must be strongly cmphasized that in the definition of a ring A, nothing is assumed about the natiirc of the elemcnts of A . Any collcction of objects for which operations x y, .r y, and -z are defined satisfying (a) through (g) is eligible to be called a ring. 'Liloreovcr, although the opcrations of a ring are called "addition, " "multiplicatioil, " and "negation," they need not a t a11 resemble the familiar operations of addition, multiplication, and negation of numbers. Thc only reyuirement is that therc are definitions which, for every x and y in A, determine the elements represented by x y, x y, and -x. I t should also be remembered that a ring is determined not by its elements alone, but by the elements, togethcr with the operations of addition, multiplication, and negation. There are important examples of differcnt rings having the same set of elements.

+

+

* The use of the symbol O to rcprcscnt the zero ir1 cvcry ring is a long-standing mathematical tradition. Thcrc are instances in whicli this convention might cause confusion, but thcy are rare.

108

TIIE INTEGERS

[CAAP.

4

EXAMPLE 1. Thc numbcr systems Z (the intcgers), Q (the rational numbers), and R (the real numbers), with their familiar operations, are al1 rings. In fact, as we have already obscrved, these systems are integral domains, that is, they satisfy thc laívs given in (4-1.4) and (4-1.6). I t is easy to see t h a t (4-1.6a) and (4-1.6e) together imply Definition 4-2.1 (g), so that any integral domain is a ring. EXAMPLE 2. The sct (2aja E Z ) of al1 even integers is a ring, again with the familiar opcrations.

EXAMPLE 3. Let 24 = {a, 0). Define (a) a + a = O , a + O = a , O + a = a , 0 + 0 (b) a - a = a, a - O = 0 , O . a = 0 , O . O = 0; (c) -O = O, -a = a.

=

0;

Then -4 is a ring. The symbols a and O may be interpreted in this exaniple as rcprcscnting the l->ropcrticsof an integer being odd or even. Howevcr, such an interprctation has no bearing on the question of A bcing a ring.

EXAMPLE 4. Let 11 = P(S), the set of al1 subsets of a set S. For X E A and Y E 1.1 (that is, X and Y are any subscts of S), define

X+ Y

=

( X n YC)u ( S c n 1');

x.Y = x

Y

-X

=

X.

Then with thcse operations, ;l is a ring. Nore generally, if A is any collection of subscts of S such that if ,Y and Y are in 11, then X U Y and X n Yc are in A, then i l is a ring with respect to these operations. These are the collcctions which \ve callcd rings of sets in Section 1-6. Thc fact that these collections form a ring justifics the tcrminology "ring of sets."

The reader should verify that Examples 3 and 4 are rings as \ve claim (see Problem 14, Sectioil 1-4). It should be noted that the commutative 1aw of miiltiplication, n: y = y x, is not postulated for rings. If a ring satisfies the identity x y = y x, then it is called commutatice. There are important examples of rings which are not commutative, one of ivhich will be given in Chapter 10. Because the commutativc larv for multiplication is omitted from the postulates for a ring, it is necessary t.0 state both distributive laws, x (y x) = x . y z and (.c y ) x = z x y x. If the ring is commutative, then either of thcse laws can be deduced from the other. For example, (x y ) x = x (.c y) = x .z: z y =x x y 2.

+

+

+ +

+

THEOHEM 4-2.2. Let A be a ring, and let (-2)

+

2 =

o.

+

+

2

E

,4. Then O

+

+ n: = x and

THEOREM 4-23. J,et A be a ring aiid let x, 11, and x he any elcmcnts of A . (a) If x x = y x, theii .l: = y. (b) If x n: = -C y, t,hen x = y.

+ +

+

We leavc the proof of Theorem 4-2.2 as an cxercise for thc rcader. T o prove Thcorem 4-2.3(a), supposc t,hat x x =y 2. Thcn, by Dcfinition 4-2.l(b), (c), and (d), z = x O =z [X (-x)] = (2 x) (-2) = (y X) (-2) = y [Z (-x)] = y O = y. The implication (b) folloivs from (a) and the commutative law, 4-2.l(a).

+ + +

+ +

+

+ + +

+ +

+

TIIEOREM4-2.4. Let A be a riilg, and let r a i ~ dy be elemcilts of 11. Then (a) -(-X) = X ; (b) (-2) (-y) = - ( . E -1- y); (c) 2 . 0 = 0 . x = o ; (d) (-x) y = z ( - l j ) = -(z y); (-y) = x y. (e) (-x)

+

I t is not hard to prove the identitics of Theorem 4-2.4 for the integers by the direct use of Definit,ioris 4-1.2, 4-1.3, and 4-1.5. I t is significant however that the proof for general rings is simpler and more clegant. To prove (a), note that by Definition 4-2.1(a) and (d),

Thus, by Theorem 4-2.3, .x = -(-x). The proof of (b) also uses thc cancellatiori law, Theorem 4 - 2 3 By Definition 4-2.1 (a), (b), (c), (d), and Theorem 4-2.2, \ve obtain (.E y) [(-x) (-Y)] = (Y x) -1 [(-x) (-y)] = Y [x ( ( - 4 (-u)I = y [(x (-x)) (-y)] = y [O (-!/)1 = Y (-y) = 0 =-(-y) = -(.L y). (X y) [-(x y)]. Thus, (-2) By Definition 4-2.1 (e), O O = O. Therefore x O -1O = .r O = .r (O 0) = (x 0) (.E O) by Definition 4-2.1 (f) and (e). Lysing Thcorem 4-2.3, \ve obtain x O = O. Similarly, O . x = O. This proves (4 To provc (d), use the distributive law, Definition 4-2.l(f) and (g), togcther with the result just proved, and the cancellation law, Theorem 4-2.3. For instance, x y $- (-m) . y = [x (-z)] y = 0 y = O = y = (z y) [-(x y)] by Definition 4-2.1 and (c). Therefore, (-2) - (z y) by Theorem 4-2.3. Thc final statement (e) of Theorem 4-2.4 is obtaincd by tn-o applications of part (d), together with (a) : (-.x) (-y) = -[.x (-y)] = - [ - ( J y)] = x0y. From a mathcmatician's viewpoiiit, the advantage of the integcrs over the natural numbers is that thc integers are closed under subtraction. That is, if a and b are any iritegers, then it is al~vayspossible t'o find an intcger n: which is a solution of

+ + +

+ + +

+

+

+ +

+ + +

+ + + + + + +

+

+

-+

+

As a matter of f w t , subtraction is always possible in any ring.

110

[CHAP. 4

THE IKTEGERS

THEOREM 4-2.5. Let A be a ring. Let x E A and y E A. Then there is x = x, namely x = one and only one element x E A satisfying y x (-Y>.

+

+

+

+ +

+

+ +

Proof. Let x = n: (-y). x =y [x (-y)] = y Then y [(-y) + x ] = [y (-y)] x = O + x = x + O = x, bythefirstfour (-y) is a solution of y laws of Definition 4-2.1. Therefore, x = x x = x. On the other hand, if x is a solution of y x = x,then x (-y) = (y 2) (-y) = ( 2 y) (-y) = 2 t [y (-y)] = x O = x. Hence, x = x (-y) is the unique solution of y z = x.

+

+ +

+

+

+ +

+ +

+

+

+

+

It is customary to use the subtraction notation x - y to denote the solution of the equation y x = x in an arbitrary ring. That is,

+

The postulates for rings can be given using the binary operation of subtraction instead of the unary operation of negation. [Definition 4-2.l(c) and (d) are replaced by the single identity y (x - y) = x.] However, Definition 4-2.1 is more familiar and,convenient. As we have pointed out in Example 1, the systems Z and Q of integers and rational numbers are rings. Also, Z is a subset of Q. However, more can be said: the operations of addition, negation, and multiplication in Q of the elements belonging to Z agree with the usual operations for the integers. In the study of rings, this situation occurs frequently enough to justify the introduction of a special term to describe it.

+

DEFIKITIOX4-2.6. Let A be a ring. A nonempty subset B of A is called a subring of A if for every x and y in B (not necessarily different) the sum x y, the negative -x, and the product x y al1 belong to B.

+

+

Since x E B, y E B implies that x E A and y E A, the sum x y, negative -x, and product x y always exist as elements of A. The condition that B be a subring is merely the added assumption that these elements are in B and not just A. If B is a subring of A, then the operations of A, applied to B, can be considered as operations on B. The set B with the operations which it inherits from A forms a ring because the identities of Definition 4-2.1 are automatically satisfied in B, so that the term subring is justified. I n speaking of a subring B of A, it is customary to think of B as a ring with the ope O, then by Theorem 4-6.2(h),

Thus, as before, min { y x l , y

. . . , y . xn)

~ 2 ,

=

Y

This proves the first part of (b). If 2~

max { y . x l , y a x 2 , .

. . , y - x,)

=

y.

Xi =

y min ( ~ 1X,2 ,

. . . , x,).

< O, then by Theorem 4-6.2(i),

Xi =

y 0 m i n( x l , ~

. ., ~ n ) .

2 , .

This proves the first part of (e). The second statement of each part of the theorern is proved in a way which is similar to the proof of the first statement.

132

THE INTEGERS

[CHAP.

4

DEFINITION 4-6.6. Let A be an ordered integral domain. Suppose that x E A. The absolute value of x, denoted* by 1x1, is defined to be 1x1 = rnax (x, -x). In other words, 1x1 = x if x integers for example,

2

O and 1x1 = -x if x

< O.

Thus, in the

THEOREM 4-6.7. Let A be an ordered integral domain, and let x and y be arbitrary elements of A . (a) 1x1 2 O; moreover, 1x1 = O only if x = 0. (b) If x > O, then Iyl x if and only if -x y x.

<
0.


1 and c > 1. Suppose that b 5 c. (One of the factors of a is less than or equal to the other one, and we can denote that factor by b.) Assume that b > d a . Then c 2 b > 4;. Therefore, a = b c > sible. Since the assumption that b > & led to a contradiction, we can conclude that b 5 &. By Theorem 5-3.3 or Example 2, Section 2-3, b is divisible by a prime p. Hence a = b c is divisible by p where p 2 b .da. To test whether a natural number a is a prime, it suffices by (5-4.1) to divide a by al1 primes which are not larger than .\/a. If each division has a nonzero remainder, then a is a prime. For example, consider a = 787. Since 2g2 = 784 and 2g2 = 841, 28 < < 29. The primes which are 2, 3, 5 , 7, 11, 13, 17, 19, and 23. By trial we are not larger than find that 787 is not divisible by any of these primes. Therefore, by (5-4. l ) , 787 is a prime. The first tables of prime numbers were compiled by a simple process based on (5-4.1). This method "sifts" the composite numbers from the sequence of al1 natural numbers which are less than or equal to some fixed natural number. The process is credited to the Greek mathematician Eratosthenes (276-194 B.C.). Suppose that we wish to find al1 primes 100. By (5-4.1), every composite number 5 100 is divisible by a prime p -\/iOO = 10. Therefore, the primes 5 100 are those numbers which are not proper multiples of 2, 3, 5, and 7. Thus, if we let the multiples of 2, 3, 5, and 7 fa11 through a sieve which contains the first hundred natural numbers, the primes will be left. This process, the sieve of Eratosthenes, is illustrated in Fig. 5-1. \/a


4, and in fact F, has been shown to be composite for 28 values of n. Nevertheless, the Fermat numbers have numerous interesting properties. A related class of numbers from which one might hope to obtain primes is given by the formula M, = 2,

-

1,

p a prime.

These are called Mersenne numbers after a rather undistinguished French mathematician hlarin Mersenne (1588-1648)) who asserted in 1644 that M, is a prime for p = 2, 3, 5, 7, 13, 17, 19, 31, 67, 127, and 257, and is composite for al1 other p less than 257. I t has since been shown that Mersenne's statement was incorrect: M67 and M257are not primes, and and Mio7 are not composite. There is an efficient method for MG1, testing whether certain Mersenne numbers are primes. This test has been used (with the aid of an automatic digital computer) to find the largest known prime M2281,a number with 686 digits. I t is not known, however, whether there are infinitely many Mersenne primes. There are two apparent ways to generalize the Mersenne numbers: replace 2 by an arbitrary natural number a > 1, and drop the restriction that the exponent p be a prime. Keither of these generalizations leads to new primes, however.

THEOREM 5-4.3. Let a and n be natural numbers greater than 1. Suppose that k = a" - 1 is a prime. Then a = 2 and n is a prime.

+

+ +

Proof. If a > 2, then lc = a" - 1 = (a - l)(an-1 anW2 1) has a proper divisor a - 1 which is larger than l . This contradicts the assumption that Ic is a prime. Hence, a = 2. If n = r S, where r > 1

5-41

163

MORE ABOUT PRIMES

and s > 1, then lc = 2 ° C 1 = bs - 1, where b = 2' > 2. As we have just seen, this implies that lc is composite. Thus, n is a prime. The Mersenne primes are closely connected with a class of numbers which greatly interested the ancient Greeks: the so called perfect numbers. A perfect number is a natural number which is equal to the sum of its proper divisors, that is, the sum of al1 of the divisors except the number itself. 3 and 496 = 2*. 31 = 1 2 4 8 For example, 6 = 1 2 16 31 62 124 248 are perfect numbers. Since a(n) is the sum of al1 of the divisors of n, including n, n is a perfect number if and only if a(n) = 2n. From Euclid's time a rule has been known for determining al1 even perfect numbers.

+ + +

+ + +

+ + + +

THEOREM 5-4.4. A number of the form

where p and 2" - 1 are primes, is a perfect number. Conversely, if n is an even perfect number, then n is of this form.

Proof. If n = 2p-'(2p (5-3.5) ,

-

1))where p and 2" - 1 are primes, then by

Hence, n is a perfect number. Conversely, suppose that a(n) = 2n, where n is even. Since n is even, n = 2' k where 1 > O and k is odd. Therefore, a(n) = 42') a(k) (see Problem 7, Section 5-3), and

Since 2 is the only prime dividing 2"') and 21f' - 1 is odd, it follows that 2'+' and 2'+' - 1 are relatively prime. In view of the equality

Theorem 5-2.5 implies that (2'+' - 1) divides k. Thus, k = (2'+'

-

1) . m

and

a(k) = 2'+'

m.

164

ELEMENTARY NUMBER THEORY

Now m and k are divisors of lc and

Thus, the sum of al1 of the divisors of k is the sum of the two divisors m and k. Hence, 1c has only two divisors. This implies that m = 1 and 7 is a prime. Moreover k = 2'+' - 1. Thus,

where k = 2"' - 1 is a prime. By Theorem 5-4.3, 1 prime p. Therefore, n = 2 ~ - ' ( 2 ~- 1 ) )

+ 1 must also be a

where p and 2P - 1 are primes. Whether there are any odd perfect numbers is another unsolved problem in number theory. Results have been obtained which show that if an odd perfect number exists, it must be larger than 2,200,000,000,000.

1. Determine which of the following natural numbers are primes and justify your answer. (a) 503 (b) 943 (c) 1511 (d) 213 - 1 (e) 899 2. Use the sieve of Eratosthenes to compile a table of primes less than 300. 3. Prove that the only prime triple (that is, three consecutive primes of the form p, p 2, p 4) is 3, 5, 7.

+ +

4. Show that 28 is a perfect number.

5. Show that 33,550,336 is a perfect number. 6. Show that 2,096,128 is not a perfect number.

7. (a) Prove that if m < n, then F, divides F, - 2 (where F, and F, are the Fermat numbers 22m 1 and 22n 1). (b) Show that if m # n, then F, and F, are relatively prime. (c) Use the result of (b) to give a new proof of Euclid's Theorem 5-4.2. 8. Show that if n is a natural number and if k = 2" 1 is a prime, then n is a power of 2.

+

+

+

9. (a) Prove that the product of natural numbers which are al1 of the form 3s 1 is a number which is again of this form. (b) Use this remark to prove that there are infinitely many primes of the 2, that is, that the infinite sequence 5, 8, 11, 14, 17, . . . of natural form 3x numbers contains infinitely many primes. [Hint: Proceed as in the proof of

+

+

5-51

THE FUNDAMENTAL THEOREM OF ARITHMETIC

165

Theorem 5-4.2. Suppose that there is only a finite number of primes of the form 3x 2. List them all: 5, 11, 17, . . . , p,

+

where p is the largest such prime. Show that the number

is divisible only by primes of the form 3x contrary to (a).]

+ 1, but n itself is not of this form,

"5-5 Applications of the fundamental theorem of arithmetic. The importance of the fundamental theorem of arithmetic can hardly be overestimated. This fact can be appreciated after some applications of the theorem are examined. In this section, we will present four different applications. Numerous others will appear later in the book. Godel numbering. Any scheme which associates a natural number with each sentence, or sequence of sentences, in some language in such a way that different expressions are associated with different numbers is called a Godel numbering of the language (after the mathematician Kurt Godel, who used such a numbering to prove important results in mathematical logic). One of the ways in which this can be done depends on the fundamental theorem of arithmetic and the fact that there are infinitely many prime numbers (Theorem 5-4.2). Nearly al1 expressions in the English language can be written using 38 symbols and a space marker. The symbols are the 26 letters of the alphabet, the period, question mark, exclamation point, comma, colon, semicolon, hyphen, apostrophe, two parentheses, and two quotation marks. Associate the numbers 1 to 38 with these symbols in the given order, that is,

1

2

3

1

5

5

A

B

C

. . . 26 27 28 . . . 37 38

5 2

5 .

1

1

5

?

Lt

>>

Associate zero with the space symbol. Let pl, p2, p3, p4, . . . denote the sequence of al1 primes in the order of increasing size. That is, pl = 2, p2 = 3, p3 = 5, pq = 7, . . . . I t is now possible to define a Godel numbering of the English language by associating with the expression

(where the si are either one of the 38 symbols listed above, or else a space marker) the number p11p?p33 Pnen,

166

ELEMENTARY PXJMBER

THEORY

[CHAP.

5

where ei is the integer from O to 38 which corresponds to si. For example, the number associated with the expression GEORGE WA4SHINGTON

Since there are infinitely many primes, this scheme associates numbers with expressions of any length. Of course, the numbers involved may be very large. The number associated with the expression GEORGE WASHINGTON has more than 250 decimal digits. Nevertheless, even the text of a book such as the King James version of the bible (written in capitals, and with numbers written out) has a uniquely associated number. I t is theorectically possible to determine any expression from the knowledge of its corresponding number. For example, the number

factors to

and therefore

1 DO is the expression from which it is obtained. Different expressions must correspond to different numbers, since by the fundamental theorem of arithmetic, two different products of primes cannot be equal to the same natural number. Thus, our scheme satisfies the requirements for a Godel numbering of the English language. The scheme for constructing a Godel numbering which we have presented is not very practical, since the numbers involved are usually very large. However, when applied to formal mathematical languages, the method has important theoretical consequences for logicians and philosophers. A cardinal number problem revisited. In Section 1-2, we showed that the set F of al1 fractions a / b (where a and b are natural numbers) has the same cardinality as N, the set of natural numbers. We will now use the fundamental theorem of arithmetic to give another proof of this fact, that is, to establish a one-to-one correspondence between N and F. First, define a one-to-one correspondence between the set of al1 nonnegative integers and the set of al1 integers in such a way that O corresponds to O. Any such

5-51

THE FUNDAMENTAL THEOREM O F ARITHMETIC

correspondence will do, but to be specific, let

For each nonnegative integer e, let correspondence. For example,

stand for the mate of e under this

THEOREM 5-5.1. With each natural number

where p,, pz, . . . , pQ are distinct primes and e l , ez, negative integers, associate the fraction

. . . , e, are non-

Then the association a ++ r is a one-to-one correspondence between N and F. Before discussing the proof of this theorem, let us compare the correspondence between N and F given by Theorem 5-5.1 with the correspondence defined in Section 1-2. We see immediately that they are different. For example, with the definition given in Theorem 5-5.1,

which bears no resemblance to the correspondence given in Section 1-2. The correspondence of Section 1-2 was defined in rather vague terms. We gave no rule stating what fraction would correspond to a specific natural number n. Instead, it was pointed out how one could, with sufficient patience, find the fraction corresponding to any particular n. For large values of n, the method would not be practical. For example, to find the fraction corresponding to 90,000,000 would be a long, tedious job. On the other hand, the correspondence given by Theorem 5-5.1 is much more explicit. To apply the rule, the only requirement is that we be able to factor the natural number a into its prime factors. For example, the number 90,000,000 = 27 32 . 57 corresponds to 2-* 3 5-4 = 3/10,000. For a mathematician, the correspondence defined in Theorem 5-5.1 is much more satisfying than the vague directions laid down in Section 1-2. Never-

168

ELEMESTARY

NUMBER THEORY

[CHAP.

5

theless, he would admit, perhaps reluctantly, that the discussion in Section 1-2 proves just as effectively that the set F is denumerable. The proof of Theorem 5-5.1 is based on a generalization of the fundamental theorem of arithmetic.

THEOREM 5-5.2. The positive rational numbers r can be expressed iil the form r

=

p11pi2. . . p i ~ ,

where pl, p2, . . . , p, are distinct primes and xl, xs, . . . , xg are integers. Moreover, this representation is unique, except for the order of the factors and the occurrence of primes with exponent zero. This theorem is an almost immediate consequence of Theorem 5-3.3, and the fact that every positive rational number r has a unique representation a/b in "lowest terms," that is, with a and b natural numbers which are relatively prime. We leave to the reader the chore of supplying a detailed proof. Theorem 5-5.1 can now be easily proved by reinterpreting Theorem 5-3.3 and 5-5.2. For this purpose, let p l , p2, p3, p4, . . . denote the sequence of al1 primes in increasing order. Thus, pl = 2, p2 = 3, p3 = 5, p4 = 7, . . . . Then by Theorem 5-3.3, each natural number a can be written

where now el, e2, . . . , e, are nonnegative integers, and g is some sufficiently large number. The number of factors in the expression is not uniquely determined because we can always multiply by primes to the zero power. Thus, 10 = 2 l . 3O. 5 l . 7 O . l l O 13O. . However, the number a determines, and is determined by, the sequence of exponents el, e2, . . . , e,. By adjoining an infinite number of zeros, we do achieve complete uniqueness. I n other words, there is a one-to-one correspondence between the natural numbers and the infinite sequence of nonnegative integers

which are zero from some point on (that is, for sufficientlylarge g, = 0, = O, . . .). The uniqueness statement in the fundamental theorem of arithmetic tells us that the correspondence

a is one-to-one.

=

py1pi2.. . pg"

(el, e2,

. . . , e,, O, 0, . . .)

5-51

169

THE FUNDAMENTAL THEOREM OF ARITHMETIC

In exactly the same way, there exists, by Theorem 5-5.2, a one-to-one correspondence between the set F of al1 positive rational numbers and the set of al1 sequences

of integers with the property that x , + ~ = O, xg+2 = 0, point on. The correspondence is

. . . from some

We now have two sets of infinite sequences: the set J of al1

-

where the ei are nonnegative integers which are zero from some point on, and the set K of al1 (xl, x2, . . . , x,, . . .), where the xi are integers which are zero from some point on. The one-to-one correspondence e e given by (5-4) clearly determines a one-to-one correspondence between J and K : (el, ez, . . . , e,,

--

. . .)

-

(él, e2, . . . , e,,

-

. . .).

If al1 of these one-to-one correspondences are combined, we obtain pt1p3. . . pzg

. . . , e,, O, . . .) p ; ~ ; ~. .. pgg, (el, e2,

-

(e1, e2, . . . , e,, O,

. . .)

which is the correspondence described in Theorem 5-5.1. A Diophantine problem. I t is well known that there are right triangles whose sides have integral length. The best known example is the 3, 4, 5 right triangle with bases of length 3 and 4, and hypotenuse of length 5. Somewhat less well known is the right triangle with sides of length 5, 12, and 13. Since the length c of the hypotenuse of a right triangle is related to the lengths a and b of the sides by the Pythagorean formula

the problem of finding al1 right triangles with sides of integral length is equivalent to finding al1 natural numbers a, b, and c which satisfy (5-5). An equation such as (5-5) involving powers of unknown quantities with integral coefficients is called a Diophantine equation (after the ancient b = 2, a2 Greek mathematician Diophantus). For example, a 5b2 = 1, a2 ab b2 = 5c2, and a 4 b4 = c2 are al1 Diophantine equations. The problem of finding al1 integral solutions of a Diophantine equation, or a system of Diophantine equations, is called a Diophantine problem.

+ +

+

+

170

ELEMENTARY NUMBER THEORY

[CHAP.

5

Using the fundamental theorem of arithmetic, it is possible to obtain the complete solution of (5-5). First note that if r, s, and t are natural numbers, with r > S, and if we let then

Therefore, (5-6) gives a large family of solutions of (5-5). We will show that every solution of (5-5) with a, b, and c natural numbers is of the form (5-6) (or a similar form with a and b interchanged) for suitable natural numbers r, s, and t. The proof is based on the following useful consequence of the fundwental theorem of arithmetic. THEOREM 5-5.3. Suppose that a and b are natural numbers which are relatively prime, and ab = cn for some natural number c. Then a = al, b = bl, where a l and bl are natural numbers. Proof. Let a =

p p . . . pp,

b =

q{l

.

qhf h

where pl, . . . , p, are distinct primes, q l , . . . , qh are distinct primes, and the exponents el, . . . , e, and f 1, . . . , fh are al1 positive. Then the pi must be different from al1 qj, since otherwise a and b would have a common prime factor, contrary to the assumption that they are relatively prime. Let

where rl, . . . , rk are distinct primes and ml, . . . ,mk are positive exponents. Then the condition ab = cn can be written

By Theorem 5-3.3, it follows that the primes rl, . . . rh must be pl, . . . , p,, ql, . . . , qh in some order, and that el, . . . , e,, f l , . . . , fh are the corresponding exponents nml, . . . , nmk. Thus, each ei and f j is divisible by n, that is, el/n, . . . , e,/n, f l/n, . . . , fh/n are al1 natural numbers. Let

.: Then a = ay, b = b We now return to the problem of finding al1 natural iiumber solutions of (5-5). Suppose that a, b, and c are natural numbers which satisfy (5-5).

5-51

THE FUNDAMENTAL

171

THEOREM OF ARITHMETIC

Let t be the greatest common divisor of a, b, and c. Then a/t, b/t, and c/t are natural numbers with no prime factor in common which satisfy

+

We will show that a/t, b/t, and c/t have the form r2 - s2, 2rs, and r2 s2, respectively, or else 2rs, r2 - s2, and r2 s2, respectively. Let x = a/t, y = b/t, and x = c/t. Then

+

where no prime divides any two of these natural numbers, that is, each pair of the numbers x, y, x are relatively prime. For example, if plx and plx, then p divides x2 - x2 = y2. Thus, by (5-3.2)) ply. But this is a contradiction, since x, y, and x have no prime factor in common. Since x and y are relatively prime, they cannot both be even. Suppose they are both odd. Then we could write x = 1 2m, y = 1 2n, with m and n nonnegative integers. Consequently

+

+

and z2 = x2

+ y2 = 2 + 4[m(m + 1) + n(n + l)].

This implies that z is even, say x = 21. Then x2

=

412, so that

This is clearly impossible. Therefore, one of x or y is even, while the other is odd. Suppose that x is odd and y is even. Then x is odd, so that x - x x) are integers. Moreand x x are even. That is, $(z - x) and $(z over, they are relatively prime, since if a prime p divides +(x - z) and +(x x), then p divides +(x x) +(x - x) = x and *(x x) +(x - x) = x. But this is impossible, since x and x are relatively prime. BY (5-7) ,

+

+

+

+ +

+

+

where *y is a natural number, since y is even. By Theorem 5-5.3, *(x x) and *(z - x) are squares, that is, there exist natural numbers r and sbuch that $(z - Z) = s2. +(z x) = r2,

+ Consequently, z = r2 + s2, x

=

r2 - s2, and

5-51

THE FUNDAMENTAL

173

THEOREM OF ARITHMETIC

(5-5.5). If a, b, and c are natural numbers which have no common prime factor and satisfy a2 b2 = c2, then (a) c is odd; (b) either a is even and b is odd, or vice versa; (c) if a is even,

+

where r and

S

are relatively prime natural numbers and r

> s.

+

Now suppose that the equation x4 y4 = z2 can be satisfied by some natural numbers. Then the set of al1 natural numbers z for which there exist natural numbers x and y, such that x4 y4 = z2, is not empty. Consequently, by the well-ordering principle, this set contains a smallest number c. Let a and b be corresponding natural numbers such that a4 b4 = c2. We will obtain a contradiction by showing that there is a natural number t smaller than 'c such that t2 = x4 y4 for some natural numbers x and IJ. This will show that our original assumption that a solution exists is false. If a and b had a common prime factor p, then p41c2. Thus, by the fundamental theorem of arithmetic, p2/c, and therefore (a/p)4 ( b / ~= )~ ( ~ 1 ~ Since ~ ) ~clp2 . < c, this contradicts the assumption that c is the smallest of the natural numbers z for which z2 = x4 y* has a solution. Consequently, a and b are relatively prime. This implies that a2, b2, and c have no common prime factor, so that (5-5.5) applies to the equation (a2)2 (b2)2= c2. We obtain that either a2 or b2 is even, and assuming that a2 is even, we have

+

+

+

+

+

+

where r and S are relatively prime natural numbers and r > s. Since r and S are relatively prime, it follows that S, b, and r in the equation s2 b2 = r 2 have no prime factor in common. Thus, by (5-5.5a), applied to the equation s2 b2 = r2, r is odd. However, a2 is even, so that a is even. Thus, 4 divides a2 = 2rs, and consequently 2/73. Since r is odd, S must be even, and we have

+

+

Since (r, S) = 1, it follows that r and s/2 are relatively prime. Consequently, by Theorem 5-5.3, the equation (a/2)2 = r (s/2) implies that r and s/2 are squares:

174

ELEMEKTARY NUMBER THEORY

Now apply (5-5.5) to the equation s2 we can write s

=

2vw,

b = u2

-

[CHAP.

+ b2 = r2 again.

w2,

r = v2

5

Since s is even,

+ w2,

where u and w are relatively prime natural numbers. Hence,

By Theorem 5-5.3, it follows that u = x2,

W

=

y2

for some natural numbers x and y. Combining these equalities with the w2, we obtain equations r = t2 and r = v2

+

+

Moreover, t 5 t2 = r $ r2 < r2 s2 = C. Thus, we have arrived at the promised contradiction, and proved the f ollowing result. THEOREM 5-5.6. There are no natural numbers a, b, and c which satisfy a4 b4 = c2. In particular, the equation x4 y4 = z4 has no solution in natural numbers.

+

+

The reader should reexamine the proof of this theorem, noting the following aspects of it. (1) The main step of the proof is to show that the existence of one triple = z: leads to another (xl, y,, zl) of natural numbers satisfying xf = zz with zz < zl. Repeating the triple (x2, y2, z2) satisfying x i argument would lead to a sequence of triples (x,, y,, z,), n = 1, 2, 3, . . . , with x$ y$ = Z: and zl > 22 > z3 > . . . . This sequence of inequalities is impossible by the well-ordering principle, and therefore proves that the existence of the original triple (xl, yl, zl) is impossible. (Actually, it was convenient for our argument to use the well-ordering principle at the beginning of the proof.) This technique of proof is common in number theory. It is called the "method of infinite descent. " The reader may recall that this method was used to establish the Euclidean algorithm in Section 5-2. (2) The main step of the proof is carried out by two applications of (5-5.5) and two applications of Theorem 5-5.3. Remembering this observation and the general method of proof, the reader should be able to reconstruct the argument without the help of the book. (3) The method of proof which we used would not suffice to show directly that the equation x4 2/4 = z4 has no solutions in N. The generalization

+

+

+

+

5- 61

175

CONGRUENCES

+

to x4 y4 = z2 is essential to the success of our proof. This is another instance of the situation discussed in Section 2-4, where induction fails in the proof of a certain theorem, but is successful in proving a stronger result. In the case of Theorem 5-5.6, induction occurs as an application of the well-ordering principle. (4) I t is an immediate consequence of Theorem 5-5.6 that no equation of the form X41 + y4m = x2n has a solution x = a, y = b, z = c, with a E N, b E N, c E N. Indeed, if such a solution exists, then a" bm, cn is a solution of x4 y4 = z2. I n particular, if 4 divides n, then the Fermat equation xn y" = zn has no solution in N.

+

+

1. Using the Godel numbering of the English language which was defined in this section, find the Godel numbers (in factored form) of the following expressions. (a) ALGEBRA (b) U.S.A. (c) DON'T GIVE U P THE SHIP! 2. Give the proof of Theorem 5-5.2. 3. Let a and b be any natural numbers. Show that integers r and s exist such that rs = (a, b), (alr, b/s) = 1. 4. Let a be a natural number. Let s2 be the largest square dividing a. Show that if d2 is a square dividing a, then dls. 5. Suppose that (a, b) = 1, (c, d) = 1, and ab = cd. Show that integers r, S, t, and u exist, each pair of which are relatively prime, such that a

=

rs,

b

=

tu,

rt,

c =

6. Show that if p is a prime, and if 1 2 i . coefficient (I)

d

< p,

=

su.

then p divides the binomial

7. Show that every solution in natural numbers of the Diophantine equation

a2

+ 2b2 = c2

is given by

a

=

3t(r2 - 2s2)t,

[or a = Zrst, b numbers.

=

+(r2 - 2s2)t,c

b =

=

(r2

Zrst,

c =

(r2

+ 2s2)t

+ 2s2)t],where r,

S,

and t are natural

5-6 Congruences. Many interesting problems and numerous theoretical questions in number theory are concerned with properties of the remainder obtained by dividing an integer by a fixed natural number m. For example, if the first of July falls on Sunday, then what will be the day of the week on

176

ELEMEKTARY PYUMBER THEORY

[CHAP.

5

which the first of September falls? Since July and August each have 31 days, the answer is that the first of September falls r days after Sunday, where r is the remainder obtained on dividing 31 31 by 7, namely, r = 6, and the day is Saturday . Another example is the following problem : a certain chemical reaction requires 100 hours; if it is desirable to complete the reaction at 8:00 A.M.,at what time of day should it be started? The answer is r hours before 8:00 A.M.,where r is the remainder obtained on dividing 100 by 24, that is, 4:00 A.M. A property of remainders which was needed for the solution of Problem 9, Section 5-4, is the fact that if the natural number a leaves the remainder 1 on division by 3, then the same is true for every power of a. The study of many such problems involving remainders is simplified by the systematic use of a concept which was introduced by the great German mathematician Carl Friedrich Gauss (1777-1855).

+

DEFINITION 5-6.1. Let m be a natural number. An integer a is congruent modulo m to an integer b if a - b is divisible by m in the ring of integers. I t is customary to write a

-

b (mod m)

to indicate that a is congruent to b modulo m. The relation a = b (mod m) is called a congruence, and m is called the modulus of the congruence. By the definition of congruence, every pair a, b of integers are congruent modulo 1. Thus, congruence with the modulus 1 is not very interesting. congruence modulo 2 has a familiar meaning: a = b (mod 2) if and only if a and b have the same parity; that is, either a and b are both even, or they are both odd. The connection between the remainders on division by m and congruence with the modulus m is seen from the following fact. THEOREM 5-6.2. Let m be a natural number. Then each integer is congruent modulo m to one and only one of the numbers O, 1, 2, . . . , m - l. This theorem is an immediate consequence of the division algorithm. If a is any integer and m is a natural number, then there are unique integers q and r, with O 5 r < m, such that a = qm r. Thus, there is a unique number r among the numbers O, 1, 2, . . . , m - 1 such that a - r is divisible by m. By Definition 5-6.1, this means that a is congruent modulo m to one and only one of the numbers O, 1, 2, . . . , m - 1. I t is clear that an integer a is divisible by a natural number m if and only if a = O (mod m). Moreover, a b (mod m) is equivalent to the

+

-

-

5-61

177

CONGRUENCES

statement that a - b O (mod m). Thus, the notion of congruence is apparently only a variation of the concept of divisibility. It is therefore surprising that this notion is so useful. The usefulness is partly explained by the fact that congruence has many of the familiar properties of ordinary equality, so that manipulations with congruences are similar to the computations of elementary algebra. THEOREM 5-6.3. Let m be a natural number and let a, b, c, and d be integers. Then (a) a a (modm); (b) if a b (mod m), then b = a (mod m); b (mod m) and b = c (mod m), then a c (mod m) ; (c) if a (d) if a = b (mod m) and c = d (mod m), then a + c=b d (modm) a n d a - c b - d (modm); (e) if a = b (mod m) and c d (mod m), then ac bd (mod m); b (mod m), then ca cb (mod m); (f) if a (g) if a r b (mod m), then a" = bn (mod m) for any natural number n.'

--

-

-- - -

+

The properties (a), (b), and (c) follow easily from Definition 5-6.1. To prove (d), suppose that a = b (mod m) and c = d (mod m). Then by Definition 5-6.1, a - b = km and c - d = lm for some integers k and l. Thus,

and

+

+

-+

c) - (b d) and (a - c) - (b - d) are Therefore, the differences (a both divisible by m. By Definition 5-6.1, a c b d (mod m) and a - c b - d (mod m). The statement (e) is proved similarly. Using the same notation as in the proof of (d), we have

-

-

+

+ + + +

ac - bd = (a - b)(c - d) ad bc - 2bd = (a - b)(c - d) d(a - b) b(c - d) = (km)(lm) d(km) b(1m) = (klm dk b1)m.

+ + +

+

Property (f) is an immediate consequence of (e) and the fact that c c (mod m) by (a). Property (g) is obtained by successively applying (e) to the congruence a = b (mod m). Using the given congruence twice, (e) implies a2 b2 (mod m). Using a = b (mod m) and a2 = b2 (mod m),

-

178

-

ELEMEXTARP XUMBER THEORY

[CHAP.

5

(e) gives a3 b3 (mod m), and so forth. Of course, this argument can be formalized by induction. The "transitive law," Theorem 5-6.3(c), and the "reflexive law," Thcorem 5-6.3(a), justify the use of sequences of equalities and congruentes. For example,

is a convenient abbreviat,ion for a = b (mod m), b = c, c d (mod m), and d = e. By (a) and (c), the congruenccs obtained by omitting one or more quantities from this sequencc are valid: a c (mod m), a d (mod m), a = e (modm), b = d (modm), b e (modm), and c e (modm). I t is a consequence of Theorem 5-6.3 that in a congruence with modulus m which involves sums and differences of products, any integer in the congruence can be replaced by any other integer to which it is congruent modulo m. For example, if ab3 - 2abc 5d2 (mod m), and if b = e (mod m), then ae3 - 2aec 5d2 (mod m). I n fact by (g), b3 = e3 (mod m). Using (f), we obtain ab3 = ae3 (mod m). Simjlarly, 2abc 2aec (mod m). ae3 - 2aec (mod m). Finally, employing (e), \\re By (d), ab3 - 2abc find ae" 2aec 5d2 (mod m). Even the simple properties of congruence given in Theorem 5-6.3 have useful applications.

- - -

-

--

-

-

-

EXAMPLE 1. L c us ~ find the remainder obtained on dividing the sum

by 7. By Thcorem 5-6.3,

s..

110+ 210 +

. . . + 610 + 010 + 991° + 1001° (mod 7))

mhere this sum contains 14 occurrences of the blocks 11° 01° (since 14 7 = 98). Thus,

+ 21° + + 61° +

Consequently, the remainder obtained on dividing the sum 1l o 1001° by 7 is 3.

+

+ 21° + 31° +

5- 61

CONGRUENCES

179

EXAMPLE 2. A well-known property of natural numbers written in decimal notation is that such a number is divisible by 9,if and only if the sum of its digits is divisible by 9. The basis for this useful fact is the observation that if

where O

5

ri


- 1,

Then s j = S (mod m/(a; m)), so that s j is a solution of (5-8)) and therefore of ax = b (mod m). Moreover, since

i t follows that if O 5 i < j 5 (a, m) modulo m. We will show that

-

1, then si is not congruent to

sj

is a representative set of solutions of the congruence ax = b (mod m). That is, every integer t satisfying at = b (mod m) is congruent modulo m to S, for some r. By Theorem 5-6.4(c), at = b (mod m) implies that t is a solution of (5-8). Therefore, t S (mod m/(a, m)) by Theorem 5-7.1. That is, t =S l[m/(a, m11

-

+

for some integer l. By the division algorithm, 1 = q(a, m) O 5 r 5 (a,m) - l . Thus, t=s+-

rm (a, m>

+ qm = + qm = S,

S,

(mod m).

+ r, where

5-71

LINEAR CONGRUENCES

185

EXAMPLE 2. Solve the congruence 15x = 20 (mod 35). Since (15, 35) = 5, and 5120, the congruence has 5 solutions which are incongruent modulo 35. These are obtained by first solving 32 = 4 (mod 7). We find the solution x = 6. Then a representative set of solutions of 152 = 20 (mod 35) is obtained from (5-9) and (5-10). These are

For (a, m) = 1, the congruence ax = b (mod m) can be solved as in Theorem 5-7.1 using the Euclidean algorithm. This is probably the best method if the numbers a and b are large. If these numbers are small, the congruence can often be solved more easily by trial, or by using the properties of congruences given in Theorem 5-6.3. EXAMPLE 3. Solve 3x = 4 (mod 7). If x is a solution, then 6x = 8 (mod 7), so that -x = 1 (mod 7), and x E -1 = 6 (mod 7). Suppose that we wish to solve 5x = 9 (mod 13). If x is a solution, then 18x = 9 (mod 13), and therefore 1 (mod 13); consequently, 142 = 7 (mod 13), and x = 7 (mod 13). As a 22 final example, if x is a solution of 5x = 11 (mod 17), then 52 45 (mod 17); hence x = 9 (mod 17).

There is an important application of Theorem 5-7.1 to the construction of sets of orthogonal Latin squares. A Latin square of side m is an arrangement of m distinct symbols in m2 subsquares of a square, in such a way that every row and every column contains each symbol exactly once. I t is immaterial what symbols are used, but it is convenient to let them be the number symbols O, 1, 2, . . . , m - 1. As an example,

is a Latin square of side 3. Two Latin squares of the same size are called orthogonal if, when one is superposed on the other, every ordered pair of symbols occurs exactly once in the resulting square. For instance

186

ELEMENTARY NUMBER THEORY

[CHAP.

5

are orthogonal Latin squares, since when one is superposed on the other we have

For centuries, amateur and professional mathematicians have found Latin squares interesting. In recent years the study of pairs of orthogonal Latin squares has taken a serious turn, because of the discovery that such pairs have important applications in algebra, geometry, and applied statistics. Let p be a prime. For any integer a, let r(a) be the remainder on dividing a by p. That is, O 5 r(a) < p, and a = r(a) (mod p). For O < lc < p, define a Latin square (which we designate by Lk) as in Table 5-1. In other words, the number in the ith row and jth column of Lk is

To show that Lkis a Latin square, it is necessary to prove that if O 5 b < p, then b occurs in every row of Lk and in every column of Lk. Consider the ith row. Then b - (i - 1)k = c (mod p) for some c satisfying O c 5 p - 1. Let j = c 1. Then

+

(j

-

1)

+ (i

Thus, r((j

-

1)

-

1)k = b (modp).

+ (i - 1)k)

=

b.

Therefore, b occurs as the jth entry of the ith row. Now examine the jth column. Since O < k < p and p is a prime, it follows that (k, p) = 1.

5-71

LINEAR CONGRUENCES

Hence by Theorem 5-7.1, there is an integer d such that kd = b - ( j

-

1) (modp).

5d5p

-

1. Define i = d

We-can select d so that O

+ l.

Then

+

Consequently, r (( j - 1) (i - 1)k) = b, so that b is the it,h ent,ry of t,he ,jth column in Lk. Thus, we have shown that each row and column contains each of the numbers O, 1, . . . , p - 1 at least once. Since there are only p entries in each row and column, it follows that the rows and columns cannot contain these symbols more than once. Therefore, Lk is a Latin square. We wish to show now that if O < k < 7' < p, then the squares Lk and Lkl are orthogonal. For this, we have to prove that if O 5 a 5 p - 1 and O 5 b 5 p - 1, there are natural numbers i and j such that 1 5 i 5 p, 1 5 j 5 p, and r ( ( j - 1) (i - 1)k) = a, r ( ( j - 1) f (i - 1 ) = b. This is elearly equivalent to the problem of solving the congruenees (i - 1)k = a(modp), ( j - 1) ( j - 1) (i - 1)k' 5 b (modp)

+

+ +

for i and j. Subtracting these congruences, \ve obtain the condition (i

-

1)(k'

-

lc)

=b

-

a (mod p),

which can be written in the form (k' - k)i = (b

-

a)

+ (k' - k) (modp).

Since O < Ic' - 7 < p and p is a prime, it follows from Theorem 5-7.1 that this congruence has a solution i such that 1 5 i 5 p. Choose j so that 1 5 j 5 p and j - 1=a

-

(i

-

I)lc (modp).

+

Then by construction, j - 1 and i - 1 satisfy the congruence ( j - 1) (i - 1)lc = a (mod p). However, these values of j - 1 and i - 1 also satisfy the congruence ( j - 1) (i - l)kf b (mod p). In fact,

+

j -1

+ (i

-

-

+

l)kf = a - (i - 1)lc (i - l)kf = a (i - l)(kf - k) = b (modp).

+

This proves that Lk and Lkl are orthogonal. Note that we have constructed a set of p - 1 Latin squares, each pair of which is orthogonal.

188

ELEMENTARY NUMBER THEORY

[CHAP.

5

Many problems in number theory require the simultaneous solution of systems of congruences. We will prove a famous and important theorem about such congruences. This result was known to Chinese mathematicians as early as 250 A.D., and for this reason i t is usually called the Chinese remainder theorem. THEOREM5-7.3. Let ml, m2, . . . , mk be natural numbers such that (mi, mj) = 1 if i # j. Then if bl, b2, . . . , bk are any integers, there exists an integer x such that

Moreover, x is unique modulo mlm2

. . . mk.

Proof. Let ni = mlm2 . . . mi-lmi+l . . . mk. Then (ni, mi) = 1 since (mi, mj) = 1if i # j. Consequently, by Theorem 5-7.1, there is a n integer ti S U C ~that niti bi (mod mi). Let

bi (mod mi), since if j # i, then milnj, and conseThen z = niti quently njtj = O (mod mi). Thus, x is a simultaneous solution of the given system of congruences. If y also satisfies y = bl (mod ml), y b2 (mod m2), . . . , y = bk (mod mk), then x = y (mod ml), x = y (mod m2), . . . , x = y (mod mk). Therefore by Theorem 5-6.4(f), x y (mod m), where m is the least common multiple of (ml, m2, . . . ,mk) . But since these integers have no common prime factors, their least common multiple is mlm2 . . . mk.

l. Give the representative set of solutions for each of the following linear congruences. (a) 3622 236 (mod 24) (b) 552 = 5 (mod 31) (c) 84x = 96 (mod 7) (d) 36x: = 6 (mod 21) (e) 2702 = 30 (mod 150) 2. Let p be a prime. Show that if p i a, then the congruence ax = b (mod p) has a unique solution modulo p. 3. Find the solutions of the following systems of congruences. (a) x r 5 (mod 6)) x = 7 (mod 11) (b) x = 1 (mod 2)) x = O (mod 3)) x = 2 (mod 5) (c) x 21 (mod 29)) x = 5 (mod 30), x = 24 (mod 31)

5-81

THE THEOREMS OF FERMAT AKD EULER

189

4. Let a, b, and c be integers and let m be a natural number. Suppose that (c, m) = l. (a) Prove that the congruence ax = b (mod m) is equivalent to the congruence caz = cb (mod m), that is, every solution of ax b (mod m) is a solution of caz cb (mod m), and conversely. (b) Suppose, in addition, that (a, m) = 1. Prove that the congruence ax b (mod m) is equivalent to the congruence x b' (mod m) for some integer b'.

-

-

-

5. Let mi, m2, . . . , mk be natural numbers such that (mi, mi) = 1 if i # j. Let a l , a2, . . . , ak and bi, b2, . . . , bk be integers. Prove that the system of congruences

has a solution if and only if 1 ,1

,

(a2, ma)lbz,

..

(ak, mk) 1 b k .

[Hint: Reduce the system of congruences to the form treated in Theorem 5-7.3 by using Problem 4(b), together with an argument similar to that given in the proof of Theorem 5-7.2.1 6. Determine which of the following systems of congruences have a solution, and mhen solutions exist, find a t least one. (a) 5x = 1 (mod 7), 22s 2 (mod 6) 1 (mod 125) (b) 8x = 14 (mod 24), 4x 1000 (mod 91) (c) 3 8 r ~ 3 (mod 12), 50x 75 (mod 125), x (d) 233x 10 (mod 12), 73x 1 (mod 219), 12x 4 (mod 8)

-

--

-

--

7. A band of 17 thieves stole a large sack of dollar bills. They tried to divide the bills evenly, but had three bills left over. Two of the thieves began to argue about the extra money, so one of them shot the other. The money was redistributed, but this time there were ten bills remaining. Again argument developed, and one more thief was shot. When the money was redistributed, there waqnone left over. What was the least possible amount of money which could hstve been stolen originally?

8. Construct a set of 4 Latin squares with 5 rows and 5 columns, such that each pair of the set is orthogonal. "5-8 The theorems of Fermat and Euler. One of the oldest aiid most famous theorems in number theory was discovered by Fermat and communicated to a friend in 1640. The first published proof of Fermat's theorem, due to the Swiss mathematician Leonhard Euler (1707-1783), appeared almost a century later. Subsequently, a more general theorem mTasfound by Euler. In this section we will discuss these classical results and some of their applicatioiis.

190

ELEMENTSRY KUMBER THEORY

[CHAP.

5

Fermat7s theorem concerns congruences with prime moduli. These are important because many problems concerning congruences with composite modulus can be reduced to questions about congruences with prime modulus. We begin by noting a simple property of the binomial coefficients. (5-8.1). If p is a prime and if i is an integer such that O

(r)

=

< i < p, then

P! -O(rnodp). i!(p - i)!

We leave the proof of this fact as an exercise for the reader (see Problem 6, Section 5-5). If p is a prime, and if a and b are any integers, tlien by the binomial theorem

1) abp-'

+ (p

+ bP

-

aP

+ bp (mod p),

= O (mod p) if 1 2 i 2 p - 1. Using mathesince by (5-8.1), matical induction, this observation can be generalized as follows. (5-8.2). If p is a prime, and if al, a2, . . . , a, are any integers, then (al

+ a2 + + anlp

5

al

+ a; +

.

+ a:

-

(modp).

Proof. If n = 1, then the assertion is that al; ay (mod p), which is clearly valid. Assuming that the result holds for n, it follows from the remarks above that [(al

+ a2 + +

a,)

-

4- an+llP= (al ay

+ a2 + . + a d p + a:+l

+ a; +

This proves the induction step.

+a:

+ a:+l

-

(modp).

If welet a l = a2 = . . . = a, = 1 in (5-8.2), weobtainnp n (modp). Also, if p is odd, and a l = a2 . . . = a, = -1, then (5-8.2) specializes to (-n)p r -n (mod p). This is also true if p = 2, since -n n (mod 2). Obviously, Op O (mod p). Therefore, we have proved the following theorem.

-

-

THEOREM 5-8.3. If p is a prime, and if a is any integer, then ap

a (mod p) .

5-81

191

THE THEOREMS OF FERMAT AND EULER

Alt,hough this theorem is obtained as a special case of (5-8.2)) it is evident that (5-8.2) can be deduced easily from the theorem. The "little theorem of Fermat" is a slight variation of Theorem 5-8.3. THEOREM 5-8.4. If p is a prime, and if a is any integer which is not divisible by p, then a ~ - l= - 1 (mod p).

-

Proof. By Theorem 5-8.3, p divides a(ap-' - 1). Since p does not 1 (mod p). divide a, it must divide ap-' - 1, by (5-3.2). Hence, ap-' The method by which we have proved Theorem 5-8.4 is similar to Euler's first proof of this theorem. Some years later, Euler found a different way to prove Fermat's theorem. Using the ideas of this second proof, he was able to establish the more general result known as Euler's theorem. We will prove Euler's theorem by a method which was discovered about 50 years later. This proof is important because it introduces a technique which has many applications in number theory. The following definition is needed. DEFINITION5-8.5. Let m be a natural number. The totient of m is the number of nonnegative integers less than m which are relatively prime to m. The totient of m is usually denoted by p(m). In other words, cp(m)is the number of integers k such that O _< k < m and (k, m) = 1. For example, p(1) = 1, p(2) = 1, p(3) = 2, p(4) = 2, p(5) = 4, and p(6) = 2. If p is a prime, then the numbers 1,2, . . . , p - 1 are al1 prime to p, so that p(p) = p - 1. THEOREM 5-8.6. Euler7stheorem. If m is a natural number and a is an integer which is relatively prime to m, then a'"(") =

1 (mod m).

Proof. To simplify notation, let t denote p(m). According to the definition of p(m), there are exactly t different natural numbers in the set (0, 1, 2, . . . , m - 1) which are relatively prime to m. Let these be designated as Ic', k2) . . . , h. Consider the set of integers

By the division algorithm, we have for i = 1, 2,

. . .,t

192

ELEMENTARY NUMBER THEORY

[CHAP.

5

where qi is an integer and O 5 ri < m. Thus, ski r ri (mod m). The main step of the proof consists of showing that the list of numbers rl, r2, . . . , rt is just a rearrangement of the sequence kl, k2, . . . , let. We do this indirectly. First note that each ri is relatively prime to m. In fact, if a ri = aki. T ~ u s , prime p divides both m and Ti, then p also divides qim either p[aor pllci. However, since plm and both a and l& are relatively prime to m, p cannot divide either a or ki. Therefore, (ri, m) = 1. Since lcl, k2, . . . , lct is the list of all integers k such that O 5 le < m and (lc, m) = 1, and since each ri satisfies these conditions, it follows that each ri must be equal to some lc,. If we can show that the numbers rl, r2, . . . , rt are al1 different, then our proof that r l , r2, . . . , r t is a rearrangement of kl, k2, . . . , kt will be complete. Suppose that ri = r j for some i # j. Then subri and akj = qjm r j gives tracting the equations ski = qim

+

+

+

Therefore, mla(lci - kj). Since a is prime to m, it follows from Theorem 5-2.6 that ml(ki - kj). However, i # j implies ki # kj, and O 2 lei, kj < myields -m < lei - lej < m. Hence, O < Iki - kjl < m. Therefore, m cannot divide ki - kj. This contradiction proves that the numbers rl, r2, . . . , rt are al1 different, and that the list r l , r2, . . . , rt is the same (in possibly different order) as kl, le2, . . . , kt. In particular, by the commutative law of multiplication,

Consequently, since ski = ri (mod m),

It only remains to observe that the product lcl lc2 k t can be cancelled from each side of this congruence. In fact, no prime factor of m divides any of the integers lel, lc2, . . . , kt since these numbers are relatively prime to m. Thus, m has no prime factor in common with the product kl k2 . lct. That is, (lcl k2 . lct, m) = 1, and the cancellation is permissible by (5-6.4d). Thus, 1 at = aq'm' (mod m).

-

This proof can be illustrated by carrying it out in a particular numerical case. Let m = 14. Then the integers in the range from O to 13 which are relatively prime to 14 are 1, 3, 5, 9, 11, and 13. These can be taken as the numbers kl, le2, . . . , let in the proof of Theorem 5-8.6. In this example,

5-81

t

=

193

THE THEOREMS OF FERMAT AND EULER

(s(14) = 6. Let a = -5.

Then the numbers alci are

The division algorithm gives

Therefore in our special case, the numbers rl, r2, . . . , rt occurring in the proof of Theorem 5-8.6 are 9, 13, 3, 11, 1, and 5. This agrees with the general result that r l , r2, . . . , r t is a rearrangement of kl, k2, . . . , Ict. To conclude the illustration, note that 1.3.5.9.11-13 = 9.13.3.11.1*5 = [(-5) 1][(-5) 3][(-5) 5][(-5) 9][(-5) = (-5)6(i - 3 . 5 . 9 . 1 1 13) (mod 14).

111[(-5)

131

Since 1 3 5 9 11 13 is relatively prime to 14, it follows that

If the natural number m in Euler's theorem is a prime p, then (s(m) = p(p) = p - 1, and the theorem asserts that if (a, p) = 1, then ap-' 1 (mod p). This is exactly the statement of Fermat7stheorem. In order to use Euler's theorem, it is necessary to know the value of the totient (s(m). For small values of m, (s(m)can be obtained by counting the numbers from O to m - 1 which are relatively prime to m. However, if m is large, this procedure is impractical. Fortunately there is a convenient formula for q(m). TKEOREM 5-8.7. If m is a natural number different from 1, and if m = p;'pi2. . . py, where pi, p2, . . . , p, are distinct primes, and the exponents el, e2, . . . , e, are positive, then

We will not give a proof of this theorem (however, see Problems 14, 15, and 16 below) . Euler's theorem has numerous applications. For example, it provides another method of solving linear congruences of the type discussed in

194

ELEMENTARY NUMBER THEORY

Theorem 5-7.1 : ax

-

b (mod m),

Indeed, if we let x = av'"'-' ax = a .

where

(a, m) = 1.

b, then

.b

=

aq(m'

-

.b -

1 . b = b(m0dm).

EXAMPLE1. Consider the congruence 152

6 (mod 22).

-

We have ~ ( 2 2 )= p(2 11) = 1 10 = 10. Then 6 159 is a solution of the ~ congruence. Since 152 = 225 r 5 (mod 22), 1 5 ~ 52 = 3 (mod 22), 1 5 = 32 = 9 (mod 22), 6 159 r 6 15 9 = 90 9 = 2 9 = 18 (mod 22). Therefore, x = 18 is the smallest nonnegative solution of the congruence. This method of solving linear congruences is very often not the easiest. If 15x 6 (mod 22), then 52 = 2 = 90 (mod 22), and x = 18 (mod 22).

Another application of Euler's theorem is the reduction of large powers of a number modulo m.

-

EXAMPLE 2. Suppose that we wish to find the least nonnegative integer to which 5221is congruent modulo 18. Since ~ ( 1 8 )= 6 and (5, 18) = 1, Euler's theorem yields 56 1 (mod 18). Since 221 = 36 6 5, we obtain

+

-

13 (mod 18), and 55 5 13 = 65 = Finally, 52 7 (mod 18), 54 = 49 11 (mod 18). Thus, 11is the least nonnegative integer to which 5221is congruent modulo 18. EXAMPLE3. What are the last two decimals of the number 3119? This is equivalent to the problem of finding the least nonnegative integer to which 3119 2 = ~ 40, is congruent modulo 100. Since (3, 100) = 1 and ~ ( 1 0 0 )= ~ ( 52) we have 340 r 1 (mod 100). Thus, (340)3 = 3 3119 1 (mod 100). Consequently, by Theorem 5-7.1, 3119 r (mod 100), where r is any solution of 3 67 3x 1 (mod 100). Since 100 = 33 3 1, we obtain 1 = 3 (-33) (mod 100). Hence, 3119 67 (mod 100), SO that the last two decimal digits of 3119 are 6'7.

-

-

+

DEFINITION 5-8.8. Let m be a natural number and let a be an integer such that (a, m) = 1. The order of a modulo m (or the exponent to which

5-81

THE THEOREMS OF FERMAT AND EULER

195

a belongs modulo m) is the smallest natural number d such that ad = 1 (mod m). By Theorem 5-8.6, the set of al1 natural numbers TL such that a" = 1 (mod m) is nonempty, since in fact cp(m) belongs to this set. Therefore, d is well defined and d 2 cp(m). It is clear from Definition 5-8.8 and Theorem 5-6.3 that if a = b (mod m), then a and b have the same order modulo m. THEOREM 5-8.9. Let d be the order of the integer a modulo m. If a" = 1 (mod m), then d[n. In particular, d[cp(m). Proof. By the division algorithm, n = qd integer and O _< r < d. Consequently, a'(ad)q

=

a@+'

=

+ r, where q is a nonnegative

a" = 1 (mod m).

Since d is the smallest positive exponent such that ad = 1 (mod m), i t follows that r = O. That is, dln. The last statement of the theorem is a consequence of Theorem 5-8.6. I t is possible to find the order modulo m of an integer a by trial, provided that m is small. For example, if m is 5, then cp(m) = 4, and the numbers which are relatively prime to m are 1, 2, 3, and 4. If d is the order of a modulo 5, then d14, by Theorem 5-8.9. Hence, d = 1, 2, or 4. Clearly, 1 belongs to the exponent l. Also, 22 = 4 = -1 (mod 5 ) , 32 = 9 = -1 (mod5), 42 = 16 = 1 (mod5). Thus, 4 belongs to the exponent 2, while 2 and 3 belong to the exponent 4 modulo 5. The problem of finding the order of a modulo m can be difficult if a and m are large. By Theorem 5-8.9, the largest possible order of an integer modulo m is p(m). If the integer a is relatively prime to m and a belongs to the exponent cp(m) modulo m, then a is called a primitive root modulo m. For example, 2 and 3 are primitive roots modulo 5. I t is possible to prove that if m is a prime, then there are exactly cp(cp(m)) primitive roots modulo m among the natural numbers 1,2, . . . , m - 1. However, if m is composite, there may not be any primitive roots for this modulus. For example, every odd integer belongs to one of the exponents 1, 2, or 4 modulo 16, and cp(16) = 8.

196

ELEMENTARY NUMBER THEORY

[CHAP.

5

An amusing application of Theorem 5-8.9 concerns the perfect shuffling of cards. Consider a deck of 2m cards. Let the cards of the deck be numbered from top to bottom: 1, 2, 3, . . . , m, m 1, . . . , 2m. The deck is split into two equal piles, the first pile consisting of the cards 1,2, 3, . . . , m 1, m 2, . . . ,2m in order, and the second pile consisting of the cards m in order. A perfect shuffle results if the cards are shuffled together from the bottom up, alternating a card from each pile, and beginning with the first pile. After a perfect shuffle, the arrangement of the cards will be changed f r o m 1 , 2 , 3, . . . , m , m + l , . . . , 2 m t o m + l , l , m + 2 , 2 , . . . , 2m,m. A card numbered 1, 2, . . . , m which was in position i before the perfect 1, m 2, shuffle is in position 2i after the shuffle. A card numbered m . . . , 2m which was in position i before the shuffle is in position 2i (2m 1) afterwards. Note that for 1 _< i _< m,

+

+

+

+

+

+

while for m

+ 1 5 i 5 2m,

Thus, in every case the ith card goes into position rl, where r l is the remainder obtained on dividing 2i by 2m l . Hence,

+

rl

E

2i (mod 2m

+ 1).

A second perfect shuffle will send a card which is now in position r l into position r2, where r2 = 2rl

-

2 2i = 22 i (mod 2m

-

+ 1).

In general, after n perfect shuffles, the ith card will be in position r,, where r,

2" i (mod 2m

+ 1).

The question now arises: what is the least number of perfect shuffles required to return a deck of 2m cards to its original order? The answer is plainly the smallest positive integer n satisfying

+

1, . . . , 2m. Since this congruence must hold for i = 1, 2, 3, . . . , m, m in particular for i = 1, it is necessary that 2"

-

1 (mod 2m

+ 1).

5-81

THE THEOREMS OF FERMAT AND EULER

On the other hand, if this latter congruence is satisfied, then

i

-

2" i (mod 2m

+ 1)

for every i, b y Theorem 5-6.3(f). Thus, the positive integer which is the answer to the problem is the order of 2 modulo 2m l . [Note t h a t Definition 5-8.8 applies since (2, 2m 1) = l . ] Suppose now t h a t we are considering a n ordinary deck of 52 cards. Then 1 = 53. By Theorem 5-8.9, the order of 2 modulo 53 m = 26, and 2m is a divisor of (p(53) = 52. T h a t is, the order of 2 is one of the numbers 2, 4, 13, 26, or 52. Clearly 2 2 and 2* are not congruent to 1 modulo 53. Also, 26 = 64 11 (mod 53), 212 = 121 = 15 (mod 53)) and therefore 302 = 900 = 53 17 - 1 2 l 3 30 (mod 53). Finally, 226 = (2 13) -1 (mod 53). Thus, the order of 2 modulo 53 is 52. Consequently, i t follows from our general result t h a t 52 perfect shuffles are required to return a n ordinary card deck to its original order.

+

+

+

-

--

-

-

-

l. Solve the following linear congruences, using Euler's theorem.

(a) 682 13 (mod 19) (c) 2 6 9 1 x - l l ( m ~ d 9 )

(b) 502 -21 (mod 33) (d) 11x-25(mod12)

2. Find the last three decimal digits of the following numbers: 32m00,71610, 99999.

3. Find the last two decimal digits of gg9. 4. Prove that for every natural number a, a and a5 have the same final decimal digit. 5. Show that if p is an odd prime which does not divide the integer a, then either a(~-l)I2 1 (mod p), or a(p-l)I2 G -1 (mod p). 6. Find p(m) for m = 1, 2, 7, 8, 9, 10, 12, and 16 by listing the numbers Ic which satisfy O k < m, and (k, m) = 1.


(b/n> = (ab)/(mn).

+

+

Proof. Let r denote the rational number a/m, and let s represent b/n. That is, r and s are the unique rational numbers satisfying

We first prove (a). Note that

If r = S, then mnr = mns. Hence na = mb. Conversely, if na = mb, then mnr = mns. Since m and n are natural numbers, mn f 0, and by the cancellation law in an integral domain, r = s. The proof of (b) is similar to the proof of (a). If r < S, then na = mnr < mns = mb, since mn is positive in 2, and therefore also positive in Q. Conversely, if na < mb, then mnr < mns. This implies that r < s. For otherwise, s 2 r and hence mns _< mnr, by Theorem 4-6.2. The proofs of (e), (d), and (e) are very simple. Note that by Definition 4-2.1 and Theorem 4-2.4

+

+

(mn)(r S) = mnr mns m(-r) = -(mr) = -a, (mn) (rs) = (mr) (ns) = ab.

=

na

+ mb,

Thus, by Definition 4-4.9, (a/m) -(a/m) (a/m)

+ (b/n) = r + s = (na + mb)/mn, =

-r

. (b/n)

=

=

(-a)/m,

r s = (ab)/(mn).

Although the system of rational numbers is constructed in order to divide integers by natural numbers, it happens that this system enjoys the strongest possible divisibility property: if r and s are rational numbers, and if r f O, then r divides s in Q. This fact is easily proved using the properties of Q given above. By (6T1.1), we can write r = a/m, s = b/n, where a and b are integers and m and n are natural numbers. Then it is well known that s/r = mb/na is the required quotient. However, if a is negative, then na is not a natural number, and it does not follow from

6-11

203

BASIC PROPERTIES OF THE RATIONAL NUMBERS

(6-1.1~)that mblna is in Q. This defect is easily corrected by noting that s/r can just as well be represented by mab/na2, where a2 is a positive integer, and consequently na2 E N. This is the idea involved in the proof of the important divisibility property, which we now formulate more carefully . THEOREM 6-1.4. If r and s are rational numbers, and if r # O, then r divides S in Q; that is, there is a rational number t such that r . t = s. Proof. By (6-1.1)) we can write

tvhere a and b are suitably chosen integers, and m and n are natural numbers. Thus, the rational numbers r and S satisfy

Since r # O, it follows that a # O. Thus, by Theorem 4-5.5, a2 is a positive integer. Therefore na2 E N. Evidently, mab E 2 . By (6-1.1~))there is a rational number t such that na2t = mab. Theref ore, (mna2)rt = (mr) (na2t) = a(mab)

=

(ma2)b = (ma2)(ns)

=

(mna2)s.

Sinee Q is an integral domain, and mna2 E N (hence, mna2 Z O), it follows that rt = s. I t should be noted that in severa1 places in the above proof, we have used the fact that multiplication in Q of elements belonging to Z agrees with the usual multiplication in 2, that is, Z is a subring of Q.

1. Prove the cancellation law for quotients: if m and n are natural numbers and a is an integer, then ma/mn = a/n in Q.

2. Prove that each positive rational number can be represented uniquely in the form m/n, where m and n are relatively prime natural numbers.

3. Prove that if a E 2, then a

=

an/n in Q for every n E N.

4. The Farey series F k of order k is the ascending sequence of rational fractions 01'12 m/n, where O 5 m 5 n 5 lc and (m,n) = 1. For instance, F4 is 1, 4, 31 29 37 3 , L. Write the Farey series F5 and Fs.

,

5. Prove that a/m - b/n

=

(na - mb)/mn (where a, b E 2, m, n E N ) .

204

THE RATIONAL NUMBERS

[CHAP.

6

6. Prove that if r and s are rational numbers, then (+)/S

=

r/(-S)

=

-(r/s)

(-r)/(-S)

and

=

r/s.

7. Point out the places where the condition (6-l.lb) was used in the proof of Theorem 6-1.4. 8. Prove Theorem 6-1.2. 6-2 Fields. The theory of ordered integral domains developed in Chapter 4 can be applied to the ring Q of rational numbers. However, Q also satisfies the divisibility property, given in Theorem 6-1.4, which does not hold in al1 integral domains (for example, it is not satisfied in 2 ) . I t is to be expected that certain properties of the rational numbers are consequences of Theorem 6-1.4 (together with the other properties of integral domains). If this is so, then these properties will hold as well for any ordered integral domain which satisfies this divisibility condition. There are examples of such integral domains. For us, the most interesting one other than Q itself is the ring R of al1 real numbers. Thus, as in Section 4-2, it appears that by introducing a new abstract concept, we will be able to prove theorems in a general setting which will apply to a number of important special cases.

DEFINITION 6-2.1. A jield is a commutative ring F such that (a) F contains a t least one element different from O; (b) if z E F, y E F, and x f O, then there is an element x E F such that z x = y. EXAMPLE 1. The rings Q and R are fields, as we have mentioned. So is the system C of al1 complex numbers. The ring of integers is not a field. EXAMPLE 2. Let F a + a = 0;O.O = a . 0 is a field. EXAMPLE 3. Let F

=

= =

{O,a), where 0 + 0 = O, O + a 0 . a = O , a - a = a;-O = O,-a

=

=

a + O = a, a. T h e n F

(0, 1, u, u). Define addition and multiplication by the

tables

+ O l u v

.lo

o

0 ' 0 o o o 1 O l u v

O 1 l u u u v Define -x verify.

-

l O v u

u v o 1

v u 1 0

1 u v

U

O

v

O v l u

U

V

l

x for x = 0, 1, u, and v. Then F is a field, as the reader can easily

6-21

205

FIELDS

The definition of a field does not explicitly require the existence of an identity element. However, it is not hard to show that every field does contain an identity. In fact a much stronger statement can be made. THEOREM 6-2.2. Every field is an integral domain. Proof. Suppose that F is a field. We first prove that F contains a nonzero identity element. Let x be any nonzero element of F. There is such an x by Definition 6-2.l(a). By Definition 6-2.1 (b), there is an e E F such that x e = x. Since x # O, it is evident that e cannot be O. To prove that e is an identity element, it is only necessary to show that y . e = y for al1 y E F. Note that since F is commutative, e y = y . e for al1 y. If y is any element of F, there exists z E F such that x z = y. Consequently, y = x . 2 = ( x . e ) . z = ( e . x ) . z = e . ( x . z ) = e - y = yse. Thus,eis a nonzero identity in F. To complete the proof of the theorem, it will now be enough (by Theorem 4-4.5) to prove that F has no proper divisors of zero. Suppose that y is a divisor of zero in F. That is, x y = O for some nonzero element x. By Definition 6-2.1 (b), there is an element w E F such that x . w = e, the identity of F. Consequently, y = y e = y (x w) = (y x) w = (x y) w = O . w = O. Thus, if y is a divisor of zero, then y = O, that is, F contains no proper divisors of zero. As we mentioned in Chapter 4, the identity element in any ring is usually denoted by 1. Of course, this custom is observed for fields in particular. Since every field F is an integral domain, there is, for each x # O and y in F, only one x E F satisfying the equation x z = y. Thus, as in any integral domain, we can write z as the quotient y/x. The property which distinguishes fields from arbitrary integral domains is the fact that in a field the quotient y/x always exists when x # 0. DEFINITION6-2.3. Let F be a field. Let x be a nonzero element of F. The quotient 1/x is called the inverse of x i n F, and is denoted by x-l. Thus, x-' is the unique element satisfying n: x-' = 1. I t should be emphasized that x-' is not defined for z = 0. Moreover, if x # O, then x-' # o. THEOREM 6-2.4. Let x, y, xl, x2, . . . , n:, (n a field F. Then (a) (x . y)-' (b) (2' ~ (c) (x-l)-' 1

= 2

1) be nonzero elements of

. y-';

x-'

xn)-' = x i '

.

=

2

2;

(d) 1- == 1; (-1)-'

=

-1.

. x2'. . . . x,'. S

206

THE RATIONAL NUMBERS

[CHAP.

6

Proof. The proofs of al1 of these statements [except (b), which can be obtained by induction from (a)] are based on the above obser~at~ion about the uniqueness of the inverse, namely, if s and t are elements of F such tha,t S t = 1, then t = S-'. For example, to prove (a), let s = x y, t = x-l y-1. Then s t = (x y) (x-l t-l) = (x x-l) ( y . y-1) = 1 . 1 = 1. Thus, x - ' - ~ - ' = t = s-l = (x y)-'. The proof of (c) is similar. By definition of the inverse, x x-l = 1. Thus, x-' x = 1. Therefore, x is the inverse of x-l. That is, x = (x-l)-'. The proofs of (b) and (d) are left for the reader to complete. Quotients can be expressed in terms of the inverse operation: if x # 0, then Y- .-l. y = y . x-1. (6-1) X Indeed, x (x-l y) = (x x-') y = 1 y = y. This observation is useful, because inverses are easier to manipulate than quotients. DEFINITION 6-2.5. Let x be a nonzero element of the field F. Define xn for natural numbers n by the inductive conditions

Define x0 = 1, and X(-n)

-

(x-'1".

For a natural number n, xn is the product n factors & Z . X . x.

...

We have briefly discussed powers of real numbers in Section 2-6. The new concept which Definition 6-2.5 introduces is the idea of zero and negative exponents. That is, if x is a nonzero element of a field, then the object xa is defined for every integer a. (6-2.6). Ruies of eaponents. Let x and y be nonzero elements of a field

F. Let a and b be arbitrary integers. Then (a) (b) (c) (d) (e)

xa . xb = x a + b (xa) = xa'b; (x y)a = xa ya; (x-')~ = x f - a ) la = l .

The identities (d) and (e) are easy consequences of Definition 6-2.5. Also, if a and b are natural numbers, then the identities (a), (b), and (c)

6-21

FIELDS

207

can be proved by induction on a (see Problem 1, Section 2-6). To extend these results to arbitrary integers involves a somewhat tedious checking of cases. As an illustration, let us consider the identity (a) for the case in which a is a positive integer and b is a negative integer. Then a = n and b = -m, where n and m are natural numbers. If n > m, then n = (n - m) m. Hence,

+

assuming that al1 of the identities above have been verified in the cases where a and b are natural numbers. If n = m, the proof is simpler:

If n

< m, t~henm

=

(m

-

n)

+ n and

An ordered integral domain which satisfies Definition 6-2.1 (b) is naturally called an ordered field. The most important examples of ordered fields are the systems of rational numbers and real numbers.

THEOREM 6-2.7. Let F be an ordered field. Let x and y be elemeiits of F, and let a and b be integers. (a) If x > O, thenx-' > 0;if z < O, thenx-' < 0. (b) If O < x < y, o r x < I/ < 0, thenx-' > y-'. (c) If x > O, then za > O; if x < O and a is odd, then xa < O; if x < O and a is even then xa > 0. (d) If O < x < y, and a > O, then xa < ya; if O < x < y, and a < O, then xa > ya. (e) If O < x < 1 and a < O, then xb < xa; if 1 < x, and a < b, then xa < xb. Proof. If x > O, then x-' # O. Hence, either x-' > O, or x-' < 0. If z-' < O, then 1 = x x-l < O, which is false by Theorem 4-5.5. Thus, x-1 > O. Similarly, if n. < O, then x-' must also be < O. Suppose that O < x < y. Then x-l and y-' are positive. Assume that a-' 5

208

THE RATIONAL NUMBERS

[CHAP.

6


4) (b) {x E Rlx (c) {x E Rlx x-l 23.. 8. Let F be an ordered field. Suppose that x E F, y E F, and x # O. Show that (a) Ix-lI = I X I - ~ , (b) Ix/ Y I = lxl/lyl. 9. Let x, y, x, and w be elements of an ordered field. Suppose that x # O and w # O. Prove the following. (a) If x and w have the same sign, then x/x < y/w if and only if xw < yx. (b) If x and w have opposite sign, then x/x < y/w if and only if xw > yx. 10. Prove Theorem 6-2.7(c), (d), and (e). 11. Prove Theorem 6-2.6 in detail. 12. Show that if A is a commutative ring with an identity element e such that for every x # O in A, there is an element y E A such that x y = e, then A is a field. 13. Prove that if F is a field, and if A is a ring which is isomorphic to F (see Definition 4-2.7)) then A is a field.

>

+


O in A. Then 2x = x 32 = 22 x >x x = 2x, and so on

+

+

+ x > O + x = x,

In particular nx # O for al1 n E N. If x < O, then -x > 0, and -(nx) = n(-x) # O for al1 n E N. Therefore, nx # O for al1 n E N and x E A. Consequently, Theorem 6-3.1 (a) is satisfied, and the characteristic of A is zero.

* In order to avoid confusing the identity of A with the natural number 1, we do not follow the custom of denoting the identity of A by 1 in this proof.

6-31

CHARACTERISTIC

OF INTEGRAL DOMAINS AND FIELDS

211

The fields in Examples 2 and 3 of Section 6-2 have characteristic 2. I t is possible to construct fields of arbitrary prime characteristic.

EXAMPLE l. Let p be a prime. Define Z, = {O, 1, 2, . . . , p - 1). Instead of the usual addition, negation, and multiplication of integers, define operations 0,0, and O by

where d is the unique integer such that O

5 d < p,

where e is the unique integer such that O

5e
r arid U > S , by (7-2). Therefore, t u >r S,

+

+

240 that is, t

THE REAL NUMBERS

+ u E X(r + S). This shows that +

+

S). Then v > r S, by (7-2). There is a rational Suppose that v E X(r number w satisfying u > w > r S; for example, w = i ( r S u) has this property. Then w - r > S and ( u - w) r > r. Thus, if t = (u - w) r and u = w - r, it follows that t E X(r), u E X(s), and t U = (u - W) r (W - r) = u. Therefore,

+

+

+

+ +

+

+ +

+

S), it follows that X(r Since u was any rational number in X(r {t ult E X(r), u E X(s)). This proves (b).

+

+

S)

E

I t should be noted that (7-4.3~)is not true if either of the assumptions r 2 O and S 2 O is omitted. In fact, if r < 0, and S is any rational number, then {u v[uE X(r), v E X(s)) = Q (see Problem 3 below). The one-to-one correspondence r * X(r) which is established by (7-2) between the set Q of rational numbers and a set of Dedekind cuts serves to identify the rational numbers with a subset of R. Of course, Q itself is not a subset of R, and in order to be able to think of the rational number system as a part of the system of real numbers, it is necessary to "identify" each rational number r with the corresponding cut X(r). A similar identification process was used when we enlarged the system of integers to the field of rational numbers (see Section 6-5). In effect, the rational numbers are redefined to be the set of al1 Dedekind cuts X(r). I t is important to show that the operations and ordering which will be defined in R agree for cuts of the form X(r) with the usual operations and ordering in Q. Specifically, it will be necessary to prove X(r)

+ X(s)

-X(r) X(r) X(s)

= = =

+

X(r S), X(-r), X(r S),

and X(r)

< X(s)

if and only if

r

< s.

These facts will be established as each operation is defined in R. I t is convenient to discuss the ordering of R before defining the operations of addition, negation, and multiplication.

DEFINITION 7-4.4 Order in R. Let X E R and Y E R. Define X


X)

In this case, X is said to be less than Y.

if X > Y.

7-41

CONSTRUCTION OF THE REAL NUMBERS

241

I t may seem odd that the ordering of R is the reverse of the inclusion relation. This reversal is necessary, however, to make the ordering in R agree with the usual ordering in Q. In fact, by (7-4.3a), X(r) > X(s) is equivalent to r < s. Hence, X(r) < X(s) if and only if r < s according to Definition 7-4.4. THEOREM 7-4.5. The ordering of R has the properties: (a) for any X and Y in R, exactly one of the relations X X = Y,or Y < X is satisfied; (b) if X < Y and Y < W, then X < W.

< Y,

The statement (a) is a reformulation of (7-4.2), using the Definition 7-4.4, and statement (b) is a consequence of the transitivity of inclusion. DEFINITION 7-4.6. Addition in R. Let X E R,

Y E R. Define

+ Y is called the sum of X and Y. I t is necessary to show that X + Y is a Dedekind cut. Obviously, Q. Since X c Q and Y C Q, there are rational numbers u @ CX + Y and v such that u < r for al1 r E X and v < s for al1 s E Y.Consequently, u + v < r + s for al1 r E X and s E Y. Therefore, u + v 4 X + Y. This proves that X + Y c Q. Next, suppose that r, and t are rational s. numbers and that r + s < t, where r E X and E Y. Then r < t Thus, t s E X. Consequently, t = (t + s E X + Y.This shows that X + Y satisfies Definition 7-3.2(b). Finally, to show that X + Y has no smallest element, suppose that t E X + Y. Then by definition, t = r + s for some r E X and s E Y. Since r is not the smallest element of X, thereexistsr' E Xsuchthatr' < r. Thent = r + s > r' + s E X + Y. Hence, t is not the smallest element of X + Y,and since t was any number in X + Y, it follows that this set has no smallest element. Therefore, X + Y satisfies al1 of the conditions required to be a Dedekind cut, so that X + Y E R. Then X

S,

S

-

-

- S)

By Definition 7-4.6 and the equality (7-4.313)

Therefore, addition of the elements of R which we have identified with rational numbers agrees with the usual addition in Q. Defining negation in R is a bit tricky. The negative, -X, of a Dedekind cut X E R must be a cut such that the sum of X and -X is the zero element of R. If the rational numbers [which we are identifying with the cuts of the form X(r), r E Q] are to be a subring of R,then the zero of R

242

THE REAL NUMBERS

[CHAP.

7

must be X(0). By Definition 7-4.6, this means that

+

s > O, so that s In particular, if r E X ? s E -X, then r sequently, if S E -X, then s > -r for al1 r E X ; that is, -X E {S E Qls

>

>

-r.

Con-

-r for al1 r E X).

As a first guess, one might suppose that the set Tx = {S E QIs

>

-r for al1 r E X)

is the cut -X for which we are looking. Indeed, it is easy to see that Tx satisfies the first two conditions in Definition 7-3.2 of a Dedekind cut, namely, @ C Tx c Q, and if s < t and s E Tx, then t E Tx (see Fig. 7-11). What makes Tx most attractive as a candidate for the role of -X is the fact (which we will not prove) that {r sjr E X, s E Tx) = X(0). That is, if Tx is a Dedekind cut, then according to Definition 7-4.6, X Tx = X(0). Unfortunately, the set Tx is not always a cut. In fact, if X = X(r), where r E Q, then

+

+

Tx

{S E Qjs > {S E Q/s > = {S E Qjs > = {S E QIs 2 =

=

-t for al1 t E X(r)) -t for al1 t E Q such that t > r} -t for al1 t E Q such that -t < -r) -r),

and the set Tx has a smallest element -r. Therefore, Tx is not a Dedekind cut, by Definition 7-3.2(c). I t appears, however, that the negative of X

7-41

243

CONSTRUCTION OF THE REAL NUMBERS

should be Tx if T x has no least element, and it should be the set obtained from Tx by deleting the srnallest element, in case Tx has a least element. A convenient way to formulate this definition is to say that -X is the set of al1 elements in T x which exceed some other element of Tx. This description of -X is equivalent to the following one.

DEFINITION 7-4.7.

Negation in R. Let X E R. The negative of X is

defined to be

-X

=

(r E QIr

> t for some t

E Q such that

t

>

-S

for al1 s E X).

We must prove that -X is a Dedekind cut. Obviously, -X G Q. Moreover, if r E X, then by Definition 7-4.7, -r 4 -X. Hence, -X C Q: Suppose that t X. Then t < S for al1 s E X, by Definition 7-3.2(b). Consequently, -t > -S for al1 S E X. Thus, if r > -t, then r E -X. Therefore, @ c -X. I t is obvious from Definition 7-4.7 that if r < s and Finally, if r E -X, then by Definition 7-4.7, r E -X, then S E -X. r > t for some t such that t > -8, for al1 s E X. Let r' be a rational Connumber satisfying r > r' > t (see Problem 1 ) . Then r' E -X. sequently, r is not the smallest element of -X. Since r was an arbitrary element of -X, it follows that -X has no smallest element. Therefore, -X is a Dedekind cut. We note that negation in R agrees on cuts of the form X(r) with negation in Q. In fact, by Dehition 7-4.7,

(u E Qlu > t for some t E Q such that t > -S for al1 S E X(r)). Since X(r) = (S E Q / s > r) , we have -X(r)

=

-X(r)

=

(u E Qlu

> t for some t

E Q such that

t

>

-S

for al1 S

> r).

If t > -S for every rational number S which is greater than r, then -t < S for al1 s > r. This implies that -t 5 r; that is, t 2 -r. Conversely, if t -r, then -t 5 r, and therefore -t < S for al1 S > r. We have shown -r. Consequently, that t > -s for al1 S > r if and only if t

>

>

-X(r)

= =

( u E Qlu > t for some t E Q such that t (U E QIu > -r> = X(-r).

2

-r>

Before we define multiplication in R, it is nec,essary to prove a simple fact about negation. (7-4.8). If X E R and X

< X(O), then X(0)
O. Hence, -t E X(0). If r E -X, then r > -t, so that r E X(0). This shows that -X 2 X(0). Since - t E X(0) and -t 4 -X (by Definition 7-4.7)) it follows that -X C X(0). Therefore X(0) < -X. As one might expect, X(0) is the zero element of R. Therefore, X E R is called positive if X(0) < X, negative if X < X(O), and nonnegative if X(0) < X or X(0) = X (that is, X(0) 5 X). By (7-4.8)) if X is negative, then -X is positive. DEFINITION 7-4.9. Multiplication in R. Let X E R and Y E R. Define (a) X Y = {r slr E X, S E Y)if X and Y are nonnegative, (b) X Y = -[(-X) Y]if X is negative and Y is nonnegative, if X is nonnegative and Y is negative, and (c) X Y = -[X (- Y)] (-Y) if X and Y are negative. (d) X Y = (-X) To justify this definition,* three remarks are needed. First, if X and Y are nonnegative, then {r slr E X, S E Y)is a cut. The proof of this fact is similar to the argument which we gave to show that ( r slr E X, S E Y> is a Dedekind cut, and we leave it for the reader. [Note that since X E X(0) and Y c X(O), it follows that C X Y E X(0) c Q].Second, if X is negative and Y is nonnegative, then -X is positive, so that the expressiori -[(-X) Y]makes gense because products of nonnegative cuts have been defined. A similar remark applies to the cases (e) and (d). Our final remark is that if r and S are rational numbers, then

+

* It is unfortunate that to define the product of two Dedekind cuts, four cases must be considered separately. We can easily see, however, that if either X or Y is negative, then ( r slr E X, S E Y) = Q (see Problem 3). Thus it would not do to use Definition 7-4.9(a) without some restriction on X and Y. This problem can be avoided by arranging the construction of R in a different order. Instead of proceeding from the natural numbers, to the integers, to the rational numbers, to the real numbers, as we have done in Chapters 3, 4, 6, and 7, the system R could have been obtained by the construction: natural numbers

-+

positive fractions -+ positive reals and negative reals.

-+positive

This route from N to R is somewhat more convenient, but less interesting, because i t does not give us an opportunity to study the important rings Z and Q along the way.

7-41

CONSTRUCTION OF THE REAL NUMBERS

245

If r and s are nonnegative rational numbers, this identity follows from (7-4.3~). Then using the identity X(-r) = -X(r), together with Definition 7-4.9(b), (e), and (d), the desired result is easily obtained for al1 combinations of the signs of r and s. For example, if r is negative and S is nonnegative, then X(r) X(s) = -[(-X(r)) X(s)] = -[X(-r) X(s)] = -[X((-r) S)] = X(-[(-r) S ] ) = X ( r S). Until now, the only examples of Dedekind cuts which we have seen are the sets X(r) corresponding to rational numbers. In Section 7-10, it will be shown that the sets Q and R do not have the same cardinal number. Consequently, there must be a vast set of cuts which are not of the form X(r) for any r E Q. I t seems worthwhile to give here a specific example of such a cut.

-

EXAMPLE 1. Let X = {r E Qlr > O and r2 > 2). Obviously, @ C X C Q, and if r E X, r < S, then s E X. To prove that X has no smallest element, suppose that r E X. Let r 1 S = -+-. 2 r

Then r - s = r/2 - l/r = (r2 - 2)/2r > O. Hence, r > s > O. Also, s2 - 2 = (r2 - 2)2/4r2 > 0, SO that s2 > 2. Therefore, s E X. This proves that X is a Dedekind cut. Obviously X is nonnegative. Thus, X2

=

(r-slr E X, s E X).

If r E X and s E X, then (r s ) = ~ r2 s2 > 2 . 2 = 4. Therefore, r s > 2. That is, X2 X(2). On the other hand, if t > 2, it is possible to find positive rational number r such that t > r2 > 2 (see, for example, Problem 7, Section 7-1). Hence, r E X and t E X2. This shows that X2 X(2). Therefore, X2 = X(2). In other words, X is the real number 2/2. In particular, X cannot be of the form X(t) for any rational number t, since otherwise X(t)2 = X(2) would imply t2 = 2.

THEOREM 7-4.10. The system R of al1 real numbers, given by Definition 7-4.1, with the operations of addition, negation, multiplication, and order defined by Definitions 7-4.6, 7-4.7,7-4.9, and 7-4.4, and with X(0) and X ( l ) as zero and identity element, is an ordered field. The reader should refresh his memory by listing al1 the identities which have to be checked in the proof of this theorem. Some of these are trivial. Por example,

246

THE REAL NUMBERS

[CHAP.

7

establishes the commutative law of addition. The identities which involve multiplication (particularly the distributive law) are troublesome, because their proofs require the consideration of numerous cases. There are two rules whose proofs involve a new idea. x (-X) = X(0). If X E R, W E R, and X # X(O), then there is a Y E R such that X . Y = W.

+

The proofs of both these results use the following property of Dedekind cuts. (7-4.11). If X is a Dedekind cut, and if r is a rational number greater than zero, then there is a rational number s such that s 4 X and s + r ~ X . Proof. Since X c Q, there is some s E Q with s 4 X. Suppose that r 4 X. (7-4.11) is false. Then for any s not in X, it follows that s Starting with such an S, we obtain S r 4 X, s 2r = (S r) r 4 X, nr 4 X for al1 s 3r = (S 2r) r 4 X, etc. By induction, s natural numbers n. However, this is impossible. In fact, since r > O, it is nr exceeds any rational possible to choose n large enough so that s number. In particular, choosing t E X, we can find n so that s nr > t. Then by Definition 7-3.2(b), S nr E X.

+

+

+ +

+

+

+

+ + + +

+

+

Using (7-4.11)) we show that X (-X) = X(0). Let r E X and s E -X. Then by Definition 7-4.7 there is a rational number t such that s > t, and t > -u for al1 u E X. In particular, s >. -r, so that r (-X) = (r slr E X, s E -X} c X(0). On s > O. Therefore, X the other hand, suppose that r E X(O), that is, r > O. By (7-4.11)) it is possible to find S E Q such that s 4 X, and s (r/2) E X. Hence, s < t for al1 t E X. Consequently, (-S) r/2 > -S and -S > -t for al1 r/2 E -X. I t follows that t E X. Therefore, (-S)

+

+

+

+

+

+

+

(-X) 2 Since r was an arbitrary element of X(O), we have proved X X(0). Therefore, X (-X) = X(0). We conclude this Section by showing that if X > X(0) and W 2 X(O), then there is a Dedekind cut Y such that X Y = W. Define

+

Y

=

{r/slr E W, O

< s < t for al1 t

E X}.

There must be rational numbers s satisfying O < s < t for al1 t E X, because X is a Dedekind cut which is properly contained in X(0) = (r E Q I ~> O>. Hence, @ c Y c X ( 0 ) cQ. If r E W and O < s < t

7-41

247

COPI;STRUCTIOS OF THE REAL XUMBERS

for al1 t E X, and if r / s < u, then r < su. Hence, su E W and u = su/s E Y . Finally, Y has no smallest element, because if r / s E Y, with r E W and O < S < t for al1 t E X, then there exists r' E W such that r' < r. Consequently r r / s < r / s and r r / s E Y. This proves that Y is a nonnegative Dedekind cut . By Definition 7-4.9,

If u E X and O < s < t for al1 t E X, then in particular s < u. Moreover, since r E W, and W >_ X(O), i t follows that r > O. Therefore, u ( r / s ) > r. Hence, X Y W. To reverse this inclusion, suppose that r E W. Since W has no smallest element, there is an r' E W with r' < r. Then ( r - rr)/r' > O. Select s E Q so that O < s < t for al1 t E X. Then s(r - rr)/r' > O. Hence, by (7-4.11)) there exists S' E Q such that S' 4 X and S' [s(r - rr)/r'] E X. We can suppose that S' >_ S , since otherwise S' could be replaced by s. Since S' 4 X, it follows that O < S' < t for al1 t E X. Thus rr/s' E Y by the definition of Y. Therefore,

+

Consequently, r E X Y. Since r was any element of W, we have proved that X . Y 2 W. Therefore, X Y = W .

1. (a) Show that if u and v are rational numbers with u < u, then w = +(u u) is a rational number satisfying u < w < v. (b) Use part (a) to prove that X(r) is a Dedekind cut for every rational number r.

+

2. Prove (7-4.3~). 3. Show that if r

< O and S is any rational number, then

4. Suppose that X

5. Show that X


X(0).

Define a cut Y such that Y 2

=

X.

X(r) if and only if r E X.

6. Prove that if X is a Dedekind cut, then the set Tx = { S E Qls > -r for al1 r E X) satisfies Definition 7-3.2(a) and (b), and {r slr E X, s E Tx) = X(0) 7. Draw a diagram to illustrate the proof that X (-X) 2 X(0).

+

+

8. Show from the definition of multiplication that X . X(0) = X(0) for al1 X E R.

248

THE REAL NUMBERS

[CHAP.

9. Show from the Definitions 7-4.4 and 7-4.7 that if X

10. Prove the following laws in R. (a) X (Y TIT) = ( X Y) IV (b) X X(0) = X (c) X . Y = Y - X (d) X . (Y TV) = ( X Y) W (e) X < Y implies X 11' < Y TV (f) X < Y and TV > X(0) implies X TV

+ + +

Y, then

+ +

+

11. Show that -(X




13. Prove directly that X X ( l )

=

+

X for al1 X E R.

14. Show that if X # X(0) and TY is any element of R, then there exists Y such that X Y = TV. It is necessary to consider the three cases: X > X(O), W < X(0); X < X(O), T V 2 X(0); X < X(O), T.V < X(0). These can be reduced to the case X > X(O), W 2 X(O), which has already been considered.

7-5 The completeness of the real numbers. Theorem 7-4.10 shows thal the system R of al1 real numbers is an ordered field. The same is true of the rational numbers, but we have seen that the field of real numbers is more versatile than the field Q. For example, such equations as x 2 = 2, x 2 = 3, x 2 = 5,etc., can be solved in R , but not in Q. 1s it possible to find a property of R which distinguishes it from arbitrary ordered fields? In this section we will show that such a fundamental property exists.

DEFINITION 7-5.1. Let A be an ordered integral domain." Let S be a subset of A. (a) An element x E A is called an upper bound of S in A if x al1 y E S. (b) An element z E A is called a iower bound of S in A if x al1 y E S.

2

y for

5

y for

* To state this definition, or Definition 7-5.2,i t is not necessary that A be an integral domain. The only requirement is that A be a partially ordered sei. That x for al1 x E A ; is, there is a relation 2 defined on A which satisfies (i) x (ii) if x 5 y and y x, then x = y; (iii) if x 5 y and y 2, then x 2.


4 2 ) . An element u E Q is a lower bound of S if u < O and u2 > 2 (that is, u < - 4 2 ) . EXAMPLE2. Let A = Z . Let S = ( a E ZIa2 < 2). Then S = (-1, 0, 1). Consequently, the upper bounds of S in Z are al1 integers b 2 1. The lower bounds of S are the integers b 5 -1. EXAMPLE3. If A is an ordered integral domain, and if S is a subset of A which has a greatest element x, then the upper bounds of S in A are al1 elements y E A such that y 2 x. Similarly if x is the least element of S, then the lower bounds of S are al1 of the elements u E A such that u 5 2 . EXAMPLE4. Let A bound in A.

=

&, S

=

Z . Then S has no upper bound, and no lower

DEFINITION 7-5.2. Let A be an ordered integral domain. Suppose that S is a subset of A. An element x E A is called the least upper bound of S in A if x is the smallest element in the set of al1 upper bounds of S. An element y E A is called the greatest lower bound of S in A if y is the largest element in the set of al1 lower bounds of S. I t is sometimes convenient to have a more formal statement of this definition. Referring to Definition 4-6.3, we see that x is the least upper bound of S if and only if (a) x 2 y for al1 y E S, (b) if x 2 y for al1 y E S, then x 2 x. Similarly, x is-the greatest lower bound of S if and only if (a') x 5 y for al1 y E S, (b') if x 5 y for al1 y E S, then x 5 x. Since the largest element in a set and the smallest element of a set are unique, if they exist a t all, we are justified in speaking of the least upper bound and the greatest lower bound. Of course, the least upper bound and the greatest lower bound of a set may not exist a t all. The expressions 1.u.b. S and g.1.b. S are frequently used as abbreviations for the least upper bound of S and the greatest lower bound of S, respectively. Of ten the Latin terms "supremum" and "injimum" are used instead of "least upper bound" and "greatest lower bound." In this case, the abbreviations sup S and inf S are used. Thus, 1.u.b. S = sup S, and g.1.b. S = inf S. EXAMPLE5. Let A = Q and let S = {r E &Ir2 < 2). Then S has no least upper bound and no greatest lower bound in Q, because the set

250

THE REAL NUMBERS

[CHAP.

7

of al1 upper bounds of S has no smallest element, and the set

of al1 lower bounds of S has no largest element. (See the Example in Section 7-4 .)

EXAMPLE 6. Let d Then 1.u.b. S 7-4 .)

=

dS

=

R and let

in R and g.1.b. S

=

-dS

in R. (See Example 1, Section

= R and let T = {X E RIX2 5 2 ) . Then 1.u.b. T and g.1.b. T = -dS. Note that in this example, the least upper bound and the greatest lower bound of T actually belong to T, whereas in Example 6, this was not the case.

EXAMPLE 7. Let A

=

2/Z

THEOREM7-5.3. Let F be an ordered field. Let S and T be nonempty subsets of F such that g.1.b. S and g.1.b. T exist. (a) If U = (x+ ylx E S , y E T), theng.1.b. U = g.1.b. S + g.1.b. T. (b) If V = (x ylz E S, y E T), and if al1 the elements of S and T are nonnegative, then g.1.b. V = (g.1.b. S ) . (g.1.b. T) . (c) If W = {-x!x E S), then 1.u.b. W = -(g.l.b. S).

Proof. We will prove (a) and (c), leaving (b) as a test for the reader. By definition of the greatest lower bound, it follows that g.1.b. S 5 x for al1 x E S and g.1.b. T 5 y for al1 y E T. Hence, g.1.b. S g.1.b. T x y for each x E S and y E T. That is, g.1.b. S g.1.b. T is a lower bound of (x ylz E S, y E T) = U. We wish to show that this sum is the greatest lower bound of U. That is, if x x y for al1 x E S and y E T, then x 5 g.1.b. S g.1.b. T. Let x be an arbitrary element of S. Then x x y for al1 y E T, so that x - x is a lower bound of T. Therefore, x - x g.1.b. T. Transposing, we obtain x - g.1.b. T x. Since x can be any element of S, it follows that x - g.1.b. T is a lower bound of S. Thus, x - g.1.b. T g.1.b. S. This gives the desired result : x g.1.b. S g.1.b. T. Therefore, (a) is proved. To prove (c), note that by Definition 7-5.1, w is an upper bound of W if and only if w 2 -x for al1 x E S. The condition w 2 -x is evidently equivalent to -w x. Thus, w is an upper bound of W if and only if -w is a Iower bound of S. Since S has a greatest lower bound, the condition for -w to be a lower bound of S is the same as -w 5 g.1.b. S, or -(g.l.b. S). This sequence of equivalent statements equivalently w shows that -(g.l.b. S ) is an upper bound of W and every other upper bound of W is larger. Therefore, -(g.1.b. S) is the least upper bound of W.

+

+

+

< +
O. Thus, x 1. This inequality contradicts the original assumption that x > 1. To prove (b), we first dispose of a trivial case. If x = O, then y > O = xl, so that (b) holds with n = 1. If x > O, then since x < 1, it foIlows that 1 < x-l. By (a), there is a natural number n such that (x-')" > y-'. Consequently, xn < y.


1. However, with minor changes of notation, the argument which follows is valid in the case m = 1, also. The proof is divided into three parts. (1) We will use the completeness of F to show that there is an element x E F satisfying the following conditions: (a) x > 0; (b) if O y < x, then y" < x; (c) if x < w, then wm 2 x.




>

+

>

>

+

>

>

>

262

THE REAL NUMBERS

Using this observation and Theorem 7-7.3 (a), we have

Finally, it should be mentioned that

This formula is more general than Theorem 7-7.3(b), but we will not prove it. (See Problem 9, however.) There are two problems associated with every sequence. Does the sequence converge to some number? If so, to what real number does it converge? I t appears from Definition 7-7.1 that in order to give a "yes" answer to the first of these questions, it would be necessary to have the answer to the second. I t turns out that this is not always the case. Many methods have been devised which, for particular types of sequences, yield a criterion for convergence. One of the simplest is the following.

THEOREM 7-7.4. Let ul, u2, u3, . . . be an increasing sequence of real . Then this sequence converges u2 u3 numbers, that is, ul if and only if it has an upper bound (in other words, there is a real number w such that u, w for al1 n).




THEOREM 7-8.4. Let CF=l v k be an infinite series such that v k O for al1 lc. Then this series is convergent if and only if the set of its partial sums has an upper bound, that is, there is a real number w such that Ck=lv k = u, 5 w for al1 n.

Proof. By Definition 7-8.2, the series C g l vk is convergent if and only if its sequence of partial sums ul, u2, u3, . . . is convergent. Since v k 2 O for al1 k , i t follows that ul 5 u l v2 = u2 5 u2 v3 = u3 5 . . Hence, the partial sums of CZl v k form an increasing sequence. By

+

+

268

THE REAL NUMBERS

[CHAP.

7

Theorem 7-7.4, such a sequence converges if and only if it is bounded. This proves the theorem. As it stands, Theorem 7-8.4 is not a very useful criterion for deciding whether or not a series converges. However, there are numerous tricks for determining whether the partial sums of particular infinite series are bounded or not. Such tests are studied a t length in calculus courses. We will implicitly use one well-known test (the "comparison test ") to prove a result which makes it possible to assign a real number to every infinite decimal sequence.

THEOREM 7-8.5. The infinite series

. . . , ao, bl, b2, . . . , b,, . . . are integers between O and 9 where a,, (inclusive), converges to a real number . Proof. The (m

+ 1 + n)th partial sum of this series is

Since each a; and b j is 5 9, this partial sum is a t most equal to

Thus, lorn+' is an upper bound of the set of al1 partial sums of

so that by Theorem 7-8.4, this series converges to a real number. By Theorem 7-8.5, we see that an infinite decimal sequence can be considered as an abbreviation for a convergent infinite series:

7-81

269

INFINITE SERIES

Thus, associated with every infinite decimal sequence is a real number (the sum of the corresponding series). This definition of the real number associated with an infinite decimal sequence agrees with the intuitive idea of the decimal representation of real numbers which we discussed in Section 7-1. Indeed, the decimal representation of a real number u was described there as a sequence of progressively more accurate approximations of u by decimal fractions. This sequence of decimal fractions is exactly the sequence of partial sums of the series associated with the infinite decimal sequence representing u, so that if the intuitive idea of "progressively more accurate approximations of u" agrees with the exact notion of convergence, then the series associated with the infinite decimal representation of u must converge to u. In the next section we will completely justify this viewpoint.

1. I n Example 4, i t was stated that

> 1.

does not exist if Itl

Prove this in detail, using Theorem 7-7.3.

2 . What is the numerical value of the 10th term of the series (a)

uk =

k+2 (b) ux 2k-

1'

2k k!

= -9

(c)

U* =

uk

if

k loAk.

xr=l

3. Prove that if u k is an infinite series such that O = un+l = un+z = un+sn= ,that is, al1 terms after the nth one are eero, then u k converges to

xr=l

Uk.

4. Show that if an infinite series

xyZl

uk

converges, then limk+mu k = 0.

5 . Prove that the converse of the theorem of Problem 4 is false by showing that (a) lirnk,, 1 / ( d m 1 % ) = 0, and (b) the series

+

diverges. [Hint: First show that l / ( d k $-

1x1 = d

6. Prove the comparison test: If u* is an infinite szies witli u k 2 O for al1 k = 1, 2, . . . , and (b) v k converges, then

x:=l

E,=,

k

-

5, such that (a) uk

dX.1

u*

5

vn for

converges.

7. Use the comparison test to show that the following infinite series are convergent.

270

THE REAL NUMBERS

[CHAP.

7

*7-9 Decimal representation. At the end of the last section, it was shown that every infinite decimal sequence can be considered as the representation of a real number, namely,

This observation provokes the two main questions which will be answered in this section. Can every real number be represented in this way by a decimal sequence? Can certain real numbers be represented by more than one decimal sequence, and if so, which ones, and in how many ways? Throughout this section, both finite and infinite decimal sequences will be considered as abbreviations of their corresponding decimal sums; that is

A decimal fraction which has n decimal places (see Definition 7-1.2) is called an n-place decimal fraction or an n-place decimal sequence. These are the decimal sequences with n digits following the decimal point, that is, . . . a o . b1b2.. . b,. A nonnegative rational number r is an n-place decimal fraction if and only if 10" r is an integer (see Problem 4, Section 7-1). I t is convenient to summarize some familiar properties of decimal sequences which will be used in this section. THEOREM 7-9.1. (a) If r is an n-place decimal fraction, then r is an n-place decimal fraction. (b) If r and S are n-place decimal fractions, and r < s, then

+ lo-"

(c) If amam-1 . . . a. . blb2. . . bn = cmcm-l . . . co . dld2. . . dn, then a, = cm, a,-1 = cm-1, . . . , a0 = CO, 61 = di, b2 = d2, . . . , b, = d,. . . . a. . b l b 2 . . . b, (d) < amam-1 . . . a. . blb2. . . b n b n + l . . . bn+k < (ama,-1.. . a o . 6162.. . b,) lo-".

+

Proof. By the remark preceding this theorem, if r is an n-place decimal fraction, then 1 0 9 is an integer. Therefore, 10nr 1 = 10n(r loMn)is

+

+

7-91

271

DECIMAL REPRESENTATION

+

lo-" is an n-place decimal fraction. also an integer. Consequently r The proof of (b) is based on the same idea. Since r < S, This proves (a). Thus, IOnr 1 5 10"s. Hence, r 10nr is an integer less than 10"s. lo-" 5 s. To prove (c), note that if amam-1 . . . a0 . blb2 . . . bn = cmcm-l . . . co . dld2 . . . dn is multiplied by lon, then we obtain

+

+

Thus, by the uniqueness of the decimal represent'ation of a natural number (Theorem 5-1.3), a, = cm, a,-1 = cm-1, . . . , a0 = co, b l = dl, b2 = d2, . . . , bn = dn. Finally, the proof of (d) is a simple calculation:

+ + + + + + + + + ... + + + + = amam-l.. . a o . b l b 2 . . . bnbn+l.. . bn+k lom-' + . . + a. + bl - lo-' + 62. l o w 2 + 5 (a,. 10" + + bn

amam-1 . . . a0 . blbz . . . b, = a, . l o m lom-' . . a. b1 10-1 bz. . bn lo-" . lorn-' . . . a. bl 10-l+ b2 . ior2 a,. 10'" + 6, lo-" b,+l - bn+k. 1 0 - ( ~ + ~ '

+

+

+ (g.lo-'"+l' + . . . + 9 . lo-'"+")

=


0.

Thcn

+

+

S o t e that r/d, q, r/d, and qn+k r/d are not decimal fractions, since otherwise c/d would be a decimal fraction. This fact is needed so that we can use the uniqueness of the decimal representations which was proved in Theorem 7-9.6. Because q, and qn+k are integers nnd O 5 r/d < 1, i t follows that

O bn+l Thereforc,

bn+2kbn+2k+l = r/d = O . bn+k+l . . . bn+2kbn+2k+l . . . b n + 3 k . .

bn+kbn+k+l

..

284

THE REAL NUMBERS

Consequently, U

= amam-1

. . . a0 . blb2 . . . bnbn+l . . . bn+k,

t h a t is, the decimal repre~entat~ion of u is ultimately periodic.

1. Find the rational numbers which are represented by the following ultimately periodic decimal sequences. (a) 21.01 (b) 4.0010012 (c) 0.00111. 2. Find the decimal sequences which represent the following rational numbers. (a) 2/7, (b) 201/999 (c) 18/17 3. Let u be the real number 0.1010010001000010... whose decimal representation consists of a sequence of ones separated by blocks of zeros, with the length of each block equal to the number of ones which precede it. Show that u is irrational. 4. Show that the number

k=l is irrational. 5. Let A be a set containing a t least two elements. Use the diagonal method to prove that the set S of al1 sequences al, a2, as, . . . of elements of A is not denumerable. Use this result to show that the set of al1 subsets of the set N is not denumerable. [Hint: Let A = {O, 1) and establish a one-to-one correspondence between the set P(N) of al1 subsets of N and the set S of al1 sequences al, a2, a3, . . . of zeros and ones. For instance, let

where for each i, ai

=

O if i 4 M and ai = 1 if i E 31.1

6. Let

[For example, (121.2121..., 003.3333...) +--+ 102013.23132313....] (a) Show that this definition establishes a one-to-one correspondence between the set of al1 pairs (u, u ) of real numbers and a subset T of R, provided the following convention is accepted: each real number is represented by an infinite decimal sequence (which may begin with a finite number of zeros), possibly ending with a sequence of al1 zeros, but not with a sequence of nines. (b) Show that T is not al1 of R.

7- 1O]

APPLICATIONS

OF DECIMAL REPRESENTATIONS

285

7. Use Theorem 7-10.4 and the proof of Theorem 7-10.3 to show that any natural number k: which is not divisible by 2 or 5 will divide some number of the sequence 9,99,999,9999, . . . . 8. Show that if m is a natural number which is relatively prime to 10, then the decimal expansion of l/m is of the form

where d is the order of 10 modulo m (see Definition 5-8.8).

CHAPTER 8

THE COMPLEX NUMBERS 8-1 The construction of the complex numbers. One of the properties of the system of real numbers which was derived in the preceding chapter concerned the solution of the equation xm = U, where m is a natural number and u is a real number: If m is odd, then x m = u has exactly one real solution, and if m is even and u is positive, there are exactly two solutions which are real numbers. However, if m is even and u is negative, then the equation xm = u has no real solution (see Theorem 7-6.3, and Problem 7, Section 4-5). In particular, the equation x 2 = -1 has no solution in the field of real numbers. The desirability of solving such equations poses a problem which should now be familiar to the reader: invent a new number system which contains R and which includes numbers which satisfy the equations under consideration. More precisely, we wish to construct a number system C which satisfies the following conditions:

(i) C is a field containing R as a subring, and (ii) C contains a number* i which satisfies i2 = -1.

(8-1

I t is also reasonable to require that C be minimal among the systems satisfying these conditions. That is, there should be no proper subring of C which also satisfies (8-1). For otherwise, we could attain our objectives more economically with the subring than with C. The construction which gives the desired field turns out to be remarkably easy. The result is the complex number system, which not only contains a solution of x2 = -1, but also solutions of the most general algebraic equations. Complex numbers were introduced in about 1560 by the Italian mathematician Rafael Bombelli (1530-1572?). Bombelli was a teacher a t the University of Bologna, an important center of mathematics during the Renaissance. Until about 1800, complex numbers were viewed as mysterious objects, devoid of any real meaning.t At the end of the eighteenth century, severa1 mathematicians independently gave logically correct definitions and useful geometrical interpretations of these numbers.

* The use of the symbol i to represent 4-1in C is standard mathematical notation. This element is usually called the imaginary unit. t A vestige of the early mysticism surrounding complex numbers is the common use of the term "imaginary" to distinguish them from "real7' numbers. 286

8-11

THE CO;~;STRUCTION OF THE COMPLEX XUMBERS

287

In order to see how the complex numbers and their operations should be defined, we suppose that there is a field F which satisfies the conditions (8-1). Then F contains R and the number i, and therefore it will contain i u, where u and v are real numbers. al1 expressions of the form u Also, since the usual rules of arithmetic are available in a field, it is easy to derive expressions for the sum, negat,ive, and product of such numbers:

+

(x

+

+ i -y) = (-X) + i - (-y),

-(x i y) (U

+ i . U) = + i IU

=

(ZU-

+ +

+ +

(yu XV) i Z y v yv) i . (yu XL)).

(8-2)

These identities show that the collection of al1 t'he elements which can be written in the form u i v is a subring of F. Moreover, it is not hard to show that this subring also satisfies the conditions (8-1). In particular, if F is a field C with al1 of the desired properties, then the assumption that C is minimal implies that C coincides mith the subring of al1 elements of the form u i v. Therefore, it must be possible to write every element of C in the form u i u, where u and v are real numbers. I t is apparent that u i v is determined by the two real numbers u and v. Moreover, if x i y=u i u, then x = u and y = v. Indeed, if y # u, then i = (x - u)/(v - y). However, i2 = -1, and since (X - u)/(v - y) is a real number, it follows that [(x - u)/(v - y)]2 0, which is a contradiction. Therefore, y = u, and consequently x = u. We can summarize this discussion by saying that if a number system C with the desired properties exists a t all, then there is a one-to-one correspondence, (U,u) c-, U i . L',

+

+

+

+

+

+

>

+

between the set R X R of al1 ordered pairs of real numbers and C. This observation suggests that a way to construct the complex numbers is to define suitable operations on the set R X R. The identities of (8-2) show how the operations of addition, negation, and multiplication must be defined for the ordered pairs. There is another important fact which is a consequence of the above discussion. Any two rings which satisfy al1 of the requirements desired for C are isomorphic. That is, if C exists a t all, then C is unique.

DEFIKITION 8-1.1. The set C of al1 complex numbers consists of al1 ordered pairs (u, u) of real numbers. If (x, y) E C and (u, u) E C, then (a) (x, y) (u, u) = (x u, Y 4; (b) -(x, y) = (-z, -y); and (e) (x, y ) (U, u) = (X U - y v, y u x u).

+

+

+

+

288

THE COMPLEX NUMBERS

[CHAP.

8

The ordered pairs of real numbers are definite objects which can be interpreted as complex numbers without any logical contradiction. However, the set of al1 ordered pairs of real numbers often occurs in mathematics with other interpretations. The intended meaning of (u, v) should be specified whenever such pairs are used. In the case of complex numbers, this will usually be unnecessary, because once we show that the system C defined above satisfies the requirements listed in (8-l), it will be possible to return to the convenient notation u i v. The reader should be aware of the double use of the signs -, and . in Definition 8-1.1. On the left-hand sides of the identities (a), (b), and (e), they represent the operations which are being defined for ordered pairs, while on the right-hand sides of these equalities, they indicate the known operations in the field R of real numbers. There is no problem about the operations in Definition 8-1.1 being well defined, as there was in the case of the rational numbers and the real numbers. Definition 8-1.1 involves no arbitrary choice, such as was made in defining the operations on the equivalence classes which are the elements of Q. Also, the expressions on the right-hand sides of (a), (b), and (c) obviously belong to the set C of al1 ordered pairs of real numbers, so that the problem of closure, which was troublesome in defining addition, negation, and multiplication of real numbers, does not arise. I t must now be shown that the complex numbers as defined above satisfy the description given in (8-1). This result is the content of the two following theorems.

+

+,

THEOREM 8-1.2. The set C of al1 complex numbers with the operations defined in Definition 8-1.1 is a field with (O, O) as the zero element and (1, O) as the identity element. The complex number (O, 1) is a solution of the equation

x2

=

-(l, O).

Proof. The proof that C is a commutative ring with (O, O) as the zero element and (1, O) as the identity element consists of checking the identities of Definition 4-2.1 in a straightforward way. For example, me will prove the associative law of multiplication:

8- 11

THE COSSTRUCTION

289

OF THE COMPLEX NUMBERS

Hence, (ul, V I ) ( ( ~ 2~, 2 )( ~ 3va)) , = ( ( ~ 1V , I ) .(~2,v2)) ( ~ 3~, 3 ) . To prove that C is a field, it is necessary to show that if (u, u) # (O, 0) in C and (w, z) E C, then there exists (x, y) E C such that

(8-3)

(u, U) (:c, y) = (w, 2).

If both sides of this cquality are multiplied on the left by (u, -u), then by the associative law just proved, we obtain (u2

+ v2, O)

(5, y) =

The real number u2

(U,

-U)

. (w, z) = (uw + uz, (-v)w

+ uz).

+ v2 is not zero, since otherwise

so that 'ZL = u = O. This contradicts the assumption that (u, u) # (O, 0). Thus, (u2 v2)-' exists in R, and

+

(x,y)

+

+

(1, O) (2,y) = (((u2 v2)-l, 0) . (u2 v2, 0)) (x, 9) = ((u2 u2)-l, 0 ) . (U, -z!) (w, 2) = ((u2 v2)-l (uw L'z),(u2 u2)-l (u2 - uw)).

=

+ +

+

+

As frcquently happens in elementary algebra, the steps which lead to the solution of (8-3) can be reversed to prove that the expression obtained for (x, y) really is a solution:

+ vz), (u2 + v2)-l. (uz - vw)) = (U, u) (U, -u) ((u2 + v2)-l, O) (w, z) = (u2 + u2, O) ((u2 + v2)-l, O) . (w, = (1, o) (w,

(u,v) ((u2

+ u2)-l

(uw

2)

2)

= (w, 2).

By Definition 8-1 .l (c) and (b), (0, 1)2 = (- 1,O) servation completes the proof of Theorem 8-1.2.

= -(1,

O). This ob-

The definition of a complex number as an ordered pair (u, v) of real i u, where numbcrs was suggested by the correspondence (u, u) t, u u and v are real and i2 = - 1. In particular, a real number u = u i O should corrcspond to the pair (u, O).

+

+

290

THE COMPLEX KUMBERS

[CHAP.

8

THEOREM 8-1.3. The correspondence zc t, (u, O) is an isomorphism between R and the subring R' = ((u, 0)Ju E R ) of C. Each element (0, 1) (v, O). of C can be expressed in the form (u, O)

+

This theorem, whose proof we leave for the reader, is the justification for identifying each real number u with the corresponding element (u, O) of R'. If this identification is made, then R becomes a subring of C. Thus, C satisfies condition (i) of (8-1). In particular, we have now attained the following chain of inclusions relating the classical number systems of mathematics:

NcZcQcRcC. For simplicity, each element of R in C will be denoted by a single symbol such as O, 1, +, 2, u, and v, rather than by the corresponding pair (O, O), (1, O), (3, O), (2, O), (U,O), and (v, O). Note that with this notation, O and 1 represent the zero and identity of C, as they should. Moreover, by Theorem 8-1.2, (0, 1)2 = -1, which leads to an exact definition of the symbol i as an abbreviation for (0, 1). Therefore,

and C satisfies condition (ii) of (8-1). By virtue of the notat,ion just introduced, the expression t c on a definite meaning as a complex number. In fact, u

+ i . v = (U,O) + (O, 1)

(u, O)

=

+i

v takes

(u, u).

We see from this equality that every complex number can be represented uniquely in the form u i v, with u and v real numbers. From this fact it follows easily that no proper subring of C satisfies (8-1); that is, C is minimal.

+

+

1. Express the following coinplex numbers in the form u iv. (4 (2, 1) . (172) (4 (3,2b'(l, 1) (a) (-1, 1) (b) ( 0 , l ) (2, -1) where (u, u) # (O, O) (e) (u, 2. Complete the proof of Theorem 8-1.2. 3. Prove Theorem 8-1.3. 4. Determine t,he value of the sum i q o r al1 values of n. 5. Show that the following sets are subrings of C. ( 4 ((Y, s)lr E Q, s E Q) (b) {(a, b)la E 2, b E 2)

+

1s either of these subrings a field? 1s either of them isomorphic to N, 2, Q, or E ?

8-21

COMPI~EX COSJUGATES

A X D ABSOLUTE VAL'L'E IS c

291

8-2 Complex conjugates and the absolute value in C. I t is iiot possible to dcfinc an orderiiig of thc complcx riumbcrs such that they will form an ordered ficld. I'or if C could be made into an ordered ficld, then i2 = - 1 would have to be both positivc : ~ n dnegativc, by 'i'heorem 4-53. Ho~vever, the ficld C has somc important special propertics ~vhichare not present in every field, or evcn iii ordcred fields. I n this sectioii the clonsequences of somc of thcse propcrties will be examined. Throughout this section and the remainder of the book, we \vil1 represent complcx numbcrs cithcr by single lettcrs, such as z and w, or else by the notation z i y and zc i c , where .c, y, u, and c dciiotc real numhcrs. Thc discussion a t the cnd of Section 8-1 justifies this c:oiivention. Since .x iy = u iu implics that s = u and = v, wc sec t,hat the real numbers n: aiid ?j appearing in the rcpreseritation z = .c i y are uniclilcly detcrmined by the complex riumber z. The real iiumber n: is called the real part of x, and y is called the imnginary part of z. I t is convenient to write n: = o ] ( ~ )and y = g(z) in this case. T h a t is,

+ +

+ +

+

I t is obvious from t,he dcfiiiitioii of addition snd negation iii C that

+ w) = m(z) + di(w), g(z + w) = 9(z) + g(w),

R(x

DEFIXITION8-2.1. Let, z = z conjugate of z is the iiumber

and

a(-z)

=

-m(z),

and

S(-z)

=

-g(z).

+ i y be a complex number.

(8-5)

The complex

We ~villoften simplify the phrase "complex conjugate of 2'' to "conjugate of z," although t,hc latter expression has a broadcr meanirig in ot,her phases of algebra. Also, it is customary to write n: - i y instead of z i(-y).

+

THEOREM8-2.2. Let z aild w be complex numbers. Theii (a) z + w = Z + w ; (b) (-x)= -2; (c) 2 . w = X - w ; (d) if w f O, thcn = z/w; (e) if w = 2, t,hen = z, that is, ¿ = z; (f) x Z = 26i(z), z - Z = 2iS(z).

3

+

292

THE COMPLEX NUMBERS

[CHAP.

8

We will omit the proof of (a), (b), (e), and (f). The proof of (c) is obtained by direct computation. Let z = x iy, w = U iv. Then Z = x i(-y), and m = u i(-u). Hence,

+

+ X . = [(xu - yv) + i(yzc + xv)] = (xu

+

-

+

yv)

+ i[-(yu + xv)],

and

+ i[(-y)u + %(-u)] yo) + i[-(yu + xv)] = X.W.

2 üj = [XU- (-y) (-u)]

(u .

=

-

To prove (d), note that by what we have just showii Hence, Z/w = Z/w.

If z = x

+ iy, then

Therefore z Z is a nonnegative real number, and it has a square root in R.

+

DEFINITION 8-2.3. Let z = x iy be a complex number. The absolute value or modulus of z is the nonnegative real number

+

e.

If z is a real number, say z = x i O, then ltl = If x 2 0, then @ = x. If x < O, then @ = -x. Therefore, the definition of the absolute value of z given above is consistent with Definition 4-6.6 for the absolute value of elements of an ordered integral domain (in particular, the absolute value in R). THEOREM 8-2.4. Let z and w be complex numbers. Then O; if IzI = O, then z = 0; (a) IzI (b) z Z = 1212; (c> 1 .4= 1x1; (d) 1-21 = 1x1; (e) lz wl = 1.4 ; (f) if w # O, then Iz/wl = IzI/IwI; (g) l@(z)l 5 121, Ig(z)l 5 121; (h) 12 wl :' 1.4 Iwl.

>

IwI

+

+

8-21

COMPLEX CONJUGATES AND ABSOLUTE VALUE IN

c

293

+

iy. By Definition 8-2.3, 1x1 2 0. If jz/ = O, then Proof. Let z = x O = x2 + y2 2 x2 2 0; hence, x = 0; similarly, y = O. To prove (b), observe that z

z=

(x

+ iy)

[x

+ i(-y)]

= x2

+ y2 = Izj2.

The equality (c) is obtained from (b) and Theorem 8-2.2(e) by taking the square root of both sides of the identity 1212 = I =Z z= z E = 1.~1~. Using Definition 8-2.3,

The identity (e) is obtained from (b) and Theorem 8-2.2(c) by taking the square root of both sides of the equality

Using this result, we have Iz/wl . Iwl = 1 (z/w) . wl = jzj. If w # O, then Iwl t' O by (a), so that this identity can be divided by Iwl to obtain (f). If z = x iy, then by definition,

+

The second statement of (g) is proved in a similar way. Finally, to obtain the triangle inequality {h), note that by Theorem 8-2.2,

Taking the square root of the first and last term of this inequality yields (h). The theorem we have just proved contains the most important elem e n t a r ~properties of the absolute value. The reader should become thoroughly familiar with these f acts. The result of Theorem 8-2.4(b) can be used to calculate quotients in C. The general idea, which was used implicitly in the proof of Theorem 8-1.2, is that

294

T H E C O M P L E X KUMBERS

[CHAP.

8

We will use the results of Theorems 8-2.2 and 8-2.4 and the fact that every nonnegative real number has a square root to prove that every complex number w has a square root x in C. In fact, an explicit expression for x in terms of w can be obtained. Let w E C. First assume that there is a complex number x which satisfies x2 = W. We will solve this equation for z in terms of w. By Theorem 8-2.4, x2 implies Iwl = / z 2 /= lz12 = 2 . 2. Therefore,

=

w

Moreover, by Theorem 8-2.2,

+ @(w)]is a nonnegative real number. Taking square roots, 2@(z) = & . \ / [ 2 ~ ~ ( z = ) ] 2f d ~ [ l w l+ @(w)]. (8-7) There are now two cases to consider. If jwj + @(w) # O, then by (8-7),

Thus, 2[lwl we obtain:

2@(x) # O. Then (8-6) can be written in the form

Using (8-7) again, \ve find that x has the two possible values,

If

IwI

+ @(w) = O, then

Hence g(w) = 0, and w = @(w) = -Iwl. That is, w = -u, where u is a nonnegative real number.' By (8-7)) @ ( E ) = O. Hence, x = i g ( x ) , and

8-21

COMPLEX CONJUGATES ,4ND ABSOLUTE VALUE I N C

Therefore, $(z) = ble values,

295

&m. Consequently, in this case z has the two possiz =

(8-9)

Our discussion shows that if there is a compIex number x satisfying z2 = w, then z must have the form (8-8) if lwJ @(w) # 0, and 2 is @(w) = O. I t remains to show conversely that if given by (8-9) if lwl @(w) # 0, and by (8-9) when lwl is given by (8-8) in case Iwl @(w) = O, then z2 = w. This is done by an easy computation. Suppose first that Iwl @(w) # O. Then

+

+

+

+

+

If Iwj

+ a ( w ) = O, theii ( f i f l ) 2

=

-1wI

=

W.

THEOREM 8-2.5. If w is aiiy nonzero complex number, theii there are o numbers z such that x2 = w. If jwl @(w) # O, exactly t ~ complex then these numbers are given by

+

If Iwl

+ @(w) = O, the solutions of z2 = w are z

=

i m

and

x

=

im.

For any complex number w, it is convenient to Iet the symbol fistand f or IwI J2[lwl @(w)l

+

+

+

i\/m +

if Iwl a ( w ) # 0, and for if lwl @(w) = O. Then we caii say that the two square roots of w are 6and -&.

=

EXAMPLE 4. Let w = 3 16. Hence

+ i4. Then lwj

=

5, @(w)

=

3, and 2[/wl

+ @(w)]

296

THE COMPLEX NUMBERS

[CHAP.

8

In the case of square roots of complex numbers, just as for square roots of real numbers, we must be careful not to assume that @ is always equal to w. I t is in fact easy to see that

@ = w if @(w) > O, @ = w if R(w) = 0, @ = -wif@(w) = O ,

@ = -wif @(w) < 0, and 9(w) > 0, andS(w) < O .

(8-1 O)

In any case, 4 3 = h w . More generally, we obtain the following result. (8-2.6). Let z and w be complex numbers. Then (a) 4X.W = &(&-&); (b) if w # O, then = =t (G/&). We leave the proof of these identities for the reader. The theorem that every complex number has a square root in C can be used to show that any quadratic equation

where a, b, and c are complex numbers and a jL 0, has a solution x in C. Suppose that x is a complex number which satisfies (8-1 1). Rewrite (8-1 1) in the form

That is, the term b2/4a is added and subtracted on the left-hand side of (8-ll), so that the expression in parentheses becomes a perfect square. This is the familiar method of completing the square. I t leads to the equality

Therefore,

Conversely, it can be checked by direct substitution that the two numbers given in (8-12) are solutions of (8-11). That is, the following result holds.

8-21

297

COMPLEX CONJUGATES AND ABSOLUTE VALUE IN C

THEOREM 8-2.7. Let a, b, and c be complex numbers and a

#

O. Then

the solutions of the equation

are given by the formula

EXAMPLE 5. Find the solutions of the equation

Apply the formula of Theorem 8-2.7 with a

X =

-(1

+ i2) + (3 + i2) 2(1

+ i)

=

=

1

+ i, b = 1 + i2, and c = -2:

2 A -

2(1

+ i ) --

1

(1 - i))

l. Simplify the following quotients.

2. Find the square roots: (a) 4 7 i(24) (b) 42 (c)

+

4-

(d)

dm

(e)

fl

3. Find the solutions of the following equations. 1 = O (b) (3 i)x2 (a) x2 2ix 10x - (9 -j- i3) = O (c) -5x2+ 2/Zx - 1 = o 4. Prove Theorem 8-2.2(a), (b), (e), and (f).

+ +

+

+

298

THE COMPLEX NUMBERS

[CHAP.

8

5 . Show that if z and w are complex numbers, then the following are true.

+ IwI

WI

( 4 lz 5 lzl (b) Iz - wl 2 IzI ( 4 lz wI2 Iz - wI2

+ +

IwI

+

2(1zI2 1wI2) 6. Show that for any complex number w, @(2/6) 2 0. =

7. Prove (8-10). 8. Prove (8-2.6). 9. Show that if @(w) > O and @(z) > O, then

2//x = fi d .

10. Show that the numbers given by (8-12) are solutions of (8-11). 11. Prove that if w = u

+ iv, and v # O, then

+

12. Let w = a ib, where a and b are integers. Prove that Iwl is an integer if and only if w = t z2 or w = it z2, where z = r is with r, S, and t integers. [Hint: See Theorem 5-5.4.1

+

13. Solve for z in terms of w in the equation z4

=

w.

8-3 The geometrical representation of complex numbers. We mentioned in Section 8-1 that ordered pairs (u, v) of real numbers have severa1 interpretations in mathematics. One of the most familiar applications of these pairs occurs in analytic geometry. In fact, analytic geometry is based on the "coordinatization" of the plane, that is, a one-to-one correspondence between the set of al1 points P cif the plane, and the set of al1 pairs (x, y) of real numbers. This correspondence provides an important way of representing complex numbers by points in the plane. For the reader who is not familiar with analytic geometry, we will discuss briefly the process of defining coordinate systems in a plane. The construction begins with the choice of any two perpendicular lines. It is convenient to take one of these to be horizontal. This line is called the x-axis, and is denoted by X. The other line must then be vertical. I t is called the y-axis, and is denoted by Y. Let O be the point of intersection of X and Y. The point O is called the origin of the coordinate system in the plane. Let I be a point on X which lies to the right of O. Using 01 as the basic unit interval, define a coordinate system on X by the construction described in Section 7-3. Let J be a point on Y, above O, such that the distaiice is equal to the distance That is, the segments 01 and O J are congruent. Establish a coordinate system on Y using OJ as the basic unit interval. Let P be any point in the plane. Construct the line i through P and parallel to X (hence perpendicular to Y). Also draw the line m passing

m

m.

8-31

GEOMETRICAL REPRESEXT.4TION OF COMPLEX XUMBERS

299

through P and parallel to Y (hence perpendicular to X ) . Then 1 meets Y at some point S, and m meets X at some point T. Let x be the real number corresponding to T in the coordinate system on X . Let y be the real number corresponding to S in the coordinate system on Y. We associate with P the number pair (x, y) (see Fig. 8-1) :

Different points evidently correspond in this way to different number pairs, and every pair of real numbers is associated with some point. In fact, the point corresponding to (x?y) can be found as the intersection of the vertical line through the point associated with x on X and the horizontal line through the point corresponding to y on Y. Thus, P * (x, y) is a one-to-one correspondence between the set of al1 points of the plane and the set of al1 pairs of real numbers. A plane, together with a correspondence between points and number pairs defined in this way, is called a coordinate plane. The numbers x and y in the pair (x, y) corresponding to the point P are called the cartesian* coordinates of P. Sometimes, to be more specific, x is called the X-coordinate or abscissa of P, and y is called the Y-coordinate or ordinate of P. The points on the x-axis are exactly the points whose coordinates are of the form (x, O). The points on the y-axis have coordinates (O, y). In (O, O), 1 +-+ (1, O), and J * (O, 1). particular, O (8-3.1). Let S and T be points with cartesian coordinates (xs, ys) and (xT, yT), respectively. Then the distance between S and T is

m

* The term "cartesian" is used in honor of the French mathematician and philosopher Rene Descartes (1596-1650), who was the founder of analytic geometry.

300

THE COMPLEX NUMBERS

Prooj. The proof of this statement is based on the Pythagorean triangle theorem. Let ls and lT be horizontal lines through S and T, respectively, ~ vertical lines through these same points. Let P be and let ms and r n be the point of intersection of the perpendicular lines ms and lT. Then P S T is a right triangle with S T as its hypotenuse. Figure 8-2 illustrates a typical situation. If ST is horizontal or vertical, the triangle PST is degenerate, and this case requires special treatment. The lines ms and r n ~ intersect the x-axis a t points corresponding to the real numbers xs and XT, and these two points, together with T and P, determine a rectangle. Thus, the distance between P and T is the same as the distance between the points on the x-axis corresponding to xs and x ~ : T P = IxS - xT]. Similarly, PS = \ys - YTI. Hence,

si

-72

=

T P+ ~ FS2 = l x s =

-

xT12

+ lYS

+

-

yT12

(XS - x T ) ~ (YS - yT)'.

Taking the square root completes the proof. We now turn to the representation of complex numbers as points in a coordinate plane. This representation is obtained simply by using the definition of complex numbers as pairs of real numbers, and associating each complex number x i y = (x, y ) with the point in the coordinate plane whose coordinates are x and 3. I t is then possible to use the complex numbers as labels for the corresponding points in the plane (see Fig. 8-3)) just as the real numbers are used to represent the points on a line. The term complex plane is often used to describe a coordinate plane whose points are labeled by complex numbers. If complex numbers are interpreted in this way, then the operations with iy, them have interesting geometrical meanings. For example, if x = x

+

+

then @(z) = x is the abscissa of z and g(z) = y is the ordinate of z. Thus, in particular, the real numbers represent points on the x-axis. The absolute value /zl = is the distance from the origin O to z. More generally, if z and w are complex numbers, then (z - wl is the distance between the point z and the point w. To see this, let z = x iy and w = u iv. which, Then Iz - WI = 1 (x - U) i(y - U) 1 = d ( x 4- (y by (8-3.1), is the distance between the point with coordinates (x, y) and the point with coordinates (u, u). Often it is possible to give concise descriptions of sets of points in the plane, using complex numbers.

.\/m

+

+

+

EXAMPLE 1. {zIB(z) > O) is the set of al1 points in the upper half plane; in other words, the set of al1 points which lie above the x-axis. EXAMPLE 2. {z/121 < 1) is the set of al1 points which have distance less than one from the origin O, that is, the set of points which lie inside a circle of radius one with center a t O. EXAMPLE 3. {zI Iz - 'il = 1) is the set of al1 points on the circle with center a t i, and radius equal to one. EXAMPLE 4. {z14(z) = m@(z)),where m is a real number, is the set of al1 points on a line 1 through the origin, with slope equal to m (see Fig. 8 4 ) .

The addition of complex numbers has an interesting geometrical meaning. Let z and w be complex numbers representing points in the complex plane. Let O be the origin in the plane. If x, w, and O lie on a line E which is not the y-axis, then by Example 4, B(z) = m@(z) and 4(w) = mR(w) w) = $(z) S(w) = for some real number m. Consequently, 4(x m[@(z) @(w)]= m@(z w). Therefore, z w corresponds to a point on E. [If z and w lie on the 3-axis, then R(z) = R(w) = O implies @(z w) = 0, and z w is on the y-axis.] If the origin O does not separate z from w on E, then z w is a t a distance 1x1 Iwl from O on the same w is at a distance side as z and w. If O is between x and w, then x llzl - lwll from O? on the same side as x if 1x1 > Iwl, and on the same side as w if lwj > lzl (see Fig. 8-5). If x, w, and O do not lie on the same line, then the point corresponding to x w can be determined by the parallelogram rule.

+

+

+

+

+

+

+

+

+

+

+

THE COMPLEX XUMBERS

[CHAP.

8

(8-3.2). Parallelogram rule. Let x and w be complex numbers representing points S and T, such that O, S, zlnd T do not lie on a line. If P is the point corresponding to z w, then OSPT is a parallelogram (see Fig. 8-6).

+

I t should be remarked in connection with (8-3.2) that OSPT js the order in which the vertices are encountered in moving around the sides of the parallelogram. That is, ST and OP are diagonals, not sides of the figure. The proof of (8-3.2) is an exercise in elementary geomet'ry, which we will leave for the interested reader.

1. Draw coordinate axes in a plane, and plot the points with the following coordinates: (2, 1), (-1, 2), (-1, -l), (-$, +). 2. Find the distance between the following pairs of points in the complex plane. (a) 4, i9 (b) i, 2 - i (c) -1 i, 1 - i (d) 9 + i(15),4 - i9

3. Describe the following sets in geometrical terms. (4 (b) (4 (d) (e) (f) (g)

L

g(2) 5 1) 1) (21 Iz - 1 1 > 1) (21 1z21 = 4) (21 1z2 - 2x+ 1 > 0) ( z j ~ ( 2 ) = r t l , S ( x ) = f1) (zlg(2) = 2@(4,g(2) 2 01 (21-1

{zl9(ix)

=

I2[] is the circle with centcr a t -w, with 4. Sliow t h a t {xl Iz - zr;l = radius 4 2 1x1. [Hint:Use the ideiitity obtained in Problerii 5(c), Scction 8-2: ' 7 -L w ' 2 -t - 2C12 1% I 2(/s12-i- Izc12).] 5 . \\-1i:it is tlie geon~ctricalinterl)rctation of tlie law Iz wl 5 1x1 IwI? ITscthis intrr1)rctation t o tlccide ivlicri tlie cquality Ix wl = 1x1 f Iwl holds.

IZ

1

+

+

+

6. \\-1i:tt is tlie geon1etrica.1 mclnnirig of thc idcritity givcn in Problem 5(c), Scctioii 8-2:>

7. Describe tlic riietliod of finding the point corresponding t o z -l- w, if you are givcn thc poiiits corrcspoiidirig t o z and x. 8. M-hat is thc gcoriictrical iiitcr1,rctation of 2 , -2, and z poiiits rcl)resciitccl 1.13' x and zo) 3

-

w (in terrns of thc

9. Slio\\- thnt if z # O, ~vhcrex is a coiiiplex riuniber, and if t is a n y real niiiiiljcr, t1ic.n tlic poirits 0, z, an(1 t z arc al1 in a line. S h o ~ vt h a t O, z, sncl zu lie ori :L liiic if iiritl only if eitlicr z = O, or w is a real multiljlc of z.

10. l'rovc (8-3.2).

8-4 Polar representation. T o iiitcrpret multiplication, \ve introduce a 11t.n- n-ay of 1-eprcsciitirig complcx iiumbcrs. 'i'his reprcsciitatioil is bascd oii thc polar coordinatc systcm* used iii analytic geometry, and for this rcasoii it is crtlled the polar reprcscntation of complcs iiiimbers. Lct O be tkic origin of s cartesirtn coordiilate system iii tlie plaiie. As iri the 1;ist scctioii, tlic points of the plaiie \vil1 bc lat~eledby complex iy be a noiizero complex iiumbcr. 'i'he line scgnumbcrs. I,et x = .r merit from O to the poiiit x has lciigth 171 = 2/F+TI,et . 8 dcilote thc :lnglct whicbh this lirie scgmeiit makcs n-itli tlic riglit lialf of the .r-axis (SCCZ:ig. 8-7). -1s is (bi~stomiiry, \ve will meusiirc aiiglcs couiitcrcloc~k\visebctu-ccii O :~iid 300 dcgrccs. 'i'hc compoiiciits .L. :iiid of x cnii be espresscd in tcrms of 12; alid 8 by the cquatioiis 2: X

+-

.r

=

{xi cos e,

y

=

;xl siii 8.

FIGURE 8-7

* 'i?ic dcfiriition of polar coordinates niakcs use of t,he geonictrical concept of "anglc" arid tlic trigononictric functions "sinc" and "cosine." Iii ordcr t o obtaiii rcsults sucli as 'i'licorcril 8-4.3, bcloiv, ~vithoutresortirig to tlie usc of "gconietric:illy cvident" f:icts, \\-e \\-ould liavc to dcfiiic :iriglcs, sirics, aiid cosines rnorc carcfully, and work h:irtl to show tliat thcsc, iiotions liave tlie 1,roljerties n-liiclli are o1)vious to our geoii~etricalintuitioii. Tlo~\-cver,no attcriipt will be iiiadc to carry out sucli a 1)rograni here. t Tlie syrnbol 8 is tlic siilall Grcck ltttcr tlicta. -Ingles in ri~atlien~aticsare oftcn rc1)rcscntctl by l o \ ~ e rcase Greek lettcrs, sucli as 8, 4 (phi), and x (chi).

THE COMPLEX NUMBERS

Hence, we can write x

=

1x1 (COS 6

+ i sin 6).

This expression is called the polar representation of x. The angle 6 is called the argument, or arnplitude, of t'he complex numbei x. This angle will be denoted by Arg x. I t should be remembered that the argument of the complex number O is not defined. Since we are measuring angles in degrees* between O and 360, the argument of every nonzero complex number satisfies

O

< Arg x

< 360.

It is evident that if x is a positive real number, then Arg x = 0, and if z is a negative real number, then Arg x = 180. Although the argument of a complex number x is always betureen O and 360, it should be noted that if x = 1x1 (COS8 i sin 8)) where 8 = Arg x, then we also have

+

x = 1x1 [COS(8 for n = 0, d=1, =t2,

+ n - 3 6 0 ) + isin (8 + n.360)]

. . . . Thus, for example, x = 3 (cos 410

+ i sin 410)

is a complexnumber with Arg x # 410. Infact, Arg x = 410 - 360 = 50. Let x and w be two nonzero complex numbers, with Arg x = 8, and Arg w = 4. Then x =

IxI(cos8+isin6),

w = Iwl(cos++isin+).

Hence, x w = 1x1 Iwl [(COS 6 cos 4

-

sin 8 sin 4)

+ i (sin 6 cos 4 + cos 8 sin +)l.

This expression can be simplified by using the sum formulas of trigonometry : cos (6 4) = cos 6 cos 4 - sin 6 sin 4, sin (8 4) = sin 6 cos 4 cos 8 sin 4. We obtaiii (8-14) x w = 1x1 IwI [COS (6 4) i sin (6 +)l.

+ +

+ + +

+

* I n most higher mathematics, angles are measured in radians rather than degrees. However, for the applications in this book, radians have no advantage over degrees. I n computational work, i t is more convenient to use degrees rather than radians, since most trigonometric tables list angles in degrees.

8-41

305

POLAR REPRESEXTATION

Comparing this formula n-ith the equation which expresses the trigonometric representation of z w,we obtain the rule for determining the argument of the product of two numbers. Y

THEOREM8-4.1. Let x and w be iionzero complex iiumbers. Theil Arg z w = Arg x

+ h r g w,

-+ Arg w < 360, and Arg z w = Arg x + Arg w if Are; x + Arg w 2 360.

z

if Arg x

-

360,

O

1

x

FIGURE 8-8

This theorem provides the desired geometrical interpretation of multiplication in C. The point x . w is the point on the half line which makes an angle of (Arg z Arg w) with the positive real axis, and which is a t a distance lzl Iwl from O (see Fig. 8-8). A particularly important case of (8-14) occurs when w = z. This i sin 28). We can easily genformula then becomes z2 = /zI2 (COS28 eralize this result by induction:

+

+

xn

= Iz jn

(cos n8

+ i sin no),

where 8

=

Arg x.

(8-15)

In particular, if 1x1 = 1, this identity gives Demoivre's theorem. TIIEOHEM 8-4.2.

(cos 8

+ i sin 8)" = cos n8 + i sin no.

The theorem of Demoivre has numerous applications. One which students often appreciate is its use as a device for deriving trigonomet,ric formulas for multiple angles.

n

EXAMPLE 1. JVe use Theorem 8 4 . 2 to determine cos 48 and sin 48. Taking = 4 in this formula, and using the binomial theorem, we obtain: cos 48

+ i sin 48

= =

=

+ i sin + 4 cos3 8 ( i sin 8) -t6 cos2 8 ( i sin + 4 cos 8 ( i sin + (i sin (cos4 8 - 6 cos2 8 sin2 8 + sin4 8)

(cos 8 cos4 8

4-i (4 cos3 8 sin 8 - 4 cos 8 sin3 8). Thus, cos 48 sin 48

= =

+

cos4 8 - 6 cos2 8 sin2 8 sin4 8, 4 cos3 8 sin 8 - 4 cos 8 sin3 8.

THE COMPLEX S U M B E K S

l+i

zo = $2(cos

+

15 i sin 15)

X

A more significant application of t,his theorem occurs in the proof of the follo~vingresul t. THEOHEM 8-4.3. Let w bc ariy nonzero complex number. Let n be a natural number. Then there are exttctly n distinct complex numbcrs z sat,isfying zn = w. If w = Iwl (cos O i sin O), wit,h O = Arg w, t,hen these numbers are given by z = 20, z = 21, . . . , z = Zn-l, where

+

Zj

=

7i.I

[tos (" 1'

"O)

+ i sin (O

+:

360)]

This theorem is illust,rated in E'ig. 8-9, with w = 1 The polar representation of 1 i is

+

1

(8-16)

+ i and n = 3.

+ i = 4(cos 45 + i sin 45).

I n order to prove Theorem 8-4.3, first not,c that by Sheorem 8-42)

(":

"O)

+ i sin (O

1' 360)])1

=

Iwl [COS(e

+ j 360) + i sin (O + j 360)]

=

Iwl (COSO

+ i s i n 8) = w.

Thus, for any nonnegative integer j, the formula (8-16) gives a solution o£ the equation zn = w. What ]ve must shom is that for j = 0,1, . . . , n - 1, the numbers given by (8-16) are al1 ditrerent, and that for any z sueh that zn = w, there is somc j = 0, 1, . . . , n - 1, such that z = zj. First observe that if O 5 j < n, then

8-41

POLAR REPIEESESTATIOS

Theref ore, Arg zj =

S

n

(Kote hotvcver that ArgzjZ

+ j 360

S

+ j 360

if j 2 n. Ver cxample, Arg zn = S/n.) Suppose that

Thcn by tvhat has just been observed, Arg zjl

=

0

+ j~n 360 # S + n 360 j2

=

Arg zj2.

Thercfore, zj, # zj,. This proves that the numbcrs 20, 21, . . . , ~ n - 1 are al1 different. Assume next that z is a complex number which satisfies zn = w. )Ve want to prove that z is one of the numbers 20, 21, . . . , ~ ~ - 1 that is, /zl = and S j 360 Arg z = n

vm

+

for some j = 0, 1, . . . , n - 1. I t follows from Theorem 8-2.4(e) (using mathematical induction) that zn = w implies lzln = iwl. Therefore, Izl = Let z = lzl (cos i sin +) be thc polar representation of z, with + = Arg z. Thcn by Theorem 8-4.2,

w.

++

Izln (cos n+

+ i sin n+) = zn = w = Iwl (cos S + i sin S).

Therefore, since jzln = (w!, this equality implics cos n+ = cos 0, and sin n+ = sin 8. Using the fact that ttvo anglcs mhich have the same sine and cosine differ by an integral multiplc of 360, we obt,ain n+ - S = j 360, where j E 2. Thereforc, S j 360

+= +

+

Sincc O 5 = Arg z < 360, (n+ - 8)/36O, it follows that

O 5 S

=

Xrg w


11(x). Prove t h a t if a ( x ) and b ( x ) are nonzero polynomials in k'[x], then a ( x ) b ( x ) / ( a ( x ) ,b ( x ) ) is a 1.c.m. of a ( x ) and b ( x ) . 12. Find a least common multiple for thc follo\ving pairs of polynomials. (a) x5 3x4 5x3 4x2 42 1, x5 2x4 3x3 2x2 2.2: (b) x4 - x 3x2 - 22 2, x3 x2 2x 2 (c) ~3 - 2 ~ +1 , x ~ +1

+ + + + + + + + + + + + + +

9-5 The unique factorization theorem for polynomials. The fundamental theorem of arithmctic, which was proved in Section 5-3, states that every natural number can be written uniquely as a product of prime numbers. Thc purpose of this section is to prove a similar theorem about the arithmetic in an integral domain F[z],wherc F is a field.

Our first task is to define the analogue in F[r] of a prime number.

DEICIKITION 9-5.1. IJet p(x) be a polynomial of positive degree in F[x]. Then p(x) is irreducible in F[x] if p(x) is not divisible by any polynomial in F[.L]except constant polynomials and constant multiples of p(x). Other~vise,p(x) is called reducible in F[x]. This defiriition requires some discussion. By (9-&la, b), any polynomial a(x) in F[x] is divisible by every nonzero constant polynomial and by every nonzero constant multiple of a(.r). Thus, the irreducible polynomials in F[z] are exactly those which have no divisors other than these "trivial" ones. This parallels closely the definition of a prime number (Definition 5-3.1). Suppose that a(x) is a polynomial of positive degree which is reducible in F[.x]. Then by Definition 9-5.1, a(x) = f(x) g(x), where f(x) is not a constant and f(x) is not a constant multiple of a(x). I t follo~vsthat Deg [ f(x)] < Deg [a(x)]. For if Deg [f(x)] = 1)eg [a(x)], then by Theorem 9-3.2(a), Deg [g(.z)] = O. Therefore, g ( x ) is a nonzero constarit ~vhich implies that f(x) is a constant multiple of a(.c). This contradictiori proves that Deg [ j(.z)] < Deg [a(x)]. Therefore, a reducible polynomial a(x) in F[x] has a factor f(x) such that O < Deg [f(.e)] < Dcg [a(x)]. Conversely, it is easy to show that if a(x) E F[x] has a factor f(x) E F[x] which satisfies O < Deg [f(.c)] < Deg [a(z)], then a(x) is reducible in F[x]. Since Definition 9-5.1 applies only to polynomials of positive degree, thc constant polynomials are neither reducible nor irreducible. These polynomials play a special role in F[x] similar to that of the integers 1 aiid - 1 in the arithmctic of %. I t is very important to observe that irreducibility is defined rclative to a particular field F. That is, a polynomial which is irreducible in F[.r]may be reducible in K[x] for some field K containing F.

E~XAMPLE1. The polynomial x2 - 3 is irreduciblc in Q[x]. Suppose thnt x2 - 3 is reducible. Then

x2 - 3

=

(ax

+ b)(cx + d)

=

acx2 -/- (ad

+ bc)x + bd, +

where a, b, c, and d are rational numbers. This iinplies that ac = 1, ati bc = 0, and bd = -3. Thus, c = ]/a, d = -3/b, and substituting in ad bc = O, \\-e obtain

+

Thercfore, -3a2

+ b2

=

O and ( b / ~ )=~ 3. However,

d3 is iiot a rational

334

THE T I ~ E O R Y OF ALGEBKAIC EQUATIOSS

[CIIAP.

number. Thus, x2 - 3 is irreducible in Q[x]. On the othcr hand, x2 - 3 (x - d3)(x d3),so that x2 - 3 is reducible in R[x].

+

9 =

+ +

EXAMPLE 2. Any polynomial of dcgree one, ax b, a # O, with coefficients in a field F, is irreducible in l+'[x].In fact ax b = f(x) g(x) with O < Dcg [f(x)] < 1 is obviously impossible. 3lorcover, if K is any field containing F as a subring, then ax b is also irrcducible in K[x].

+

The principal result of this section is that every polynomial of positive degree in F[x] can be expressed as a product of an element in F and one or more monic irreduciblc polynomials in F[x]. fi,foreover, this factorization is unique, except possibly for the order of the factors. This is the unique factorization theorem in F[x], which is the analogue of the fundamental theorem of arithmetic. The following preliminary results are needed for the proof of this important theorcm. (9-5.2). If p(x) is irreduciblc in F[x] and f (x) E F[x], then either p(x) 1j (x) in F[x], or p(x) and f(x) are rclatively prime. Proof. Let d(x) = (p(a), f(x)). Then d(x)lp(x), by Definition 9-1.2. Since p(x) is irreducible, i t follows that either d(x) is a constant or d ( 4 ) is a nonzero constant multiple of p(x). If d(x) is a constant, then d(x) = 1 (because d(x) is monic), so that p(x) and f(x) are relatively prime. If d(x) is a nonzero constant multiple of p(x), then p(x) = k d(x) for some nonzero 1c E E. Since d(x)l j(z), it follows that p(x) 1 j(x), by (9-4.la). ( - 5 . ) . If p(x) is irreducible in F[x], and p(x) divides the product a,(x) of polynomials in F[x], then p(x) divides a t a l (z) a2(x) least one of the polynomials ai(x). The proof is the same as the proof of (5-3.2). THEOREM9-5.4. Unique factorization theorem i n F[x]. Every polynomial a(x) E F[x] of positive degree can be written as a product of a nonzero element of F and monic irreducible polynomials in F[x]. Except for the order of the factors, the expression of a(x) in this form is unique. Proof. Roth parts of this theorem are proved by course of values induction on n = Ileg [a(x)]. The proof that a(x) can be factored into a product of a nonzero element of 17 and monic irreducible polynomials in F[x] is similar to the corresponding part of the fundamental theorem of arithmetic. Suppose that Deg [a(x)] = l. Then a(x) = bz c, where b E F , c E F, and b # O. By Example 2, x (b-' . c) is a monic irreducible

+

+

9-51

335

U S I Q U E FACTORIZATION THEOREM FOR POLYXOMIALS

polynomial in F [ x ] ,and a(.)

=

b [x

+ (b-l

c)].

Suppose that a ( x ) has degree n > 1: and assume that every polynomial of degree m, with 1 5 m < n, can be expressed in the form

where c f O is in F and the pi(x) are monic irreducible polynomials in F [ x ] . If

is irreducible, then

+

+

is the desired expression for a ( x ) , since xn

(añla,-l)xn-l If a ( x ) is not irreducible, then a ( x ) = b ( x ) c ( x ) , where b ( x ) and c ( x ) are polynomials in F [ x ] satisfying 1 5 Deg [ b ( x ) ]< Deg [ a ( x ) ]and 1 5 Deg [c(x)] < Deg [ a ( x ) ] . Therefore, by the induction hypot,hesis

+ ( a ñ l a o )is monic and irreducible, by (9-4.1).

b(x)

=

ci p i ( x ) P ~ ( x' )

c(x)

=

c2 q1(x) q2(x) '

'

pr(x)

and ' ' ' '

qs(x):

where cl and c2 are nonzero elements of F , and the pi(x) and q j ( x )are monic irreducible polynomials. Thus, a(.)

=

b( x ) c ( x )

=. (cl ' c2) ' p l ( x ) ' p 2 ( x ) '

' ' ' '

p&)

q1(x) ' q2(2)

' ' ' '

qs(x),

which is the required form. To prove that the factorization of a polynomial a ( x ) is unique, we can use induction either on the degree of a ( x ) , or on the number of monic irreducible polynomials which occur in some decomposition of a ( x ) into a product of irreducible polynomials. This last method corresponds to the proof of the uniqueness given in Theorem 5-3.3. However, for the proof of Theorem 9-5.4, it is slightly easier to induce on the degree of a ( x ) . Suppose first that a ( x ) has degree one and that

Thcn a l = a2 f 0, and albl = a2b2. Multiplying the last, equation by a;' = a;', we obtain bl = 62. Therefore, any t\vo factorizat,ions of

336

THE THEORY OF ALGEBRAIC

EQUATIONS

[CHAP.

9

a ( x ) are identical. Now, suppose that a ( x ) has degree n > 1, and assume that the unique fact,orization theorem is true for al1 polynomials of degree less than n. Let

of a ( x ) into products of an element of F and one be any two fa~torizat~ions or more monic irreducible polynomials. Since the P ~ ( xand ) q j ( x ) are monic polynomials, the leading coefficient of a ( x ) is both cl and c2. That is, c1 = cg. Thus,

so that p l ( x ) divides q l ( x ) q 2 ( x ). . . qs(x). Since p l ( x ) is irreducible, it follows from (9-5.3) that p l ( x ) divides one of the polynomials q j ( x ) . However, q j ( x ) is irreducible, and p l ( x ) is not a constant, so that p l ( x ) must be a constant multiple of q j ( x ) . Since p l ( x ) and q j ( x ) are both monic polynomials, it follows that pl ( x ) = q j ( x ) . If r = 1, then a ( x ) is irreducible, so that s = j = 1. In this case, the factorizations a ( x ) = c l p l ( x ) = c2q1(x)are identical. Otherwise, p l ( x ) can be cancelled from the above expression to obtain

+

Since n = Deg [ p l ( x ) ] Deg [ p z ( x ) . . . pT(x)] and Deg [ p l ( x ) ]2 1, it follows that Deg [p2(x) p,(x)l < n. By the induction hypothesis, the polynomials p 2 ( x ) , . . . , pT(x) are just the polynomials ql ( x ), q2 ( x ), . . . , qj- 1 ( x ), qj+ 1 ( a ) , . . . , qs ( x ) in some order. Therefore, the two factorizations of a ( x ) are the same, except possibly for the order of the factors. The process of expressing a polynomial as a product of an element of F and a product of monic polynomials which are irreducible in F[x] is the familiar "complete factorization" which is studied in elementary algebra. I t would be convenient to have a systematic method which would give a complete factorization of any polynomial a ( x ) in any integral domain F [ x ] . Simply to have a way of deciding whether or not a given polynomial in F [ x ]is irreducible in F [ x ]would be helpful. Unfortunately, such methods exist only for particular fields F. For example, if the field F is a finite field of the form 2, (where p is a prime), then there are only finitely many polynomials of a given degree. By examining al1 products of two polynomials of degree less than a ( x ) , it is possible to decide whether or not a ( x ) is irreducible.

9-51

C N I Q U E FACTOHIZ.4TION T H E O R E M FOR P O L Y S O M I A L S

337

EXAMPLE 3. I3y a method which is similar t o the "sieve of Eratosthenes" (see Section 5-4), the monic irreducible polynomials of any degree in thc rings Z,[x] can be determined. Actually, the method is practica1 only for small p, and for polynomials of low degree. )Ve will consider the case p = 3. The following list includes evcry monic polynomial in Z3[x] of degree lcss than or equal t o two : x x -1 1 x +2 x2 x x

+

+1 +2

x2 x x2+x 1 x2+x + 2 x2 22 x2 2x 1 x2 22 2

+

+ + + + +

= X'X

= (x+ l).(x+

2)

=

x . ( x + 1)

=

(x+2).(x+2)

=

x (x

=

(x

+ 2)

+ 1) (x + 1)

I t follo\vs t h a t the monic, irreducible polynomials of degrce one and two in Z3[x] are

1. Determine which of the following polynomials are irreducible in Q[x]. (a) x3 - 2 (b) x3 1 (d) x4 - x2 - 1 (e) x2 2x2 22 1 (e) x4 zx 4 (f) X~ zx3 I

+

+

+

+

+ +

+

2. Which of thc polynomials listed in Problcm 1 arc irreducible in R[x]?

+ +

3. Let j(x) = ax2 bx c be a polynomial with rational coefficients, where a # O. (a) Prove t h a t j(x) is irreducible in Q[x] if and only if b2 - 4ac is not the square of a rational number. (b) Prove t h a t f (x) is irreducible in Rlx] if and only if b2 - 4ac < O. (c) Prove t h a t f(x) is reducible in C[x] for al1 values of a, b, and c . 4. Express the polynomials listed in I'roblem 1 as a product of monic irreducible polynomials in Q[x], R[x], and C[x].

5. TJsc the method of Example 3 to find al1 irreducible monic polynomials of the third degree in Z3[x]. 6. Find the complete factorization of al1 1)olynomials of degree four in Z ~ [ X ] .

7. I'rove t h a t if p(x) is irreducible in F[x], and c # O in F, then cp(x) is irreducible in F[x].

338

THE THEORY OF ALGEBRAIC EQUATIONS

[CHAP.

9

8. Let a ( x ) = cp1 ( ~ ) ~ i p 2 ( x ).". 2. p,(x)"r be a polynomial in F[x],where the pi(x) are monic polynomials which are irreducible in F [ x ] , pi(x) # p j ( x ) for i # j, and the exponents ni are natural numbers. Prove that b(x) E F[x]divides a ( x ) if and only if b(x) = dpi(x)"lp2(~)"2. . . p,(x)"r, where O mi 5 ni for i = 1 ) 2) . . . )r .


3. For large n it is customary to write a'"'(x) for the nth derivative of a ( x ) , and we will follow this practice if n > 2.

THEOREM 9-6.2. Let b(x) and c(x) be polynomials in F[x]. ( a ) If a ( x ) = b(x) c ( x ) , then a' ( x ) = b' (z) c' ( x ). (b) If a ( x ) = b(x) c ( x ) , then a f ( x ) = b(x) c l ( x ) bl(x) c ( z ) . (c) If a ( x ) = b(x)", where n 2 1, then a f ( x ) = n b(x)"-' bf(+).

+

Proof. First consider ( a ) . Let

+

+

340

THE THEOKY OF -4LGEBRAIC EQUATIOSS

[CHAP.

9

(As we obscrvcd in Section 9-2, there is no loss of gcnerality in assuming that b(.x) and c ( x ) are written with the same number of terms.) Then

a ( r ) = (6, f cn).rn

+ . + (bl + c1)x + + col. + (bn-1 +

c,-1)~"-'

(O0

Hence, by Definition '3-6.1,

af(.c) = n (O,

+1

=

+

-

1) (bn-1

+ c n - l ) - ~ ~+- ~

(61 e l ) [ ( n bn)xn-l ( ( n - 1) b,-l)xn-2 [(n-cn)xn-l ( ( n - 1) . c , - ~ ) x " - ~ bt(a) c r ( x ) .

+ =

+ cn)xn-' + ( n

+

+

+

+

+ 1 bi] + . + 1 .ci] .

This provcs (a). We prove (b) first in t.hc case that b ( x ) = eam a,nd c ( x ) = f.cn where e, f E F , m 1 O and n 2_ O. Then a ( x ) = b ( x ) c ( x ) = (ef)xm+". By definition, a r ( x ) = [ ( m n) e j ] ~ ~ + ~ - ' , and

+

br(x) c ( x )

+ b(.x)

+ (exm)

cr(.r) = [ ( m e).rm-'1 ( f i n ) = [ ( m n) ef ].x'"+"-',

+

[ ( n f)xn-'1

so that a' ( x ) = b r ( x ) c ( a ) --t b ( x ) c' ( x ). Yext observe that if the identity (b) is correct for a l ( x ) = b l ( a ) c ( x ) and a2(:c) = b 2 ( x ) ~ ( x )then , it is truc for a ( x ) = b ( x ) c ( x ) , where b ( x ) = b l ( x ) b 2 ( x ) . Indeed, a ( x ) = [bl(n.) b 2 ( x ) ] ~ ( x= ) bl(.x) c(.c) b2(.r) C ( Z ) = a l ( x ) a2(x), so that

+

+

+

+

Similarly, if thc identity (b) holds for b ( x ) c l ( x ) and b ( x ) c 2 ( x ) , then it holds for b ( x ) [cl( x ) c 2 ( x ) ] . The proof of the identity ( b ) can now be completcd by induction. I t is convenient to use two steps. First we prove by induction on m thnt (b) is valid when

+

9- 61

DERIVATIVES

The general case

is then ohtained by induction on n. The reader can renew his ski11 in the use of mathematical induction by filling in the details of this argument. I n order to prove (e), \ve usc induction on n. If n = 1 , the statement is that if a(x) = b(x), then at(a) = 1 b(.r)O bf(x). Since b(.c)O is 1 (the usual convention for the exponent zero), this identity is correct. Assume that n > 1, and that the derivatiie of b ( ~ ) ~ -is' (n - 1) O ( Z ) ~ - ~bt(z). Write b(z)"-' = c(.c). Then if a(.r) = b ( . ~ = ) ~ b(n) . c(.x), it follo117s from (b) and the induction hypothesis that

+

a' (x) = b(s) ct(.c) bf( . E ) c (x) = b(.r) (n - 1 ) b ( ~ ) " - ~bf(x) = =

(n - 1) . b ( ~ ) ~ -. bt(.r) ' n b(.r)"-' bt(x).

+ b'(s)

b(.r)"-l

+ b ( ~ ) ~ - bt(x) l

Therefore, the induct,ion is complet,e, and Theorcm 9-6.2 is completcly proved. Thc reader should examine the proof of (b) very carefully, siilce the method is common in mathematical arguments. Our proof consists of three steps. I;irst, it is shown that the identity is true for the simplest polynomials, that is, the monomials. S e x t we prove that the set of polynomials satisfying the identity is closcd undcr addition. Finally, sincc every polynomial is a sum of monomials. it follows that the identity is true for al1 polynomials. This last stcp is of course a form of mathematical induction. I t is possiblc to provc (b) by straightforward calculation, but the notation becomes un~vieldy. EXARIPLE 2. Let a ( x ) = (x - c)". Thcn a l ( x ) = n . ( x - c)"-l, a U ( x ) = n ( n - 1) ( x - c ) " - ~ , a ( n - l ) ( x ) = n . ( n - 1) a(")(x) = n ! . l .

2 (x

-

c),

The derivative is useful for studying the multiple factors of a polynomial. I;or this application, \ve need thc following formula, ~vhichis a combination of Thcorem 9-0.2(1)) and (c).

342

THE THEORY OF ALGEBHAIC EQUATIONS

[CHAP.

9

>

THEOREM 9-6.3. Let a(x) = cpl(x)"1 . . . pk(x)"k, k 1, where c E F, pl(x), . . . , pk(x) are polynomials in F[x] which are not constant, and n l , . . . , nk are natural numbers. Then

This result is easily obtained from Theorem 9-6.2 by induction on lc. We leave thc details for the reader to supply.

>

THEOREM 9-6.4. Let a(x) = cpl(x)"1 . . . pk(x)"k, k 1, where ( 4 C E F, (b) pl(x), . . . , pk(x) are distinct monic, irreducible polynomials in FbI, (c) n l 1,. . . , n k 1,and (d) F has characteristic zero. Then the monic grcatest common divisor of a(x) and af(x) is

>

>

Prooj. I t is immediate that p1(x)"l-' . . . pk(x)"k-' divides a(x) = cpl(s)"l . . . pk(x)"*. We next observe that pl(x)nl-l . . . pk(x)"k-l divides a(x)/pj(x) for j = 1, . . . , k. Therefore,

divides

where we have used the formula for a' (x) givcn by Theorem 9-6.3. Thus pl(x)"1-' . . . pk(x)nk-l is a common divisor of a(x) and al(s). To com) plete the proof, we must show that every common divisor of a ( ~ and af(x) divides pl(x)nl-l . . . pk(x)"k-l. Let j(x) be a common divisor of a(x) and af(x). Thcn since j(x)la(x), it follows that

where ml _< n l , . . . ,mk 5 nk. I t is now sufficient to show that m1 # n l , . . . , mk # nk, for in this case ml 2 n l - 1, . . . , mk nk - 1, so that Assume that m1 = nl. Then f(x) divides pl(x)"l-' . . . pk(x)"k-l. f (x))at(x) implies that p l (x)"1laf (x). Moreover,