Elementary Number Theory Second Edition
V nderwood Dudley DePauw University
rn
w. H. FREEMAN
AND COMPANY
New York ...
940 downloads
2512 Views
7MB Size
Report
This content was uploaded by our users and we assume good faith they have the permission to share this book. If you own the copyright to this book and it is wrongfully on our website, we offer a simple DMCA procedure to remove your content from our site. Start by pressing the button below!
Report copyright / DMCA form
Elementary Number Theory Second Edition
V nderwood Dudley DePauw University
rn
w. H. FREEMAN
AND COMPANY
New York
Contents
Preface
vii
Section 1
Integers
1
Section 2
Unique Factorization
Section
3
Linear Diophantine Equations
Section 4
Congruences
Section 5
Linear Congruences
Section
6
10 20
27 34
Fermat's and Wilson's Theorems
42
50
Section 7
The Divisors of an Integer
Section 8
Perfect Numbers
Section 9
Euler's Theorem and Function
Section 10
Primitive Roots
Section 11
Quadratic Congruences
57.
73
v
83
63
vi
Contents 94
Section 12
Quadratic Reciprocity
Section 13
Numbers in O ther Bases
Section 14
Duodecimals
Section 15
Decimals
Section 16
Pythagorean Triangles
Section 17
Infinite Descent and Fermat's Conjecture
Section 18
Sums of Two Squares
Section 19
Sums of Four Squares
Section 20
Xl
Section 21
Bounds for mx)
Section 22
Formulas for Primes
172
Section 23
Additional Problems
182
Appendix A
Proof by Induction
Appendix B
Computer Problems
Appendix C
Factor Table for Integers Less Than 10,000

Ny::!
106
1 14
119
=
1
References
127 135
141 149
155 163
205 210 217
225
Answers to Selected Exercises
227
Answers to Selected OddNumbered Problems
231
Comments on Selected OddNumbered Problems Index
247
238
Preface
Mathematics exists mainly to give us power and control over the phys ical world, but it has always been so fascinating that it was studied for its own sake. Number theory is that sort of mathematics: it is of no use in building bridges, and civilization would carry on much as usual if all of its theorems were to disappear, nevertheless it has been studied and valued since the time of Pythagoras. That greatest of mathe maticians Carl Friedrich Gauss called it "The Queen of Mathematics," and "Everybody's Mathematics" is what the contemporary mathe matician Ivan Niven calls it. The reason for its appeal is that the subject matternumbersis part of everyone' s experience, and the things that can be found out about them are interesting, curious, or surprising, and the ways they are found can be delightful: clean lines of logic, with sustained tension and satisfying resolutions. A course in number theory can do several things for a student. It can acquaint him or her with ideas no student of mathematics should be ignorant of. More important,it is an example of the mathematical style of thinkingproblem, deduction , solutionin a system where the problems are not unnatural or artificial. Most important, it can help to diminish the feeling that many students have, consciously or not, that mathematics is a collection of formulas and that to solve a problem you need only find the appropriate formula. VII
viii
Preface
This text has been designed for a onesemester or onequarter course in number theory, with minimal prerequisites. The reader is not re quired to know any mathematics except elementary algebra and the properties of the real numbers. Nevertheless, the average student does not find number theory easy because it involves understanding new ideas and the proofs of theorems. I have tried to make the proofs detailed enough to be clear, and I have included numerical examples, not only to illustrate the ideas, but to show the fascination of playing with numbers, which is how many of the ideas originated. I have included an introduction to most of the topics of elementary number theory. In Sections 1 through 5 the fundamental properties of the integers and congruences are developed , and in Section 6 proofs of Fermat' s and Wilson's theorems are given. The number theoretic functions d, cr, and 1> are introduced in Sections 7 to 9. Sections 10 to 12 culminate in the quadratic reciprocity theorem . There follow three more or less independent blocks of material: the representation of numbers (Sections 13 to 15), diophantine equations (16 to 20) , and primes (21 and 22) . Because I think that problems are especially im portant and interesting in number theory, Section
23
consists of
260
additional problems, some classified by section and some arranged ' without regard to topic. There are three appendixes. Appendix A, Proof by Induction, should be read when and if necessary . Because computers integrate naturally with number theory , Appendix B presents problems for which it com puter can be programmed . Appendix C contains a table that makes it easy to factor any positive integer less than 10,000. Because I believe that the best way t o learn mathematics i s to try to solve problems, the text includes almost a thousand exercises and problems. I attribute the success of the first edition not to the expositionafter all, the proofs were already knownbut to the prob lems, and the problem lists have been revised , deleting unsuccessful problems and including new ones that may be mOre successful . The exercises interrupt the text and can be used in several ways: the stu dent may do them as he reads the material for the first time; he may return to them later to check on his understanding of material already studied; or the instructor may include them in his exposition . Some of the exercises and problems are computational and some classical , but many are more or less original, and a few , I think, are startling. Number theory pr?blems can be difficult because inspiration is some times necessary to find a solution, and inspiration cannot be had to
Preface
ix
order. A student should not expect to be able to conquer all of the problems and should not feel discouraged if some are baffling . There is benefit in trying to solve prOblems whether a solution is found or not. I. A . Barnett has written [1] "To discover mathematical talent, there is no better course in elementary mathematics than number theory . Any student who can work the exercises in a modern text in number theory should be encouraged to pursue a mathematical career." Answers are provided where appropriate for exercises and odd numbered problemsthose marked with an asterisk. Comments are given for those problems marked with a dagger . Although there are more problems than a student could solve in one semester, they should be treated as part of the text, to be read even if not solved. Some times they may be more interesting than the material on which they are based. The first edition contained many errors, and I want to thank the many people who pointed them out and suggested improvements. These errors have all been removed, but inevitably new ones have been added . I hope that when the reader finds one , he will feel pleased with his acuteness rather than annoyed with the author . Corrections will be welcomed.
Underwood Dudley May 1978
Elementary Number Theory
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, 1 7x2 + 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 1 7 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 coinparable 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. 1
Section
2
1
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 uglythings. 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 integersa property that you may not be consciously aware of because it is not stated explicitly as the others. It is the leastinteger principle: a nonempty set of integers that is bounded below contains a smallest element. There is the corresponding greatestinteger principle: a nonempty set of integers that is bounded above contains a largest element. We will say that a divides b (written a I 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. t
Which integers divide zero?
Show that if a I b and b 1c , then a 1c . As a sample of the sort of properties that division has, we prove
Exercise 2.
Lemma !.
Ifd l a and d l b, then d l (a + b) .
Proof. From the definition, we know that there are integers q and· r
such that
dq = a
and
dr = b .
t Answers to selected exercises, those preceded by an asterisK (*), are provided on 226ff.
pp.
Integers
J
Thus
a +b =d(q +r) , so from the definition again, d I (a +b). In the same way, we can prove
Ifd l al, dla!, .. . ,dla", then dl(cla l + c2a 2 + . . . +c"a,,) for any integers Cl, C2 , , CII'
Lemma 2 .
•
•
•
From the definition, there are integers qI> q2,' .. ,qll such that a l =dql, a2 = dq2' . . . ,a" =dq". Thus cla l +cza:+ . . . + cna" = d(Clq l+ C2Q! + . . . +C.,.Q,,) , and from the definition again , dlcla] +CZa 2+ . . . +c"a".
Proof.
Exercise 3.
Prove that if d I a then d I ca for any integer c .
As an application of Lemma 2 , let us see if it is possible to have 1 00 coins, made up of C pennies, d dimes, and q quarters, be worth exactly $5.00. If it is possible, then c+d+q=l00 and
C+ 1 0d +25q = 500. Subtract the first equation from the second and we get 9d+24q = 400. Since 3 19 and 3 124,Lemma 2 says that 3 19d+ 24q. That is, 3 1400.But that is impossible, so having exactly $5.00 is impossible with 1 00 pen nies, 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 commerceif 1 5 Athenian drachmas are worth 1 8 drachmas from Miletus, how many Athenian drachmas are equivalent to 60 Miletian drachmas? That is one reason why the Euclidean Algorithm for finding
4
Section I
greatest common divisors was part of Euclid's Elements, written around 3 00 Be. 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) dla and dlb, and (ii) ifcla and c l b , thel1 c :5 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 greatestinteger 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 lla and lib for all a and b. '" Exercise
4. What are (4, 14), (5, 15), and (6, 16)?
" Exercise 5.
O)?
What is (n , 1), where n is any positive integer? What is (n,
" 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 (aid, bid) = 1.
Suppose thate= (aid, bid). We want to show thate= 1. We will do ihis by showing that e :5 1 and e� 1. The latter inequality follows from the fact that e 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 :5 1, we use the facts that c I (aid) and c I (bid). We then know that there are integers q and r such that eq = aid and cr = bid. That is, Proof.
(ed)q·= a
and (ed)r = b. These equations show that cd is a common divisor of a and b. It is thus no greater than the g reatest common divisor of a and b, and this is d.
Integers
5
Thus cd :S d. Since d is positive, this gives c :S 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 f= 0,. there exist unique integers q and r, with 0 :S r 0, then (a, b) a . Prove that «a, b), b) = (a, b). (a) Prove that (n, n + 1) = 1 for all n > O. (b) If 11 > 0, what can (11, n + 2) be?
8. Prove that if
10.
+

= l.
b.
=
11 + k)
= 1 if and only if (k,
(b) Is it true that (k, 11 + k) =
11)
=
l.
d if and only if (k, 11) = d ? Prove: If a Ib and c Id, then ac Ibd. Prove: If dla and d l b , then d"lab . Prove: If c lab and (c, a) = d, then c Idb. (a) If x' + ax + b = 0 has an integer root, show that it divides b . (b) Ifx' + ax +b 0 has a rational root, show that it is in fact an integer. =
*
Answers to selected oddnumbered problems, those preceded by an asterisk (0). are
provided on pp. 231ff. Comments on selected oddnumbered problems, those preceded by a dagger (t), are given on pp. 238ff.
Section
2 Unique Factorization
The aim of this section is to introduce the prime n1).mbers, which are one of the main objects of study in number theory, and to prove the unique factorization theorem for positive integers,which is essential in what comes later. In this section, lowercase italic letters invariably denote positive integers. A prime is an integer that is greater than 1 and has no positive divisors other than 1 and itself. An integer that is greater than 1 but is not prime is called composite. Thus 2, 3 , 5, and 7 are prime, and 4, 6, 8, and 9 are composite. There are also large primes: 170,141,183,460,469,231,731,687,303,715,884,105,727 is one, and it is clear that there are arbitrarily large composite numbers. Note that we call 1 neither prime nor composite. Although it has no positive divisors other than 1 and itself, including it among the primes would make the statement of some theorems inconvenient,in particular the unique factorization theorem. We will call 1 a unit. Thus the set of positive integers can be divided into three classes: the primes, the composites, and a unit. " Exercise 1.
digit is 5?
How many even primes are there? How many whose last 10
Unique Factorization
J1
Our aim is to show that each positive integer can be written as a product of primesand, moreover, in only one way. We will not count products that differ only in the order of their factors as different factori zations. Thus we will consider each of 7·3·2·2 2·3·7·2, to be the same factorization of 84. The primes can thus be used to build, by multiplication, the entire system of positive integers. The first two lemmas that follow will show that every positive integer can be written as a product of primes . Later we will prove the uniqueness of the representation . Lemma 1.
Every integer n, n > 1, is divisible by a prime.
Consider the set of divisors of 11 which are greater than 1 and less than 11. It is either empty or nonempty. If it is empty, then n is prime by definition, and thus has a prime divisor, namely itself. If it is nonempty, then the leastinteger principle says that it has a smallest element, call it d. If d had a divisor greater than 1 and less than d, then so would n, but this is impossible because d was the smallest such divisor. Thus d is prime, and n has a prime divisor, namely d.
Proof.
Lemma 1 can also be proved using the second principle of induction (see Appendix A). The lemma is true by inspection for n = 2. Suppose it is true for 11 :s k. Then either k + 1 is prime, in which case we are done, or it is divisible by some number kl with kl :S k. But from the induction assumption, kl is divisible by a prime, and this prime also divides k + 1. Again, we are done. With the aid of Lemma 1, we can prove that every positive integer can be written as a product of primes in at least one way. Lemma 2 .
Every integer n, n > 1, can be written as a product of primes.
From Lemma 1, we know that there is a prime PI such that P I I n. That is, n = Plnl, where 1 :S nl < n. I f nl = 1, then w e are done: n = PI is an expression of n as a product of primes . If nl > 1, then from Lemma 1 again, there is a prime that divides nl . That is, nl = P2nZ, where pz is a prime and 1 :S /12 < n I. If /12 = 1, again we are done:
Proof.
12
Section 2
= PIP! is written as a product of primes. But if n2 > 1, then Lemma 1 once again says that 112 = PaJl3' with P3 a prime and 1 ::s n3 < 112. If n3 = 1, we are done. If not we continue. We will sooner or later come to one of the ni equal to 1 , because n > 111 > n2 > . . . and each ni is positive; such a sequence cannot continue forever. For some k, we will have nk = 1, in which case n = PIP! ...Pk is the desired expression of 11 as a product of primes. Note that the same prime may occur several times in the product. 11
Exercise 2 '" Exercise 3.
(optional). Construct a proof of Lemma 2 using induction. Write prime decompositions for 72 and 480.
Before we show that each positive integer has only one prime de composition, we will prove an old and elegant theorem: Theorem 1
(Euclid). There are infinitely many primes.
Suppose not. Then there are only finitely many primes. Denote them by PI> P2' . ,Pr. Consider the integer (1) n = PIP2 ... Pr + 1. From Lemma 1, we see that n is divisible by a prime, and since there are only finitely many primes, it must be one of PI' P2, . . . , Pro Suppose that it is Pk. Then since and it divides two of the terms in (1). Consequently it divides the other term in 0); thus Pk 1 1. This is nonsense: no primes divide 1 because all are greater than 1. This contradiction shows that we started with an incor rect assumption. Since there cannot be only finitely many primes, there are infinitely many. The table on page 13 shows how adding 1 tOP1P2 . . .Pr will always give a prime different from PI' P2, . . ,Pr. Theorem 1 is strong. We can actually identify only finitely many primesthe largest prime currently known is 219937 1, and we by no means know all of the primes smaller than this one. (A list of all the primes smaller than 10,000,000 fills a large book.) The prime 2U937 1 is a very large number: it has more than 6000 digits. Although 219937 1 is a large number, there are infinitely many integers larger than it, and only finitely many smaller. Thus, although we can name only finitely Proof.
.



