Paperback(Second Edition)
-
PICK UP IN STORECheck Availability at Nearby Stores
Available within 2 business hours
Related collections and offers
Overview
The opening chapters offer sound explanations of the basics of elementary number theory and develop the fundamental properties of integers and congruences. Subsequent chapters present proofs of Fermat's and Wilson's theorems, introduce number theoretic functions, and explore the quadratic reciprocity theorem. Three independent sections follow, with examinations of the representation of numbers, diophantine equations, and primes. The text concludes with 260 additional problems, three helpful appendixes, and answers to selected exercises and problems.
Product Details
| ISBN-13: | 9780486469317 |
|---|---|
| Publisher: | Dover Publications |
| Publication date: | 09/25/2008 |
| Series: | Dover Books on Mathematics |
| Edition description: | Second Edition |
| Pages: | 272 |
| Sales rank: | 480,550 |
| Product dimensions: | 5.30(w) x 8.40(h) x 0.60(d) |
About the Author
Underwood Dudley: Cranking Out Classics
Any editor involved with publishing in mathematics for any length of time is familiar with the phenomena — the receipt, usually via snail mail, of generally handwritten, and generally interminable, really, really interminable, theses on some bizarre and unprovable point — theses hoping, trying against all hope, demanding in fact, to prove the unprovable, to rewrite some fundamental part of mathematics, often in my experience to demonstrate for one final time that, for example, Einstein didn't know what he was talking about — in short, the work of a mathematical crank!
Underwood Dudley (Woody to everyone in the math world), Professor Emeritus, Depauw University, provided an inestimable service to all math editors in the universe by demonstrating that they are not alone in their experience. His unique and wonderful book Mathematical Cranks (The Mathematics Association of America, 1992) is a readable feast, especially for those who have been on the receiving end of mathematical crank mail. We're all in Woody's debt for having assembled this collection of failed squared circles, angle trisections, and much, much more.
However, chronicling the cranks — as enjoyable as it may have been to the rest of us — is hardly a career, Woody has written many other books as well. And any reader who wants to check out a totally uncranky, reader- and student-friendly, time-tested basic text in Elementary Number Theory could hardly do better than to look at the Dover edition of Woody's book by that name, which started its career with Freeman in 1969 and which Dover was pleased to reprint in 2008.
Read an Excerpt
Elementary Number Theory
By Underwood Dudley
Dover Publications, Inc.
Copyright © 1978 Underwood DudleyAll rights reserved.
ISBN: 978-0-486-46931-7
CHAPTER 1
Section 1
Integers
The subject matter of number theory is numbers, and a large part of number theory is devoted to studying the properties of the integers — that is, the numbers ... , -2, -1, 0, 1, 2, ... . Usually the integers are used merely to convey information (3 apples, $32, 17 x2 + 9), with no consideration of their properties. When counting apples, dollars, or x2'S, it is immaterial how many divisors 3 has, whether 32 is prime or not, or that 17 can be written as the sum of the squares of two integers. But the integers are so basic a part of mathematics that they have been thought worthy of study for their own sake. The same situation arises elsewhere: the number theorist is comparable to the linguist, who studies words and their properties, independent of their meaning.
There are many replies to the question, "Why study numbers?" Here are some that have been given:
Because teacher says you must.
Because you won't graduate if you don't.
Because you have to take something.
Because it gives your mind valuable training in thinking logically.
Because numbers might be interesting.
Because numbers are a fundamental part of man's mental universe and hence worth looking into.
Because some of the most powerful human minds that ever existed were concerned with numbers, and what powerful minds study is worth studying.
Because you want to know all about numbers: what makes them work, and what they do.
Because mathematics contains some beautiful things, and someone told you that number theory contained some of the most beautiful- and few of the most ugly-things.
Because it is fun.
Let us begin.
In this section, and until further notice, lower case italic letters will invariably denote integers. We will take as known and use freely the usual properties of addition, subtraction, multiplication, division, and order for the integers. We also use in this section an important property of the integers-a property that you may not be consciously aware of because it is not stated explicitly as the others. It is the least-integer principle: a nonempty set of integers that is bounded below contains a smallest element. There is the corresponding greatest-integer principle: a nonempty set of integers that is bounded above contains a largest element.
We will say that adividesb (written a|b) if and only if there is an integer d such that ad = b. For example, 216, 12160, 17117, -5150, and 81 -24. If a does not divide b, we will write a [??] b. For example, 4 [??] 2 and 3 [??] 4.
Exercise 1. Which integers divide zero?
Exercise 2. Show that if a|b and b|c, then a|c.
As a sample of the sort of properties that division has, we prove
Lemma 1. If d|a and d|b, then d|(a + b).
Proof. From the definition, we know that there are integers q and r such that
dq = a and dr = b.
Thus
a + b = d(q + r),
so from the definition again, d|(a + b).
In the same way, we can prove
Lemma 2. If d|a1, d|a2, ..., d|an then d|(c1a1 + c2a2 + ... + cnan for any integers c1, c2, ..., cn.
Proof. From the definition, there are integers q1, q2, ..., qn such that a1 = dq1, a2 = dq2 ..., an = dqn. Thus
(c1a1 + c2a2 + ... + cnan = d(c1q1 + c2q2 + ... + cnqn),
and from the definition again, d|(c1a1 + c2q2 + ... + cnan.
Exercise 3. Prove that if d|a then d|ca for any integer c.
As an application of Lemma 2, let us see if it is possible to have 100 coins, made up of c pennies, d dimes, and q quarters, be worth exactly $5.00. If it is possible, then
c + d + q = 100
and
c + 10d + 25q = 500.
Subtract the first equation from the second and we get 9d + 24q = 400. Since 319 and 3124, Lemma 2 says that 319d + 24q. That is, 31400. But that is impossible, so having exactly $5.00 is impossible with 100 pennies, dimes, and quarters. There are, however, five different ways of getting $4.99, and later we will develop a method for finding them.
Fractions are not as natural as integers, and there seems to be a human tendency to avoid them. For example, we divide a gallon into quarts, a quart into pints, and a pint into ounces so that we can always measure with integer multiples of some unit. Finding a unit common to different measures was a problem which would arise naturally in commerce—if 15 Athenian drachmas are worth 18 drachmas from Miletus, how many Athenian drachmas are equivalent to 60 Miletian drachmas? That is one reason why the Euclidean Algorithm for finding greatest common divisors was part of Euclid's Elements, written around 300 BC. The rest of this section will be devoted to the greatest common divisor and its properties, which we will use constantly later. We say that d is the greatest common divisor of a and b (written d = (a, b)) if and only if
(i) d|a and d|b, and
(ii) if c|a and c|b, then c ≤ d.
Condition (i) says that d is a common divisor of a and b, and (ii) says that it is the greatest such divisor. For example, (2, 6) = 2 and (3, 4) = 1. Note that if a and b are not both zero, then the set of common divisors of a and b is a set of integers that is bounded above by the largest of a, b, -a, and -b. Hence, from the greatest-integer principle for the integers, the set has a largest element, so the greatest common divisor of a and b exists and is unique. Note that (0, 0) is not defined, and that if (a, b) is defined, then it is positive. In fact, (a, b) ≥ 1 because 1|a and 1|b for all a and b.
Exercise 4. What are (4, 14), (5, 15), and (6, 16)?
Exercise 5. What is (n, 1), where n is any positive integer? What is (n, 0)?
Exercise 6. If d is a positive integer, what is (d, nd)?
As an exercise in applying the definition of greatest common divisor, we will prove the following theorem, which we will use often later:
Theorem 1. If (a, b) = d, then (a|d, b|d) = 1.
Proof. Suppose that c = (a|d, b|d). We want to show that c = 1. We will do this by showing that c ≤ 1 and c ≥ 1. The latter inequality follows from the fact that c is the greatest common divisor of two integers, and as we have noted, every greatest common divisor is greater than or equal to 1. To show that c ≤, we use the facts that c|(a/d) and c|(b/d). We then know that there are integers q and r such that cq = a/d and cr = b/d. That is,
(cd)q = a and (cd)r = b.
These equations show that cd is a common divisor of a and b. It is thus no greater than the greatest common divisor of a and b, and this is d.
Thus cd ≤ d. Since d is positive, this gives c 1. Hence c = 1, as was to be proved.
If (a, b) = 1, then we will say that a and b are relatively prime, for a reason that will become clear in the section on unique factorization.
When a and b are small, it is often possible to see what (a, b) is by inspection. When a and b are large, this is no longer possible. The Euclidean Algorithm makes it easy, but first we need.
Theorem 2. The Division Algorithm. Given positive integers a and b, b ≠ 0, there exist unique integers q and r, with 0 ≤ r< b such that
a = bq + r.
Proof. Consider the set of integers {a, a - b, a - 2b, a - 3b, ...}. It contains a subset of nonnegative integers which is nonempty (because a is positive) and bounded below (by 0); from the least-integer principle, it contains a smallest element. Let it be a - qb. This number is not negative and it is less than b, because if it were greater than b it would not be the smallest nonnegative element in the set: a - (q + 1 )b would be.
Let r = a - bq: this construction gives us q and r, and it remains to show that they are unique. Suppose that we have found q, r and q1, r1 such that
a = bq + r = bq1 + r1
with 0 ≤ r< b and 0 ≤ r1< b. Subtracting, we have
(1) 0 = b(q - q1 + (r - r1).
Since b divides the left-hand side of this equation and the first term on the right-hand side, it divides the other term:
b|(r - r1).
But since 0 ≤ r< b and 0 ≤ r1< b, we have
-b < r - r1< b.
The only multiple of b between -b and b is zero. Hence r - r1 = 0, and it follows from (1) that q - q1 = 0 too. Hence the numbers q and r in the theorem are unique.
Although the theorem was stated only for positive integers a and b, because it is most often applied for positive integers, nowhere in the proof did we need a to be positive. Moreover, if b is negative, the theorem is true if 0 ≤ r < b is replaced with 0 ≤ r< -b; you are invited to reread the proof and verify that this is so.
* Exercise 7. What are q and r if a = 75 and b = 24? If a = 75 and b = 25?
Theorem 2, combined with the next lemma, will give the Euclidean Algorithm.
Lemma 3. If a = bq + r, then (a, b) = (b, r).
Proof. Let d = (a, b). We know that since d|a and d|b, it follows from a = bq + r that d|r. Thus d is a common divisor of b and r. Suppose that c is any common divisor of b and r. We know that c|b and c|r, and it follows from a = bq + r that c|a. Thus c is a common divisor of a and b, and hence c ≤ d. Both parts of the definition of greatest common divisor are satisfied, and we have d = (b, r).
Exercise 8. Verify that the lemma is true when a = 16, b = 6, and q = 2.
Let us apply Lemma 3 to find the greatest common divisor of 69 and 21. From 69 = 3 x 21 + 7 we get (69, 21) = (21, 7), and from 21 = 3 x 7 we get (21, 7) = 7. The ancient Greeks would have found the greatest common measure of these two lengths
[ILLUSTRATION OMITTED]
By laying the shorter against the longer as many times as possible
[ILLUSTRATION OMITTED]
And then breaking off the remainder and applying it
[ILLUSTRATION OMITTED]
until, as in this case, a common measure is found. The formal statement of the process just carried out for a special case is
Theorem 3. The Euclidean Algorithm. If a and b are positive integers, b ≠ 0, and
[MATHEMATICAL EXPRESSION OMITTED]
then for k large enough, say k = t, we have
rt-1 = rtqt+1,
and (a, b) = rt.
Proof. The sequence of nonnegative integers
b > r > r1 > r2 > ...
must come to an end. Eventually, one of the remainders will be zero. Suppose that it is rt+1. Then rt-1 = rtqt+1. From Lemma 3 applied over and over,
(a,b) = (b, r) = (r, r1) = (r1, r2) = ... = (rt-1, rt) = rt.
If either a or b is negative, we can use the fact that (a, b) = (-a, b) = (a, -b) = (-a, -b).
* Exercise 9. Calculate (343, 280) and (578, 442).
The computation of (343, 280) = 7:
(2) 343 = 1 x 280 + 63
(3) 280 = 4 x 63 + 28
(4) 63 = 2 x 28 + 7
28 = 4 x 7
can be worked backward. From (4), 7 = 63 - 2-28. Substitute for 28 from (3): 7 = 63 - 2(280 - 4 -63) = 9-63 - 2-280. Substitute for 63 from (2): 7 = 9(343 - 280) - 2 -280 = 9 -343 - 11-280. We have found x and y such that 343x + 280y = 7, namely x = 9 and y = -11. What was done in this example can be done in general:
Theorem 4. If (a, b) = d, then there are integers x and y such that ax + by = d.
Proof. Work the Euclidean Algorithm backward. The details are omitted.
We will find a better method for solving ax + by = (a, b) later, so the computational process in Theorem 4 is not important. What is important is the existence of x and y and not their values. To illustrate the usefulness of Theorem 4, here are three corollaries.
Corollary 1. If d|ab and (d, a) = 1, then d|b.
Proof. Since d and a are relatively prime, we know from Theorem 4 that there are integers x and y such that
dx + ay = 1.
Multiplying this by b, we have
d(bx) + (ab)y = b.
The term d(bx) can of course be divided by d, and so can (ab)y, since d divides ab. Thus d divides the left-hand side of the last equation and hence divides the right-hand side too, which is what we wanted to prove. Note that if d and a are not relatively prime in Corollary 1, then the conclusion is false. For example, 6|8 x 9, but 6 [??] 8 and 6 [??] 9.
Corollary 2. Let (a, b) = d, and suppose that c\a and c\b. Then c\d.
Proof. We know that there are integers x and y such that
ax + by = d.
Since c divides each term on the left-hand side of this equation, c divides the right-hand side too.
This corollary thus says that every common divisor of a pair of integers is a divisor of their greatest common divisor.
Corollary 3. If a|m, b|m, and (a, b) = 1, then ab|m.
Proof. There is an integer q such that m = bq, and since a|m we have a|bq. But (a, b) = 1, so Corollary 1 says that a|q. Hence there is an integer r such that q = ar, and thus m = bq = bar. That shows that ab|m.
Problems*
* 1. Calculate (314, 159) and (4144, 7696).
2. Calculate (3141, 1592) and (10001, 100083).
* 3. Find x and y such that 314x + 159y = 1.
4. Find x and y such that 4144x + 7696y = 592.
5. If N = abc + 1, prove that (N, a) = (N, b) = (N, c) = 1.
6. Find two different solutions of 299x + 247y = 13.
7. Prove that if a|b and b|a, then a = b or a = -b.
8. Prove that if a|b and a > 0, then (a, b) = a.
9. Prove that ((a, b), b) = (a, b).
10. (a) Prove that (n, n + 1) = 1 for all n > 0. (b) If n > 0, what can (n, n + 2) be?
11. (a) Prove that (k, n + k) = 1 if and only if (k, n) = 1. * (b) Is it true that (k, n + k) = d if and only if (k, n) = d?
12. Prove: If a|b and c|d, then ac|bd.
13. Prove: If d|a and d|b, then d2|ab.
14. Prove: If c|ab and (c, a) = d, then c|db.
15. (a) If x2 + ax + b = 0 has an integer root, show that it divides b. (b) If x2 + ax + b = 0 has a rational root, show that it is in fact an integer.
(Continues...)
Excerpted from Elementary Number Theory by Underwood Dudley. Copyright © 1978 Underwood Dudley. Excerpted by permission of Dover Publications, Inc..
All rights reserved. No part of this excerpt may be reproduced or reprinted without permission in writing from the publisher.
Excerpts are provided by Dial-A-Book Inc. solely for the personal use of visitors to this web site.
Table of Contents
PrefaceIntegers
Unique Factorization
Linear Diophantine Equations
Congruences
Linear Congruences
Fermat's and Wilson's Theorems
The Divisors of an Integer
Perfect Numbers
Euler's Theorem and Function
Primitive Roots
Quadratic Congruences
Quadratic Reciprocity
Numbers of Other Bases
Duodecimals
Decimals
Pythagorean Triangles
Infinite Descent and Fermat's Conjecture
Sums of Two Squares
Sums of Four Squares
x(superscript 2) - Ny(superscript 2) = 1
Bounds for pi(x)
Formulas for Primes
Additional problems
Proof by Induction
Computer Problems
Factor Table for Integers Less Than 10,000
References
Answers to Selected Exercises
Answers to Selected Odd-Numbered Problems
Comments on Selected Odd-Numbered Problems
Index