Uniqu e Factorization r
Pr
1 2 3 4 5 6 7 8
2 3 5 7 11 13 17 19
13
PIPZ · . . Pr + 1 Prime Divisors
3 7 31 211 2311 30031 510511 9699691
3 7 31 211 2311 59, 509 19, 97, 277 347, 27953
many primes, we may be sure that no matter how many we discover , there is always one more that we have yet to find. Before the develop ment of computers, the largest prime known was the comparatively puny 39digit number displayed at the beginning of this section. Hence if you set out to find a prime larger than 219937 1 without the aid of a machine, you will need a great deal of time to spareseveral centuries at the least. We will show how to construct a table of prime numbers before . proving the unique factorization theorem. 
Lemma 3 .
If
l < d:::5n1l2.
Proof. did!
then
n
is composite, then it has a divisor
(j
.
such that
Since 11 is composite, there are integers dl and dz such that and 1 < dl < n, 1 < dz < n. If dl and dz are both larger than nil!,
= 11
which is impossible. Thus, one of d1 and dz must be less than or equal to
n112.
If equal to n 112
Lemma 4.
•
n is composite, then it has a prime divisor less than or
We know from Lemma 3 that n has a divisorcall it dsuch that 1 < d:::5n1l2. From Lemma 1, we know that d has a prime divisor p. Since P :::5 d :::5 the lemma is proved.
Proof.
n112,
Lemma 4 provides the basis for the following method for finding primes, the wellknown named after the
Sieve of Eratosthenes,
14
Section 2
Alexandrian mathematician who lived in the third century Be who is
also remembered for being the first to estimate the circumference of the earth using geometry. That was a golden century for mathematics:
besides Eratosthenes, there was Archimedes, who had one of the most powerful mathematical minds ever, and Euclid, who wrote his geometry book so well that it was used as a textbook for the next two thousand years. The idea behind the sieve is simple: the primes are the numbers left when all the composites are gone. Then, to find primes remove multi ples of
2, of 3 , of 5, .
. . ; if we stop after removing multiples of N, the
numbers remaining between 2 and N2 are precisely the primes less than N2 . To see this, note that any number remaining is prime, because if it were composite it would have, according to Lemma 4, a prime divisor less than or equal to N, and all the multiples of such primes have been removed. For example, let us list the integers up to already removed:
121
with the multiples of
2 5 7 3 9 1 1 13 15 17 27 29 3 1 33 35 37 39 41 43 53 55 57 59 6 1 63 65 67 69 79 8 1 83 85 87 89 91 93 95 105 \107 109 1 1 1 1 13 1 15 1 17 1 19 121
19 45 71 97
2
21 23 25 47 49 5 1 73 75 77 99 101 103
Now remove all the multiples o f 3every third number after
3:
2 5 7 1 1 13 17 19 23 25 29 3 1 35 3 37 41 43 47 49 53 55 59 61 65 67 71 73 77 79 83 85 89 91 95 97 101 103 107 109 1 13 115 119 121 Now remove the multiples of
5, which fall in a pattern:
every seventh,
third, seventh, third, . . . number; a stencil could be made to pick them out, and such stencils have been made in the past:
2 3 5 7 1 1 13 17 19 23 29 3 1 37 41 43 47 49 53 59 61 67 71 73 77 79 83 89 91 97 101 103 107 109 1 13 1 19 121 Mter
49,
the pattern is t o have a multiple of
seventh, fourth, . we have
7 every seventh,
fourth,
. number; removing them and the multiples of
11,
Unique Factorization
15
2 3 5 7 1 1 13 17 1 9 23 29 3 1 37 41 43 47 53 59 61 67 71 73 79 83 89 97 101 103 1 07 1 09 1 13 and these are all the primes less than 1 2 1 . If there were a composite number in the list, from Lemma 4 it would have a prime divisor less than or equal to 1 1 , and we have removed all of the composite numbers with divisors 2, 3, 5, 7, and 1 1 . To find all ofthe primes less than 10,000, we would only have to cross out the multiples of the 25 primes less than 1 00. Today, any sieving that is necessary is done by computer,but in the nineteenth century, before there were computers, an Austrian as tronomer named Kulik constructed an enormous sieve of all the inte gers up to 1 00,000,000. It took him 20 years, off and on. All that work was so little valued that the library to which he left his manuscript lost the part that included the integers from 12,642,600 to 22,852,800. The simple sieve idea is quite powerful, and refinements of itthe Selberg Sieve, and the new Large Sieve of Linnikare producing new results. . The following lemma, proved in Euclid's Elements, gives the result that makes unique factorization possible. For the rest of this section, and until further notice, the letters p and q will be reserved for primes. Lemma S.
Ifplab, then pla orplb.
Proof. Since p is prime, its only positive divisors are 1 and p . Thus ( p, a ) = p or ( p, a ) = 1 . In the first case, pla , and we are done. In the second case, Corollary 1 of Section 1 tells us thatp Ib, and again we are done.
The next lemma illustrates a common technique: extending a result from 2 to any number using mathematical induction. Lemma 6.
Ifp lala2 . .. ak, then plai for some i,
i= 1,
2, .
. . ,k.
Lemma 6 i s true b y inspection if k = 1 , and Lemma 5 shows that it is true if k = 2. We will proceed by induction. Suppose that Lemma 6 is true for k=r. Suppose that plala2' . . ar+1• Then p l (a 1a2 . . . ar )ar+1, and Lemma 5 lets us conclude that p iala2 . . . �r orp lar+1• In Proof·
16
Section 2
the first case, the induction assumption tells us that P lai for some i, i = 1, 2, . . . , r . In the second case, P lai for i =r + 1. In either case, P la i for some i, i = 1, 2, . . . , r + 1. Thus, if the lemma is true for k = r, it is true for k = r + 1 , and since it is true for k = 1 and k =2, it is true for any positive integer k. Ifql,q2,' . . ,q1f/.are primes,andp l qlq2·· ·q1f/.,thenp =qlt for some k.
Lemma 7.
From Lemma 6 we know that P I q k for some k. Since P and q It are primes. P = q k' (The only positive divisors of q It are 1 and q k' and P is not 1 .)
Proof.
The Unique Factorization Theorem. Any positive integer can be written as a product of primes in one and only one way.
Theorem 2.
Recall that we agreed to consider as identical all factorizations that differ only in the order of the factors. We know already from Lemma 2 that any integer n, n > 1 can be written as a product of primes . Thus to complete the proof of the theorem,we need to show thatn cannot have two such representations. That is, if (2) and n =PIPZ' . . P'"
Proof.
then we must show that the same primes appear in each product, and the same number of times, though their order may be different. That is, we must show that the integerspl>pz, . . . 'P'" arejust a rearrangement of the integers ql. q2 , q From (2) we see that since PI In, PI ! qlq2 . . . qT' From Lemma 7, it follows thatpl = qi for some i. If we divide PIP! . . . Pm = qlq'l ... qr by the common factor, we have (3) P2P3' . . Pm =qlq2 . . . qiIqi+1 .. . qT' Because P2 divides the lefthand side of this equation,it also divides the righthand side. Applying Lemma 7 again, it follows that P2 = qj for somej(j = 1, 2, . . . ,i  1, i + 1, . . . , n). Cancel this factorfrom both •
.
.
.
r'
Unique Factorization
17
sides of (3), and continue the process. Eventually we will find that each is a q . We cannot run out of q' s before all the p ' s are gone,because we would then have a product of primes equal to 1, which is impossible. If we repeat the argument with the p ' s and q's interchanged,we see that each q is ap . Thus the numbers Pl>P2,' . . 'Pm are a rearrangement of ql, Q2,· . . ,qr> and the two factorizations differ only in the order of the factors. The uniqueness of the prime decomposition can also be efficiently proved by induction, though the idea is no different. The theorem is true, by inspection,for 2. Suppose that it is true for k. Suppose that k + 1 has two representations: k + 1 = P lP2' .. Pm = qlQ2' .. q T' As in the last proof, PI = qi for some i, so
p
n=
n :S
P2PS . . . P'" = qlq 2 ... qiIqi+1 . .. qT'
But this number is less than or equal to k, and by the induction assump tion, its prime decomposition is unique. Hence the integers ql, q 2,' . . , qil> qi+1> . . . , qr are a rearrangement ofp 2 ' P3, . . . ,Pm, and since PI = qi the proof is complete. Because of your long experience with the positive integers (can you remember what it was like not to know what 2 + 3 was? ),you may not find the unique factorization theorem very exciting; you may even think that it is obvious and selfevident. The following example is in tended to show that it is not as selfevident as you might think: we will construct a number system in which the unique factorization theorem is not true. Consider the integers 1, 5, 9, 13, 17,. . . ; that is, all integers 0, 1, . . . . We will call an element of this set of the form 4n + 1, prome if it has no divisors other than 1 and itselfin the set . For example, 21 is prome, whereas 25 = 5· 5 is not .
n=
*
Exercise 4.
Which members of the set less than 100 are not prome?
In the same way that we proved Lemmas 1 and 2, we can show that every member of the set has a prome divisor and can be written as a product of promes. (You are invited to inspect the proofs of Lemmas 1 and 2 to see if any words need to be changed.) But an example shows that the prome decomposition of an integer in the set is not always unique: 693 21·33 = 9'77,
=
and 9, 21, 33, and 77 are all prome.
18
Section 2
From the unique factorization theorem it follows that each positive integer can be written in exactly one way in the form
;:::
1, i = 1 , 2, . . . , k, each Pi is a prime, and Pi f= Pi for i f=j. We call this representation the primepower decomposition of n, and whenever we write where
ei
it will be understood, unless specified otherwise, that all the exponents are positive and the primes are distinct. The factor table in Appendix C gives the smallest prime that divides n for all n less than 1 0,000 and not divisible by 2 or 5 . With the aid of this table, the primepower decom position for any n 10,000 can be found readily. For example, take 8001. It is clearly not divisible by 2 or 5, and Table A gives its smallest prime factor as 3. Then 800 113 = 2667, and the table shows that 3 is a factor of 2667: 2667/3 = 889. Again referring to the table, we see that 7 / 889. Finally, 889/7 = 127, which is prime. Thus
:S
8001 = 32 . 7. 127. '"
Exercise 5. What is the primepower decomposition of 7950?
To conclude this section, we note that the prime decomposition of integers gives another way of finding greatest common divisors besides the Euclidean algorithm. For example, consider n = 120 = 23 . 3 . 5 and
m = 252 = 21• 32 . 7. We see that 22 divides m and n, but no higher power of 2 is a common divisor of m and n. Also, 3 divides m and n, and no higher power of 3 is a common divisor. Furthermore, no other prime n. Thus 22. 3 is the greatest common divisor of m
divides both m and
and n. Given the primepower decompositions of m and n, we can write
m
and n as products of the same primes by inserting primes with the exponent zero where necessary. For example, and
In general, we have
Theorem 3 . If ei
;::: O,J;
m =P l e' P 2 O. For example , 1 ... 5 (mod 4), 2 '" 9 (mod 1 1) , 6 "", 20 (mod 7) , and 720 "" 0 (mod 10). '" Exercise 1 . True or false?
2 '" 2 (mod 8). 1 12 == 1
91 ,.. o 3).
(mod
(mod
7) . 3 + 5 + 7 "'"
5 (mod
10) .
Really , m I (a  b) and a "'" b (mod m ) are only different notations for the same property , but a good notation can make things easy to see. Notation is vital. The ancient Greek mathematicians from 600 Be to 300 AD did not develop algebra at all. though they did such a fine job with geometry that Euclid' s Elements was used as a textbook for 2000 years. It was not because they could not havethere is no question that Archimedes could have solved the general cubic polynomial equation , perhaps in his head. if he had put his mind to it and had had a satisfac27
Section 4
28
tory notationit was the lack of notation that stopped them. The solu tion of the cubic had to wait another 1 700 years or so. The congruence notation was invented by the great mathematician and physicist Carl Friedrich Gauss ( 1 7771855) , to whom is due quite a bit of the content of this book, and any other number theory book. His notation simplifies the proofs of theorems that would be difficult even to state without it. Another example of the value of a good notation is in calculus , in which Leibniz' s notation (dy/dx, fy dx) was superior to Newton's (y, y'). There is another way to look at congruences : Theorem 1 . a
=
a
b + km .
�
b
(mod
m)
if and only if there is an integer k such that
Proof. Suppose that a :;, b (mod m). Then , from the definition of con gruence , m I (a  b) . From the definition of divisibility , we know that since there is an integer k such that km = a  b , then a = b + km . Con
versely, suppose that a
'" Exercise 2.
=
b + km .
Complete the proof.
Theorem 2. Every integer is congruent (mod
. . . , m  1.
m)
to exactly one of 0,
1,
= qm + r , with 0 :s; r < m . We know from Theorem 2 of Section 1 that q and r are uniquely determined. Since a "" r (mod m ) , the theorem is proved.
Proof. Write a
We call the number r in the last theorem the least residue of a (mod
m). For example , the least residues of 7 1 modulo 2, 3 , 5, 7, and 1 1 are 1 , 2, 1 , 1 , and 5 , respectively . '" Exercise 3. To
41
congruent?
what least residue (mod
1 1) is each of 23 , 29, 3 1 , 37, and
Yet another way of looking at congruences is given by a '" b (mod m) if and only if a and b leave the same remain der on division by m .
Theorem 3.
Congruences
29
Proof. If a and b leave the same remainder r when divided by m , then
b = qzm + r
and
for some integers ql and q 2 ' It follows that
2m + r) = m {l j  Q2) ' From the definition of divisibility , we have m I (a  b). From the defini a
 b = (qjm
+ r) 
(q
a "'" b (mod m ) . To prove the b (mod m ) . Then a !!!lE b r (mod m), where
tion of congruence, we conclude that converse , suppose that a
r
"""
is a least residue modulo
""
m.
Then from Theorem
b = Q2m + r
and for some integers Q 1 and
q2 ;
since
1,
0 $ r <m ,
the theorem is proved .
1 609 by 197 : the quoti�nt is 8 and the remainder 1 21 5 by 1 97: the quotient is 6 and the remainder is 33 . It 1609 "" 1 2 1 5 (mod 197) , and in fact
For example , divide is 33. Divide
follows that
1 609  1 2 1 5 = 394 = 2 . 1 97. It follows from Theorems
"n
=7
+
1
and 3 that the phrases
8k for some integer k , " and
"
n
"
n
"" 7 (mod 8) , "
leaves the remainder
7
when
divided by 8" are different ways of saying the same thing. " Exercise 4. Say
"n
is odd" in three other way s .
Exercise 5. Prove that
p Ia
if and only if a
"'"
0
(mod p).
Congruence acts like equality i n many way s .
Lemma 1 . For integers (a) a .... a (mod m).
"" b "" b If a "" b
(b) If a (c) If a
(d)
m).
(e) I f a
""
a, b, c ,
and
d
b ... a (mod m). m) and b "'" c (mod m ) , then a .,. c (mod m). (mod m ) and c "" d (mod m) , then a + c ,... b + d (mod
(mod m ) , then
(mod
b (mod m) and c
"'"
d (mod m), then ac "" bd (mod m).
Proof. All of these follow directly from the definition of congruence . . Here is a proof of (e): We are given that b  a = km and d  c = jm for some integers k and j; thus
30
Section 4
ae  bd = ae  (a + km)(e + jm) == ae  ae  ajm  ekm  kjm2 = m(aj  ek  kjm ) ; from the definition of congruence, Exercises 6 , 7 , 8 , and 9.
ae "'" bd (mod m).
Prove parts (a) , (b) , (c) , and (d) .
Note that the lemma implies that we may substitute in congruences just as we do in equations . For example , ifx '" 2 (mod 5) , then
2x2  x + 3 "'"
2·4

2+3
,..
9 """
4 (mod 5) .
Although ab = ae and a 1= 0 imply b = e for all integers a, b, and e, it is not true that ab ,... ac (mod m) and a " 0 (mod m) imply b "'" e (mod m). (The symbol " means "not congruent to ." ) For example, 3 · 4 "", 3 · 8 (mod 1 2) "' Exercise 10.
4 � 8 (mod 1 2) .
but
Construct a like example for modulus 10.
Although we cannot cancel freely, all is not lost, as we shall see from Theorem 4. If ae
"" be
(mod
m)
and
(e, m) =
1 , then a
"'" b
(mod m) .
m I (ae  be); consequently , Because (m, c ) = 1 , we can conclude from Theorem 5 of Section 1 that m I (a  b). That is, a "" b (mod m).
Proof. From the definition of congruence ,
m ! c(a  b).
'" Exercise 1 1 .
What values of x satisfy (a) 2x
(Hint for (b): 1
...
"'"
4 (mod
8 (mod
7)?
(b)
2x ""
1 (mod
7)?
7) .)
We can, then, cancel a factor that appears on both sides of a congru ence if it is relatively prime to the modulus . We now consider the case in which the factor and the modulus are not relatively prime. Theorem 5. If ae
"" be
(mod m) and
(c,
m)
= d,
then a
"'" b
(mod mid) .
Con gruences
31
Proof. If ae
5 be (mod m), then m I c(a  b) and mid I (c!d)(a  b). Since we know that (mid, eld) = 1 , from Theorem 5 of Section 1 we get mid I (a  b), so a e b (mod mid) .
That is, we can cancel a common factor from both sides of a congru ence if we divide the modulus by its greatest common divisor with the factor. For example, 30x "'" 27 (mod 33) implies lOx m 9 (mod 1 1). " Exercise 12.
Which x will satisfy
2x "" 4
(mod
6)?
Now we can see how easy it is to show that no integer of the form
8n + 7 is the sum of three squares. Suppose that k = 8n + 7 is the sum of three squares . Then k E 7 (mod 8) and k = a 2 + b 2 + e2 for some integers
a, b,
and e . Thus
a2 + b2 + e2 "" 7
(mod 8) .
We now show that this last congruence is impossible for any integers a, and e . What values can x2 assume , modulo 8? Every integer has one of 0, 1 , 2, 3 , 4, 5, 6, and 7 for a least residue (mod 8) , and
b,
()2
"" 0,
P
"" 1 , 52 "" 1 ,
22 ... 4 , 62 "" 4,
32 "" 1 72  1 ,
all modulo 8 . Thus the square of any integer i s congruent modulo 8 to one of 0, 1 , and 4. It is impossible to make any combination of three numbers selected from 0, 1 , and 4 add up to anything congruent to 7 (mod 8) . (The statements 1 + 1 + 4 "" 6 and 0 + 4 + 4 1m 8 (mod 8) are as close as you can come.) Hence a 2 + b 2 + e 2 is never congruent to 7 (mod 8) for any integers a, b, and e . Thus a2 + b2 + e 2 = 8n + 7 is an impossible equation. You may already know the handy test for divisibility by 9: an integer is divisible by 9 if and only if the sum of its digits is divisible by 9, and you may already know why it is true . Congruences make the proof trivial. Since 10 "", 1 (mod 9), 10" m In "", 1 (mod 9) , and that is all we need to prove Theorem 6. Every integer is congruent (mod 9) to the sum of its digits . Proof. Take an integer n, and let its digital representation by
Section 4
32
That is, n = dlc lOk + dlc_1 101c1 + dlc_ 1Ok2 + . . . + d1 l01 + dolOo 2
"'" d� + dlc1 + dlc2 + . . . + do (mod 9) , which is what we wanted to show .
This theorem shows why the process of casting out nines to check an addition or a mUltiplication works . The rule was a feCJ.ture of many arithmetic books in the past, when long columns of numbers had to be added by hand and there were no mechanical devices to perform mul tiplications. Now we can all have p ocket calculators, but it is wise to be prepared for the time when our batteries fail . If two numbers are equal, they are congruent to any modulus, 9 in particular. So if we are told that (3 14) ( 159) = 49826, we can see right away that we are being lied to , because (3 14)( 1 59) "'" (3 + 1 + 4)(1 + 5 + 9) "'" 8 · 15 "" 8(1 + 5) ==
48 "", 4 + 8 "'" 12 "" 1 + 2 "" 3 (mod 9) ,
while 49826 ... 4 + 9 + 8 + 2 + 6 "'" 29 "'" 2 + 9 """ 1 1 "'" 1 + 1 ... 2 (mod 9) : the numbers are not congruent (mod 9) , so they cannot be equal.
Problems " 1 . Find the least residue of 1492 (mod 4) , (mod 1 0) , and (mod 1 0 1 ) . 2 . Find the least residue o f 1 789 (mod 4) , (mod 1 0) , and (mod 1 0 1 ) .
 b (mod m ) , then a ' "" b' that i f a ' "" b2 (mod m ) , then a "" b
3 . Prove or disprove that i f 4 . Prove o r disprove
8 5.
a
m). b (mod m).
(mod or
Find all m such that 1 066 "" 1776 (mod m).
6. Find all m such that 1848 "" 1 9 1 4 (mod
m).
" 7 . If k "" 1 (mod 4) , then what is 6k + 5 congruent to (mod 4)? 8. Show that every prime (except 2) is congruent to I or 3 (mod 4) . 9. Show that every prime (except 2 or 3) is congruent to I or
1 0 . What can primes (except 2, 3 , or
5)
5
(mod 6) .
be congruent to (mod 30)?
Congruences
*
11.
12. '" 13. 14. 15. 16.
33
2910 93995, one digit in the product is In the multiplication 31415 · 92653 ' missing �nd all the others are correct. Find the missing digit without doing the multiplication. =
Show that no square has as its last digit,
2, 3 , 7,
or
8.
What can the last digit of a fourth pDwer be? Show that the difference Df two cDnsecutive cubes is never divisible by
3.
Show that the difference Df two consecutive cubes is never divisible b y 5 . Show that
dkl0k + dk_1IO k1
+. . . +
dllO + do "" d o  d1
+
d2  d3 +
. . .
+
(  l)lrdlt (mOod 1 1)
11. "27,182,8 18,284,590,452 i s divisible by 1 1 . " B says, "No, it isn' t."
and deduce a test for divisibility by
'" 17.
A says,
Who is right?
18.
A
palindrome
Examples are
is a number that reads the same backward as forward . and 935686539.
22, 133 1 ,
(a) Prove that every fourdigit palindrome is divisible by (b) What about sixdigit palindromes?
19.
ShDW that if n cubes .
20 .
ShDw that for k > O and m
""
4 (mOod
9) , then n ;e:
11.
cannot be written as the sum Df three
1,x � 1
(mod m�") implies x'·
""
1 (mod mk+ ' ) .
Section
5 Linear Congruences
Mter defining congruences and studying some of their properties, it is natural to look at congruences involving unknowns, like 3x "'" 4 (mod 5) and X l7 + 3x  3 "'" 0 (mod 3 1 ), and see how to solve them, if we can. The simplest such congruence is the linea r congruence ax "'" b (mod m), and this i s what this section i s devoted to . The congruence ax "'" b (mod m ) has a solution if and only if there are integers x and k such that ax = b + km . Hence , the problem of solving linear congruences is es sentially the same as that of solving linear diophantine equations, and Theorem I of this section is the same as Theorem 1 of Section 3 , but in a different notation. If one integer satisfies ax "'" b (mod m), then there are infinitely many . For example, the table below shows that 3x == 4 (mod 5) is true if x = 3 x
3x (mod 5)
1
0
1
° 3
2
I
3
4
4
2
5
0
6 3
7 1
8
4
9
2
or x = 8 , and it is clear that it is also true if x = 1 3 , 1 8 , 23 , . . . or x = 2,  7 ,  12 , . . . . In general, if t is an integer such that ar "'" b (mod m) , then all of the integers t + m, r + 2m , . . . , r  m , t  2m . satisfy the congruence, since •
a (t + km ) "'" at "'" 34
b (mod m)
Linear Congruences for any integer
k.
Among the integers r +
km , k = 0,
there will be exactly onesay sthat satisfies
0
:$
s
± 1 , ±2,
.
35
. . ,
< m . This is be
m . If r k, then
cause every integer lies between two successive multiples of
km :$ r < (k + l)m for some  km . We will single this integer out and say that by a solution to ax E b (mod m), we mean a number r such that ar "'" b (mod m) and r is a least residue (mod m) . Thus , the solution to 3x "'" 4 (mod 5) is 3 , because it makes the congruence true and it is a least residue (mod 5). Unlike the familiar linear equation ax = b , the linear congruence ax "'" b (mod m) may have no solutions, exactly one solution , or many solutions . For example, 2x "" 1 (mod 3 ) is satisfied by x = 2 and for no other values of x that are least residues (mod 3) . Hence it has just one solution, namely 2. The congruence 2x ... 1 (mod 4) has no solutions, because 2x is congruent to 0 or 2 (mod 4) for any x. The congruence 2x "'" 4 (mod 6) has two solutions, 2 and 5. satisfies the congruence and
o :$
*
I' 
km
< m ; we can put
s
=r
Exercise 1 . Construct congruences modulo
12
with n o solutions, just
one solution, and more than one solution. ,. Exercise 2. Which congruences have no solutions?
(a) (d)
3x =" 6x "'"
1 1
(mod (mod
1 0) , 1 0) ,
(b) (e)
4x iE 1 7x � 1
(mod (mod
10) , 10) .
( c) 5x �
1
(mod
10) ,
* Exercise 3 (optional) . After Exercise 2 , can you guess a criterion for telling when a congruence has no solutions ?
We will now set out to prove a theorem that will let us see how many solutions a linear congruence has .
Lemma 1 .
If
(a, m)%b , then ax "" b
(mod
m) has no solutions .
Proof. We will prove the contrapositive, which is logically the same
ifax =" b (mod m) has a solution , then (a, m) l b . Suppose that r is ar ... b (mod m) , and from the definition of congruence , m I (ar  b), or from the definition of divides , ar  b = km for some k . Since (a, m) la and (a, m) l km, it follows that (a, m) l b .
thing:
a solution . Then
For example. 6x
="
7
(mod
8)
has no solutions .
36
Section 5
Lemma 2. If (a,
m)
=
1 , then ax
"" b (mod m) has exactly one solution.
Proof. Since (a, m) = 1 , we know that there are integers r and s such that ar + ms = 1 . Multiplying by b gives
a(rb) + m (sb) = b . We see that arb  b is a mUltiple of m , or a(rb) "" b (mod m) . The least residue of rb modulo m is then a solution of the linear congru
ence. It remains to show that there is not more than cine solution . Suppose that both r and s are solutions. That is, since and ar "'" b (mod m) then ar "'" as (mod m) . Because (a, m)
as "'" b
(mod m) ,
= 1 , we can apply Theorem 4 of the last section, cancel the common factor, and get r "'" s (mod m). That is, m I (r  s) . But r and s are least residues (mod m), so
<m.  m < r  s < m ; together with m I (r  s), this gives r  s o :5
r<m
and
0 :5
S
= 0, or unique. The above argument is quite general and will be used often : if two least residues (mod m) are congruent (mod m), then they are equal.
Thus
r = s , and the solution is
I nspection is one way of solving congruences with small moduli, and another is substituting all possible values for the variable. But the best way is to manipulate the coefficients until cancellation is possible. For example, to solve 4x � 1 (mod 1 5) , we can write 4x "" 1 "'" 1 6 (mod 1 5)
and cancel to get x "'" 4 (mod 1 5) . As another example, let us solve 14x "'" 27 (mod 3 1) . From we get 7x
==
14x "'" 27 "'" 58 (mod 3 1)
29 (mod 3 1) .
W� continue adding 3 1 until we can cancel:
7x "" 29 "", 60 "'" 9 1 (mod 3 1) ,
so we get x "'" 1 3 (mod 3 1) , and 1 3 is the solution .
Linear Congruences
37
This method is the best to use when solving l inear diophantine equa tions . The equation ax + by = c implies the two congruences
ax "'" c
(mod b)
by """
and
c
(mod
a).
We can choose either one , solve for the variable , and then substitute the result into the original equation to get all the solutions . For exam ple , let us solve 9x + 16y = 35. This gives 16y ... 35 (mod 9) or 7y "'" 35 (mod 9) , from which we get y "" 5 (mod 9). That is , y = 5 + 9t for some integer t. Substituting this in the original equation, we get 9x o r 9x
+
144t = 45 , o r x
+
+ 16(5 + 9t) = 35, 16t = 5.
We thus have all the solutions:
x = 5  161, y = 5 + 9t, t
an integer.
.. Exercise
4.
Solve (a)
8x "'" 1
(mod
15),
(b)
9x + l Oy = 1 1 .
There remains the c�se where (a, m) I b and (a, m) 1= 1 . Cancellation reduces this to the case (a, m) = 1 . For example , to solve 6x "'" 15 (mod 33) , apply Theorem 4 of the last section to get 2x ... 5 (mod 1 1) which is satisfied by all integers x "'" 8 (mod 1 1). The solutions to the original congruence are all of the least residues (mod 33) which satisfy it, and _ these are 8, 19, and 30: (6, 33) = 3 , and the congruence has three solutions . This is what happens in general.
Lemma 3 . Let solutions .
d = (a, m) .
If d l b , then
ax "" b
(mod
m)
has exactly
d
Proof. If we cancel the common factor, we get a congruence (ald)x "" (bid) (mod mid), which we know has exactly one solution , be cause (aid, mid) = 1. Call it r, and let s be any other solution of ax "'" b (mod m). Then ar ;;;;; as "'" b (mod m), and it follows from Theo rem 5 of the last section that r "" s (mod mid). That is, s  r = k(mld) or s = r + k(mld) for some k . Putting k = 0, 1 , . . . , d  1 , we get numbers which are least residues (mod m), since o
::=;:
r + k(mld) < (mid) + (d  l)(mld)
= d(mld) = m ,
38
Section 5
ax 2 b (mod m) , because (a/d)(r + k(m/d) "'" (ald)r '"'" bid (mod m/d) ,
and they all satisfy and this implies
a (r + k(m/d» "" b
(mod m).
" Exercise 5 .
Determine the number of solutions o f each of the following congruences: 4x
3x "'" 6 (mod 15) , 6x
*
Exercise 6 .
E
11
"'"
(mod
8 (mod
15) ,
5x ;;E 10 (mod 15), 15) , 7x '" 1 4 (mod 15) .
Find all of the solutions of ix
"'"
1 0 (mod 15) .
We can summarize the results of Lemmas 1 to
3
b (mod m) has no solutions if then there are exactly (a . m ) solutions .
Theorem 1 . ax ""
" Exercise 7.
in
(a, m)tb .
If (a.
m) \ b ,
Solve the rest of the congruences in Exercise 5.
In a Chinese work on mathematics written more than 1000 years ago, there was a problem like , " Find a number that leaves a remainder of 1 when divided by 3 , of 2 when divided by 5, and of 3 when divided by 7 . " It is hard to imagine a practical situation where such a problem could arise. Mathematics was developed to deal with problems coming from commerce, government, astronomy, and religion, and this one does not seem to come from any one of those. Yet Babylonian clay tablets , written more than 2000 years ago, contain some types of cubic polynomial equations and their solutions, and those do not arise in everyday life either. Both are examples of the fascination that mathe matics has had for the human mindfor some human minds, anyway . After the practical problems are solved, mathematics is interesting for its own sake. We will now consider, for its own sake , and because it is useful elsewhere in number theory, how to solve problems like the ancient Chinese one mentioned above . In our notation, the problem is to find x such that X "'"
1 (mod
3) ,
x 52
2 (mod
5) ,
and
X ""
3
(mod
7).
39
Linear Congruences , Exercise
8. Verify that 52 satisfies each of the three congruences .
The first congruence says that x = 1 + 3k1 for some k 1 • Substituting this into the second congruence, we see that kj must satisfy Solving, we get kj thus
="
x =
1 + 3kj
�
2 (mod 5).
2 (mod 5) . That is, kj
1 + 3kj
=
1 + 3 (2
+
=
2 + 5k2 for some k2 ' and
51( 2) = 7
+ 1 5k 2 .
This x satisfies the first two congruences . If i n addition x satisfies the third, we must have 7 + 1 51 e; .) Thus every divisor of n is a member of the set D . Thus D is identical with the set of divisors of n . Each fi in ( 1 ) may take on ei + 1 values . Thus there are
52
Section 7
numbers in D , and because of the unique factorization theorem, they are all different. Since d(p1t) = n +, I , this proves the theorem. For example , from 24 = 23 3 we get d(24) = d(23)d(3) = 4 . 2 = 8 . •
Calculate d(240).
., Exercise 4.
Now we will get a formula for
a(n).
" Exercise 5.
Verify that the following table is correct as far as it goes, and complete it.
n a(n)
i
l 2 3 4 5 6 1 3 4 7 6 12
7
8
8
15
9
10 1 1 12 13 14
As with den), some special cases are easy. ' For example, a(p) = p + 1 for all primes p . Furthermore , the divisors of p2 are 1 , p , and pi, so a(p2) = 1 + P + p2. " Exercise 6. Exercise 7. " Exercise· 8 .
What is
a(P3)? a(pq),
Show that a(2") What i s
a(p"), n
= =
where p and q are different primes?
21tH
 1.
1 , 2, .
?
Let us calculate a(p eqf) , where p and q are different primes, and see if it suggests a general result. The divisors of p€qf are
p pq pq2
qf
pq f
peq f.
If we add across each row, we get
a(peqf ) = (1 + P + . . . + pe) + q(1 + P + . . . + pe) + q2(1 + P + . . . + pe) + . . . + q f(l + P + . . . + p€) = (1 + q + . . . + qf)(1 + P + . . . + pe) = a(qf)O'(pe ) . What is true for the product of two prime powers is true in general:
The Divisors of an Integer Theorem 2. If Ple'P2e, then
•
.
.
53
Pk e• is the primepower decomposition of n ,
Proof. We will use mathematical induction. The theorem is true for k 1 and, as we have just seen, for k 2 . Suppose that it is true for k = r . We will show that this implies that it is true for k = r + 1 . Let =
=
To simplify the notation, let u s write n Np' . Let 1 , d1 , be the divisors of N. Since (N, p) 1 , all of the divisors of n are =
, dt
=
P
Summing, we get
cr(n) = ( 1 + d1 + d2 = cr(N)cr(pe) .
+ . . . +
dt)(1
+P
+ . . . + pe)
But from the induction assumption,
cr(N)
=
cr(Ple ')cr(p2e,) .. . cr(Pke,),
and the last two equations complete the proof.
For example , from 24 cr(24)
=
=
23 . 3 we get
cr(23)cr(3 )
=
(1
+
2
+
4
+
8)( 1
+
3)
=
60 .
.. Exercise 9. Calculate cr(240) .
Both d and cr are members of an important class of numbertheoretic functions: the multiplicative functions . We will now define this term , verify that d and cr are multiplicative functions , and explain why the idea is important. A function f, defined for the positive integers, is said to be multiplicative if and only if
(m,
n)
=
1
implies
f(m n ) f(m)f(n ). � =
54
Section
7
.
A simple example of a multiplicative function is given by fen) = Another i s g , where g (n ) is the product of the prime divisors of n . Theorem 3 .
d is
n.
multiplicative.
Proof. Let m and n be relatively prime. Then, no prime that divides m can divide n, and vice versa. Thus if and are the primepower decompositions of m and n , then no q is a P and no p is a q , and the primepower decomposition of mn is given by
1 , we have d(mn) = d(P le,)d(P.:/,) . . . d(P,/k)d(q/,)d( q l') . . . d( q / ) = d(P ,€'P 2e, . . . Pke,)d( q/'q/' . . . q/) = d(m)d(n).
Applying Theorem
Theorem 4.
a
is multiplicative .
Proof. The proof is exactly the same as the proof of Theorem 3 , with d replaced by a and "Theorem 1" by "Theorem 2 . "
The reason multiplicative functions are important is that i f we know the value of a multiplicative function f for all primepowers , then we can find the value off for all positive integers . To see this, we note
Theorem 5. If f is a multiplicative function and the primepower decomposition of n is p,ep2e, . . . Pke" then
Proof. The proof is by induction on k . The theorem is trivially true for k = 1 . Suppose it is true for k = r . Because we have , from the definition of a multiplicative function , f((p,e'P2e,
.
.
. P /")P r+ /"H )
= f(Ple'P2e,
. . . p /")f(Pr+ le" , ) .
The Divisors of an Integer
55
From the induction assumption, the first factor is
f(P{,pze, . . .p /')
= f(Pl e' )f(P2e, )
. . . f(P/') ,
and this, together with the preceding equation, completes the induction .
For an example, suppose thatf(Pe) = ep " l for all primes p and all e , e 2: 1 . The first few values off are n
f(n)
I
2
3
4
5
6
7
8
9
1
1
4� 1
1
1
12
6
f(3 14 1 ) = f(3 2
•
10
11
12
1
4
349) = f(32)f(349) = 6 · 1 = 6,
and we can calculate fln) for any n in a similar manner. *"
Exercise 10. Compute f(n) for n = 1 3 , 1 4 ,
�
. . , 24 .
We will apply Theorem 5 of this section i n Section 9 t o get a formula for an important numbertheoretic function, Euler ' s function .
Problems " *
" *"
1 . Calculate d (42),
2. 3. 4. 5. 6. 7.
8. 9.
10. ,. 1 1 . 12. 13. 14. t 15.
0(42) , d(420), and 0(420) . d(540), 0(540) , d (5400), and 0(5400) . Calculate d and 0 of 101 15 = 5 . 7 · 1 72 and 100 1 1 5 = 5 . 20023. Calculate d and 0 of 101 1 6 22 . 32 281 and 1 00 1 16 22 . 35 1 03 . Show that o(n) is odd if n is a power of two. Prove that if f(l1) is multiplicative, then so is f(n)/l1 . What is the smallest integer 11 such that d (11) 8? Such that d (n) = 1O? Does d(l1) = k have a solution 11 for each k ? In 1644, Mersenne asked for a number with 60 divisors . Find one smaOer than 10,000 . Find infinitely many n such that d(n) = 60. If p is an odd prime, for which k is 1 + p + . + p k odd? For which 11 is o(n) odd? If 11 is a square, show that d (l1) is odd. If d(l1) is odd, show that n is a square. Observe that 1 + 113 = 413; 1 .+ 112 + 114 7/4; 1 + 1/5 = 6/5; 1 + 1/2 + Calculate
=
•
=
�
.
=
.
•
56
Section
7
1/3 + 1/6 = 1 5/6; 1 + In prove a theorem. *t
t
1 6 . Find infinitely many
n
=
817; and 1 + 112 + 114 + 118
such that
(T(n)
:S
17. If N is odd, how many solutions does x 2
=
15/8. Guess and
(T(n 1). y2 = N have? 

1 8 . Develop a formula for (T (n), the sum of the squares of the positive divisors 2 of n .
19.
Guess a formula for
where k is a positive integer . 20. Show that the product of the positive divisors of n is
n o. Then
s) = 2Hlm  m + (2e+l
 1)s .
Thus
m = (2Hl  1)s , which says that s is a divisor of m and s < m . But (F(m) = m + s ; thus s is the sum of all the divisors of m that are l�ss than m . That is, s is the sum of a group of numbers that includes s . This is possible only if the group consists of one number alone. Therefore, the set of divisors of m smaller than m must contain only one element , and that element must be 1 . That is, s = 1 , and hence m = 2e+ l  1 is a prime. We repeat the argument, because it is slippery. Let the divisors of m (2)
be
Then
(F(m) = m + s , or
= 1 + d2 + ds + . . . + d/ n , and it is deficient if + 1)/2.
and only if O"(n )  n < n . Triangular numbers have the form n (n
Problems 1 . Verify that 2620, 2924 and 17296, 1 84 1 6 are amicable pairs . (The latter pair, discovered by Fermat, was the second pair found. Note that 17296 24 . 23 · 47 and 184 1 6 = 2< . 1 15 1 .) =
2. It was long thought that even perfect numbers ended alternately in 6 and 8. Show that this is wrong by verifying that the perfect numbers correspond ing to the primes 213  1 and 217  1 both end in 6. " 3. Classify the integers 2, 3 , . . . , 21 as abundant, deficient, or perfect.
62
Section 8
4. Classify the integers 402, 403 , . . . , 421
as
abundant, deficient, or perfect .
5. If fT(n ) = kn , then n is called a kperfect number . Verify that 672 is 3perfect and 2 , 178,540 = 22 . 32 . 5 . 72 • 1 3 . 19 is 4perfect. 6. Show that no number of the form 2"3b is 3perfect. 7. Let us say that n is superperfect if and only if fT(fT(n» n = 2k and 2k+1 1 is prime, then n is superperfect.
Show that if
= 2n.

8. It was long thought that every abundant number was even. Show that 945 is abundant, and find another abundant number of the form 3a 5 · 7. •
9. In 1 575, it was observed that every even perfect number is a triangular number. Show that this is so. 10. In 1652, it was observed that 6= 1 28 = 1 496 = 1
+ 2 + 3, + 2 + 3 + 4 + .') + 6 + 7 , + 2 + 3 + . . + 31. .
Can this go on?
I I . Let
p = 3 · 2· 1 , q 3 2(6) = 2, 4>(9) 6, and 4>( 10) = 4. If you worked more exam ples you would almost certainly guess that the following theorem, first proved by Euler, is true: =
Theorem 1. Suppose that m
m).
2:
1 and (a , m) = 1 . Then a�("') '" 1 (mod
We know that the theorem i s true in the special case when m = p , a prime . Every positive integer less than p is relatively prime to it, so 4>(P ) = p  1 , and it is Fermat' s Theorem that a p l "'" 1 (mod p ) when (a , p) = 1 . The theorem is also true if m = 1 , since the definition of the 4>function gives 4>(1) = 1 . In this section we will prove Theorem 1 ,  and we will develop a formula for calculating 4>(n) from the primepower decomposition of n . The idea used to prove Fermat's Theorem is that if (a, p) = 1, then the least residues (mod p ) of a, 2a , . . . , (p  l)a are a per mutation of 1 , 2, . . . , p  1. This is also the key to Euler' s gen eralization:
Lemma 1 . If (a, m ) = 1 and r 1 , rz, . . . , r(m ) numbers r1 > r'J. , , r$( m) we have to show that they are all different and that they are all relatively prime to m . To show that they are all different, suppose that •
•
•
ari "'" arj
(mod m )
for some i andj ( 1 ::; i ::; 1>(m ) , 1 ::; j ::; 1>(m» . Since (a, m) 1 , we can cancel a from both sides of the congruence to get rj "'" rj (mod m ) . Since rj and rj are least residues (mod m ) , it follows that ri = rj. Hence, r; f= rj implies ar; ". arj (mod m ) , and so the numbers in ( 1 ) are all different. =
To prove that all the numbers in ( 1) are relatively prime to m , suppose that is a prime common divisor of ar i and m for some i , 1 ::; i ::; 1>(m ) . Since is prime , either or jr;. Thus either p is a common divisor of a and m or of ri and m . But (a , m ) = (r; , m ) = 1 , so both cases are impossible. Hence (ari ' m ) = 1 for each i , i 1 , 2 , . . . , 1>{m ). The proof of Euler's Theorem proceeds as does the proof of Fermat' s Theorem:
p
p ia p
p
=
Proof of Theorem 1 . From Lemma 1 we know that
r1 r2
•
•
•
r$(", ) """
(ar1 )(ar2 ) . . . (ar$(m»
"'" a 4>(m) (r 1 rZ . . . r$(",»
(mod m ) .
66
Section 9
Since each of r l , r2 ' . . . , 1"$(",,) is relatively prime to m , it follows that their product is, also; thus that factor may be canceled in the last congruence, and we get 1 l!!!l a (m ) (mod m ) .
The rest of the section will be mainly devoted to the properties of 1jJ ; our goal is to find a way of calculating ljJ(n ) by some method other than actually counting all the positive integers less than n and relatively prime to it. Exercise 3.
Verify that the entries in the following table are correct.
/
n ljJ(n )
Exercise 4.
2
3
4
5
6
7
8
9
10
1
2
2
4
2
6
4
6
4
Verify that 34>(8) ;;a 1 (mod 8).
Which positive integers are less than 4 and relatively prime to it? What is the answer if 4 is replaced by 8? By 16? Can you induce a formula for 1jJ(2"), n = 1 , 2 , . . . ?
" Exercise 5.
In general , it is not hard to see what ljJ(p " ) is, wherep is a prime and n is a positive integer. Lemma 2. ljJ(p " ) = p " l (p  1) for all positive integers n . Proof. The positive integers less than or equal to p " which are not relatively prime to p " are exactly the mUltiples of p :
1 · p, 2 · p, 3 · p ,
.
•
.
, (P "l)p,
and there are p " l of them. Since there are in all p " positive integers less than or equal to p \ we have 1jJ(p ") = p"
_
p
'H
= p 'H (P
 1).
For example, the positive integers less than or equal to 27 which are not relatively prime to 27 are 3 , 6, 9 , 1 2 , 1 5 , 1 8 , 2 1, 24, and 27; nine of them, so cp(27) = 27 9 = 9(3  1 ) . 
Euler's Theorem and Function
= 5 and n
=
2.
for all primepowers . If we knew that
4>
was a
Exercise 6. Verify that the formula is correct for p
Thus we know
4>
multiplicative function , then we could apply Theorem get a formula for
67
4>(n).
5 of Section 7 to
That 4> is in fact multiplicative we will now
demonstrate in a theorem whose proof, in common with many other proofs in number theory, is neither long, technical, nor complicated ; it is just hard. First we need an easy lemma:
Lemma 3. If (a ,
m) = 1
and a E
b
(mod
m), then (b, m) =
1.
+ km from some k .
Proof. This follows from the fact that b = a
Corollary. If the least residues (mod m ) of
(2) are a permutation of 0,
1,
. . . , m  1, m.
then
(2) contains exactly 4>(m)
elements relatively prime to We can now prove
Theorem 2.
4> is multiplicative.
Proof. Suppose that
(m , n)
=
1 and write the numbers from 1
to mn as
follows:
1 m + 1 2m + 1 2 m + 2 2m + 2
m Suppose that (m,
2m
3m
(n  1)m + 1 (n  l)m + 2
mn
r) = d and d > 1 . Then we claim that no element in the
rth row of the array:
r m + r 2 m + r . , . km + r . . . (n  l)m + r is relatively prime to mn . This is so because if d i m and d I r, then d I (km  r) for any k . S o , if we are looking for numbers that are rela�
Section 9
68
tively prime to mn , we will not find any except in those rows whose first . element is relatively prime to m .
'" Exercise 7.
How many such rows are there?
For an example, let us take n = 5 and m 1
7
=
13
19
25 26
2
8
14
20
3
9
15
21
27
4
10
16
22
28
5
11
17
23
29
6
12
18
24
30
6. Then the array is
No element in the second, third, fourth , or sixth row is relatively prime to mn = 30, because the fi rst element in each of those rows is not relatively prime to m = 6. All numbers relatively prime to 30 are found in the two remaining rows , (3)
1
7
13
19
25
5
11
17
23
29
Suppose we can show that there are exactly ¢(n) numbers relatively prime to mn in each of the rows that have first elements relatively prime to m . Since there are ¢ (m ) such rows, it will follow that the number of integers in the whole array that are relatively prime to mn is ¢(n)¢(m ) : that is, ¢(mn) = ¢(m)¢(n ) , and the theorem will be proved , But the numbers in the r th row (where r and m are relatively prime) are (4)
r , m + r , 2m +
r,
, . , . , (n  l)m + r ,
and we claim that their least residues (mod n ) are a permutation of (5)
0, 1 , 2, . . , , (n

1).
To verify this claim, all we have to d o i s show that no two of the numbers in (4) are congruent (mod n ) , because (4) contains n elements, just as (5) does. This is easy: suppose that km + r 1i!E jm + r (mod n ) , with 0 :s; k < n and 0 :5 j < n . Then km � jm (mod n ) , and since (m , n ) = 1 , we have k � j (mod n ) , On account of the inequalities on k and j ,
Euler 's Theorem and Function
69
it follows that k = j. Hence, if k i=j, then km + r ". jm + r (mod n ) , and no two elements of (4) are congruent (mod n ) . I n the example above, the least residues (mod 5) of the numbers in (3) are 1
o
2
3
4
0
2
3
4
and each row contains (5) = 4 numbers relatively prime to 30. Thus 8 = (30) = (6)(5). By the Corollary to Lemma 3 , we have that (4) contains exactly (n) elements relatively prime to n . But from Lemma 3, every element in the rth row of the array is relatively prime to m . It follows that the r th row of the array contains exactly (n) elements relatively prime to mn . As we noted before , this is enough to complete the proof.
We can now get a formula for (n ) : Theorem 3 . If n has a primepower decomposition given by
then
Proof· Because is multiplicative , Theorem 5 of Section 7 applies here to give
(n )
=
(Ple')(P 2 e,) . . . (Pj(k).
If we apply Lemma 2 to each term on the right, the theorem is proved .
The best way to . calculate a value for is to use this multiplicative property . For example , to find (72) , factor 72 into 23 32 and write (72) = (23)(32) = 22 . 1 . 3l . 2 = 24. •
" Exercise 8.
Calculate (74), (76) , and (78).
The formula of Theorem 3 can be written in another form, which is neater and sometimes useful , though not for computation:
70
Section
9
The proof of this corollary is left to the reader. We conclude with a theorem we will need in the next section. " Exercise 9.
Calculate
dL in
cp(d)
(a) For n = 12, 13, 14, 15, and 16. (b) For n = 2k, k :2: 1. (c) For n = pk , k :2: 1 and p an odd prime. You should have guessed by now that the following theorem is true . Theorem 4 . If n :2: 1 , then
L
din
cp(d) = n .
Proof. It would be natural to try to apply the formula of Theorem 3 to get this result. This would be difficult; instead we use a clever idea first thought of by Gauss . Consider the integers 1 , 2, . , n . We will put one of these integers in class Cd if and only if its greatest common divisor with n is d. For example , if n = 12, we have .
C 1 = { l , 5 , 7, I l } , C3 = {3 , 9} , C6 = { 6 } ,
" Exercise 10.
'
.
C2 = { 2 , 10} , C4 = {4 , 8 } , Cn = { 12 } .
What are the classes Cd for n = 14?
We have m in Cd if and only if (m . n ) = d. But (m, n ) = d if and only if (m/d, n /d) = 1 . That is, an integer m is in class Cd if and only if mId is relatively prime to n/d. The number of positive integers less than or equal to n/d and relatively prime to n/d is cp(n/d) by definition. Thus, the number of elements in class Cd is cp(nld) .
Exercise 1 1 .
Check that this is correct for n = 1 2 and n = 14.
Euler's Theorem and Function
7J
Since there is a class for each divisor of n , the total number of ele ments in all the classes Cd is
2:
din
That is, n = L cf>(nld) . But din
L
din
cf>(nld ) .
cf>(nld) is the same as
L
din
if,
cf; (n) . For ex
ample, the positive divisors of 9 are 1, 3, and 9, so 2: cf;(d) cf; (3) + cf;(9) and 2: cf>(nld) dl 9
d l9
= cf;(9) + cf;(3) + cf>(1) ;
opposite order. Hence n =
L
din
=
cf;(1) +
the same terms in the
cf;(d) , and the theorem is proved.
Problems 1 . Calculate residues (mod p) of •
•
•
.
.
5 1 , 52'
a , 2a ,
s"( I )g ",,,
(p ; 1 )
! ( mod p ) .
, s" are, by definition, the least
. . . , «p
 1)/2)a
in some order, so that the product 1"[1"2 . . I"kS IS2 · . (mod p) to a (2a)(3a ) · . . « p  1 )/2) a . Thus (4) gives .
a(pJ)f2 (  1)!'
511
is congruent
� ; I } "" � ; I } (mod p ).
The common factor is relatively prime to p and may be canceled to give
a(p I >/2 ( 1)" "" 1 (mod p). If
we mUltiply both sides of the last congruence by (  1) ", we have
Quadratic Reciprocity
97
a (Pl l/2 "" (  1) 11 (mod p). But we know that a (p Il/2 "'" (alp) (mod p). Putting the last two congru ences together, and noting that if the two numbers are congruent (mod p), then they must be equal, we have (alp) = (_ 1)9, and this is what we wanted to prove. 7
Apply the theorem to determine whether x 2 "'" has a solution.
'" Exercise 2.
(mod 23)
We will now apply the last theorem to evaluate (2/p) for any odd prime p . According to the theorem, we need to find out how many of the least residues (mod p) of 2, 4, 6, . . . 2 p ; 1 (5)
, (

)
are greater than (p 1)/2. Since all the numbers in (5) are already least residues, none of them being larger than p , we have only to see ,how many of them are greater than (p  1)/2. Let the first even integer greater than (p  1)12 be 2a. Between 2 and (p  1)12 there are a ' 1 even integers, namely 2, 4, 6, . . . , 2(a  1 ) . So, the number of even integers from 2 to p 1 which are greater than (p 1)12 is the total number of even integers, (p  1)12, minus the number less than (p  1)/2, which is a  I . That is, p 2 1  (a  1) . = '


g
f+Ij
o
2
•••
p l 2
1+1'*)(+11 2a  l
2a
••• 2a + !
p

1
P
But 2a is the smallest integer greater than p ; 1 , so
,
a is the smallest integ�r greater than p � 1 so a  I
is the smallest integer greater than p � 5 , so
98
Section 12
 (a  (a
 1) is the largest integer less than  ( p � 5) , so  _(p � 5) a I
I)
g g
p5
pl    : is the largest integer less than 4 2
is thus the largest integer less than (p + 3)/4.
Exercise 3.
Verify that the entries in the following table are correct. P g
1
3
5
I
l
7 2
11 3
13 3
17 4
19 23 29 5 6 7
Suppose that p "'" 1 (mod 8). Then p = 1 + &/( for some k , and (p + 3)/4 = (4 + 8k)/4 = 1 + 2 k . It follows that g = 2k and that ( 1)" = 1 . From Theorem 1 , (2Ip) = 1 if p is 1 (mod 8). Suppose that p "" 3 (mod 8). Thenp = 3 + 8k for somek, and (p + 3)/4 = (6 + 8k)/4 = 2k + 3/2. It follows that g = 2k + 1 and that ( 1)9 =  1 . From Theorem 1 , (21p) =  1 if p "" 3 (mod 8). Exercise 4.
Check the cases p 50 5 (mod 8) and p == 7 (mod 8).
Thus we have proved Theorem 2.
If p is an odd prime, then (2/p) = 1 if p ",, 1 (2Ip) =  1 if p """ 3
or or
7 (mod 8), 5 (mod 8).
As an example of the use of Theorem 2 , we will state and prove a result that is not used later, but is pleasing. Although we know when a number has primitive roots, finding the actual roots is generally not easy. For example, 2 is a primitive root of 3 , 5 , 1 1 , 13 , 19, 29, 37, 53 , 59, 6 1 , 67, and 83 among the primes less than 1 00 , and it is not a primitive root of the others . No theorem has been proved that will tell which primes 2 is a primitive root of, and it has not even been proved that 2 is a primitive root of infinitely many primes. But we do have
Quadratic Reciprocity
99
Theorem 3 . If p and 4p + 1 are both primes, then 2 is a primitive root of 4p + 1 . Proof. Let q = 4p + 1. Then <J>(q) = 4p , so 2 has order 1 , 2 , 4, p , 2p , or 4p (mod q ) ; w e will show that the first fiv e cases are impossible. We have 221' "" 2('1 1 ) 5 (2Jq) (mod q )
b y Euler' s Criterion . But p is odd, s o 4p ... 4 (mod 8) , and q "'" 4p + 1 ,... 5 (mod 8); we know from Theorem 2 that 2 is a quadratic non residue of primes congruent to 5 (mod 8) . Hence 221' ""
1
(mod q),
so 2 does not have order 2p. Nor can the order of 2 be any of the divisors of 2p , which are of course 1 , 2, and p . Since 2 does not have order 4 either (24 5' 1 (mod q) implies q 1 1 5 , so q = 5, which is im possible) , the theorem is proved .
We will now give Gauss' s third proof of the quadratic reciprocity theorem. It depends on Gauss's Lemma (Theorem 1) and on a lemma we will now prove .
[
Lemma 1 . If p and q are different odd primes , then (1'1)f2
2:
k I
[ P] k
�
+
(q l)12
2:
k=l
k � q
]
=
1 .q 1 . _
_
p
2
2
The notation [kq/p J denotes the greatest integer not larger than kq/p . For example, take p = 1 1 and q = 7 . Then (6)
� [ �� ] = [ ] [ �i ] [ i! ] [ ;� ] [ ii] 7 11
=
+
+
0+ 1 + 1 +2+3
=
7
and (7) = 1+
3 + 4 = 8,
+
+
1()()
Section 12
and (p  l )(q  1 )/4 = 15 = 8 + 7. The numbers have a geometrical interpretation: [3 5/ 1 1 ] is the number of positive integers less than 35/1 1 , and in the figure below that is the number of lattice points (points with integer c oefficients) above the xaxis and below the line y 7x/l l when x = 5 . The other terms in (6) are the number of =
y
3 2
x
4
2
lattice points below the line when x = 1 , 2, 3 , and 4. In the same way , the terms in (7) are the number of lattice points to the left of the line and to the right of the yaxis for y = 1 , 2, and 3. The number of lattice points in the 5by3 rectangle is 1 5 . Exercise 5 . Verify that the lemma i s true for p = 5 and
q
=
7.
[k ] 6 : ;
Proof of Lemma 1 . The idea used in the example works in general . Let
S (p, q)
(1'1)/2 =
we are thus trying to prove that
S(p, q)
+ S (q, p)
= (p

l)(q  1)/4 .
The figure on page 1 0 1 shows the same geometry as the figure on this page, but in general (actually , in the figure on page 101, q = 13 and p = 1 1) Just as in the example , S(p, q) is the number of lattice points below the line y = qx/p and above the xaxis for x 1 , 2, . . . , (p  1)/2 . Also, S (q, p ) is the number of lattice points to the left of the line and to the right of the yaxi s . There are no lattice points on the line, because if (a, b) were on the line, then b = qa/p or bp = qa , and this is impossible. (Since p I bp , we have p I qa and since (p, q) = 1 , it follows .
=
Quadratic Reciprocity
'I  I �
101
y c
D
'1  3 2� 
./
J
.'
2
A
B
2
3
p3 
2
p  I 2
x •
that p l a . But 1 :::; (p  1)/2, and there are no multiples ofp in that interval.) Thus each of the lattice points in or on the boundary of the rectangle ABeD is counted exactly once; on the one hand, this number is S (p, q) + S (q, p ) , and on the other it is «p  l)/2)«q  1)/2) . This proves the lemma.
a :::;
Theorem 4. The Quadratic Reciprocity Theorem. If p
primes, then
(p/q)(q/p)
=
and
q
are odd
( _ 1 ) :s:
q2 = q 3 b + d'].,
o
q 3 = q 4 b + d3 ,
0 :5 d3
d2
q [ > q 2 > q 3 > . . and each q i is nonnegative, the sequence of q ' s will sooner or later terminate. That is, we will come to k such that .
But then n =
=
= do
+ d[b + qzb2 = do + d[b + (dz + q3b)b! = do + d[b + dzb 2 + q3b 3 do + q [b
= do + d[b
do + (dl + qzb)b
+ d2b2 + . . . + dk_ [bk 1 + qkbk
= do + d1b + d2b 2 + . . . + dkbk,
and this is the desired representation. To show that it is unique, we use the same idea we used in the proof of Theorem 2. Suppose that n has two representations:
n
= do + d1b + d2b2 + . . . + dk bk = eo + e 1b + ezb2 + . . . + e k bk
for some k , where
(7)
and
for i = 0, 1 , . . . , k . (As in Theorem 2, there is no loss in generality in assuming that the two representations have the same number of terms .) Subtracting one representation from the other gives
Numbers in Other Bases
111
0 = (do  e o) + (dj  e j )b + (dz  ez)b 2 + . . . + (die  ek)b' . . . , eb fl , fz, . . , fj are even . Thus s and t are squares . .
2 by induction on r as follows . The lemma i s triv ially true for r = 1 and r = 2 . Suppose that it is true for r ::;; n  1 . Note that n has a prime divisor v, and V I s or V I t , but not both. Also , p2 l n z . Apply the induction assumption to nip. Exercise 3 (optional). Prove Lemma
•
Note that it is impossible to conclude from r2 st that s and t are squares if s and t are not relatively prime. For example, 62 = 18 · 2, but neither 18 nor 2 is a square. =
:,
The next lemma gives a condition that fundamental solutions of ( 1 ) must satisfy.
Lemma 3. Suppose that a, b; c is a fundamental solution ofx2 + y2 = Z2, and suppose that a i s even . Then there are positive integers m and n with m > n , (m , n) = 1 and m � n (mod 2) such that
2mn , b = m2  n2, c = m2 + n2•
a =
(Note that w e lose no generality i n assuming that a is even. Lemma 1 tells us that exactly one of a and b is even, so we may as well call the even member of the pair a , b by the name of a.)
Proof. Since a is even, a Z = c2 b 2 follows 
(2)
a
4r2
=
2r
for some r . So,
a '.! =
4r2 ; from
= (c + b)(c  b).
We know that b i s odd , and from the Corollary to Lemma 1, w e know that c is odd too . Thus c + b and c b are both even. Thus we can put 
(3)
c + b = 2s
and
c

b = 2t.
13 1
Pythagorean Triangles
Then c
(4)
=s
+t
and
Substituting (3) into (2) , we get 4r 2
=
b = s  t.
(2s)(2 t ) , or
,.2 = sl .
If s and t are relatively prime, we can apply Lemma 2 and conclude that s and t are both squares . In fact, s and t are relatively prime, as we now show. Suppose that d is and d I t . From (4) it follows that d I b and d i e . But from Exercise 1 , w e know that b and c are relatively prime. Hence d' = ± 1 and (s, t) = 1 . Lemma 2 says that and for some integers m and n , which we may assume to be positive. Thus a 2 = 4r 2
= 4s t = 4 m 2 n 2
o r a = 2mn . From :4) , c = s
b =s
+
t = m2 + n2,
/
= m2  n2•
Having established the last three equations, we need now only estab lish that m > n , (m , n) = 1 , and m ofr n (mod 2) to complete the proof. The inequality follows because b is part oliifundamental solution and hence positive.
Exercise 4. Suppose that
clude that (m , n) = 1 .
d im and d i n . Show that d I a
Exercise 5. Suppose that m
"'" n ""
both even, which is impossible.
0 (mod
2).
and d l b. Con
Show that
a
and b are
Exercise 6. Suppose that m ... n "'" 1 (mod 2) . Show again that a and
are both even.
Exercises 4 , 5, and 6 have completed the pro0f of Lemma 3 . For example , 3 3 , 56, 65 is a fundamental solution, since 1 089 + 3 13 6 = 4225, and from r2 = (5612)2 = 282 = 7" . 42 we get m = 7 and n = 4. They are the right values, since m 2  n2 = 49  1 6 = 3 3 and m 2 n 2 = 4 9 + 16 = 65.
+
33
b
132
Section 16
We have shown that if a , b , c is a fundamental solution, than a , b , and c satisfy the conditions of Lemma 3 . It is also true that if a , b , c satisfy the conditions of Lemma 3 , then a , b , c is a fundamental solution of x2 + y 2 = Z 2 . We prove this in
Lemma 4. If a = 2mn , b = m2  n2, c = m2
+
ni,
then a , b, c is a solution of x2 + y2 = Z2 . If in addition, m > n, m and n are positive, (m , n ) = 1 , and m �n (mod 2), then a, b, c is a fundamental solution .
Proof. To see that a , b, c is a solution is a matter of computation: a2
+ b2 =(1:mnr + (m 2  n2)2 = 4m 2 n2 + m 4  2m 2 n2 + n4 = (m 2
+
n2 )2 = ct .
= m4
+ 2m2n2
+
n4
It remains to show that (m , n ) = 1 and m � n (mod 2) imply that (a, b ) = 1 . Suppose that p is an odd prime such that p i a and p i b . From c 2 = a 2 + b2 it follows that p i c . From p l b and p i c it follows that p i (b + c) and p i (b  c ) . But
b + c = 2m2
and
So, p i 2m2 and p 1 2n2. Since p is odd, this implies that p l m2 and p l n 2 , and hence that p l m and p i n . Since m and n are relatively prime, this is impossible. The only way in which a and b could fail to be relatively prime is for both to be divisible by 2 . But b is odd tecause b = m2  n2, and one of m, n is even and the other is odd. Thus (a, b ) 1 , and because m > n, b is positive. Because m and n are positive, a is positive. Thus a, b, c is a fundamental solution . =
We restate Lemmas 3 and 4 as
Theorem 1 . All solutions x = a, y = b, Z = c to x2 + y2 = Z2, where a, b, c are positive · and have no common factor and a is even, are
Pythagorean Triangles
133
given by
a = 2 mn , b = m 2  n2 , C = m2 + n2 , where m and
m > n.
n
are any relatively prime integers, not both odd, and
Here is a table of some fundamental Pythagorean triangles with small sides: .,
m
n
a
b
c
a
b2
c2
2 3 " c 4 jeJ 4 :c � r, 5 1 ';'::' 5 i in 6 ':� ">i7
1 2 1 3 2 4
4 12 8 24 20 40 12 28
3 5 15 7 21 9 35 45
5 13 17 25 29 41 37 53
16 144 64 576 400 1600 144 784
9 25 225 49 441 81 1 225 2025
25 169 289 625 841 1 68 1 1369 2809
"! "
I
2
Problems *'
1 . There are eleven nonfundamental Pythagorean triangles with hypotenuses less than 50; find them . 2 . Find a fundamental Pythagorean triangle with hypotenuse 265 .
" 3 . Find a fundamental Pythagorean triangle with leg 1 00.
4 . How many Pythagof\;la:1J tri angles (fundamental or not) can you fi nd with hypotenuse 1 105? 5 . If (a , b)
=
d and at
+ bt
6 . If (a , b) = 1 and ab = c
7 . If (a , b) powers.
=
= c t , show that (a , c) = (b ,
/I ,
c) = d.
show that a and b are n th powers .
d and ab = c , show that aid and bid are not necessarily n th "
8 . Bh ascara (ca. 1 150) found a right triangle whose area is numerically equal to the length of its hypotenuse . Show that this cannot happen if the triangle has integer sides. *'
9. In all of the Pythagorean triangles in the table in the text, one side is a multiple of five. Is this true for all Pythagorean triangles ? 10. Show that 12 divides the product of the legs of a Pythagorean triangle. 1 1 . Show that 60 divides the product of the sides of a Pythagorean triangle.
134
12.
Section
16 7
Here is a quadrilateral, not a parallelogram, with integer sides and integer area: (a) What is its area? (b) Such quadrilaterals are not common; can you find another? (c) Could you find 1 ,000,000 more?
20 15
*
13.
Find all fundamental Pythagorean triangles whose areas are twice their perimeters .
14.
Find all fundamental Pythagorean triangles whose areas are three times their perimeters.
t 1 5 . Prove that 3 , 4, 5 is the only solution ofx� + y 2 = Zi in consecutive positive
integers.
1 6 . Show that the only Pythagorean tri angles with sides in arithmetic progres sion are those with sides 3 n , 4n , 5 n , n = 1 , 2 , 3 , . . . .
t 1 7 . 3' + 4t = 5:1 . 5:1 + 1 2:!
=
1 31 . 71 + 24t = 25t . 9:! + 401
=
4P.
(a) Guess a theorem. (b) Prove that the numbers in. (a) give the only Pythagorean tri angles with consecutive integers for one leg and a hypotenuse .
18.
19. 20.
(a) Look in the table in the text and find two Pythagorean triangles with the same area. (b) Can you fi nd two others with the same area? (c) Prove that two Pythagorean triangles with the same area and equal hypotenuses are congruent.
Show that fl ' + (n + If = 2 m t is impossible. (a) 3 1 + 42 st. 20t + 2 P = 292• 1 1 9" + 1 201 = 169" . To fi nd another such relation, show that if a� + (a + If = c " , then =
(30 + 2 c + I)' + (3 a + 2 c + 2)2 = (4a + 3 c + 2)2.
(b) If a' + ( a + 1 )2 c' , let u = c  a  I and v = (2a + 1  c)/2. Show that v is an integer and that lI( U + 1 )12 = Vi. This shows that there are infinitely many square triangular numbers. =
Section
17 Infinite Descent and Fermat's Conjecture
In the section on Pythagorean triangles , we found all of the solutions in integers of x 2 + y 2 = Z 2 . After disposing of that problem , it would be natural to try the same ideas on an equation of one higher degree, 3 x + i'l = Z 3 . The same ideas would not work, nor would any others ; there is no solution in integers of x 3 + y 3 = Z 3 . There is one exceptiona solution in which one of the variables is zero. We will call such a solution a trivial solution , treating it with the contempt it de serves. When we say "solution" in this section, we will mean "nontri vial solution. " In fact, no one knows any solution in integers to any of the equations x II + y n = z " for n ;::: 3. Fermat thought he had a proof that x " + y 1'l = Z n has no nontrivial solutions when n ;::: 3; he wrote a note in the margin of his copy of the works of Diophantus saying that he had a proof, but that the margin was too small to contain it. It is almost certain that he was mistaken, but of course we cannot be cer tain. He may have had a proof. Or, he may have realized how deep the proof must lie and wrote the comment to keep future generations of mathematicians at work. Could he have been such a practical joker? It is not likely: Fermat was a judge, and judges tend to be sober and not given to pranks. " The statement x R + y1'l = z " has no nontrivial solutions if n ;::: 3" is 135
136
Section 1 7
often called " Fermat's Last Theorem" to distinguish i t from the theorem that bears his name (see Section 6), but a better name would be Fermat's Conjecture . An enormous amount of work has been de voted to it,but it is still not settled one way or the other. The conjecture is known to be true for n < 25 ,000 and for many larger values of n , but this is far from a proof. Before the First World War, there was a large prize offered in Germany for a correct proof, and many amateurs of fered attempted solutions . It is said that the great number theorist Landau had postcards printed which read, "Dear Sir or Madam: Your attempted proof of Fermat' s Theorem has been received and is herewith returned. The first mistake is on page line ___ ,
" Landau would give them to his students to fill in the missing numbers . Even though there is no longer a prize for the solution,math ematical amateurs still attempt proofs, and many convince themselves that they have succeeded. They then try to convince mathematicians, fail, and sometimes become quite b itter about what they think is a conspiracy of mathematicians to keep them from getting the recogni tion due them. It is sad. Besides amateurs, many powerful mathe maticians have worked on the problem, and it may be that Fermat's Conjecture is forever undecidable one way or the other. There may exist a solution of x U + y " = Z /I in numbers so large that no one could ever find them . There are,after all, integers so b ig that the world could not hold them if they were written out. If they take up that much room, can they fit into the head of man? The object of this section is to show that Fermat' s Conjecture is true for n = 4, and in so doing, to illustrate Fermat' s method of infinite descent. You might wonder why we avoid considering the case n = 3 . It turns out to be harder to show that x3 + y 3 = Z 3 has no solutions than it is to show that x4 + y4 = Z4 has none, though it is also possible to apply the method of infinite descent when n = 3 . We will prove ___ .
Theorem 1 . There are no nontrivial solutions of
Note that this implies that there are no solutions of x4 + y4 = z\ if a , b , c were a solution to that equation,we would have a4 + b4 = (C2)2 , contrary to Theorem 1 .
InjiniteO Descent and Fermat's Conjecture
137
Proof. We will apply Fermat's method of infinite descent. Consider the nontrivial solutions of X4 + y4 = Z2 . We want to show that there are
none. We will suppose that there is one and deduce a contradjction. Among the nontrivial solutions, there is one with a smallest value of z 2. Let c2 denote this value ofz 2. There may be several solutions with this same value ofz ; if there are, we will pick any one of themit makes no difference which. Call the solution that we pick a , b , c . The idea of the proof is to construct numbers r , s , t that also satisfy X 4 + y4 = Z 2 , with [ 2 < c 2 • Since c2 was chosen as small as possible, it follows that the assumption that there were nontrivial solutions was wrong. Hence there are no nontrivial solutions . This method is no mere trick , but is quite natural. It is very possible that Fermat one day set himself to the task of finding solutions of X4 + y4 = Z 4 ; he may have a plied various devices to reduce the equation in the same way we reduced the equation x2 + y2 = Z 2 ; and maybe he was surpri sed when the result of his efforts was another equation of the same form , but with smaller numbers surprised and pleased too, because this allowed him to conclude that if there was a solution , then there was another smaller solution , and then another and another and another: an infinitely descending chain of so lutions . But since we may assume that x, y, and z are positive, this is impossible. (On the other hand , Fermat may have sat down and thought, " I will now apply my method of infinite descent to X4 + y4 Z4" ; history is silent on the subject.) We suppose that we have a nontrivial solution a, b, c, with c2 as small as possible. We can suppose that a and b are relatively prime. Suppose not. Then there is a prime p such that p / a and p / b, and hence p2 / c . Thus (alp)4 + (blp)4 = (c/p 2)2 provides a solution t o X 4 + y4 = Z 2 with a smaller value of Z 2 than c2, and we have supposed this to be impossible.
p
=
" Exercise 1. Show that
c2 modulo 4 . )
a
and
b cannot both be odd.
(Consider a4 + b4
=
B ecause (a, b) 1 , a and b cannot both b e even, either . Thus one i s even , and look at b2 = m 2  n2 modulo 4 . Remember that x 2 ,..  1 agree to call the even member of the pair a,b by the name of a . But now we have a fundamental solution ofx2 + y 2 = Z2 as defmed in Section 16: =
(a2)2 +
(b2)2 = c2, and b2 is odd.
(a2, b2 ) = 1, and a2 is even Section 16, there are integers odd, such that
In
Hence, by Lemma 3 of and n, relatively prime and not both
138
Section 17
a'l = 2 mn, b'J. = m 2  n2, c = m 2 + n2 •
(1) Exercise 2. Show that
n is even. (Suppose that n is odd and m is m 2  n 2 modulo 4 . Remember that x2 "'"  1
even, and look at bl = (mod 4) is impossible. )
Because n i s even, i t follows that m is odd . Put
n = 2q. Then
from ( 1) , a 2 = 4 mq,
or
(2)
( a ) 2 = mq . 2
We would like to conclude that m and q are both squares. To do that, we need, according to Lemma 2 of the last section, to show that m and q are relatively prime. Exercise 3. Show that
(m , n) I=
1 .)
So , there are integers
(m, q) =
t and
v
1 . (Suppose not, and deduce that
such that and
Exercise 4. Verify that t and
deduce that
v
are relatively prime . (Suppose not, and
(m, q)1= 1 .)
Exercise 5. Note that t is odd. (Suppose not, and deduce that
m
is even .)
a, b,
So far, we have found out a good many things about We need more yet. We start with the obvious observation
n 2 + (m2  n 2 ) = mi . Substituting into this the various facts we know, namely
n = 2 q = 2 v'l., the equation becomes
and c .
Infinite Descent and Fermat's Conjecture
139
so we have another Pythagorean triangle . Is 2 V 'I. , b , t 2 a fundamental solution? It is if 2 v2 and b are relatively prime , and they are . *
Exercise 6.
Supply the reasons for the following implications: ifp 1 2 v'l. and p 1 b , then p i n arid p I b,
ifp l n and p l b , then p l n and p l m , if (m , n) = 1 , then (2 v2, b ) = 1 .
even, we have a fundamental solution of x'l. + y2 = Z2, so we can apply Lemma 3 of the last section to show that there are integers M and N , with (M, N) = 1 and M � N (mod 2), such that With
2 v2
2 v'l. = 2MN,
(3)
b = M2  N2,
Thus we have v'l. = MN and (M, N) = 1 . The product of two rela tively prime integers is a square if and only if both integers are squares (Lemma 2 of the last section) , so there are integers r and s such that and From the third equation in (3 ) , we have (2
=
(r 2 )2 + (S2 )2 ,
or Here is another solution of X 4
+ y 4 = z 'l..
It has the property that
which is impossible, because c2 was chosen as small as possible. This contradiction proves the theorem .
Here is another example of the method of infinite descent. S uppose that there are positive integers a and b such that (4)
�V'3j = � b
'
where the fraction is in lowest terms, so that so
a2 = }h'/. ,
(a,
b)
= 1.
From (4) ,
Section 1 7
140
3(a  b)2
=
3a2  6ab + 3b 2 = 9bz  6ab
+
a2 = (3b  a)2,
from which we get
v3 Jb  a .
.(5) '
=
a b
Since 1 < V3 < 2, from (4) we have b < a < 2b or 0 < a  b < b. Thus the denominator in (5) i s smaller than the denominator i n (4), so we can start with a fraction equal to Y3 and descend through infinitely many others w ith smaller and smaller denominators . Since this is im possible, we conclude that V3 is not equal to a quotient of two integers ,
and so is irrational. This process can be reversed to ascend to better and better rational approximations to V3. If we start with 3/2 and put (3b  a )1 (a  b ) = 312, we get alb = 9/5. Continuing, we get the sequence 3/2, 915, 1217, 33/19, 45/26, . . . or 1 .5, 1 .8, 1 . 7 14, 1 .737, 1 .73 1 , converging to yJ = 1 .732050808 . . . .
Problems 1 . Use the method of the text to show that
square .
vii is irrational if n is not a perfect
2. Why does the method of the text fail to show that vii is irrational if n is a perfect square?
*t 3.
Does
x8 + y B
=
z:5
have nontrivial solutions?
4. Use the method of infinite descent to show that X3 + 3y3 nontrivial solutions.
" 5 . Generalize: does Xl + py3
=
=
9z3 has no
p2z:3 have nontrivial solutions?
6. Generalize: does X4 + py4 + p2Z4 = p3W' we have nontrivial solutions?
* 7. Generalize: does X I " + PX2" + P 2X " + 3 trivial solutions? 8. Show that
Xi
+ y2 + Z2
=
. . .
+ p"2X"_I"
=
p"'x,," have non
2 xyz has no nontrivial solutions .
,. 9. For what values of k does the method used in solving Problem 8 show that there are no nontrivial solutions to x2 + y2 + Z2 kxyz? =
10. Show that there are no nontrivial solutions to Xi + y2 =
x 2y 2 .
=
x2y2 or Xi + y2 + Z 2
Section
18 Sums of Two Squares
Among the integers from 1 to 99, the following as the sum of two squares of integers:
57 are not representable
14 33 54 70 88
15 35 55 71 91
19 38 56 75 92
21 39 57 76 93
42 are: 2 4 5 8 9 25 26 29 32 34 50 52 53 58 6 1 80 81 82 85 89
10 36 64 90
13 37 65 97
1 6 17 18 40 41 45 68 72 73 98
3 6 24 27 44 46 62 63 79 83 96 99
7 28 47 66 84
11 30 48 67 86
12 31 51 69 87
22 23 42 43 59 60 77 78 94 95
But the remaining
1 20 49 74
It would be an exercise of your inductive powers to look at these lists and, in the spirit of the scientific method, try to formulate a hypothesis that would explain the presence of a number on its list and which could be used to predict results for numbers greater than 99. There is a fairly 141
142
Section 18
simple property (other than not being representable as a sum of two squares) that the numbers in the first list share. It is not to your dis credit if you cannot observe what it is, since probably only one mind in a million would have the power and training necessary to see it; but once one mind sees it; others can understand it, see why it is so , appreciate it, and apply it. It is 1. n cannot be written as the sum of two squares if and only if the primepower decomposition of n contains a prime congruent to 3 (mod 4) to an odd power.
Theorem
p is a prime, p � 3 (mod 4), which appears in the primepower decomposition ofn to an odd power. l That is, for some e :2:: 0, p 2 e+ \ n and p2e±2 Jn . Suppose that n x2 + y2 for some x and y . We will deduce a contradictionnamely that  1 is a quadratic residue (mod p). Let d = (x, Y), Xl = x/d, Yl = y/d, and n l = n/d2 • Then
Proof (of the "if" part) . Suppose that
=
and
( 1)
If pi is the highest power of p that divides d, then nl is divisible by and this exponent, being odd and nonnegative, is at least one. Thus p \ n l l and if p lx l ' it follows from (1) that p \ Y I . But (x l ' Y I) = 1 , so p Jx l • Hence there is a number u such that
pU2f+l,
XIU
�
YI (mod p).
Thus
0 "", n l �X12 + YI 2 s Xl2 + (UXI)2 "' XI2(1 + u2)(mod p). Since (x I, p) 1 , X I may be cancelled in (2) to give 1 + u2 ;;;;: 0 (mod p). This says that  1 is a quadratic residue (mod p), which is impossible, since p "'" 3 (mod 4). Hence n = X2 + y2 is impossible , and the easy part (2)
=
of the theorem is proved. The rest of Theorem 1 (the "only if" part) is harder . We will need four lemmas . Lemma
a, b, e,
1.
(a2 + b2)(e2 + d2) = (ae + bd)2 + (ad  be)! for any
and d.
Proof. Multiply it out.
integers
Sums of Two Squares
143
The result shows that if two numbers are representable as sums of two squares, then so i s their product. Rather than "n is representable as the sum of two squares of integers," we will say "n is represent able" for short. Lemma 2. If n is representable , then so is Pn for any k .
Proof. If n
=
x2 + y2 , then k2n
=
(kx)2 + (ky)2 .
Lemma 3. Any integer n can be written in the form
where k is an integer and the p' s are d ifferent pri mes . Exercise 1. Convince yourself that this is so by considering the prime power decomposition of n .
A s an example of the application of Lemmas 1 and 2, we can get a representation for 260 = 22 . 5 . 1 3 from the representations and
1, 65 = 5 · 1 3 = (22 + P)(32 + 22) (2 · 3 + 1 · 2)2 + (2 · 2  1 · 3)2
From Lemma
=
=
82 + } 2.
Hence
'" Exercise 2. Write
325 as
a sum of two squares .
Exercise 3. If the primepower decomposition of n contains no prime p, p � 3 (mod 4) , to an odd power, then note that
or for some k and r , where each p is congruent to
1
(mod 4) .
Exercise 3 and Lemmas 1 and 2 show that to prove the rest of Theorem 1 , it is sufficient to prove
Section 18
144
Lemma 4. Every prime congruent to 1 (mod 4) can be written as a sum of
two squares.
Proof. The idea of the proof is this: if P ""
there are integers x and y such that x2 +
1
(mod 4) , then we show that
= kp
y2
for some integer k, k 2: · 1 . If k > 1 , we then construct from x and y new integers x 1 and y 1 such that Xl! +
Y 12 = k i P
for some k 1 , with k 1 < k . This is the step that proves the lemma, be cause if kl > I , we repeat the process to get integers Xz and Y2 such that X 22 + Y 2 k'lP with k'J. < k l • If we keep on, we will get a descend 2 ing sequence of positive integers, k > kl > k2 > . . . , which cannot be infinite: it must eventually reach 1 . When it does, we have a represen tation of p as a sum of two squares. First we show that w e can find x and Y such that x2 + y 2 = kp for some k, k Since p "" 1 (mod 4), we know that  1 is a quadratic residue (mod p) ; hence there is an integer u such that u2 "'"  1 (mod p ) . That is , p i (u 2 + I ) , o r =
2: 1.
UZ
+
1
=
kp
kp always has a solution for some
for some k, k ;::: · 1 . Hence x + y2 k, k 2: 1 ; in fact, we can take Y 1 . For example, if p = 17, we have 42 + P = 1 · 1 7 ; if p = 29, 122 + F 5 · 29. The number u can be found by trial (we can write kp  1 for k = 1 , 2, . . . , and continue 2
=
=
=
until we come to a square) , or we can use the fact that
( ( p1 ) ! ) 
2
2
_
,.,..
 1 (mod p).
The last congruence (which follows from Wilson' s Theorem) gives a construction for u : a long one, perhaps , but one which guarantees a result. We now show how to construct Xl and Y l . Define r and s by
(3 )
r EX
(mod k),
s ;;;;;; Y
From (3) , r2
(mod k),
+ S2 ... x2 + y2
(mod k ) .
But we had chosen x and Y such that x 2 + y2
= kp .
Hence
Sums of Two Squares
145
or
(4) for some k 1 • It follows from
(4) that
(r2 + S2) (X2 + y2) = (k1k)(kp ) = k j Pp . From Lemma 1 , however, we have
Thus
(5)
(rx + sy )2 + (ry  sx)2 = k 1 k2p .
Note that from (3), rx + sy � ,.2 + S2 "" and ry

sx "'" rs  sr ...
0 (mod k) 0 (mod k) .
Thus k2 divides each term on the lefthand side of (5); dividing (5) by P , we get
(
rx
� SY f + (ry � sxr
=
k IP ,

an equation in integers . Let X l = (rx + sy)/k and Yl = (ry sx)/k . Then X 12 + Yl2 = k I P, and the lemma will be proved when we show that k l < k. The inequalities in (3) give r2
+ S2 �
(k12)2 + (k/2)2 = P/2 .
But
Thus k l k :S k2/2 or kl :S k /2 . Hence kl < k, and to complete the proof of the lemma, we need only to note that kl � 1 . If kl = 0, then from the last equation, r = s 0 It follows from (3) that k l x and k l y . Thus k i p, so k = 1 or p. If k = 1 , then x2 + y2 = P and the lemma is proved , and if k = p, then u2 + 1 p2 , which is impossible. =
.
=
Let us take an example. Starting with 1 22 + 12 5 · 29, we will carry through the calculations of the lemma to get a representation of 29 as a sum of two squares . We have x = 12;y = 1 , and k = 5. We have r "" 12 =
146
Section 18
(mod 5) and s ;;;;; 1 (mod 5) ; choosing r and s in the proper range, we get r =
2 and s
=
52 . 29
=
1 . Then
(22 + 12 )( 1 22 = 252 + 1 02 •
+
Dividing by k'l = 25 gives 29
F) =
=
(2 · 1 2 + 1 · 1 )2 + (2 · 1  1 · 1 2)2
52 + 22 , the desired representation.
Exercise 4. Try the calculation for
232 + 12
=
10 · 53.
We will end with some remarks on diophantine equations closely related to the sum of two square s . We have completely solved the problem of representing integers as the sum of two squares: we know which integers can be so represented, and Lemma 4 , combined w ith earlier lemmas, gives a method for actually calculating the representa tion. It is natural now to wonder about the representations of integers as the sum of three squares . We would expect that more integers can be represented when we have an extra square to add, and this is the case. It is a fact that n can be written as a sum of three squares , unless n = 4e(8k + 7) for some integers e and k . So, the numbers smaller than 100 which cannot be written as the sum of three squares are
7 , 1 5 , 23 , 28, 3 1 , 39, 47 , 55 , 60 , 63 , 7 1 , 79, 87 , 92, 95; a total of 1 5 , as against 57 when only two squares were allowed. There are even fewer exceptions if we look at sums of four squares ; in fact, there are none at all. E very i nteger can be written as a sum of four squares, as we will show in the next section.
That would seem to settle the squares . That is , as far as the mere representation is concerned. Of course, there are many, many other questions that can be asked, and some that can be answered. For example , how many representations does an integer have as a sum of two squares? What is the sum of the number of solutions ofx2 + y2 = n2 for
n=
1 , 2, . . . , N? And so on; as soon as one question is settled ,
others crowd i n t o take its place. What about cubes? I t is true that every integer can be written as a sum of nine cubes . No one knows what the corresponding number is for the sum of fourth powers (though it is known that every integer greater than 1 010"" is a sum of 19 fourth powers) , but the answer is known for fifth, sixth, seventh , and almost all higher powersfor example, 37 fifth powers will do. Let g(J 0 and N is not a square . With these assumptions, it is always possible to show that x2 Ny2 = 1 al ways has a solution other than x = ± 1 , y = O. We will accept this result on faith and not prove it. There are two methods for proving the exis tence of a nontrivial solution: one depends on developing the extensive machinery of continued fractions, and the other (first constructed in 1842 by Dirichlet, who improved a proof given by Lagrange in 1766) is not short. B ecause 
x2  Ny! = (x + y YN)(x  y YN), irrational numbers of the form x + y vN are closely connected with solutions of Fermat's Equation . They also have several important properties, which we develop in the following lemmas . We will say that the irrational number a
= r + s VN
integers) gives a solution of x2  Ny2 = 1 if and only if 1 For example , 3 + 2 y'2 gives a solution of x2  2y2 and 8 + 3 v'7 gives a solution of x2 7y2 = 1 .
(r and s are r2  NS2 = 1.
=

158
Section 20
Lemma 1 . If N > 0 is not a square, then
if and only
x + y V'N = r + s YN ifx = r and y = s.
Proof. If x = r and y = s, then clearly x + y VN = r + s vN. It is the converse that is important. To prove it, suppose that x + y vN = r + s vN and y f= s . Then � r:;
x r v N = s y
VN is
is a rational number . But since N is not a square , It follows that y = s , and this implies x = r.
irrational .
a, b, e, d, N, (a2  Nb2 X eZ  Nd2) = (ae + Nbd)2  N(ad + be)2.
Lemma 2. For any integers
Proof. Multiply it out. For example, (22  3 , 12)(72  3 '42) = ( 14 + 3 ' 1 . 4)2  3(2 . 4 + 1 ' 7)2 = 262  3 . 152 , and this is in fact correct:
(4  3)(49  48) = 676  675.
Lemma 3. If a gives a solution of x2
Proof. Let a have
= r + s VN .
 Ny2 = 1 ,
then so does
Then we know that r2
 Nsz = 1 ,
1 r  s VN = r  s VN r r t' s \INN r  s VN a r2  N.s 2 =  s N since r2 + N( sf = 1 , the lemma is proved. 1
Lemma 4. If a and f3 give solutions of Xi
110'.
 Ny2 = 1 ,
and we
. 1.: V
N;
then so does af3.
= a + b vN and f3 = e + d VN. Then af3 = (a + b VFJ)(e + d VN) = (ae + Nbd) + (ad + be) vN and from Lemma 2 we have
Proof. Let a
x2

Ny 2
(ac + Nbd)2  N(ad + bC)2 = (a2  Nb2)(C2  Nd'l) = and this shows that
af3
= 1
159
1,
gives a solution.
* Exercise 3. Two solutions of x 2

8y2 =
1 are
(T, y) = (3 ,
1) and ( 1 7 ,
6).
Apply Lemma 4 to find another .
Lemma 5. If a gives a solution of x2 integer k, positive, negative, or zero .

" Exercise 4 (optional). Prove Lemma
Ny2
=
1 , then so does
5. First show that it is
ak for any true for all
k ;:::: ,1 by applying Lemma 4 and induction. Then show that it is true for k :5  1 by applying Lemma 3. Then consider the case k = o. .
Lemma 5 shows that if we know one number solution of x2

given by ak, k
a k+l > a ir
x2 
2y2
for
=
=
a, a >
1 , which gives a
1 , then we can find infinitely many, namely those 2, 3 , . . . . The solutions are all different, because all k. For exampl e , 3 + 2 V2 gives a solution of
Ny2 =
1 . So, then , do
(3 + 2 Y2)2
=
17 + 1 2 V2
and
(3 + 2 V2f
and higher powers of
=
2 y2
=
=
2+
nontrivial solutions.
(3 + 2 Y2)2
=
99 + 70 v'2
and
(3 + 2 Y2)3
V3 gives a solution of x 2  3y2
Lemma 6. Suppose that a
+ 2 Y2)
give solutions of
1.
'" Exercise 6. a
a =a +
\12)(3
3 + 2 V2.
" Exercise 5. Check that
x'l 
( 1 7 + 12
b VN and f3
=
c +
< f3 if and only if a < c.
=
1 . Find two other
a, b, c, d are nonnegative and that d VN give solutions of x2 Ny? = 1 . Then 
1 + Nb2 and < c . Then a2 < c2 and because a2 Nd2 we have Nb2 < NJ2. Because none of b, d, N are negative, it follows that b < d. Together with a < c, this gives a < f3. To prove the
Proof. Suppose that a
c2 =
1 +
=
Section 20
160
converse, suppose that a < f3. If a � c, then a2 2= c2• From this follows b2 2= d2, which implies a 2=. f3. Since this is impossible, we have a < c .
·
Now we are in a position to describe all the solutions ofx2  Ny2 = 1 . Consider the set of all real numbers that give a solution ofx2 Ny2 = 1 . Let () be the smallest number in the set greater than one. Note that Lemma 6 guarantees that there will be such a smallest element, be cause the members r + s VN of the set can be ordered according to the size of r, which is an integer, and any nonempty set of positive inte gers contains a smallest element. We will call () the generator for x2 Ny2 = 1 , and we can now prove 

1. If e is the generator for x2 Ny 2 = 1 , then all nontrivial solutions of the equation withx and y positive are given by ()k, k = 1 , 2,
Theorem

Note that the restriction ofx and y to positive values loses us nothing essential, because nontrivial solutions come in quadruples { (x,
y ) , (T, y) ,
( x , y), ( x ,
y) } ,
and exactly one solution has two positive elements . Note also that we say nothing about the existence of a generator . It is a fact, as was noted earlier, that such a number can always be found. There is a method for getting 8 from the continued fraction expansion of VN by an easy calculationeasy in the sense that a computer would make light work of it. For some values of N, the computation is quite tedious . Of course, a generator can be found by trial, and for a long time, this was the only method available. In the seventh century, the Indian mathe matician Brahmagupta said that a person who can within a year solve x2 92y2 = 1 is a true mathematician. Perhaps, and perhaps not; but such a person would at least be a true arithmetician, because the generator is 1 15 1 + 120 \1'92. Solution by trial can also be difficult for so innocentseeming an equation as x2  29y2 = 1 ; its smallest positive nontrivial solution isx = 9801 and y = 1820. The equation x2 61y2 = 1 has no positive nontrivial solution untiIx = 17663 19049, y = 226153980. You can verify that this is a solution by multipljcation, if you wish. 

Proof of Theorem
1. L et x
= r,
y =s
be any nontrivial solution of
x2  Ny2 = 1
161
x2
 Ny! = 1 with r > 0 and s > O. Let a = r + s YR. We want to show that a = fJ'< for some k. We know that a � (J by the definition of generator, so there is a positive integer k such that
(Jk :::; a
2 n . Then [2 nlpr] = [2nlpr+ l ] = = 0, so the sum in Lemma 2 ends after r [n/pr+ l ] = .
.
(2)
.
r
.
=
([2nlp 1

"
= 
( )
2n . n 0, [ nip)'] = 1 terms:
Proof. Suppose that pI" is in the primepower decomposition of
2[n/p]) + ([2nlp2 ]  2[nlp2]) + . . .
+ ([2n/prt ]  2[nlpr t ] ) .
But from Lemma 3, each of the terms i n parentheses i s at most 1 . Thus (2) says that r :$ 1 + 1 + . . . + 1 (r  1 terms) or r :5 r 1 , which is impossible. Thus pl" :5 2 n . 
We next need bounds on
( ) 2n n
.
Proof. We will use mathematical induction. The lemma is true for n
=
1 because
(
(�
=
2. Suppose that it is true for n = k. Then
)
2(k + 1» k + 1
(2k + 2) ! « k + 1) !)2 =
2(2k + 1 ) k + 1
(2k + 2)(2k + i')(2k ! ) (k + l)k !(k + l)k !
( ) 2k k
.
Bounds for nix)
On the one hand ,
( )
2(2k + 1) 2k k+l k
)'''('')
n (In x )/(2 In 2 ) , and it follows that
But In x
n(x) 3 2 1n 2 , < x In x 

which is what we wanted.
Problems *t 1 . (a) What is the highest power of 2 that divides (b) For which n does 2" divide 11 ! ?
C;!)
2. Pro ve by
t
>
2tH / vn for n
f ( 2 11)
0
11
?
induction a stronger version of part of Lemma
3 . Prove that i f n < p . tlOn
1 984!
?:
5,
namely
I.
oS 2n , then p appears in the primepower decomposi
to the power 1 .
4. Prove that if p is odd and 2 n /3 < p
. . . ( 2 n) pnmepower decomposltlOn of 11 •
t 5 . Let p.. denote the n th prime . If 7r(x)
oS
oS 11 ,
then p does not appear in the
ax /I n x, show that p.
2:
�
a
n In
11 .
Section
22 Formulas for Primes
In the earlier days of mathematics, there was a feeling that " function" and "formula" were more or less synonymous. Today, the notion of function is more general. but many of us still feel more comfortable with a function if we have an explicit formula to look at. There is no difference , really, between fin ) is the largest prime factor of n and G . H . Hardy's formula fen)
=
lim lim lim
r�oo $+00
s
2:
t+'YJ u=o
[1

(COSZ (ll !y7Tln )21 ] .
The first expression is simpler, but perhaps the second lets us feel that we somehow have more cl:mtrol over f (Some primitive people believe that if you know a man's name , then you have power over him. It is the same principle. ) The importance o f formulas is of course not psychological but prac tical: in general , a formul a will let us compute things of interest . Thus the formul a above is less useful than the verbal description: it obscures whatfis, and it does not lend itseifto computation. But if we agree that formulas in general are nice things and worth having. then it is reason172
Formulas for Primes
173
able to search for them . We might ask for a formula for Pn , the n th
prime. But the primes are so irregularly scattered through the integers
that this is probably beyond all reason. The next best thing would be to have a formula that would produce nothing but primes . The aims of this section are to show that no polynomial formula will work , to exhibit a formula which will (but which is not adapted to computation) , to prove that there is a prime between n and
2n for all positive integers n,
use this to get another formula for primes .
and to
The simplest sort of formula to consider is
fen ) = an + b. If we found such a function that gave nothing but primes , then we would have an arithmetic progression, with difference
a,
consisting
entirely of primes. Looking through tables of primes, we can find vari ous arithmetic progressions of primes , but none of infinite length: for exampl e ,
3 , 5 , 7; 7, 37, 67, 97, 127 , 1 57; 199, 409, 619, 829, 1039, 1 249, 1 459, 1669, 1879, 2089. But no infinite arithmetic progression can be made up entirely of
pta,
so (a, p) = 1 ar '" b (mod m ) . Then a(r + kp) + b ",. ar + b "'" 0 (mod p)
primes , as we now show. Suppose that there is an integer r such that
for k
= 0,
I, .
.
and hence
. , so every pth term o f the sequence is divisible b y p.
The longest arithmetic progression known th at consists entirely of primes is
223092870n + 22361 3394 1 for n = 0, 1 , . . . , 15 [7], and it is
. not known if there exist arbitrarily long arithmetic progressions of primes. After seeing that a sequence
{an + b }
cannot consist entirely of
primes, it is natural to ask whether the sequence can contain infinitely many primes . The answer to this is given by Dirichlet' s Theorem: If
(a, b) = I , then the sequence {an + b } contains infinitely many primes. For example , among the members of the sequence {4n + 1 } are the primes 5 , 1 3 , 17, 29, 37, 41 , . . . , and among { 12n + 7} are 7, 19, 3 1 , 43, 67, . . . ; Dirichlet's Theorem says that we will never come to a last prime in either sequence. The condition (a, b) = 1 is clearly neces sary: {6n + 3 } contains only one prime and { 6n + 4} contains none . Dirichlet's great achievement was in showing that the condition was
174
Section 22
also sufficient. The proof of this theorem is not at all easy, and we will not attempt it. However, some special cases are easy. Consider { 3 n + 2 } , suppose that there are only finitely many primes in it, and call them P I > P2 , . . . , Pt· Let N = P I P 2 . . . Pk . I f N "'" 1 (mod 3 ) , then N + I ,... 2 (mod 3) and thus must have at least one prime divisor congruent to 2 (mod 3) (otherwise N would be congruent to 1 (mod 3)) . But N + 1 � 1 (mod p,J , so whatever prime divisor it has is not one of P I , P2 , . . . , Pk. If N "'" 2 (mod 3 ) , then N + 3 "'" 2 (mod 3), and N + 3 must have a prime divisor congruent to 2 (mod 3). But N + 3 a 3 (mod Pk), so its prime divisor is not one of PI , P2 , . . . , Pk either. This is impossible so the assumption that there were only finitely many primes in the sequence was wrong. No polynomial can have only prime values, either. Iff(n ) = aonk + a t ntI + . . + at. and if r is such thatf(r)"" ° (modp) for some p , then fer + mp ) ""' f(r) "'" ° (mod p) for m = 1 , 2, . . . . Just as with arithmetic progressions, if one term is divisible by P, then every pth term from there on is also divisible by p . The champion quadratic polynomial for having consecutive prime values is n2 + n + 4 1 , found by Euler . It has a prime value forn =  40, 39, . . . , 39. However, 402 + 40 + 4 1 = 4 1 2 , and every fortyfirst term in the sequence {n2 + n + 4 l } is divisible by 4 1 . The analogue of Dirichlet' s Theorem for higherdegree poly nomials would be that { aon'" + a t ntI + + at} contains infinitely many primes if ao , a t , . . , a t have no common factor. No such theorem has been proved , and it is not even known if n2 + n + 4 1 is prime infinitely often, though it seems unlikely that this should not be so. On the other hand , we can construct a polynomial that assumes as many consecutive prime values as we want, because if can be shown that it is always possible to make a polynomial of degree d take on d + 1 arbitrarily assigned values . For example, if .
.
.
.
.
60f(x )
=
7x'  85x� + 355x3  575x2 + 4 1 8x + 1 80,
then we have n fen )
I�
1 5
2 7
3 11
4 13
5 17
A similar polynomial could be constructed to take on 8 1 consecutive prime values , but it would be of degree 80. After giving up on polynomials, it would be natural to try expo nential functions. For example, if
Formulas for Primes
175
fen) = [ (3 /2)" ] , n = 2, 3 . 4. 5, 6 , 7 (the values of the function are 2 , 3, 5, 7 . 1 1 , and 17), but f(8) = 25, and the next prime in the sequence does not come unt il f(2 I ) = 4987 . No one h as prov ed that a formula like fe n ) = [0" ] cannot always give a prime. Nor is it known then f( n ) is prime for
whether [0" ] can be prime infinitely often. Such questions seem hopelessly difficult. Nevertheless, there do exist functions, expressible as a simple
formula, that always represent primes . We will prove , partly . a striking result of Mills
Theorem
[1 1 ] :
1. There is a real number 0 such that [tfl"] is a prime for all
n, n = 1 , 2, . . . .
As we shall see, this theorem contains less than meets the eye , and
it should not seem nearly so striking after we finish the proof. The
proof gives a construction for O . but the construction depends on being able to recognize arbitrarily large primes . If we could recognize arbitrarily large primes . we would have no need of the formula. In the proof we will use two theorems from analysis.
Theorem.
If a sequence lI j , lit, lI 3 , . . . , lI",
•
.
.
is bounded above
and nondecreasing, then it has a limit. 0, as n increases without bound.
That is, if there is a number M such that
un :::; U,,+I
for all 
n, n
=
1 , 2,
.
Un < M
for all n and
. . , then there i s a number 0 such
that the difference between e and
u"
Theorem.
•
becomes arbitrarily small as
n
increases without bound . We will not prove this theorem, or the next.
If a sequence
V 1 > V2 , V 3 ,
.
•
, Vn •
•
•
•
is bounded below
and nonincreasing, then it has a limit, r:p , as n increases without bound.
We will write and and read "the limit of
Un
as
corresponding statement for
lim
Vn
= r:p
n approaches infinity equals 0 , " and a
v".
1 76
Section 22
Proof of Theorem 1 . The proof depends on the following theorem: there is an integer A such that if n > A , then there is a prime P such
that (1)
We will not prove this but we will use it to determine a sequence of primes that will in turn determine e . Let P I be any prime greater than A , and for n = 1 , 2 , . . . , let P ,,+ 1 be a prime such that (2)
Such a prime exists for each n on account of ( 1 ) . Let
(3)
and
n
= 1 , 2, from (2) ,
v" =
(p" + lr',
. We see that as n increases, u" increases, because
(4 ) Furthermore, {v n } is a decreasing sequence, because from (2) ,
(5) V n+! = (p ,,+! + It is clear from
1 VH < «P"
(3)
+ 1)3

1 + 1 ) 3 = (p" + 1) 3." =
VIl"
that u " < v". Hence, because of (5), U"
< V ,,
for all n ; thus for all n But from the definitions of u " and _
u ,/' = p "
and
Un ,
UTt = p " + 1 .
Thus
p " < (J3"
< Pn
+
1.
This locates ()3" between two consecutive integers, and so
1 77
Formulas for Primes
[ If''] a prime , for all
= P ll '
n.
From the construction, we see that knowledge of () and knowledge of all the primes is essentially equivalent, so that the theorem gives us nothing that we did not have before , except perhaps pleasure at seeing a clever idea neatly worked out. The theorem would be important only if we could discover what () is by some method independent of all the primes, and this IS not likely . To prepare for getting another formula for primes, we will derive a result of independent interest, Bertrand's Theorem : Theorem 2. For all n 2:
2 there
is a prime p such that
n < p < 'In .
Proof. Just as in the last section , we will need properties of
we will need to recall the binomial formula (6)
(x + y)"
= x"
+
(� )
X " ly +
(n ) x 2
" 0 II  7
+ . . . +
(n n 1 ) 
( 2�1 ) , and xy "  l
+ y" ,
tme for any x and y . We will assume that for some n there are no primes p such that n < p < 2n , or what is the same thing for n < p :::; 2n , since 2n is not a prime when n 2: 2 . We will show that this implies that n < 2788 , so that the theorem is true for n 2: 2788 . By checking the cases n = 1 , 2 , . . , 2787 , we can then complete the proof. First we will show that for n 2: 2, .
(7) Thi s is not a strong inequalityfor n = 10 it asserts only that 2 1 0 :s 1048576but it is all that we need . The binomial expansion of (1 + 1 )2 111+1 is (1 + 1 )2111 + 1
=
1+
(2m t 1 ) + . . . + (2mm+ 1 ) + (2::;: 11 ) + cr;; 1 ) . . . +
+ 1
178
Section 22
2:
e ":n+ 1 )
e:: / )
+
The two terms are both equal to
(9)
 ..
(2m + 1)(2m) . . . (m + 2) 1 m(m 1) .
(8)
so 2 2>1H I 2: · 2
.
(2 m + 1 ) or m
C":n+ 1 ) 2 . 2 m 2:
( 2m + 1 ) . . 'ble by each pnme IS d'IVIS1 p such that m + 1 < p :5 ' m 2m + 1 , as inspection of (8) shows. Thus
Also ( 10)
Now we can prove (7) by mathematical induction . It is true for n = 2. Suppose that it is true for all n :5 k . If k is odd , then k + 1 is even, and ( 1 1)
IT
If k is even, say k (12)
=
p"'k+1
p =
2m , then
J�L p
=
IT p
psk
:5 22k < 2Z(k+ ! l .
CIt ) C+lJlm+l p
p
)
where the induction assumption was used on the first product and ( 1 0) on the second . ( 1 1) and ( 12) complete the induction . ( 2: ) Remember that we have assumed that = N has no prime divi sors p such that n < p :5 2n . But
N
=
 1) ' .  1)
(2n)(2n n(n
(n + 1 ) . . . 1
so if 2n/3 < p :5 n , then p is a factor in the denominator, and since 2p > 4n/3 2: n + 1 , 2p is a factor in the numerator. The two p ' s cancel, and since 3 p > 2n , there are no more factors of p in the numerator. Thus all of the prime divisors of N are at most 2n/3 , so 4,,/3 (1 3) p :5 2 ; IT ps;Z,,/3
the last inequality comes from applying (7).
Formulas for Primes
1 79
We will use ( 1 3) to get an upper bound for N . From Lemma 4 of Section 2 1 , we know that each prime power in the primepower decomposition of N is at most 2n . So , if p appears in the prime power decomposition to be a power greater than 1 , then p 2 · :5 2n and p :5 v2ri . There are at most V2ii such primes, and since each prime power is at most 2n, their contribution to the primepower decomposi tion is at most (2n)v'2n . All of the other primes appear to the power 1 , and from ( 13) , their product i s at most 2471/3 . Thus
C: )
( 14)
:5 24n /3 (2n) V2n.
On the other hand, mathematical induction shows that ( 1 5)
(
because
(
2n + 2 n +2
)
( ) 2n n
2: . 22 n
2n
( )
(2n + 2)(2n + 1) 2 n 2: . 2(2n + 1) 22" (n + 2)(n + 1) n 11 + 1 2n 2n + 1 2271+ 2 > . 22 >1+ 2 , 2n + 2  2 n + 2 2n
=
=
)
so combining ( 1 4) and ( 1 5) we get
and this does not hold if n is too large. Taking logarithms , we get 2n In 2  In 2n :5 (4 n/3) In 2 + V21l In 2n or (2n/3) In 2 :5 (V2ti + 1) In 2n :5 (v2n" = 2 V2 vn In 2n or _
I
2787. The sequence of primes 2, 3 , 5, 7, 13, 23, 43 , 83, 163 , 3 17, 63 1 , 1259, 2503 , 9973 , each less than twice the one before , shows that for n :5 2787 there is always at least one prime between n and 2 n .
We can use this to get another formula for primes like the one in Theorem 1, but which does not deperid on an unproved theorem [ 16] .
180
Section 22
Choose any PI and for n
= 1,
2 , . . . , let P n + 1 be a prime such that
(16) such a prime exists because of Theorem 2. Let ( 17)
I =
U" =
=
v"
log(ll)p ,u
log(n)(p" + 1 ) ,
where 10g lk logz k and loge>!) k = logz(log(,, l ) k ) . Taking logarithms to the base 2 in (16) gives p" < logz p n+ l < p,, + 1 , and since P,,+l + 1 :S 2P"+, , we have p" < 10gWPn+l
< 10g{ I ) (Pn+l +
1) :S p " + l .
If we take logarithms to the base 2 of the preceding inequalities n times, we have So, as in the proof of Theorem 1 , 8 lim U n and 0, d i n and (d, nld) = 1 , then d is called a unitary divisor of n . (a) What are the unitary divisors o f 1 20? Of 360? (b) Which integers are such that their only divisors are unitary divisors? (c) If n = P , " P 2 " " 'Pt " , how many u nitary divisors has n ? (d) If
where the sum is taken over the unitary divisors, d, of n, then n is called a unitary perfect number. Find two such numbers . 15. Here is Euler ' s original proof of Theorem 2. Fill in any missing details. Let n = 2km be perfect, m odd. The sum , (2k + !  I)o(m) , of the divisors of n must equal 2n. Thus
ml 7, such that cp (n )
""
2 k is impossible .
Section 1 0
'" 1.
I f (a, m ) 1= 1 , for what values o f t i s
at ""
1 (mod m)?
2. Which of the integers from 1 975 to 1 98 5 have primitive roots?
1 90
Section 23
* 3 . Find the smallest prime which has 10 for a primitive root.
4. Show that 2 is not a primitive root of 3 1 .
* 5 . Student A says, " Look. These five pages of computation show that 1 9831fMl3 ,," 1 (mod 1 024) . Isn't that amazing?" Student B says, after a glance, " No , it' s not amazingit' s wrong. " How did B know that without checking the computations?
6. Show that if (n. p 
1) =
1 , then x· "" a (mod p) has exactly one solution.
t 7. If n is a positive integer , define aII by
an "" r (mod p)
n
Prove that if m and
ran ... 1 (mod p). 
if and only if
are positive i ntegers, a "'a · ... a "'· (mod p).
8. With the notation of Problem 7 , prove that (a"')"
�
a "UI (mod p).
* 9. It is well known that at = k if and only if t = loga k . Let us define the
of an integer (mod p) analogously. If g is a primitive root of p. then t g "" k (mod p )
10.
i f and only if
index
t "" indo k (mod p  1 ) .
Calculate ind2 k (mod 1 9) for k = 1 , 2 , . , 18. With the notation of Problem 9 , prove that indo ab "" indo a + indo b (mod p  1 ) .
t 1 1 . With the notation o f Problem 9 , prove that
indo a n ..,
n
ind.. a (mod p  1 ) .
1 2 . Use the results of Problems 9 and t o t o solve 13x "'" 1 6 (mod 19). 13. Use the results of Problems 9 and 1 1 to solve 14. Suppose that ind2(P  I ) ind2 x = r + 2?
= r.
xu",
Show that ind2(p  2)
16 (mod 19). = r
+
1. What is
x
if
t 15. Prove the following generalization of Wilson' s Theorem: '"
IT
n
"�1
( " ;,,, )  1
""
{I
(mod m ) if m has a primitive root
I (mod m ) otherwise.
Section 11 * 1 . Solve x� 5).
'"
+x +
1
�
0 (mod 5), x:! + X = 0 (mod 5), and x!
+x  I�
0 (mod
2. Find quadratic congruences (mod I I) with solutions 5, 6 ; 5 , 7; and 9, t o .
3 . Find the quadratic residues (mod 3 1) .
4. Use Euler's Criterion t o calculate (mod 23) 21 1 , 3 1 1 , 41 1 , 5 1 1 , 221 1 , and 2 1 1 1 .
Additional Problems
'" 5. For which of p
=
3, 5, 7, 1 1 , 1 3 , and 17 is
Xi ""
19]
 2 (mod p ) solvable?
x2 ""
6. (a) How many solutions does 1 (mod 16) have? (b) But don't quadratic congruences have two solutions or no solutions? What' s wrong?
'" 7. Does Xi ... 53 (mod 97) have a solution? Does x· "" 97 (mod 53)?
8 . Suppose that p "" 1 (mod 4). Then x' '''  } (mod p ) has two solu tions: call them i and i. Prove or disprove: a + bi "" 0 (mod p) implies a '" b '" 0
(mod p). *t 9. If p "" 7 (mod 8) and (p (mod p)?

1 )/2 is prime, is (p  1 )/2 a quadratic residue
10. Suppose that p = q + an', where
(a lp) = (alq )?
p
and q are odd primes . Is it true that
Section 12 *t
1 . Theorem 3 had for its hypothesis: "If p and 4p + 1 are both primes Examples are 7, 29 and 1 3 , 53, and in each of these the third number in the sequence (4 · 29 + 1 1 17 and 4 · 53 + 1 = 2 1 3) is not prime. Would a computer search help in discovering longer sequences such that p, q = 4p + 1 , = 4q + 1 , s 4r + 1 , . . . are all primes? =
r
=
2. (a) Show that if p i (n2 + 2 an + b) for some (b) Which primes can divide n 2 + 2 n + 2 ?
n , then « at  b)/p ) =
1.
* t 3 . (a) Show that n2 + ( n + 1 ) 2 + (n + 2)2 m2 is impossible. (b) Show that n' + (n + 1 )2 + . . . + (n + k)2 = m2 is impossible whenever + 22 + . . . + k2 is a quadratic nonresidue (mod k + 1 ) . (c) What are the first three such values of k ? =
P
4 . (a) Suppose that p � 5 is prime. Show that  3 is a quadratic residue (mod p) if p '" 1 or 7 (mod 1 2) and a nonresidue if p "" 5 or 1 1 (mod 12). (b) Suppose that p is an odd prime, p of 3, and Suppose that x3 ,.. a (mod p) has a solution r. Then
Pja .
(x

r)(x2 + + r2) "" 0 (mod p). xr
Show that x2 + xr + r' "" 0 (mod p ) has two solutions different from r if and only if p "" 1 or 7 (mod 12). (c) If p � . 5 , show that the number of distinct nonzero cubic residues (mod p) i s p  1 (p  1 )13 t
if if
or or
1 1 (mod 1 2) 7 (mod 1 2).
5. If p = 2'" + 1 is a prime , show that every quadratic nonresidue of p is a primitive root of p .
1 92
Section 23
Section 13
*t
1.
(a) Find a base b such that aa. = 34. (b) Find a base b such that a a a b = 1842. (c) S how that it is impossible for a a a b bbc for positive =
a,
b, and c .
2. What is the smallest positive integer n such that the last digit of n is bases b, b + 1 , and b + 27
Y , and 3 . (a) Show that 1 2 13 = 42, 1 2 14 (b) Guess and prove a theorem. (c) Evaluate 169, i n base 10 (b 2: 10). =
t
4. 5.
Show that
1 1 1.
1
in the
1215 = 6�.
is not a perfect square in any base
b, b
=
2, 3, .
Prove that every positive odd integer can be represented in the form n where d;
=
= do + d\ · 2 + dz · 21 + . . . + dk ' 2� ,
1 or 1 , i 
=
0, 1 ,
.
.
.
,
k but the representation is not unique . ,
Section 14 1 . Show that the last digit of x" , n = 2, 3 , (a) i s 0 if x = 6 (b) is 4 if x = X (c) i s x if x = 3, 5 , 7, 8 , or e' and n is odd.
2. 3.
With which digits can a prime end?
4.
(a) Let n be an integer written in the base do, and let m be its reversal. Show that to! (n m ) . (b) Generalize t o any base b .
If n is an even perfect number, n f= mal representation is four.
6, show that the last digit in its duodeci

t
5.
Using the fact that 100 1 integer by 7, 1 1 , and 17.
=
7 · 1 1 · 1 7,
develop tests for the divisibility o f an
Section 15
3 1415, and the decimal has a period of 15707, half the maximum. It' s a good thing I didn ' t have t o go all the way out to 3 14 14 places . " Student B says, " You made a mistake somewhere . Again." How did B know that without checking the calculations?
,. 1 . Student A says, " With enormous labor, I have divided 1 b y
*
2.
In the hexadecimal system (base 16, with digits F) find the expansions of 1/2, 113 , . . . , lIF. .
1, 2,
3.
In which bases will the decimal representation of 7/60 terminate ?
.
.
.
,
9 A, B, . ,
Additional Problems
0./22
+
aJ/32
+
0';42
+ . . . , O :s
Does every number between 0 and unique?
" 5.
1
aj
1 93
< i" .
have such a representation? Is it
Both 1/13 and 1/14 have period 6. Find the next pair of consecutive i ntegers such that their reciprocals have the same period .
Section 1 6 t 1 . Prove that i f the sum o f two consecutive integers i s a square, then the s maller is a leg and the larger is a hypotenu se of a Pythagorean triangle . (a) Given a , how would you find b such that at + b2 is a square? (b) Carry out such a procedure for a = 13 and a = 14.
2.
t 3. Let the generators of a Pythagorean triangle be consecutive triangular num bers. Show that one side of the triangle generated is a cube.
t
4.
Note that
5.
Show how to determine all primitive Pythagorean triangles whose area is numericall y equal to k times its perimeter, k a positive integer.
4"  32 = 7, 1 22  52 = 7 . 17, and 82  152 =  7 · 23 . 02 + bi = c2 and (7, abc) = 1 imply 7 1 (02  bi) .
Show that
Section 1 7
1. 2. 3.
Given that x � + y � = z� has no solutions i n i ntegers, prove that it has no solutions in rational numbers . Show that x· + y"
= z·· , 11 = 1 ,
2, . . . , has no nontrivial solutions.
Suppose that we can show that x" + y" = zl' has no nontrivial solutions for any odd prime p . Conclude from this and Problem 2 that xlt + y. z" has no solutions for any n 2: 3 . =
4. Show that x" + y" = z" implies p i (x + y  z). t 5. Show that X,, I + y,H Z,H has no nontrivial solutions unless p Ixyz. =
6 . Show that
x3 + y3 + Z3 + x'y + y'z + z'x + xyz *t
=0
has no nontrivial solutions .
7.
Show that there are infinitely many nontrivial solutions of x " + y" for any
n 2: 1 ,
= Z "+ I
namely those given by x
=
(ac)''',
y
= (bc y" ,
z
= c',
Section 23
1 94
where
a
and b are. arbitrary , and r and s are chosen to satisfy
rn2
+ 1 =
(n
+ 1)s .
Does the last equation have infinitely many solutions in positive integers r, s?
8 . Find a solution o f X 4 + y 4 = Z5 .
* 9.
Find solutions to x" + y'" = Z" l .
10. Show that x" + y" = z '" has nontrivial solutions if (n, m)
=
1.
Section 18 1 . Show that 4 1 (x" + y" + Z1) implies that x, y, and z are even.
t
2. Verify that if n squares.
""
7 (mod 8), then
n
cannot be written as a sum of three
3 . From Problems 1 and 2 , show that n 4'(8 k + 7) for some nonnegative and k implies that n = x� + y" + z" is impossible. =
e
4. A mathematician said in 1621 that 3 n + I is not the sum of three squares if n = 8 k + 2 0r 32k + 9 for some k. Show that he was wrong.
t
5. Show that not every positive integer n can be written n = x"  y" for some integers x, y. 6. Show that every positive integer n can be written
t
for some integers x, y, Z .
7. Show that if n is the sum of two triangular numbers, then 4 n + 1 is a sum of two squares. 8. Which integers can be written as the sum of two squares of rational num bers?
+ 1 , 2 ' 3 + 1 , 2 ' 3 · 5 + 1 , 2 · 3 · 5 · 7 + 1, . sum of two squares?
>'t 9. Which of 2
.
. can be written as a
10. Is it possible to mimic the proof of Theorem 2 to prove a generalization: if (w/p) = 1 , then there are integers x and y such that p = x: + wy"?
Section 19 *t
1. Express 5 ,724,63 1 as a sum of four squares. 2 . Tabulate the number of different representations of 1 , 2 , 3 , . . . as sums of four squares, and see if any theorem suggests itself.
Additional Problems
195
3. Which integers can be written as a sum of exactly four nonzero squares? 4. Fill in any missing details in Euler's original proof of Lemma 2. Suppose that (  lip) = 1 . Then there is an integer x such that 1 + Xi "" 0 (mod p ) . So, suppose that (  l ip ) ""  1 and that the lemma is false. Then 1 + 1  2 = 0 0 shows shows that ( 21p ) =  1 , and hence that (21p) 1 . Then 1 + 2  3 that (  3Ip ) =  1 and that ( 3Ip ) = 1 . In this way, 1 , 2 , . . . , p  1 are all quadratic residues (mod p ) . =
=
t
5 . I f n > 0 and 81 n , show that n is not the sum of fewer than eight squares of odd integers.
Section 20 * t I.
If Xk
+ Yk v'2 = (3 + 2 V2)k· , calculate (XkIYk)  V2 for k ( V2 = i .4142 1 3562 . . . . )
=
1 , 2, 3, 4.
2 . (a) Show that X2  Ny2  1 has no solutions if N "'" 3 (mod 4). (b) Show that ifx, ' Yl is a solution ofX!  Ny! =  1 with x, > 1 , then U " , Vk , k = 1 , 2, . . . are solutions of X2  Ny! '" 1 , where =
Uk
t
3. Show that if Xi  Ny!
+ Vk yIN = (X , + Yl VN)2k . =
k has one solution , then it has infinitely many.
4. Let X,,+ I = X" + ry " and Y n+ 1 = X. + Y" , n = 1 , 2 , . . . . Show that x/  ry,/ 2. takes on only two different values if X02  /Y02 =
'" 5 . Apply Problem 14 of Section 2 0 t o extend the sequence o f rational approxi mations to v'2 found in Problem I to one more term .
Miscellaneous Problems 1 . Prove that 6 1 (n3  n ) for all positive integers n .
2 . Prove that the sum of three consecutive cubes i s always divisible b y nine .
+ b is even, then 24 1 ab (a2  b2) . 4. Show that (2" + (  1 )1H1 )/3 is an odd integer for n
3 . Show that if a
2::
1.
'" 5 . A man came into a post office and said to the clerk, "Give me some 13cent stamps, onefourth as many 9cent stamps , and enough 3cent stamps so this $5 will pay for them all . " How many stamps of each kind did he buy? 6. Construct a stamp problem for the future: a man bought some 25cent stamps, onefourth as many 20cent stamps, and enough l Ocent stamps to make the total exactly $ n . What values of n, n 1 , 2, . . . give a unique solution in positive integers? =
'" 7. Stamp problems can be endlessly varied: in a state with no sales tax , bottles of scotch sell for $7 each, bottles of rum for $6 each, and bottles of
196
Section 23
vodka for $5 each. The same disagreeable man as in Problem 5 came into a liquor store and said, " Give me some bottles of scotch, half as many of rum, and some of vodka. Here's $40. Keep the changethere won' t be any, har, har, har. " What did he get? 8 . Show that the sequence 5 , 1 2 , 1 9 , 26 , . . . contains no term of the form 2(/ . or 2(/  1 . t 9. Induce a theorem from the following facts: 3 2 + 42
=
362 + 372 + 3 82 + 392 + 40'
=
Y,
1 02 + 1 12 + 122 = 1 32 + 142, + 222 + 232 + 24' = 252 + 262 + 27' , 2 12
4 1 ' + 422 + 432 + 442 •
10. A palindrome is a number that reads the same backward as forward, such as 3 14 1 4 1 3 . (a) How many twodigit palindromes are there? (b) How many threedigit ones? (c) How many kdigit ones?
1 1 . Let us say that an integer is powerful if and only if p2 1 n whenever p ! n . Prove that n r2s3 for integers r and s where s is squarefreethat is, no square divides s. =
12. If a and b are positive integers, let us say that a divides b weakly (or, that a is a weak divisor of b ) , written a I b , if and only if p l a implies p I b for primes p. (a) Find examples of integers a and b such that a > b and a I b. (b) Prove that a I b implies a I b. (c) Prove that a I b and b I c implies a { c. (d) Prove that a b I c implies a I c and b I c . (e) Prove that ac bc and (a, c) I (b, c) imply a I b. (f) Prove that a b implies (a, c)I (b , c) for all positive integers c . (g) Prove that if there are integers m and n such that a J/ b"', then a J b . (h) Prove that a J c and b I c imply a b J c . (i) Which of (c) to (h) are false for ordinary divisibility of positive inte gers? Give examples .
J J
7
t 13. Construct a formula forf such thatf(n ) is 1 12 if n is even and 1 if n is odd. 14. Induce a theorem from the following data: 14 + 14 + 24 14 + 34 + 44
24 + 54 + 74
2 . 32,
14 + 24 + 34
=
2 . 132,
24 + 34 + 54 ",, 2 ' 1 92 ,
=
2 , 392,
=
34 + 44 '+ 74
=
=
2 · 72 , 2 . 372 •
1 5 . Use mathematical induction to prove that 6"  1 + 5 n (mod 25) . 1 6 . A paper was written recently to show that x3 + 1 17y 3 = 5 has no solu tions [ 10] . It used the theory of algebraic numbers . Show that the equation has no solutions by considering it (mod 9).
1 97
A dditional Problems
* 1 7 . Find the smallest integer and 49 1 n + 2.
such that
Il
11
is positive and 25 1 n , 36 1 n + 1 ,
18. Show that
2:
din
lid = (T(n )/n .
*t 1 9 . When Ann is half as old as Mary will be when Mary i s three times as old as Mary is now, Mary will be five times as old as Ann i s now. Neither Ann nor Mary may vote . How old is Ann?
20. Show that if a = r2  2rs  S2, b = r2 + s ' , e = r 2 + 21's  S 2
for some integers 1', s , then a 2 , b 2 , c' are three squares i n arithmetic progression. 2 1 . Pascal once wrote that he had discovered that the difference of the cubes of any two consecutive integers, less one, is six times the sum of all the positive integers less than or equal to the smaller one. Prove that he was right. 22. Show that if n = a' + b2 = c2 + d2 with b l d, then n =
« a  C )l + ( b  d)2)«(/ + C )2 + (b  d)2) 4(b  d)2
and hence that if n can be written as a sum of two squares in two distinct ways, then n is composite. *
23 . Using the result of Problem 20, factor (a) 533 = 23' + 22 = 222 + 72 ; (b) 1 073 = 322 + 72 = 282 + 1 72 • 24. Show that for any a and d such that (3d, m ) = 1 , the system
ax
+
(a + d)y '" a + 2d (mod m)
(a + 3d)x + (a + 4d)y "" a + 5d (mod m )
has the same solution. 25. If n = a2 + b" + ct, with a, b, c nonnegative, show that (n/3)112 s max(a, b , c) s n 1 l2 . 26. Gauss proved that a regular polygon with m sides can be constructed with ruler and compass if m = 2un, where a is an integer and 11 = 1 or n is a product of distinct primes of the form 2A' + 1 . List all the regular polygons with fewer than 40 sides that can be constructed with ruler and compass.
* t 27. P + 22 = 32  22 .
22 + 32 = 72  62 ". 42 + 5' = 2 J2  202. What happens in general ?
3 2 + 42
=
132

1 22 .
1 98
Section 23
28. It i s known that 8 k + 3 Xi + y 2 + Z 2 has a solution for any k � O. (a) Show that X , y, and z are odd. (b) Deduce that k is equal to a sum of three triangular numbers . �
t 2 9.
+ (2/3 ) + 5/24) 1 /2
( 1/3)2
30. (5
=
=
( 113) + (2/3)2. Is this astonishing? 5 + (5/24) 112 ; are there other numbers like that?
* t 3 1 . (a) Find all a and p such that a! ....  2 , a3 "" 3 , and a4 "'" O < a 3 . 55 . (a) If p i s a n odd prime, how many elements in the sequence 1 ' 2 , 2 · 3 , 3 ' 4 , . . . , p (p + l ) are relatively prime to p ?
(b ) I f p is a n od d prime, how many elements i n the sequence 1 ' 2 , 2 ' 3 , 3 ' 4, . . . , p2(p2 + 1 )
Section 23
200
are relatively prime to p ? (c) A n y guesses for a general theorem? 56. Show that n 2 + (n residue (mod k).
+ 1)2 = km 2
is possible only when  1 is a quadratic
57. Letf(x) be nonnegative and nondecreasing for x 2:: O. Let us say thatf i s semimultiplicative if and only iff(nm) 2:: f(n )f(m ) fo r all positive integers m and n. (a) Show thatfin) = n " , k a positive integer, is semimultiplicative. (b) Prove that the product of two semimultiplicative functions is semi multiplicative. (c) Show that if g(x) is nonnegative for x 2:: 0, then nY(II) is semimultiplica tive.
58. If a and b are positive integers, then a t ends with an even number of zeros, and 1 0bt ends with an odd number of zeros . Hence 10b1 at is impossible in nonzero integers, and it follows that lOll:! is irrational . (a) Adapt the above proof to integers in the base b (b not a square) to show that b1l1 is irrational. (b) Show that bl'''' (b not an mth power, m = 3 , 4, . . . ) is irrational by the same argument. =
t
59. Consider the following lists:
3 5 7
9 11 13 15
17 19 21 23
List 4
List 2
List 1 2 3 6 7
25 27 29 31
10 11 14 15
18 19 22 23
26 27 30 31
60 .
12 13 14 15
24 25 26 27
7
12 13 14 15
20 21 22 23
28 29 30 31
List 16
List 8 8 9 10 11
4 5 6
16 17 18 19
28 29 30 31
20 21 22 23
24 25 26 27
28 29 30 31
Pick a number from 1 to 3 1any numberand see which of the above lists it appears in. If you add the numbers of the lists in which the number appears, you will get the number you picked. Why does this trick work? Let P. = P I P2 · · · P n and ak = I + kPn, k = O , I , . . . , n  I , where the p ' s are the primes 2, 3, 5, 7, . . . in ascending order . Show that (ai' aj) = 1 if i ,pI
t 6 1 . If
n is an even perfect number, show that the harmonic mean of the divisors of n is an integer.
62. (a) Show that the least residues of 1 , 7, 72 , . . . , 75 (mod 36) are in arithmetic progression. (b) What are the least residues of 1 , 7, 7:1 , 7\ . . . (mod 2 1 6)?
t 63 . Show that 2rt  3 is never a square,
r
=
2, 3 , . . . .
Additional Problems
201
64. In 1 494, L. Pacioli said that 1 342 1 7727 was prime. Show that he was wrong. '" 65. Suppose that a , b, and e have no common factor. Show that solutions to ax + by + ez = 1
are given by
x = 1"1 + el"m + nbld,
y = st + esm  nald, z =
li
 dm ,
where m and n are arbitrary integers, r and s are such that ar + bs = d (a, b ) , and t and li are such that dt + eli = 1 , and apply this to . get =
solutions of 7x + 8y + 9z = 1 .
66. In a rectangular coordinate system, put a dot at the point ( n , m ) if and
only if 11 and m are relatively prime. Consider onebyone boxes. (a) Can any such box have all four corners dotted? (b) Find a box with no corners dotted. (c) Let p be an odd prime. In the row of boxes ( l, p + I )
(2, p + I )
( I , p)
(2, p)
(p  l , p + l )
I
IT
(p, p + I )
(p  I , p)
I
(p, p)
how many have three corners dotted?
67. Let I X ) denote the fractional part of x . That is, ( x ) = x (a) Show that if (a, n) 1 , then the set of numbers
[xl.
=
( aln ) , (2aln ) , . . . , « n  1 )aln )
is a permutation of the set l in , 2In , .
. , (n  1 )/n .
(b) Show that if ( a , n) = 1 , then
�[
ak
k�O

n
J
=
( a  1 )(11  1 ) . 2
68. Show that every n > 0 satisfies at least one of II ""
0 (mod 2)
n "" 3 (mod 8)
n "" 0 (mod 3)
n "" 1 (mod 4)
n "" 7 (mod 1 2)
n "" 23 (mod 24).
t 69. Show that 99" ends in 89. 70. If p is a prime and ap + b = ct ,. then show that all values of k making kp + b a square are given by
202
Section 23
k = pn 2 ± 2cn + a ,
t
where n is any integer. 7 1 . If m > 1 is odd, show that 2'" + 1 is composite. 72. Prove by induction that }"+1 1 10111  1 , n = 0 , 1 , 2 ,
*
t
73.
2'(23

1) = 13 + 33;
24(25  1) = P + 33 + 53 + 73 ; 26(27  1) = 13 + 33 + . . . + 1 53 •
We might induce that every even perfect number, except 6 , is a sum of consecutive odd cubes, starting with P . Is this so? 74 . (a) Given n > 0 , show that there is an integer m such that
(b) Can you always find an m such that « n + 1) 112 + n 112)3 = (m +
t
1) 111
+ m 1I2 ?
75. Show that if n is an even perfect number, then
IT
din
76 . If n is composite and greater than 4, show that (n
d is a power of n .

2) !
""
0 (mod n ) .
t 77. Show that the last nonzero digit of n ! i s even when n > I .
78. Show that no power o f 2 i s a sum o f two o r more consecutive positive integers.
t 79. Let f( n ) denote the smallest positive integer m such that m ! "" 0 (mod n ) . (a) Make a table o f f for n = 2 , 3 , . . . , 20 . (b) Show that f(p ) = p . (c) Show that if P and q are distinct primes, then f(pq) = max(p, q ) . (d) Show that i f p > k , then f(p '") = kp . 80. Show that
"
2:
k=[
*
k!
is never a square when n > 3. 8 1 . Find nine integers in arithmetic progression whose sum of squares is a square. 82. Let P i denote the ith prime. Show that PH = P I P • . . . P. + 1 is never a
square.
* t 8 3 . Which positive integers are neither composite nor the sum of two
positive composite integers?
84. 1000 "" 1 (mod 37). From this, develop a test for the divisibility of an integer by 37 .
*
t 85. Although 9 i s not the sum of two positive integer squares, it is the sum of two positive rational squares. Find them.
86. Suppose that we have a solution of
203
Additional Problems
ab(a + b)(a  b)
=
c·
where a, b, and c have no common factors. (a) Show that a and b are both odd. (b) Show that any two of a, b, (a + b)l2 , and (a  b)12 are relatively prime. (c) Conclude that each of a, b, (a + b)/2, and (a  b)/2 is a square. (d) Put (a + b)12 = ,.2 and (a  b)/2 = S 2 . What are a and b in terms of r and 5 ? (e) Conclude that i f there i s a solution of ab (a2  b2) = c 2 where a , b , C have no common factor, then there is a solution of ,.'  s· = u · . 87 . Euler showed that any odd perfect number must b e o f the form
a and Q integers . Fill in any missing details in this sketch of his proof: Let n P I P• . . . PIr be the decomposition of n into powers of distinct 2 n , then odd primes. Let Q; (T(P;), i = 1 , 2, . . . , k. If (T ( n )
p an odd prime, =
=
=
2P I P •
. . .
PIr = Q I Q. · . . Q" .
Thus, one of QI > Q., . . . , Qksay QIis double an odd number, and the remaining ones are odd. Thus p. , P3 , PI< are even powers of primes . Also, P I = p4n+ l for some prime p and integer a . •
•
•
88. Write the positive integers in a spirallike array as shown: 17 18 19 20 21
16 5 6 7 22
15 4 1 8 23
14 3 2 9
13 12 11 10
If 1 i s at the origin of a rectangular coordinate system and n (a) What integer is at ( n , O)? (b) What integer i s at (n, n)? (c) What i nteger is at (n, 0) 7 (d) Where i s (2n + 1 )2? (e) Where is (2n)2? (f) Where i s 1 0007
2::
0,
89. Show that the primes less than n2 are the odd numbers not included in the arithmetic progressions
for r = 3, 5 , 7 , . .
90. (a) Find all x, y,
z
.
(up to n  1).
i n arithmetic progression such that
204
Section 23
and xy F O. (b) Find all x, y,
z
in arithmetic progression such that
and xy t= o . t 9 1 . Show that x" + y" = z " has no solutions with both x and y less than n for
any positive integer n.
92. Suppose that n ' + n + 1 = p " , where n c 1 , p is prime, and r c 1 . (a) Show that P i s odd. (b) Show that if n 1 (mod 3 ) , then the only solution is n = 1, p r 1. (c) Show that r is odd. (d) Show that if p t= 3, then p 1 (mod 3). ""
=
3,
=
""
t 93 . Let f(x) a"x " + a " Ix" I + . . . + aQ . Suppose that an; aQ, and an odd number of the remaining coefficients are odd. Show that fex) = 0 has no =
_

rational roots.
94 . (a) S how that if (a, p )
=
1, n l Cp  1), and
not an nth power residue (mod p) . (b) Is 2 a fifth power residue (mod 3 1 ) ?
t 95 . Show that n I (2"
a (P I l/" c;f J (mod p ) , then
a
is
+ 1 ) i f n i s a power o f 3 .
9 6 . (a) Show that n2 + (n + 1 )' = 3m' is impossible. (b) What is a sufficient condition for
to have a solution for given k, k > o ? ' * t 97. Let m be squarefree. (That is, m = P IP! ' . 'Pk, a product of distinct primes . ) Suppose that m has the property that p I m implies (p  1) Im . (a) Show that m = 2, 6, and 4 2 have this property. (b) Does any other m ? (c) How many others? 98. (a) Show that if r and s satisfy 5"s  2"r = 1 and x = 5"s then the last n digits of x1 are the same as the last n digits of x. (b) Find such a number for n = 3 . ,
t 99. Show that the sequence {2 + np } , p a n odd prime , n tains an infinite geometric progression for any p.
100. Solve xex  3 1 )
=
y (y  4 1 ) in positive integers.
=
1 , 2, . . . , con
Appendix
A Proof by Induction
In the text, the method of proof by mathematical induction is used several times. The purpose of this section is to recall what the method is, show some examples of how it operates, and give some problems for practice. Mathematics is notoriously a deductive art: starting with a collection of postulates, theorems are deduced b y following the laws of logic . That is the way it is presented in print , but that is not the way that new mathematics is discovered. It is difficult to sit down and think , "1 will now deduce," and deduce anything worthwhile. The goal must be in sight: you must suspect that a theorem i s true , and then deduce it from what you know. The theorem you suspect is true must come from somewhere. Just as in the other sciences, a new result can come at any time, the mysterious product of inspiration, inspection, subconscious rumination, revelation, or a correct guess. *
Exercise 1.
Guess what f(n) is from the following data: n f(n)
1 01
1 o
2 1 205
3 4
4 9
5 16
206
Appendix A
Guess whatf(n) is from
"' Exercise 2.
'" Exercise 3
n \0 1 2 3 4 5 6 fen) 1 2 5 10 17 26 37
(optional) . Guess a theorem aboutf(n):
n \1 2 3 4 5 6 7 fen) 2  1 2 1 2 7 14
Since number theory i s largely concerned with the positive integers , some of its theorems are of the form, " Suchandsuch is true for all positive integers Propositions like this can often be proved by (or for shortwe will not be con cerned with any other kind) . This method of proof is based on the fol lowing property of positive integers :
n." mathematical induction (1)
induction
If a set of integers contains 1 , and if it contains + whenever i t contains then the set contains all the positive integers .
r 1
r,
This property is so fundamental that it is usually taken as a nonprov able postulate about the positive integers . It is applied when we want to show that a proposition about the positive integer is true for all = . . . . Examples of such propositions are
pen) n n, n 1, 2 , P l(n): "n2 + 3n + 2 > (n + 1)2  5 . " P2(n): "n(n + l)(n + 2) is divisible by 6. " P3(n): ' 1(x1 + x2 + . . . + xnP:: f(xl) +f(xz) + . . . +f(xlt)." Let S denote the set of positive integers for which pen) is true. If we can show that 1 is in S and that if is in S , then r + 1 is in S , then (1) r
says that all positive integers are i n S . Rephrasing this, we get the in duction principle : If is true , and if the truth of implies the truth of + 2, . . . . then is true for all
P(1) Per) pen)
per 1), There is no necessity for an induction to start with 1; we could start with 2, 3, 17, or  12 . For example, if P(3) is true and if the truth of P (r) 3, 4, . . . . implies the truth of PCr + 1), then pen) is true for n Fill in the blank : if P (2) is true, and if the truth of P (r) implies the truth of Per + 2) , then PCn) is true for n, n 1, =
=
'" Exercise 4.
__
.
Proof by Induction
207
To illustrate a proof by induction , we will take a well known exam ple. Let P en) be the statement
"1 + 2 + . . . + n = nCn + 1)/2." We will prove by induction that P (n) is true for all positive integers n. *
Exercise 5 .
What i s P (1)? Is it true?
Suppose that
per) is true; that is, suppose that 1 + 2 + . . . + r = r(r + 1)/2. (2) We wish to deduce that P (r + 1) is true . That is, we want to show that (3) 1 + 2 + . . . + (r + 1) = if + 1 )(1' + 2)/2 follows from (2). If we add r + 1 to both sides of (2), we get 1 + 2 + . . . + r + (I' + 1) = r(r + 1)/2 + (r + 1) (r + 1) (� + 1 ) = Cr + 1)(r + 2)/2, =
which is (3) . Hence both parts of the induction principle have been is true for all positive integers verified, and it follows that In any proof by induction, we must not forget to show that P(1) is true. Even if we show that the truth of implies the truth of if P( l ) is not true, then we cannot conclude that Pen) is true for any n . For example, let be
Pen)
Per)
PCr + 1),
Suppose that (4)
n.
Pen) n + (n + 1) = 2n .
Per) is true. That is, we assume that r + Cr + l) = 2r.
Using this, we have
(r + 1) + (r + 2) = r + (r + 1) + 2 = 21' + 2 = 2(r + 1), so Per + 1) is true. So , if P(1) were true, it would follow that Pen) is true for all positive integers n. Since P(1) is not true , we cannot so conclude. In fact, Pen) is false for all n . It should go without saying that in any proof by induction , we must verify that the truth of Per) implies the truth of PCr + 1). For example, from the table n il 2 3 4 5 6 fen) 2 4 6 8 10 12
208
_
Appendix A
we cannot conclude thatf(n) = 2n for all n. In fact, J(7) = 71, because the function that I had in mind when constructing the table was fen)
=
2n +
(n  1)(n  2)(n  3)(n  4)( n  5)(n  6)(71  14) . 6 . 5.4. 3 . 2
Another form of the induction principle is sometimes used:
If P(1) is true, and
if the truth ofP(k) for 1 :s k :s r implies the truth ofP(r + 1) , then Pen) is true for all n, n = I , 2, . . . .
This is valid because of the corresponding property of integers : if a set of integers contains 1 , and contains r + 1 whenever it contains I , 2, . . . , r , then it contains all positive integers .
Problems 1 . Prove that
F + 2' + . . . + n� = n (2n + l)(n + 1 )/6 for n = I , 2 ,
P
2.
=
1\
p + 2� = 3�,
P + 2 � + 33 = 6 � ,
P + 2� + 3') + 43 = 1 02 •
t
Guess a theorem and prove it. 3. From Problem 2, or by guessing and induction, derive a formula for
P + 33 + 53 + k = 1, 2,
.
.
.
+ (2k  1 ) 3 ,
. .
4 . Prove that
lIl · 2
+ 112 · 3 + .
.
.
+ lI(n  1 ) 1Z = 1  ( lin )
fo r n = 2, 3 , . . . .
t
5 . 1 , 3 , 6, and 10 are called trlaniular numbers:
Let
t. denote the n th triangular number. Find a formula for t
•.
Proof by Induction
209
6. Suppose that aI = 1 and an+J = 2 a " + 1 , n = 1 , 2, . . . . Prove by in duction that a" 2"  1 . =
7. Suppose that ao = a I = 1 Prove by induction that
a H I = a" + 2a"_ , ,
and
a. =
n = 1,
2, . .
" 2 +1 + (  1)" 3
8. Suppose that aI = a 2 = 1 and a H J = 3 a " + a . I ' Prove that ( a " , a,,+ l ) = 1 , n = I , 2, t 9.
1 · 2 · 3 · 4 = 52  1 ,
2 · 3 ·4·5 = I P 1, 3 · 4 · 5 · 6 = 1 92  1 , 4 · 5 . 6 7 = 292  1 . 
.
Guess and prove a theorem . (Induction may not be necessary . ) 1 0 . Guess and prove a formula for
P n
=
r
42 + 72 + . . . + (311 + 1)2, '
0, 1 , . . . .
1 1 . Prove by induction that n ( n + J )( n + 2) is divisible by 6 for n = 1 , 2, . 1 2. Construct a formula for a function f such that f( 1 ) = f( 2) = f( 3) = f (4) = 0,
f( 5) = 1 7 .
"'t 1 3 . Let t " denote the nth triangular number. Consider the table 11
2
3
4
5
t.
]
3
6
10
15
Sr. + I
9
25
49
SI
121.
Are all those squares a coincidence? 1 4 . Prove by induction that n'  n is divisible by 5, n = t 15. The Fibonacci numbers are defined by
Prove that f,. is divisible by 5, n = 1, 2, . . . .
I,
2,
Appendix
B Computer Problems
Computers go well with number theory. The reason is that what com puters do best is long sequences of calculations, with a single number as a result, and that is often just what is wanted to solve a problem. It would be hard to solve a congruence like 3 14 1 59x ... 26535 (mod 27 1 828 18) by hand, but quite easy to program a computeror even a programmable pocket calculatorto find the solutions : have the ma chine do the labor of substituting inx 1 , 2 , . . . , 27 1828 1 8 and check if the congruence is satisfied. Even if the machine is so slow that it can do only 1000 subs titutions and checks per second, it will take no more than eight hours for it to do them all . Plug it in and let it run all night: that is what computers like to do. It is the same when looking for solutions to a diophantine equation or seeing if a large integer is prime : the machine can grind through hundreds of millions of calculations without complaint and produce results which human life would be too short to obtain otherwise. Applying computers to number theory can also sharpen program =
ming skills . Anyone can write a satisfactory program to print paychecks , since most of the time is spent by the relatively slow printer. But when a problem requires all the computing power of a machine , the algorithm being used can make quite a difference. I have seen programs that 210
Computer Problems
211
factor ninedigit integers almost instantly and others that take months. When the machine is being used to its utmost, there is pressure on the programmer to push himself to his limits : and this can have only good effects. Some things which could be programmed are obvious, but nevertheless are listed below. Write a program to: Find greatest common divisors using the Euclidean Algorithm . Solve ax
+ by
=
(a , b ).
Determine if an integer is prime . Factor integers (a good factoring subroutine is very helpful in many problems) . Solve
ax + by = c .
Solve simultaneous congruences using the Chinese Remainder Theorem. Solve ax "'"
b
(mod m ) .
Calculate the least residue of a k (mod m ) . Calculate d (n),
(T(n) , 4>(n).
Determine i f an integer is deficient or abundant . Find primitive roots of an integer. Find for which integers a given number is a primitive root.
Solve x 2 "'"
a (mod m). Solve ax 2 + bx + c "" Evaluate (alp) .
0
(mod m).
Find the representation of an integer in one base , given its represen tation in another. Find the period of the decimal expansion of
lIn .
Find representations of integers as sums of squares, cubes, or higher powers. Find solutions of x2  Ny 2
=
1 , or x 2

Ny2
=
k.
Evaluate 1T{x) . There follow 25 other possibilities, listed essentially at random . I d o not know how hard or easy, or how frustrating or rewarding, each one is. They are examples of things that have been found i nteresting , and some references have been included.
212
Appendix
B
1 . An amusing game , a bit like writing integers using exactly four 4s 44/44 , 2 = 4/4 + 4/4, 3 = (4 + 4 + 4)/4, . . . ), is to write each (1 prime as a difference of two integers whose primepower decompo sitions include just the smaller primes. For example , 5 = 32  22 and 7 = 52  2 . 32• The game gets so hard for larger primes29 is 3 · 1 1 . 132 . 19 . 23  212 . 5 . 7 . 17that machine help is needed. This may not be =
easy to program. (Mathematical Reviews 49(1975): #492 1 .) 2 . The answer to this question is known, but it illustrates how the computer can be used to gather data from which inductions can be made: What is L(a  1 , n) in terms of n , where the sum is taken over those integers from 1 to n which are relatively prime to n ? (Mathe
matical Reviews 49(1975) : #2506 .) 3 . It is striking that 145 satisfying did! . . . die
Ie
=
.
=
1 ! + 4 ! + 5 ! , and the only other integers
2d; ! are 1 , 2, and 40585 (Mathematics MagIe
Ie
iI
iI
azine 44( 197 1) : 278279) . Does d1dz . . . die ever equal 2 2d, or 2 y, ? 4. If n = 6, or if n "'" I (mod 6) is prime , or if n = 3p where p "'" 5 (mod 6) , then 3 1 n + (T(n). Are there any other such n , and do they fall into classes?
(T(n + 1) has 1 1 3 solutions for n < 101 (Mathematics of Computation 27( 1�73):676). It is probably too hard to extend that table, but related equations like (T(n + 1) 2(T(n) or (f(n + 2) = (T(n) might yield interesting numbers . 5 . The equation (T(n)
=
=
6. Let s (n )
=
(T (n )  n, s 2 (n )
=
s (s (n » , and sk+ l (n )
=
s�k(n » . Cata
lan' s Conjecture, which dates back to 1887 , is that the sequence n, s en ) , s 2 (n) , . . . eventually either reaches 1 o r enters a cycle. The general opinion now is that the conjecture is false and that for many n the sequence is unbounded. A computer will never be able to establish that, of course, but it can discover cycles. Fourteen cycles of period 4 exist (for example, s5( 12496) = 1 2496) and there are longer cycles (s 28( 1 4 3 16) = 14 3 16) . A machine might discover more. It is likely that they would be rediscoveries though, so a variation of Catalan' s COI\iec ture might be considered, say by defining t(n) = a(n)  n  l .
7 . An integer n is semiperfect if n is a sum of distinct proper di visors of n. For example , 104 = 23 13 is semiperfect because 104 = 52 + 26 + 13 + 8 + 4 + 1 . A semiperfect integer is irreducible if it •
is not the multiple of a smaller semiperfect number. For example, 104 is irreducibly semiperfect, since none of 2, 4, 8 , 1 3 , 26, or 52 is semiper
Computer Problems
213
feet. There is a theorem that n = 21l1p is irreducibly semiperfect if Are there other irreducible semiperfect numbers ? If there are , does some theorem exist to explain them? (Mathematical Reviews 50(1975): # 12905).
2'" < p < 2m+l .
The equation 1 + 2 + . . . + n = F + 22 + . . . + k2 has just four solutions, three being ( 1 , 1), ( 10, 5) , and (13, 6). Find the fourth (n is less than 1000), and if a program can do that quickly , adapt it to con sider related equations like 1 T + 2" + . . . + n T 1" + 2' + . . + k' or 1 +2+ + n = a 2 + (a + 1)2 + . . . + k2 (Mathematical Reviews
8.
=
.
.
.
.
46(1973): #3443, #8%7). 9. Ever since the Egyptians
were building pyramids, people have been concerned with how to write fractions as sums of reciprocals. It is known that aln is a sum of three reciprocals, given a , for all sufficiently large n . When a = 4, such representations are known for all n < 107, and when a 5 for n < 922321 . Tables of solutions for those values, or for a = 6, 7, . . . might disclose interesting patterns. And they might not, but one never knows until one tries (Mathematical Reviews 44(1 972): #6600; Mathematics Magazine 46(1973):241244). =
1 0 . Given sets of integers A = {au a2 , , an} and B = {b) , b2 , . . . , b k } , define A + B to be {a; + bj} and A B to be {a;  bj} , where i = 1 , 2, . . . , n and j = 1 , 2, . . . , k . For example, if A { I , 2, 3 } , + then A A = {2, 3, 4 , 5 , 6} and A  A { 2,  1 , 0 , 1 , 2} . J . H . Conway conjectured that the number of elements in A  A is never less than the number of elements in A + A . This is false (Mathematical Reviews 40( 1970): #2635). One counterexample i s { I , 2, 3 , 5, 8, 9, 13, 1 5 , 16}. Other counterexamples could b e searChed for, but i t might be more interesting to investigate sets like (A + A )  A and A + (A A ) . 1 1 . Let fen ) = n  1>(n ) , pen) = [([(n» , and fk+l(n ) = [([k(n » , and •
•
•

=
=


consider the sequence n , f(n) , p(n ) , . . . . Since Jeri) < n , it always reaches 1 . For example, if n = 100, the sequence i s 60, 44, 24, 16, 8, 4, 2, 1 : eight steps are needed. Let s (k) be the smallest integer which reaches 1 in k steps. The first few values of s are k s (k)
1 24
3 4 5 6 7 6 10 18 30 42
and when factored, they are 2 · 2, 2 · 3 , 2 · 5, 2 · 3 · 3, 2 · 3 · 5, and 2 . 3 . 7. Could anyone have so little curiosity as to not want to know if s (8) was 2 · 3 · 5 · 7, 2 · 3 · 3 · 5, or 2 · 3 · 1 1 ? These sequences, analo gous to the sequences in Catalan' s Conjecture , have yet to be investi
Appendix
214
B
gated, I believe, though the sequences n , ¢I(n) , ¢I(¢I(n» , . . . have been studied by many writers.
12. Generalize Wilson's Theorem by looking at the values of (2p  1) ! (mod p l) , (3p  I) ! (mod p3) , (4p  I ) ! (mod p4), . . . . The result i s known but not easy to prove: with the aid of a machine it could be rediscovered (Mathematical Reviews 42(1971):#4477). One might then generalize the theorem in a different way , say by looking at a (a + 1) . . . (a + p) (mod p ) . 13.
Let
"
sen) = :2. r=l
(r,
n).
The first few values of this function , first
studied by S. S. Pillai in 1933, are 1 , 3 , 5, 8, 9, 15, 13, 20, 2 1 , and 25. Properties of this sequence might be investigated. It surely has some, since sen)  (T(n) is 0, 0, 1 , 1 , 3 , 3 , 5 , 5, 8, 8 for n = 1 , 2, . . . , 10, and can that be coincidence? (Mathematical Reviews 48(1974): #2508). 14. A search in 1 972 for solutions of a(x·  1)/(x  1) = ym with 1 < a < x s 10, n > 2, and m 2: 2 yielded only n = a = 4, x = 7, m = 2, and y = 40 (Mathematical Reviews 46(1973): # 1703). It is quite possible that there are no others, but it might be fun to put a = 1 1 and start looking.
15. Triangular numbers ( 1 , 3 , 6, 10, . . . ) have the form n (n + 1)/2. Palindromes ( 1 1 , 232, 36763) read the same backward as forward . Find some palindromic triangular numbers (Fibonacci Quarterly 12(1974): 209212), or, if you do not like to repeat work already done , find palindromic pentagonal numbers. 16. Perfect numbers (those such that (T(n) = 2n) and superperfect numbers (those such that (T «(T(n » = 2n) have been investigated. But no one has looked into superduperperfect numbers (those such that (T«(T«(T(n))) = 2n), and there may not even be any. With a good sub routine for evaluating (T(n), it shouldn' t be hard to find any that exist, and if there are none , to find solutions of variants like (T«(T«(T(n » ) = 3n or (T«(T«(T«(T(n» » = 16n . 17.
The congruences n(T(n) "'" 2 (mod ¢l(n» and ¢I(n) d (n) ""  2 (mod n) are both true if n is a prime . Find composite solutions. The answers are known (Mathematical Reviews 50( 1975): #2049) , but there are other such congruences, like ¢I(n)(T(n) "'"  1 (mod n2), that no one has looked at.
18 . If n = P 1 e'pl' . . . p,/' , define f by J( I) = 2 and fen) = 1 + elPI + e'!Pz + . . . + elrPk. See what happens to the sequences n, f(n ) , f(f(n» ,
Computer Problems
215
. for various n . The answer here is also known (Mathematical Re views 50(1 975) : #220) , but letting g(n ) = elPl + e'1lJ2 + . . . + ekPk or + ekPk) would lead to sequences that might be 1 + 2(elPl + e'1lJ2 + . .
.
dramatically different. 19. All of the integers n such that (2") = 2"1 , the number of odd 2" . 7. 4>(m ) . 8 . 24, 3 6 , 36. 9. (a) 12, 13, 14, 15, 16. (b) 21.:. (c) p '. 10. C1 { l , 3 , 5, 9, 1 1 , 13} , C. = {2, 4, 6, 8 , 10, 12}, C7 = {7} , C14 = { 1 4 } . positive integers less than
�
A nswers t o Selected Exercises
229
Section 10 1 . 2, 2,
and 2 .
or 6 . 2 and 5 have order six , 4 and 7 have order three, 8 has order two, and 1 has order one.
2 . 1 , 2, 3 ,
3. 1 9 1 (39, 77, 1 1 5 , 5. 3
and 1 53 are composite).
and 7 are primitive roots of 1 0.
Section 1 1 1. 2.
x· + 4 x + 3
""
0 (mod 5).
(x + 2)2 "" 1 (mod 5).
3. 2
and 4 .
8. 1 , 1 , 1 . 9. I f p
4 . 2 and p  2 . 5 . 1 , 2,
7. 1 , 1 , 1 , 1 .
,r a ,
13. I, 1 .
and 4.
1 4 . 5 , 13, 1 7 .
6. 1 5 and 1 6.
15.  1 ,
].
Section 1 2 2.
N o solution.
Section 13
1 . 3 1 = 24 + 23 + 22 + 2' + 2° . 33 = 2" + 2° . 2. 6, 7. 3.
n ' < 2T. Hence
r
4. 9 , 7, 64.
> e ; for all i.
5 . l�, 1 0 1 002 , I I OO I oo� .
SectiOil 1 4 1 . 1 1 , 1 9 , 1 10, 6X. 3. 28, 40, 6X6.
4. 8. 5. 371 , 275.
6 . . 1 86X35
Section
15
1 . 73/4950. 2.
.
17073.
3. 4, 2, 2 .
4 . 7, 6, 5.
5 . . 02439. 6. 5 .
then (a2/p) = 1 .
Answers to Selected Exercises
230
Section 16
1. If p divides any two of x , y , and z , then it divides the third.
2. Because 2 would divide (a , b ) .
Section 17 1.
c� '" 2 (mod 4) i s impossible.
6. Because n
=
2 v�. Because b' = mt  nt.
7. If n = 0, then a:! = 2mm = 0 , and a, b, c would be a trivial solution.
Section 18
2. 325  1 8:! + F. Section 19
Section 20
1 . The smallest solutions are 32 2. If x 3. 4. 5.


2 . 22 = 1 and 22

3
.
J2 = I .
my = x + my = I , then 2x = 2. The other case is similar.
99, 35.
(r + sN"l)k(r  SN"l)k
=
(r t  NS1)k
=
1'" = I .
Let a = c = X I and b = d = Y I in Lemma 1 .
6. 7 , 4 and 26, 1 5 .
Section 2 1 1.
1 , 9, 8 , 4 .
2. 20, 70 .
3.
10, 5.
4.
1979.
Appendix A
1 . fen) = (n  1 )2.
2. fen ) = nO + 3.
I.
fen ) = n :!  6n + 7.
4.
All positive even integers.
5. " I = 1 ·
212 . " Yes.
Answers to Selected OddNumbered Problems
Section 1 1.
1 and 592.
3.
One solution is x =  40 , Y = 79.
11.
(b) Yes.
Section
2
2 , 617, 2B · 3L 5 , 3  7 ' 1 1 ' 13  37.
1.
7 . 60466176. .
9. No.
11.
(b) No.
13.
False.
15.
No.
Section 3
1 + t, Y = 1  t ; x = 3 + 4t, y = 1 + 3 t ; x =  1 + 16t, y integer.
1. x =
3. x = 1 , Y =
y = 1. 5. tx , y , z ) = 7.
1; x =
3 + 4 t , y = 1 + 3 t , t = 0, 1 , . . . ;
x =
=
2  1 5 t ; t an
1 , Y = 6 and x = 3 ,
(22, 8 , 1 ) , (23 , 6, 2 ) , (24, 4, 3 ) , or (25 , 2 , 4) .
Nine apples at 91t each and three oranges at 6jt each.
9. If the first merchant had d, the second had 3 d , the third 5d, and the purse 15d. 231
Answers to Selected OddNumbered Problems
232
Section 4
1. 0, 2, 78.
11.
1 , 2, 5 , 10, 7 1 , 142, 355, or 7 10.
5.
7. 3 .
6.
13. 0, 1 , 5 , or 6 17. A is.
Section 5
1. 9; 6; 2, 8, 1 4 ; 1752. 3. x iii I (mod 5. 7. 9.
6), x
"'"
348 (mod 385),
x ""
1 0:8 (mod 385) .
.
0, 1 , 2, 4 , 5, 1 0, or 20 solutions . 1292.
x = 3, Y = 0 ; x
=
5, Y = 5 .
1 1.
17, 1 5 7 , or other larger and more unlikely numbers.
13.
213.
15.
30233088000000.
19.
(mi o mj ) ! (a j  aj ) for alI i andj, i fj .
Section 6 1.
1 , 4, 1 .
3.
3.
5.
1.
7. 3 1 19.
All n such that n ';' 0 or 1 (mod p) .
Section 7 1.
8 , 96, 24, 1 344.
3.
1 2 , 14736 ; 4, 120144.
7. 24, 48.
9. There are four: 5040, 7980, 8400,
and 9360.
11.
Even k.
17. 2d(N) .
Section 8
3. 1 2 , 1 8 , and 20 are abundant, 6 is perfect, and the rest are defic ient. Section 9 1.
1 2 , 96, 960.
3. 6528, 80088.
Answers to Selected OddNumbered Problems
0
15.
2
0
5_ 8
3 6
(mod 1 5)
5
6
10
6
4
7
8
9
10
6
10
12
11
13
233
14
6
5, 8, and 12.
Section 1 0 1.
2 , 6, 7, and 1 1 have order 1 2 ; 4 and 10 have order 6; 3 and 9 have order 3 ; 1 2 has order 2 ; 1 has order 1 .
3.
They are 3 , 10, 1 3 , 1 4 , and 1 5 .
5.
4, 2 , 4, 4 , 2 , 4 , and 2 . No.
7 . 6 and 26. IS. p  4. Section 1 1 1.
All of them.
3.
X "" 22 or 31 (mod 53), x "" 13 or 18 (mod 3 1 ) , x "" 2 or 5 (mod 7), X 2 5 or 992 (mod 997) .
5.  1 ,  1 ,  1 , 1 .
7 . x '" 3 or 6 (mod 7), x "" 50 or 1 00 (mod 1 0 1 ) . 9.
1, 1 .
17.
Yes : 23 , 76, 8 3 , and 1 36 are all solutions .
19.
(rIp)
=
1.
Section 1 2 1.
(3/p ) = 1 if p � 1 or 11 (mod 1 2) and  1 if p "'" 5 or 7 (mod 12) .
9.
1.
7 . (b) Then a and p

0 are both residues o r nonresidues.
Section 1 3
1 . 1 0 1 1 1 0l 01 O� , 200102 1 3 , 4226" 2037�, 1 137/ 1 , 3.
421 , 1 1 07 , 4 1 59 , 5377.
S.
1 02 , I S3 , 7 .
7.
2 3 4 5 6
2
3
4
5
6
4 6 11 13 IS
6 12 15 21 24
11 15 22 26 33
13 21 26 34 42
IS 24 33 42 SI
Answers to Selected OddNumbered Problems
234
9. 73 , 1 56 , 2 1 4 , 48848 . 1 1 . 19/49, 1/2, 13/16. 13.
Any b "" 2 , 3, or 4 (mod 5).
15. Six gifts, one each of $32, $ 128, $512, $ 1 024 , $32768, and $65536. 17. (a) COl, DODO, CODA , BODE. (b) 3243 , 45232, 57007 , 4 1438 . (c) Not that I know of. 19. (a) 296, 1 968. (b) ( 1 1 3 1 10)! .
Section
14
1 . 8X67, 1 5€43 1 26 . 3 . . 572497249 . . . , 3/13 . 5. $4E .€6. «: .
The digits in this answers are i n the base X . One dometric mile i s 98 . ordinary miles, one dometric pint is .93 . . . ordinary pints, and one do metric pound is .98 . . ordinary pounds . .
.
Section
15
1 . 2 , 1 , 4. 3 . 2, 3 . 7 . 1116, 1 1 1 8 , and 1124. Section
9.
ll. 13.
2, 4, 3, 6, 10. 6 , 1 , 16.
..,..."...:.,..,
(a) . 0 1234579 (c) . 0 1 2346.
(b) .0 1 23457
16
1. They have hypotenuses 1 0 , 1 5 , 20, 25 , 26, 30, 34, 3 5 , 39, 40, and 45. 3. ( 100, 2499, 250 1 ) and ( 100, 62 1 , 625). 9. Yes. 13. Only (40, 9, 4 1 ) . Section
17
3. No.
7.
5. No.
9. All even k.
Section
No .
18
1. None i s a sum of two squares. 3. The larger square is 179 , 178, 173 , 1 66 , 1 63 , 1 57 , 142 , or 1 3 1 . 7. Yes .
Answers to Selected OddNumbered Problems
235
Section 19 1 . 3 1 = 52 + 22 + 1 2 + 1 2 , 37 '" 62 + 1 2 = 42 + 42 + 2 2 + P , 4 1 '" 62 + 22 + F = 52 + 42 = 42 + 42 + 3 2 , 43 = 52 + 42 + P + P = 5" + 32 + 3 2 , 47 = 62 + 32 + 12 + 12 52 + 32 + 32 + 22 , 53 = 72 + 22 = 62 + 42 + ] 2 . =
1 482 + 1 082 + 1 22 + 42 • 5. 02 + 72 "" 82 + 62 "" 42 + 42 ",  2 (mod 1 7) .
3.
Section 20 1. 3 + 8'12 , 5 + 2 · 6 '/2 , 7 + 2 · 1 2 1/2 , 19 + 6 · 1 0 l!2 . 3 . (3, 1) and (1 7, 6), (5, 2) and (49, 20) , ( 8 , 1) and ( 1 27, 16). 5. The three smallest positive solutions are ( 1 , 1 ) , ( 3 , 4), and ( 1 1 , 1 5) .
7 . (c) There are infinitely many solutions. 9 . (b) Triangles with sides (3, 4, 5), ( 1 3 , 14, 1 5) , and (5 1 , 52, 53) are the
smallest.
13. X k lYk approaches n 1/ 2 . 15. The next solution i s 1 082 + 1092
+ I ID2 '" 1 3 32
+
1 342
.
Section 21 1. (a) 1 979.
(b) None.
Section 23: Additional Problems
Section 1
1 . All solutions are x = I + 1 9t , y = 1
7 . (n , n + 20) = 1 , 2, 4, 5, 1 0, or 20.

2 3 t , t an integer.
9. Yes . Section 2 1 . In its primepower decomposition each exponent is a mUltiple of k . 3 . (a) 60, 2p2q.
Section 3 1.
Four ways. There may be 14, 1 5 ; 1 6, or 17 quarters.
Section 4 3 . (a) 0, 1 , 4, or 7 .
(b) No.
7 . Any n "'" 1 5 (mod 30) satisfies the three congruences. Section 5 1.
x '" 534 (mod 240 1 ) .
3. k = 1 or 2.
236
Answers to Selected OddNumbered Problems
Section 7 3 . (c) 1 8 , 20, and 24 are examples. 5. (b) No. Section 8 7. All a � 3 . Section 9 3. All n which are a power of 2 times an integer relatively prime to 3 . 7 . (a) 1 , 1 , 2 , 1 , 2 , 2, 2 . 1 3 . (a) 0 ,  13 , 0,  15, 0 .
(b) k

1.
(d) j + k
(c) k .

1.
(d) _p h' .
(c) 0 .
(b) p o
1 5 . All such 2k , k < 50, are 14, 26, 34, 38, 50, 62, 68 , 74, 76, 86, 90 , 94 , and 98 . Section 1 0 1 . None. 3. 17. 5 . 1 9830 1 2 .,. 1 (mod 1024) and 198 3 is not a mUltiple of 5 1 2 . 9.
k °
indzk (mod 19) k
11
indzk (mod 19)
12
Section 1 1
1 . No solutions, x
""
°
3
4
5
6
7
8
9
10
13
2
16
14
6
3
8
17
12
13
14
IS
16
17
18
15
5
7
11
10
9
2
4
or 4 (mod 5), x .., 2 (mod 5).
3 . 1 , 2 , 4, 7 , 8 , 9, 10, 14, 16, 1 8 , 19, 20, 25, 28. 5. 3, I I , and 17. 7 . Yes : 2 1 or 76. Yes: 16 or 37. 9. No. Section 12 1 . No . There are no longer sequences . 3 . (c) 2, 3 , and 8 . Section 13
1 . (a) (a , b ) = (2, 1 6) or ( 1 , 3 3 ) .
(b) (a , b )
=
(6, 17).
Section 1 5
1 . 4>(3 14 15) I 3 14 14.
3 . In any base b such that 2, 3, and 5 divide b. 5 . A computer program may be necessary to find the next example, even though it comes before 11 100: 1/77 and 1178 both have period 6 .
Answers to Selected OddNumbered Problems
237
Section 1 7 7 . Yes . 9. x =
(ac)n' , y
=
(beY" , x. =
c ' , where c
=
a r.'
+ b r.' and rn2 + 1 = (n  l ) s .
Section 1 8 9. None.
Section 19 1. 2387i + 154' + 66' + 0', among others .
Section 20 1 . Approximately . 09, .002, .00007, and .000002.
5.
336312378.
Miscellaneous
5.
Eig,ht 1 3 ' s, two 9' s, and seventyeight 3 s . '
7. Two scotch , one rum , and four vodka. 1 7. 32076. 19. 5 .
2 3 . 5 3 3 = 1 3 · 4 1 , 1 073 27. No. 3 1 . (a)
a
4 1 . (c , d)
= =
=
29 · 37.
7 , p = 17.
(4, 3 ) or ( 1 1 , 9) .
49. 1 996, 2024, 2052, and 2080.
5 1 . No.
53 . 2 d (N2) = 1 .
55. (a)
p

2.
(b) p '  2p .
65. x =  1  9m + 8n , y = 1 + 9m  7n , x. = m is one way of writing the solutions. 73. Yes . 8 1 . For example , 2 2 + 5 2 + . . 83 . 1 , 2 , 3 , 5 , 7 , and 1 1 . 85. 9 = ( 12/5)2 +
(915)2
97. (b) Yes: 1 806.
Appendix A 1 3 . No.
=
.
+ 232 + 262 = 482•
(36/13)2 + ( 15/1 3 )' = (24/ 1 7)2
(c) No others .
+
(45/17)2 = .
Comments on Selected OddNumbered Problems
The outlines of solutions that follow may not be the easiest or the quickest, but they will ahnost always work. The hints may not convey �nything, but they are almost nc>¥er misleading. Section 2
7. 60466 176 = 6'0
=
(65)2
=
(61 )5.
11.
(b) 78 :s; (25ab )/32 :S 82 no matter what the digits a and b are , and none of 78, 79, 80, 8 1 , and 82 is a power, except 8 1 .
13.
A counterexample i s : 3 1 60, 5 60, and both 3 and 5 are greater than 60114 = 2 .78 . . . . But 60/3 . 5 4 is not prime. The statement would be true if p and q were the two smallest prime factors of n .
1
=
15.
2 "  1 = 2047
=
23 . 89 i s composite and 1 1 is not.
Section 5 1. 15. 19.
40x "" 777 ...  1000 (mod 1777),
so
x "'"  25 "" 1752 (mod 1777).
2'5 . 3 '0 . 5".
The condition (m;. mj) 1 (aj  aj) for all i and}. i 1= j, is both necessary and sufficient for the system to have a  solution.
Section 6 I I .  I "" (p  I) ! "" (p  1 )(p  2)(p  3) ! "" (  I)( 2)(p  3)! "" 2(p  3) ! (mod p). 1 5 . (b) I P + 2P +  . . + (p  I)" "'" 1 + 2 +   . + (p  1 ) "" p (p  1)/2 "'" 0 (mod p), since (p  1 )/2 is an integer . 238
Comments on Selected OddNumbered Problems
239
(a) a p+q  a lHI  a q+J + a 2 = (aP  a )(a Q  a ) . (b) a ''''  a P ;s a O  a (mod p) an d a PO  a O "'" a l>  a (mod q ) , s o both p and q divide apq  (I"  a" + a . 1 9 . If n '" 0 (mod p), then 1 + n + n2 + . . . + n P 2 "", 1 (mod p). If n '" 1 (mod p ) , the sum is congruent to p  1 (mod p ) . If n '" 0 or 1 (mod p ) , the sum is (n PJ  l)/(n  1 ) , and p divides the numerator but not the denominator of the fraction. Thus p divides the sum. 17.
Section 7 15.
17.
19.
If dl > da, . . . , dk are the divisors of n, then 11d + 1/d2 + . . . + lIdk J u(n)/n . To prove this, divide both sides of dk + dk J + . . . + dl = u(n) by n . =
If x + y = a and x  y b , then ab = N , and a can have 2 d (N ) different values : the positive divisors of N and their negatives. Since N is odd, so are a and b , and hence each pair (a , b ) gives a distinct solution ex , y). Uk(P') = 1 + pk + p2k + . . . + p'l: and Uk (P/'P " . . . p/') = Uk (PJe' )Uk (Pz" ) =
2
. . . Uk (P /' ) ,
'
Section 9 9.
The sum of the positive integers less than n and relatively prime to it is n cp(n)12 .
15.
n is of the form 2° with a s 3 , 2°p with a s 2, or 2apq with a ,.; 1 , where P and q are odd. Any other form would have cp(n) divisible by an odd prime or by 8.
17. Put m 2rM and n = 2'N, where M and N are odd and one of r and s is 1 . Then (M, N ) = 1 , so =
while cf:>(m)cp(n) = 2rJcp(M ) 2' Jcp(N) .
19.
n is divisible by 6, so n = 2a3 bN with (2, N ) = ( 3 , N ) = 1 . Thus cf:>(n) = 2°3b Jcp(N ) s 203 b'N
s
n/3.
Section 1 0 11.
From Problem 1 0 , g = h k (mod p ) with k odd, so
(gh )' P J )12 "" (h( k+ 1 >I2),P J ) "" 1 (mod p),
and gh does not have order p  1 . 13.
Since a '" 1 (mod p), at + a + 1
lIE
0 (mod p ) , whence
(a + 1)3 .,. a3 + 3 a 2 + 3 a + 1 "" 3(a2 + a + 1)  1
""  1 (m od p ) .
Comments on Selected OddNumbered Problems
240
Thus the order of a + 1 is a divisor of 6. It is easy to verify that it is not 1 or
2.
15. We know that a'J ""  1 , so a3 ... a and a4 "" 1 (mod p l . Thus (a + 1)4 "" a4 + ""
4
4a l + 6a1 + 4a
+ 1 "" 1  4 a  6 +
4a
+ 1
(mod p ) .
1 7 . From Problem 14, the primes other than 3 that can divide 2 1 9 + 1 are o f the form 38k + 1 . Since « 219 + 1)/3) 1 I'J < 4 1 9 , the only primes to test are 1 9 1 and 229.
19. Let x
=
g k. Then gX E x + 1 (mod p )
a n d g1x "'" x + 2 (mod p),
or J
( g  l)x "" 1 (mod p)
and (g2  1)x "'" 2 (mod pl.
The latter congruence implies (g + 1}(g  l ) x "" (g + 1 ) . 1 "" 2 (mod p), which i s i mpossible. Section
15.
11
71 (n 2 + 1) implies ( 117) =  1 .
Section
n
"
""
 1 (mod 7 ) , but this is impossible because
12
1. If p > 3 , then those integers k such that the least residue (mod p ) of 3k is greater than (p  1)/2 are just those k such that (p  1)/6 < k :5 (p  1)/3 . Consider cases: p = l2n + 1 , 5 , 7, or 1 1 .
3. Show that if p ""  1 (mod
4)
2·  1 , where q is an odd prime, then p = 2 . so (3/p) = (p/3) .
=
4{q] )12
 1
5. (a) Note that q "" 1 (mod 4) always. 9.
(b) Consider two cases: p "" 1 and p "'" 3 (mod 4).
(a) (  3/p ) = (  lip )(3/p ) and apply Problem 1 . (b) Ifx" + xr + r" "" 0 (mod p ) , then (x + s)2 ""  3 s2 (mod p ) , where s is the unique solution of 2s ... r (mod p ) .
Section 13
15. Write 10,0000 in the base 2 ( 1 1 0000 1 1 0 1 0 1 00000), and it i s possible to get 100000 as a sum of powers of two.
19.
(c) Suppose that an integer has two representations. Then
(N),
whence N = 1 . If k is zero and j is not,
n/3 = 3jW = 2 3Hcf>(N),
which is impossible since 2tf N. Ifj = 0, then n13 is not an integer.
Comments 011 Selected OddNumbered Problems
"" . .. ( _ l )n/dcp (d) = dL. In
13.
243
{11 !
f n is odd . 0 Ifl1 IS even.
Section 1 0 7 . If m 2: n, the result follows by multiplying both sides of a (mod p) by a". If /71 < /1 , start with a " "" a "II'a'" (mod p ) ,
"'
�
a II'"a "
1 1 . Let indo {f = 1' . Then g r ([ (mod p ) , s o a " g r" (mod p) . B u t this says nl' (mod p  1 ) , which was what was to be shown . that indy a"
"'"
"'"
"'"
1 5 . The first part is Problem 2 0(a) of Section 1 0 again . For the second part, see Roberts [ 14, p. 294] . Section 1 1 9. If p "" 7 (mod 8), then q = (p  1 )/2 "", 3 (mod 4), so (qlp) =  (plq) =  ( lIq) =  1 . Section 1 2
1 . One o f p , 4p + 1 , and 1 6p + 5 , i s divisible by 3 for all p .
3 . (a) The proposed equation i s impossible (mod 3 ) . (b) /71 2 = /1 2 + (/1 + 1 )2 + . . . + ( /1 + k)2 = (k + 1 )/1 2 + k(k + 1)/1 + ( P + 22 + . . . + k2) "" J 2 + 22 + . . . + k2 (mod k + 1 ) . 5 . /17:''' '''' /1)/ 1 "", 1 (mod p), and  1 = (nip ) "" /1'JI l l/2 "", /1'l!"' (mod p ) , s o /1 has order 2"' (mod p) . Section 1 3 1 . (c) a ( 1 + b· + b 2) = b ( l + c) implies b l a . B ut 5. 1 =  } + 1 . 2  1 + (1) . 2 + 1 . 4 = .
O < a < b.
=
Section 1 4 5 . I t i s like the test in Additional Problem 1 0 , Section 4 . Section 1 6
1 . I f n + (n + 1 ) = m 2 , then n 2 + m 2 = (n + 1)'.
3 . If n = t (t  1 )/2 and m = t (t + 1)/2, then m 2  /1 2 = t 3.
5 . If mn(m '  /12) = (2 m n + (/11'  n ') + (/112 + /12» , then 2 k = l1(m  11 ) . If 2 k + a b , then m = a + b and 11 = a .
k
Section 1 7 5 . If p
J
xyz ,
then Xl'l
... yP I ... ZP I "'"
7. Yes, because (/1 2 , n + 1 ) = 1 .
1 (mod p ) .
Comments
244""
on Selected OddNumbered Problems
Section 1 8
that 4'(8k + 7) = x ' + y2 + Z 2 . Apply Problt"m 1 e times to get " ' 8k + 7 = Xl2 + YI + ZI Then apply Problem 2. 5 . If n  2 (mod 4), then n = x 2  y' is impossible.
3 . . Suppose
7. If n = x (r + l)12 + y (y + l)/2 , then 4n + l = (r + y + l)2 + (r  y)' . 9. Noneall are congruent to
(mod 4).
3
Section 19 1 . 5725841 = 1 12 . 473 2 1 , so it i s necessary only to write 4732 1 as a sum of four squares . 5 . I f k l , k" . . . , k r are odd, then kl 2 + k i t + . . . + k,2 ... r (mod 8). Section 20 1. The approximations are 3/2, 1 71 1 2 , 99nO, and 577/408 . Thi s follows from Lemma 2.
3.
Miscellaneous Problems 9. The first numbers on the lefthand sides are every other triangular number. The result may be written (2n! + n)2 + . . . + (2n' + 2n)' = (2n2 + 2n + 1 )2 + . "
1 3 . fen )
+
(2n' + 3n)2 .
= ( 3 + (  l)n+ l)/4 i s one . f(n ) = (n + 1  2 [nI2})/2 i s another.
19.
3ml2  a
Ann ' s age Mary' s age = 5a  m , s o 5 m = 12a .
Now
Then
a m
3 m12 5a
27. x2 + (x + 1)2 = (r (x + 1 ) + 1)2  (, (x + 1))2.
29. No: Xl + (1  x) = x + (l  X)2 for aU x. 3 1 . (b)
2a
'" a3 E 3, plies p = 1 .
3a
"" 0 4 ""
4 (mod p) imply 0
'"'
1 (mod p), which im
3 3 . (a) If m i s composite, then one of p = 2 , 3 , 5 , 7 divides m. But then p i (2IOn + m ) too.
35.
Note that there is no loss of generality in assuming that (0 , Complete the square on the righthand side t o get (r +
(a
+ b»
2
b) =
1.
= 2(a 2 + b2 + ab ) ,
and that i s impossible (mod 4) . 39. All are congruent to divisible by 3 .
1
(mod
3).
If oot, two of the integers would be
4 1 . c 2 + 5 = c d + 3 d , s o d = c  3  1 4/(c + 3) , whence c = 4 or 1 1 .
Comments
Selected OddNumbered Problems
all
43 . Any divisor is 2 rq < where ,. s p 47. Interchange 49 and 94.

245
1 , s = 0 or I , and q = 2 J>  I .
49. There are 3 . 365 + 366 = 1461 days between one leap year February 1 and the next . 1461 "" 5 (mod 7) . Remember that 2000 will be a leap year. 5 1 . (a) If n is composite, 10"  1 is composite . (b) 1 1 1 = 3 . 37. 53. Put x = N + a and y = N + b. Then ab = N� . There are deNt) positive values of a that satisfy this and d (Nt) negative values, one of which is N. 5 5 . (c) Let l/1(n) be the number of elements in. the sequence 1 . 2 , 2 ' 3, . . . , n (n + I ) which are relatively prime to n . If n = p " , p an odd prime, then l/1(n) = p " 1 ( p 2) . 1/1 is multiplicative ; thus t/J(n) can be found for: any positive integer n . 59. For example, 1 9 = 1 6 + 2 + 1 and 1 9 appears i n lists 1 6, 2 , and 1 .

6 1 . The harmonic mean of the divisors of n is
(
1 d(n)
�d
)
1 '
'
which is nd (n)IO'(n ) . If n = 2 1, 1(21'  I ) , O'(n) = 2 n , d (n ) = 2p , and the harmonic mean is p .
63 . 2r� + 3 "" 3 o r 5 (mod 8) , which i s impossible. 69 . 9'0 "" 1 (mod 1 00). 7 1 . 3 1 (2'" + 1).
73 . Yes : 2U'(22k 1  1 ) = P + 33 + . . . + ( 2 k  1 )3 i s true for all be shown using the fact that
k,
a s may
P + 23 + . . . + n J = (n (n + 1 )/2) 1 .
75 . If n = 2 ,, 1 q , where q = 2P  1 is prime , then the divisors of n are 1 , 2 , . . . , 2" 1 , q , 2 q , . . . , 2 ,, 1q ,
and their product is n " . 7 7 . For each factors. 79. (a)
5
that appears as a factor of n t , there are a t least two even
n
2
3
4
5
6
7
8
9
10
11
12
13
14
15
fen )
2
3
4
5
3
7
6
6
5
11
4
13
7
5
n
16
17
18
19
20
fen )
8
17
6
19
5.
83 . If p > 1 2 , then p

9 is even and composite.
85. If 9 = (alc)2 + (blc)2, then a 2 + b 2 = 9c2 . Hence a 1 + b2
...
0 (mod 9) , and
246
Comments on Selected OddNumbered Problems
this implies that a = 3 r , b = 3 s . Thus r' + S2 = c:!, and this has infinitely many solutions. 91. For n so x
2:
2 , x = y is impossible, so we may assume that x > y . Then
ex + 1 ) " > x " + nx "I > x " + y " > z " > x " ,
+ 1 > z > x , which i s impossible.
93 . Iff(rls ) = 0 , then r l a " and s l a o . Hence r and s are odd. But this implies that 0 = s "f(rls) is the sum of some even integers and an odd number of
odd integers, which is impossible.
95 . Induction, using the identity
23k + 1 ..
=
( 23k + I)(p 3k  23k + 1 ) ,
i s one method that will work. 97 . (a) Let m = P ,P, . . . P k with P I < p, < . . . < P k ' Then p, lm implies (p,  l)m , so P2  1 = P I ' Thus P I = 2 and P2 = 3 . Further, P l l m implies (p,  1 ) 1 m , so (p,  1 ) I P I P 2 , whence P o = 7 . Similarly, (P4  1) 42, so P. = 43 . Finally, (Po  \) 1 2 · 3 . 7 · 43 , but there is no
1
such prime. (b) m = 2 · 3 ' 7 · 43 1 806 has the desired property . (c) But there are no others. =
99 . Apply Fermat' s Theorem: there i s a progression starting at any term with ratio 2 /)  1 .
Appendix A 3 . 13 + 3' + . "
+ (2 k  1 )3 = k:!(2k:!

I).
5 . t . = n (n + 1)/2 .
9. (n  I)n (n + l)(n + 2) = (n:! + n 1 3 . 8 t. + 1 = (2n + 1)1 .

If  1 .
1 5 . f511 + 5 = f./l + 5f'. 1 + 10f.,,2 + 1Of,;II:I + 5f5114 + f5115'
Index ·
Absolute pseudoprime, 1 86
Conway, John Horton, 2 1 3 Cubic residue, 1 9 1
Abundant number, 50, 61 ·
Alexandria , 20
Ami cable pair, 60
Deficient number, 61
Amicable pair, reduced, 2 1 5 Ancient civilizations, 1 06
D e la Vallee Poussin, Charles ( 1 86�
1 962), 165
Archimedes (2872 12 Be), 14, 27
Descartes, Rene ( I 5� 1 650), 1 1 9, 149,
Arithmetic progressi on of primes, 173
1 87
Diophantus of Alexandria (ca. AD 250?),
20, 1 3 5 , 149
Babylonians, ancient , 38, 106, 127
Dirichlet, Peter Gustav Lejeune (1 805
Bachet, Claude Gaspard, Sieur de
1859), 1 57 , 173
Merizac ( 1 587 1638), 149 Beiler, Albert, 128
Dirichlet's Theorem, 1 73 Divides, 2
Bell, Eric Temple 08831 960), 1 56 Bertrand's Theorem, 177ff
Division algorithm, 5
Divisor, greatest common, 4, 1 8
Bhascara (or Bhaskara) ( 1 1 14 1 1 58),
Divisor, unitary, 188 Divisor, weak, 196 Dometric system, 1 18
133, 1 98
Binomial expansion, 177 Brahmagupta (ca. 630) , 1 60
Duodecimal Society of Ameri ca , 1 14 ,
1 18
Cardano, Gerol amo ( 1501 1 576), 1 86
Carmichael's Conjecture, 2 1 5 Casting out nines, 32 Catalan, Eugene Charles ( 1 8 1 4 1 894) ,
Egyptian fra ctions, 2 1 3
Eratosthenes (27�195 Be), 13 Euclid (ca. 300 Be), 4, 12, 14, 15, 57,
212
58
Chinese Remainder Theorem , 3 8 , 39,
Euclidean Algorithm, 5, 7, 18, 2 1 i
21 1
Euler, Leonhard 0 707 1783), 48; 57,
Composite, 10 Computers, 2 10ff
59 , 64 , 89, 147, 149, 150, 163, 174, 1 88 . 1 95 , 203
247
248
Index
Euler's Criterion, 85ff, 95, 190 Euler's q,function, 55, 64. 79 Euler's Theorem, 65ff, 75 Exponent to which an integer belongs, 74 Factorization, 1 8 , 217 Fang, Joong, 1 5 5 Fermat. PierreSimon de ( 1 601 1665),
Legendre symbol, 87 Leibniz, Gottfried Wilhelm ( 1 64617 16), 28
Levels of mathematical understanding, 104
Lilivati, 198 Linnik, Ju. V., 15 Loomis, Elisha, 128
42, 60, 6 1 , 135, 137, 148, 149, 198
Fermat number, 199 Fermat ' s Conjecture, 1 36 Fermat's Last Theorem. 136 Fermat's Theorem, 42ff, 49. 63, 65, 75, 79, 246
Fibonacci numbers, 209 Function, multiplicative, 53 Garfield, James, 122 Gauss, Carl Friedrich ( 1777 1855) , 28, 70, 74 , 89 , 90, 94 , 9 5 , 99 , 102 , 1 64 , 165, 197 Gauss's Lemma, 94. 99. 10 1 , 102 Girard, Albert (ca. 1610), 148 Goldbach, Christian ( 1690 1764), 146
Goldbach' s Conjecture , 147 Greatestinteger principle, 2 Hadamard , Jacques Salomon ( 1 8651962), 165
Hardy, Geoffrey Henry ( 1 877 1947) , 172, 224
Hilbert, David ( 1 862 1 943) , 147, 155 Historical remarks, interesting. See In teresting historical remarks Impossible diophantine equatio[1 73 Index, 247 Index of an integer, 1 90 Integers, Iff Interesting historical remarks, 14, 20, 27, 38, 43, 60, 106, 1 19, 127, 135, 136, 146, 149, 160 Irrational numbers, 126, 140, 1 56 Irreducible semiperfect number, 2 1 2
kperfect number, 62 Kulik, Jacob Phillipp ( 1 793 1863), 15 Lagrange , Joseph Louis ( 1 736 18 1 3) , 43 , 1 50, 1 57
Landau, Edmund, 136 Large primes, 10, 12, 43 Least common mUltiple, 183 Leastinteger principle, 2 Least residue, 28 Legendre, Adrien Marie (17521833), 87, 164
Mathematical induction, l l , 12, 15, 17, 53, 130, 168, 178, 179, 202, 205
Mathematical understanding, levels of, 1 04 Mersenne. Marin ( 1 5881648), 55, 60 Mersenne primes, 60, 104 Mills, W. H . , 175 Multiple, least common, 183 MUltiplicative function, 53, 67 Newton, Isaac ( 1 6421727), 28 Nonresidue, quadratic, 8 5 Numbers abundant, 6 1 amicable, 60 deficient, 6 1 Fermat, 1 99 Fibonacci , 209 irrational, 126, 140, 156 irreducible semiperfect, 2 1 2 kperfect, 62 perfect, 50, 57, 202 powerful, 196 practical, 187 semiperfect, 2 1 2 superduperperfect, 2 1 4 superperfect, 6 2 triangular, 6 1 , 1 3 4 , 194, 208, 244 Number theory, sex in, 249 Numerology, 187 Order of an integer, 73 Pacioli, Luca (ca. 1445 1510) , 20 1 Palindrome, 33, 196 Pascal, Blaise ( 1 623 1662) , 42, I�n Pel!, John ( 1 6 1 0 1685), 156 Pell ' s Equation, 156 Perfect numbers, 50, 57, 202 Pillai, S. S . , 2 1 4 Powerful number, 196 Practical number, 186 Prime, 1 0 Prime Number Theorem, 164 Primepower decomposition, 18 Primes in arithmetic progression, 173 Prome, 17 Pseudoprime, 186
Index Pythagoras (ca. 550
BC) ,
127
Sieve of Eratosthenes, 1 3
Pythagorean Theorem, 127 pythagorean triangles, 1 28f[, 1 39, 1 93
Solution of a congruence, 35, 46 Stevin, Simon ( 1 548 1 620) , 1 1 9 Superduperperfect numbers, 2 14
Quadratic nonresidues, 85 Quadratic reciprocity, 94ff Quadratic reciprocity theorem , 90
Superperfect numbers, 62
Quadratic residues, 85, 142 Reduced amicable pair, 2 1 5 Relatively prime, 5 Residues, cubic, 1 9 1 Residues, quadratic, 85
Riemann, Georg Friedrich Bernhard
( 1 826 1 866) , 165
Roberts, Joe, 243
Roberval, Giles Persone de ( 1 602 1 675),
1 98 Schaaf, William , 128 Selberg, Alte, 1 5
Semiperfect number, 2 1 2 Sex i n number theory, 248 Shakespeare, William, 127
249
Tartaglia (Niccolo Fontana) ( 1 499 1559),
19
Tchebyshev, Pafnuti Lvovitch ( 1 82 1
1894), 164
Triangles, Pythagorean, 128 Triangular number, 6 1 , 1 34, 1 94, 208, 244 Unique factorization theorem, 1 0, 1 6 ,
130 Unit, 1 0 U nitary divisor, 1 88 Waring, Edward ( 1 7341793), 43 Waring's Problem , 1 46 Weak divisor, 1 96 Wilson, John ( 1 74 1  1 793), 42 Wilson' s Theorem, 42ff, 80, 1 44, 180, 2 14