MATHEMATICAL MONOGRAPHS. EDITED BY MANSFIELD MERRIMAN and ROBERT S. WOODWARD. No. 13. THE THEORY OF NUMBERS BY ROBERT D. CARMICHAEL, Associate Professor of Mathematics in Indiana University FIRST EDITION FIRST THOUSAND NEW YORK JOHN WILEY & SONS, Inc. London: CHAPMAN & HALL: Limited 1914 Copyright, 19 14. BY ROBERT D. CARMICHAEL. $0*0*13 THE SCIENTIFIC PRESS ROBERT DRUMMOND AND COMPANY BROOKLYN, N. Y. EDITORS' PREFACE. The volume called Higher Mathematics, the third edition of which was published in 1900, contained eleven chapters by- eleven authors, each chapter being independent of the others, but all supposing the reader to have at least a mathematical training equivalent to that given in classical and engineering colleges. The publication of that volume was discontinued in 1906, and the chapters have since been issued in separate Monographs, they being generally enlarged by additional articles or appendices which either amplify the former pres- entation or record recent advances. This plan of publication was arranged in order to meet the demand of teachers and the convenience of classes, and it was also thought that it would prove advantageous to readers in special lines of mathe- matical literature. It is the intention of the publishers and editors to add other monographs to the series from time to time, if the demand seems to warrant it. Among the topics which are under con- sideration are those of elliptic functions, the theory of quantics, the group theory, the calculus of variations, and non-Euclidean geometry; possibly also monographs on branches of astronomy, mechanics, and mathematical physics may be included. It is the hope of the editors that this Series of Monographs may tend to promote mathematical study and research over a wider field than that which the former volume has occupied. 302093 PREFACE The purpose of this little book is to give the reader a con- venient introduction to the theory of numbers, one of the most extensive and most elegant disciplines in the whole body of mathematics. The arrangement of the material is as follows : The first five chapters are devoted to the development of those elements which are essential to any study of the subject. The sixth and last chapter is intended to give the reader some indication of the direction of further study with a brief account of the nature of the material in each of the topics suggested. The treatment throughout is made as brief as is possible con- sistent with clearness and is confined entirely to fundamental matters. This is done because it is believed that in this way the book may best be made to serve its purpose as an intro- duction to the theory of numbers. Numerous problems are supplied throughout the text. These have been selected with great care so as to serve as excel- lent exercises for the student's introductory training in the methods of number theory and to afford at the same time a further collection of useful results. The exercises marked with a star are more difficult than the others; they will doubtless appeal to the best students. Finally, I should add that this book is made up from the material used by me in lectures in Indiana University during the past two years; and the selection of matter, especially of exercises, has been based on the experience gained in this way. R. D. Carmichael. 4 CONTENTS CHAPTER I. ELEMENTARY PROPERTIES OF INTEGERS PAGE j i. Fundamental Notions and Laws 7 j 2. Definition of Divisibility. The Unit 8 \ 3. Prime Numbers. The Sieve of Eratosthenes 10 & 4. The Number of Primes is Infinite. 12 & 5. The Fundamental Theorem of Euclid 13 I 6. Divisibility by a Prime Number 13 § 7. The Unique Factorization Theorem 14 I 8. The Divisors of an Integer 16 § 9. The Greatest Common Factor of Two or More Integers 18 10. The Least Common Multiple of Two or More Integers 20 11. Scales of Notation 22 12. Highest Power of a Prime p Contained in n\ 24 13. Remarks Concerning Prime Numbers. . '. 28 CHAPTER II. ON THE INDICATOR OF AN INTEGER 14. Definition. Indicator of a Prime Power 30 15. The Indicator of a Product 30 16. The Indicator of any Positive Integer 32 17. Sum of the Indicators of the Divisors of a Number 35 CHAPTER III. ELEMENTARY PROPERTIES OF CONGRUENCES 18. Congruences Modulo m 37 19. Solutions of Congruences by Triai 39 20. Properties of Congruences Relative to Division 40 21. Congruences with a Prime Modulus 41 22. Linear Congruences 43 CHAPTER IV. THE THEOREMS OF FERMAT AND WILSON 23. Fermat's General Theorem 47 24. Euler's Proof of the Simple Fermat Theorem 48 : 25. Wilson's Theorem 49 5 D CONTENTS PAGE § 26. The Converse of Wilson's Theorem 50 § 27. Impossibility of 1 -2 -3 • ... •« — i-f i=m*, «>s 51 § 28. Extension of Fermat's Theorem : 52 § 29. On the Converse of Fermat's Simple Theorem 55 § 30. Application of Previous Results to Linear Congruences 56 §31. Application of the Preceding Results to the Theory of Quad- ratic Residues 57 CHAPTER V. PRIMITIVE ROOTS MODULO m § 32. Exponent of an Integer Modulo m 61 § i2>- Another Proof of Fermat's General Theorem 63 § 34. Definition of Primitive Roots 65 § 35. Primitive Roots Modulo p 66 § 36. Primitive Roots Modulo p a , p an Odd Prime '. 68 § 37. Primitive Roots Modulo 2p a , p an Odd Prime 70 § 38. Recapitulation 71 § 39. Primitive X-roots 71 CHAPTER VI. OTHER TOPICS § 40. Introduction 76 § 41. Theory of Quadratic Residues 77 § 42. Galois Imaginaries 80 § 43. Arithmetic Forms 81 § 44. Analytical Theory of Numbers 83 § 45. Diophantine Equations 84 § 46. Pythagorean Triangles 85 § 47. The Equation x n +y n = i n 9 i THE THEORY OF NUMBERS CHAPTER I ELEMENTARY PROPERTIES OF INTEGERS § i. Fundamental Notions and Laws In the present chapter we are concerned primarily with certain elementary properties of the positive integers i, 2, 3, 4, '...•. . It will sometimes be convenient, when no confusion can arise, to employ the word integer or the word number in the sense of positive integer. We shall suppose that the integers are already defined, either by the process of counting or otherwise. We assume further that the meaning of the terms greater, less, equal, sum, difference, product is known. From the ideas and definitions thus assumed to be known follow immediately the theorems : I. The sum of any two integers is an integer. II. The difference of any two integers is an integer. III. The product of any two integers is an integer. Other fundamental theorems, which we take without proof, are embodied in the following formulas: IV. a+b = b+a. V. aXb = bXa. VI. (a+b)+c = a+(b+c). VII. (aXb)Xc = aX(bXc). VIII. aX(b+c) =aXb+aXc. Here a, b } c denote any positive integers. 8 ♦/• * 2/2 •••{ ; •: XHIJO^y Of NUMBERS These formulas are equivalent in order to the following five theorems: addition is commutative; multiplication is commutative; addition is associative; multiplication is asso- ciative; multiplication is distributive with respect to addition. EXERCISES Prove the following relations: (1+2+ . . . +n)K of each of the following series: \\ i 3 +3 3 + 5 3 + • • • +(2w-i) 3 . 5. Discover and establish the law suggested by the equations i 2 = 0+1, 2 2 = i-f-3, 3 2 = 3+6, 4 2 = 6+io, . . .; by the equations i = i 3 , 3+5 — 2 3 , 7+9+11=3?, i3 + i5 + i74-i9 = 4 3 , § 2. Definition of Divisibility. The Unit Definitions. An integer a is said to be divisible by an integer b if there exists an integer c such that a — be. It is clear from this definition that a is also divisible by c. The integers b and c are said to be divisors or factors of a; and a is said to be a multiple of b or of c. The process of finding two integers b and c such that be is equal to a given integer a is called the process of resolving a into factors or of factoring a; and a is said to be resolved into factors or to be factored. We have the following fundamental theorems: I. If b is a divisor of a and c is a divisor of b, then c is a divisor of a. Since & is a divisor of a there exists an integer /3 such that a = &j8. Since c is a divisor of b there exists an integer 7 such that b = cy. Substituting this value of b in the equation a = 5/3 we have a = cyfi. But from theorem III of § i it follows that 7jS is an integer; hence, c is a divisor of a, as was to be proved. ELEMENTARY PROPERTIES OF INTEGERS 9 II. If c is a divisor of both a and b, then c is a divisor of the sum of a and b. From the hypothesis of the theorem it follows that integers a and /3 exist such that a = ca, b = c(3. Adding, we have a + b = ca+cP = c(a-\-p)=c8, where 5 is an integer. Hence, c is a divisor oi0j-b. III. If c is a divisor of both a and b, then c is a divisor of the difference of a and b. The proof is analogous to that of the preceding theorem. DEFINITIONS. If a and b are both divisiblsJby c, then c is said to be a common divisor or a common fa»r«: a and b. Every two integers have the common factor ifHrTne greatest integer which divides both a ariU b is called the greatest common divisor of a and b. More generally, we define in a similar way a common divisor and the greatest common divisor of n integers 0i, a 2 , . . . , On. Definitions. If an integer a is a multiple -of each of two or more integers it is called a common multiple of these integers. The product of any set of integers is a common multiple of the set. The least integer which is a multiple of each of two or more integers is called their least common multiple. It is evident that the integer i is a divisor of every integer and that it is the only integer which has this property. It is called the unit. Definition. Two or more integers which have no common factor except i are said to be prime to each other or to be rela- tively prime. Definition. If a set of integers is such that no two of them have a common divisor besides i they are said to be prime each to each. EXERCISES i. Prove that n 3 — n is divisible by 6 for every positive integer n. 2. If the product of four consecutive integers is increased by i the result is a square number. ,S. Show that 2 4n+2 +i has a factor different from itself and i when n is a positive integer. 10 THEORY OF NUMBERS § 3. Prime Numbers. The Sieve of Eratosthenes Definition. If an integer p is different from 1 and has no divisor except itself and 1 it is said to be a prime number or to be a prime. Definition. An integer which has at least one divisor other than itself and 1 is said to be a composite number or to be composite. All integers are thus divided into three classes: 1) The unity 2) Prime numbers; ^ j 3) Composite numbers. We have seen that the first class contains only a single number. The third class evidently contains an infinitude of numbers; for, it contains all the numbers 2 ? , 2 3 , 2 4 , . . . . In the next section we shall show that the second class also contains an infinitude of numbers. We shall now show that every number of the third class contains one of the second class as a factor, by proving the following theorem: I. Every integer greater than 1 has a prime factor. Let m be any integer which is greater than 1. We have to show that it has a prime factor. If m is prime there is the prime factor m itself. If m is not prime we have w = mim2, where m\ and ni2 are positive integers both of which are less than m. If either ni\ or ni2 is prime we have thus obtained a prime factor of m. If neither of these numbers is prime, then write rn\=m r im f 2, m\>i, w / 2>i. Both ih\ and m r 2 are factors of m and each of them is less than mi. Either we have now found in m\ or m'2 a prime factor of m or the process can be continued by separating one of these numbers into factors. Since for any given m there is evideix. I only a finite number of such steps possible, it is clear that w ELEMENTARY PROPERTIES OF INTEGERS 11 must finally arrive at a prime factor of m. From this conclu- sion the theorem follows immediately. Eratosthenes has given a useful means of finding the prime numbers which are less than any given integer m. It may be described as follows: Every prime except 2 is odd. Hence if we write down every odd number from 3 up to m we shall have in the list every prime less than m except 2. Now 3^s_a_prime. Leave it in the list; but beginning to count from 3 strike out every third number in the list. Thus every number divisible by 3, except 3 itself, is cancelled. Then begin from 5 and cancel every fifth num- ber. Then begin from the next uncancelled number, namely 7, and strike out every seventh number. Then begin from the next uncancelled number, namely 11, and strike out every eleventh number. Proceed in this way up to m. The uncan- celled numbers remaining will be the odd primes not greater than m. It is obvious that this process of cancellation need not be carried altogether so far as indicated; for if p is a prime greater than Vw, the cancellation of any p th number from p will be merely a repetition of cancellations effected by means of another factor smaller than p, as one may see by use of the following theorem. II. An integer m is prime if it has no prime factor equal to or less than I, wJiere I is the greatest integer whose square is equal to or less than m. Since m has no prime factor less than /, it follows from theorem I that it has no factor but unity less than /. Hence, if m is not prime it must be the product of two numbers each greater than /; and hence it must be equal to or greater than (7-f i) 2 . This contradicts the hypothesis on /; and hence we conclude that m is prime. EXERCISE By means of the method of Eratosthenes determine the primes less than 200. 12 THEORY OF NUMBERS §4. The Number of Primes is Infinite I. The number of primes is infinite. We shall prove this theorem by supposing that the number of primes is not infinite and showing that this leads to a con- tradiction. If the number of primes is not infinite there is a greatest prime number, which we shall denote by p. Then form the number iV = i-2-3-. . .-/>+!. Now by theorem I of § 3 N has a prime divisor q. But every non-unit divisor of iV, is obviously greater than p. Hence q is greater than />, in contradiction to the conclusion that p is the greatest prime. Thus the proof of the theorem is complete- In a similar way we may prove the following theorem: II. Among the integers of the arithmetic progression 5, II, 17, 23, ... , there is an infinite number of primes. If the number of primes in this sequence is not infinite there is a greatest prime number in the sequence; supposing that this greatest prime number exists we' shall denote it by p. Then the number N, iV^i-2-3-. . -#-i, is not divisible by any number less than or equal to p. This number N, which is of the form 6» — 1, has a prime factor. If this factor is of the form 6& — 1 we have already reached a contradiction, and our theorem is proved. If the prime is of the form 6^i-+-i the complementary factor is of the form 6^2 — 1» Every prime factor of 6&2--1 is greater than p. Hence we may treat 6^2 — 1 as we did 6n — 1 , and with a like result. Hence we must ultimately reach a prime factor of the form 6^3 — 1; for, otherwise, we should have 6w — 1 expressed as a product of prime factors all of the form 6/+1 — a result which is clearly impossible. Hence we must in any case reach a contradiction of the hypothesis. Thus the theorem is proved. The preceding results are special cases of the following more general theorem : ELEMENTARY PROPERTIES OF INTEGERS 13 III. Among the integers of the arithmetic progression a, a-\-d, a-\-2d, a-\-$d 3 . . . , there is an infinite number of primes, pro- vided that a and b are relatively prime. For the special case given in theorem II we have an elemen- tary proof; but for the general theorem the proof is difficult. We shall not give it here. EXERCISES i. Prove that there is an infinite number of primes of the form 4» — i. , 2. Show that an odd prime number can be represented as the difference of two squares in one and in only one way. 3. The expression m p — n p , in which m and n are integers and p is a prime, is either prime to p or is divisible by p 2 . 4. Prove that any prime number except 2 and 3 is of one of the forms 6w+i, 6n— 1. § 5. The Fundamental Theorem of Euclid // a and b are any two positive integers there exist integers q and r, q>o, o=rm2>ni3> ... it is clear that after a finite number of operations we shall arrive at a decomposition of m into prime factors. Thus we shall have m = pip2 • . . pr where pi, p2, . . . , pr are prime numbers. We have thus proved the first part of our theorem, which says that the decom- position of an integer (greater than unity) into prime factors is always possible. Let us now suppose that we have also a decomposition of m into prime factors as follows: m = qiq 2 . . . q s . Then we have pip2 • • . pr = qiq2 . . . q* Now pi divides the first member of this equation. Hence it also divides the second member of the equation. But pi is prime; and therefore by theorem IV of the preceding section we see that pi divides some one of the factors q\ we suppose that pi is a factor of qi. It must then be equal to qi. Hence we have p2p3 • • - pr = q 2 q3 . . . q a . By the same argument we prove that p2 is equal to some q, say qo. Then we have p3p± • • • p r = qzq± . . . q„ 16 THEORY OF NUMBERS Evidently the process may be continued until one side of the equation is reduced to i. The other side must also be reduced to i at the same time. Hence it follows that the two decom- positions of m are in fact identical. This completes the proof of the theorem. The result which we have thus demonstrated is easily the most important theorem in the theory of integers. It can also be stated in a different form more convenient for some purposes: II. Every non-unit positive integer m can be represented in one and in only one way in the form m = p 1 a i p 2 a 2 . . . p t an where pi, p2, . . . , p n are different primes and «i, qe, . • • , u n are positive integers. This comes immediately from the preceding representation of m in the form m = pip2 . . . p r by combining into a power of pi all the primes which are equal to pi. COROLLARY i. If a and b are relatively prime integers and c is divisible by both a and b, then c is divisible by ab. COROLLARY 2. If a and b are each prime to c then ab is prime to c. Corollary 3. If ' a is prime to c and ab is divisible by c, then b is divisible by c. § 8. The Divisors of an Integer The following theorem is an immediate corollary of the results in the preceding section : I. All the divisors of m, are of the form pi (il p2 fi2 . . . pn Pn , ol 2 + • • • +^i a 0(l+/>2+^2 2 + • • . +^2 a >) • • • (l+pn + pn 2 + ... +pn an ), when this product is expanded by multiplication. It is obvious that the number of terms in the expansion is (ai + i)(«2 + i) • • • (a»+i). Hence we have the theorem: II . The number of divisors of m is (a i + 1 ) («2 + 1 ) • • . («» + 1 ) • Again we have n(i+pi+pi 2 + . . . +y)«n ^. 1> " 1 . » » pi — i Hence, III. The sum of the divisors of m is pi a i +l -I p 2 a * + \-I «n + l _ pi -I p2 — l pn—I In a similar manner we may prove the following theorem: IV. The sum of the h th powers of the divisors of m is Pi h -i ' ' ' : ' r p n h -i ' EXERCISES i. Find numbers x such that the sum of the divisors of x is a perfect square. 2. Show that the sum of the divisors of each of the following integers is twice the integer itself: 6, 28, 496, 8128, 33550336. Find other integers x such that the sum of the divisors of x is a multiple of x. 3. Prove that the sum of two odd squares cannot be a square." ^4. Prove that the cube of any integer is the difference of the squares of two integers. ""> kg. In order that a number shall be the sum of consecutive integers, it is neces- sary and sufficient that it shall not be a power of 2. 6. Show that there exist no integers x and y (zero excluded) such that y 2 = 2x 2 . Hence, show that there does not exist a rational fraction whose square is 2. 7. The number m = pi a ^pt a - . . . p n an , where the p's are different primes and the a's are positive integers, may be separated into relatively prime factors in 2 s-1 different ways. 8. The product of the divisors of m is \/m c where v is the number of divisors of m. 18 THEORY OF NUMBERS § 9. The Greatest Common Factor of Two or More Integers Let m and n be two positive integers such that m is greater than n. Then, according to the fundamental theorem of Euclid, we can form the set of equations m = qn-{-ni, oi, then m can be represented in terms of n in one and in only one way in the form ni = a n h +a 1 n ?> ~ 1 -\- . . . +a A _ 1 w+a ftj where ao^o, o^ai*- 1 .+ai/>*- 2 + • • • +a*- 2 p+a h - 1 , 26 THEORY OF NUMBERS Adding these equations member by member and combining the second members in columns as written, we have m?m + . i-o p—i ^ aop h +aip ?t ~ 1 + . . . +ah-(ao+ai+ . . . +a h ) p-i = n — (ao+ai + . . . +flft) p-i Comparing this result with theorem I we have the following theorem : II. If n is represented in the scale of p in the form n = a p h +aip h - 1 + . . . +a h , where p is prime and a 5*o, o^al!) r ; by the least common multiple of (r!) 5 and (s\) T . 7. If n^a+p+pq+rs, where a, /3, p, q, r, s, are positive integers, then n\ is divisible by 28 THEORY OF NUMBERS S. When m and n are two relatively prime positive integers the quotient (m+n — i)! mini as an integer. 9*. If m and n are positive integers, then each of the quotients (mn)l (2w)!(2»)! w!(w!) n ' mlnl(m-\-n)l! is an integer. Generalize to & integers w, n, p, . . . . 10*. If »=a+/3+^g+rs where a, /3, p, q, r, s are positive integers, then n\ is divisible by ali3lrlpl(ql) p (sl) r . ii*. Show that (rst)l / is an integer (r, s, t being positive integers). Generalize to the case of n integers r, s, t,u, . . . . § 13. Remarks Concerning Prime Numbers We have seen that the number of primes is infinite. But the integers which have actually been identified as prime are finite in number. Moreover, the question as to whether a large number, as for instance 2 257 — 1, is prime is in general very difficult to answer. Among the large primes actually identified as such are the following: ,61 I, 2 75 -5 + I, 2 89 -I, 2 127 -I, No analytical expression for the representation of prime num- bers has yet been discovered. Fermat believed, though he con- fessed that he was unable to prove, that he had found such an analytical expression in 2 2 +1. Euler showed the error of this opinion by finding that 641 is a factor of this number for the case when ^ = 5. The subject of prime numbers is in general one of exceeding difficulty. In fact it is an easy matter to propose problems ELEMENTARY PROPERTIES OF INTEGERS 29 about prime numbers which no one has been able to solve. Some of the simplest of these are the following: i. Is there an infinite number of pairs of primes differing by 2? 2. Is every even number (other than 2) the sum of two primes or the sum of a prime and the unit? 3. Is every even number the difference of two primes or the difference of 1 and a prime number? 4. To find a prime number greater than a given prime. 5. To find the prime number which follows a given prime. jo\/ To find the number of primes not greater than a given number. 7. To compute directly the n th prime number, when n is given. CHAPTER II ON THE INDICATOR OF AN INTEGER § 14. Definition. Indicator of a Prime Power Definition. If m is any given positive integer the num- ber of positive integers not greater than m and prime to it is called the indicator of m. It is usually denoted by (m), and is sometimes called Euler's ^-function of m. More rarely, it has been given the name of totient of m. As examples we have 4>(i) = 1, 0(2) = 1, 0(3) = 2, 0(4) =2. If p is a prime number it is obvious that for each of the integers 1,2,3, . . . , p — 1 is prime to p. Instead of taking m = p let us assume that m = p a , where a is a positive integer, and seek the value of 4>{p a ). Obviously, every number of the set 1, 2, 3, ... , ^either is divisible by p or is prime to p\ The number of integers in the set divisible by p is p"' 1 . Hence p a — p a ~ 1 of them are prime to p. Hence 4>{p a ) = p a -p a ~ 1 . Therefore If p is any prime number and a is any positive integer, then *(fj.v) =<£(m)0(V). •80 ON THE INDICATOR OF AN INTEGER 31 In order to prove this theorem let us write all the integers up to iiv in a rectangular array as follows: i 2 3 . . . h . . . m jliH-I jU+2 ^+3 . . . M -f^ . . . 2/x 2/i + I 2jU + 2 2/Z+3 . . . 2fi+k . . . 3M (y-l)jti+I (y-l)/* + 2 (i>-i)m+3 • • • (^-i)m+^ . . V]± (A) If a number /z in the first line of this array has a factor in common with /x then every number in the same column with h has a factor in common with /*. On the other hand if h is prime to n so is every number in the column with h at the top. But the number of integers in the first row prime to /x is <£(/*). Hence the number of columns containing integers prime to fi is 0(/x) and every integer in these columns is prime to p. Let us now consider what numbers in one of these columns are prime to v\ for instance, the column with h at the top. We wish to determine how many integers of the set h, n+h, 2>i+h, . . . , (p—i)n+h are prime to v. Write sn+h = q s v-\-r 5 where 5 ranges over the numbers s = o, i, 2, . . . , v — i and o£r,0. Clearly sn+h is or is not prime to v according as r 8 is or is not prime to v. Our problem is then reduced to that of determining how many of the quantities r s are prime to v. First let us notice that all the numbers r s are different; for, if r s = r% then from sn+h = q 8 v+r s , tii+h = q t v+r t , we have by subtraction that (s—t)n is divisible by v. But fx is prime to v and s and / are each less than v. Hence (s — t)fj, can be a multiple of v only by being zero; that is, s must equal t. Hence no two of the remainders r s can be equal. Now the remainders r s are v in number, are all zero or posi- tive, eat:h is less than v, and they are all distinct. Hence they 32 THEORY OF NUMBERS are in some order the numbers o, i, 2, . . . , v — 1. The num- ber of integers in this set prime to v is evidently 4>{v). Hence it follows that in any column of the array (A) in which the numbers are prime to fi there are just (*>) numbers which are prime to v. That is, in this column there are just 4>(v) numbers which are prime to iiv. But there are <£(/x) such columns. Hence the number of integers in the array (A) prime to fxv is 0(m) 4>{v) . But from the definition of the ^-function it follows that the number of integers in the array (A) prime to ixv is 4>(jiv). Hence, which is the theorem to be proved. Corollary. In the series of n consecutive terms of an arithmetical progression the common difference of which is prime to n, the number of terms prime to n is (n). From theorem I we have readily the following more general result : II. If mi, W2, . . . , m k are k positive integers which are prime each to each, then 4>(mim2 . . . m k ) = (mi) (m2) . . . (m k ).. § 16. The, Indicator of any Positive Integer From the results of §§14 and 15 we have an immediate proof of the following fundamental theorem: If m = p 1 a ip 2 a 2 . . . p n a n where pi, p 2 , . . . , p n are differ- ent primes and a\, a 2 , . . • , a„ are positive integers, then m = m (i-£)(t-±^ . . . (x-i). For, 4>{m) = 4>{p^)(p2 a *) . . . 4>{p n an ) ON THE INDICATOR OF AN INTEGER 33 On account of the great importance of this theorem we shall give a second demonstration of it. It is clear that the number of integers less than m and divisible by p\ is m The number of integers less than m and divisible by p2 is m }~2 The number of integers less than m and divisible by pip 2 is m p\p2 Hence the number of integers less than m and divisible by either p\ or p2 is m Pl p2 plp2 Hence the number of integers less than m and prime to p\p2 is m m . m I i \ / i m — | =m[ i ) i pl p2 Plp2 \ pl/ \ p2 We shall now show that if the number of integers less than m and prime to p\p2 . . . pi, where i is less than n, is X pin P2) ' ' i--- then» the number of integers less than m and prime to pip', . . • pipt+i is -) • • • («-—)• p2l \ Pi+l/ From this our theorem will follow at once by induction. i ii Pil\ P<< m—m\ i 34 THEORY OF NUMBERS From our hypothesis it follows that the number of integers less than m and divisible by at least one of the primes pi, P2, . . • , pi is or P\ plp2 plp2pS where the summation in each case runs over all numbers of the type indicated, the subscripts of the fs being equal to or less than i. Let us consider the integers less than m and having the factor pi+i but not having any of the factors pi, p 2 , . . . , pi. Their number is Pi+l pi+1 ( P\ Plp2 Plp2p3 where the summation signs have the same significance as before. For the number in question is evidently tn/pt+i minus the number of integers not greater than m/pt+i and divisible by at least one of the primes pi, p2, . . . , pu If we add (A) and (B) we have the number of integers less than m and divisible by one at least of the numbers pi, p2, . . . , pi+i> Hence the number of integers less than m and prime to pi, p2, . . . , pi+i is m—2j — \-2j 2j 'i pip2 pip2pz where now in the summations the subscripts run from i to i+i. This number is clearly equal to w I Pi)\ P2) ' V Pi+l)' From this result, as we have seen above, our theorem follows at once by induction. ON THE INDICATOR OF AN INTEGER 35 § 17. Sum of the Indicators of the Divisors of a Number We shall first prove the following lemma: Lemma. If d is any divisor of m and m = nd, the number of integers not greater than m which have with m the greatest com- mon divisor d is (n). Every integer not greater than m and having the divisor d is contained in the set d, 2d, 3d, . . . , nd. The number of these integers which have with m the greatest common divisor d is evidently the same as the number of integers of the set 1, 2, . . . , n which are prime to m/d, or n; for ad and m have or have not the greatest common divisor d according as a is or is not prime to m/d, =n. Hence the number in question is cj>(n). From this lemma follows readily the proof of the following theorem : If di, d2, . . . , d r are the different divisors of m, then (d 1 ) + (d 2 )+ . . . +(dr)=m. Let us define integers mi, m 2 , . . . , m r by the relations m = dimi=d2m2= . . . =d T m r . Now consider the set of m positive integers not greater than m, and classify them as follows into r classes. Place in the first class those integers of the set which have with m the great- est common divisor mi; -their number is (di), as may be seen from the lemma. Place in the second class those integers of the set which have with m the greatest common divisor m 2 \ their number is 4>(d 2 )- Proceeding in this way throughout, we place finally in the last class those integers of the set which have with m the greatest common divisor m r ', their number is 4>{d r ). It is evident that every integer in the set falls into one and into just one of these r classes. Hence the total num- ber m of integers in the set is 4>{d\) -\- 4>{d 2 ) -{- . . . -\-(d r ). From this the theorem follows immediately. 36 THEORY OF NUMBERS EXERCISES 1. Show that the indicator of any integer greater than 2 is even. 2. Prove that the number of irreducible fractions not greater than 1 and with denominator equal to n is (n). 3. Prove that the number of irreducible fractions not greater than 1 and with denominators not greater than n is *(i)+0(2)+*(3)+ • - . +*(»). 4. Show that the sum of the integers less than n and prime, to n is %n{n) if «>i. 5. Find ten values of x such that (x) = 24. 6. Find seventeen values of * such that (#) = 72. 7. Find three values of n for which there is no x satisfying the equation (x) = 271. 8. Show that if the equation (x) = 4n— 2, n>i, are of the form p a and 2p a , where p is a prime of the form 45—1. 10. How many integers prime to n are there in the set a) 1-2, 2-3, 3-4, . . . , »(»+i)? V) 1-2-3, 2-3-4, 3-4-5, . . . , «(»+i)(»+2)? \ Hi LI Hi »(»+i) ? 4) 222 2 1-2-3 2-3-4 3'4-5 »(»+i)(»+2). 6. 6 6 6 it*. Find a method for determining all the solutions of the equation (x) = n, where n is given and x is to be sought. 12*. A number theory function (n) is denned for every positive integer n; and for every such number n it satisfies the relation {di)+{d 2 )+ . . . +(d r )=n, where di, (k, . . . , d r are the divisors of n. From this property alone show that «"-(-i)(-s)-- (-£>■' where Pi, P2, • • • , />* are the different prime factors of n. CHAPTER III ELEMENTARY PROPERTIES OF CONGRUENCES § 1 8. Congruences Modulo m Definitions. If a and .b are any two integers, positive or zero or negative, whose difference is divisible by m, a and b are said to be congruent modulo m, or congruent for the modulus m, or congruent according to the modulus m. Each of the numbers a and b is said to be a residue of the other. To express the relation thus defined we may write a = b-\-cm, where c is an integer (positive or zero or negative). It is more convenient, however, to use a special notation due to Gauss, and to write a=b mod m, , an expression which is read a is congruent to b modulo m, or a is congruent to b for the modulus m, or a is congruent to b according to the modulus m. This notation has the advantage that it involves only the quantities which are essential to the idea involved, whereas in the preceding expression we' had the irrelevant integer c. The Gaussian notation is of great value and convenience in the study of the theory of divisibility. In the present chapter we develop some of the fundamental elementary properties of congruences. It will be seen that many theorems concerning equations are likewise true of con- gruences with fixed modulus; and ft is this analogy with equa- tions which gives congruences (as such) one of their chief claims to attention. * 37 38 THEORY OF NUMBERS As immediate consequences of our definitions we have the following fundamental theorems: I. If fl=cmodm, Ncmodw, then a=bmodm\ that is, for a given modulus, numbers congruent to the same num- ber are congruent to each other. For, by hypothesis, a — c=Cim, b—c = C2m, where c\ and C2 are integers. Then by subtraction we have a — b = (ci—C2)m\ whence a = b mod m. II. // a = bmodm, a=j8 mod w, then azka=b±(3 mod m; that is, congruences with the same modulus may be added or sub- tracted member by member. For, by hypothesis, a — b = c\m, a — ^ = c 2 m; whence (ad=a) — (bdtP) = (ci±c 2 )m. Hence a±a=^±/3modw. III. // a=b mod ot, then ca=cb mod m, c being any integer whatever. The proof is obvious and need not be stated. IV. If a = bmodm, a=(3modm, then aa m b(3 mod m ; that is, two congruences with the same modulus may be multiplied member by member. For, we have a = b+c\m, a = (3+c 2 m. Multiplying these equa- tions member by member we have aa = bp-\-m(bc2+fici J r ciC-2m). Hence aa=b$ mod m. A repeated use of this theorem gives the following result: V. If a=b mod m, then a n = b n mod m whtre n is any positive integer. ELEMENTARY PROPERTIES OF CONGRUENCES 39 As a corollary of theorems II, III and V we have the follow- ing more general result : * VI. If f(x) denotes any polynomial in x with coefficients which are integers (positive or zero or negative) and if further a=b mod m, then f(a) =f(b) mod m. § 19. Solutions of Congruences by Trial Let f(x) be any polynomial in x with coefficients which are integers (positive or negative or zero). Then if x and c are any two integers it follows from the last theorem of the preceding section that f(x) =f(x-\-cm) mod m. (i) Hence if a is any value of x for which the congruence /(#)=omodra (2) is satisfied, then the congruence is also satisfied for x=a-\-cm, where c-is any integer whatever. The numbers* a -\-cni are said to form a solution (or to be a root) of the congruence, c being a variable integer. Any one of the integers a-\-cm may be taken as the representative of the solution. We shall often speak of one of these numbers as the solution itself. Among the integers in a solution of the congruence (2) there is evidently one which is positive and not greater than m. Hence all solutions of a congruence of the type (2) may be found by trial, a substitution of each' of the numbers 1, 2, . . . , m being made for x. It is clear also that m is the maxi- mum number of solutions which (2) can have whatever be the function f(x) . By means of an example it is easy to show that this maximum number of solutions is not always possessed by a congruence*; in fact, it is not even necessary that the congruence bave a solution at all. This is illustrated by the example x 2 — 3=0 mod 5. 40 THEORY OF NUMBERS In order to show that no solution is possible it is necessary to make trial only of the values i, 2, 3, 4, 5 for x. A direct sub- stitution verifies the conclusion that none of them satisfies the congruence; and hence that the congruence has no solution at all. On the other hand the congruence x 5 — x=o mod 5 has the solutions x=i, 2, 3, 4, 5 as one readily verifies; that is, this congruence has five solutions — the maximum number possible in accordance with the results obtained above. EXERCISES 1. Show that (a+b) v = a v +b p .modp where a and b are any integers and p is any prime. 2. From the preceding result prove that a? =a mod p for every integer a. 3. Find all the solutions of each of the congruences x n =x mod 11, x 10 =i mod n, x b = i mod n. * § 20. Properties of Congruences Relative to Division The properties of congruences relative to . addition, sub- traction and multiplication are entirely analogous to the prop- erties of algebraic equations. But the properties relative to division are essentially different. These we shall now give. I. If two numbers are congruent modulo m they are con- gruent modulo d, where d is any divisor of m. For, from o=5 mod m, we have a = b-\-cm — b-\-c f d. Hence a=b mod d. II. If two numbers are congruent for different moduli they are congruent for a modulus which is the least common multiple of the given moduli. ELEMENTARY PROPERTIES OF CONGRUENCES 41 The proof is obvious, since the difference of the given num- bers is divisible by each of the moduli. III. When the two members of a congruence are multiples of an integer c prime to the modulus, each member of the congruence may be divided by c. For, if ca=cb mod m then ca — cb is divisible by m. Since c is prime to m it follows that a — b is divisible by m. Hence a =b mod m. IV. // the two members of a congruence are divisible by an integer c, having with the modulus the greatest common divisor 5, one obtains a congruence equivalent to the given congruence by dividing the two members by c and the modulus by 5. By hypothesis ac=bc mod m, c=8ci, m—hm\. Hence c(a — b) is divisible by m. A necessary and sufficient condition for this is evidently that c\{a — b) is divisible by mi. This leads at once to the desired result. §21. Congruences with a Prime Modulus The congruence * aox n +aix n ~ l -\- . . . +a n =omod p, ao^omod p, where p is a prime number and the a's are any integers, has not more than n solutions. Denote the first member of this congruence by f(x) so that the congruence may be written f(x) =o mod p. (i) Suppose that a is a root of the congruence, so that f(a) =o mod p. Then we have f(x) ^f(x)-f(a) mod p. * * The sign ^ is read is not congruent to. 42 THEORY OF NUMBERS But, from algebra. f(x)—f(a) is divisible by x — a. Let (x — a) a be the highest power of x — a contained in f(x) —f(a) . Then we may write f( x )-f(a) = (x-a)«f 1 (x), (2) where /i(x) is evidently a polynomial with integral coefficients. Hence we have }{x) = (x-a) a /i 0) mod p. (3) We shall say that a occurs a times as a solution of (1); or that the congruence has a solutions each equal to a. Now suppose that congruence (1) has a root b such that b=£a mod p. Then from (3) we have f(b)m(b^a) a fi(b)modp. But f(b)=omodp, (b-a) a ^omodp. Hence, since p is a prime number, we must have fi(b) =0 mod p. By an argument similar to that just used above, we may show that /1 (x) — /1 (b) may be written in the form where /5 is some positive integer. Then we have f(x) = (x-a) a (x-byf 2 {x) mod p. Now this process can be continued until either all the solutions of (1) are exhausted or the second member is a prod- uct of linear factors multiplied by the integer a . In the for- mer case there will be fewer than n solutions of (1), so that our theorem is true for this case. In the other case we have f(x)^a (x-a) a (x-by . . . (>-/) x mod/>. We have now n solutions of (1) : a counted a times, b counted times, . . . , I counted X times; «+/?+ . . . +X = w. ELEMENTARY PROPERTIES OF CONGRUENCES 43 Now let 77 be any solution of (i). Then f(r l )=ao(ri-a) a (r,-b) f ' . . . ( v -l) x =omodp. Since p is prime it follows now that some one of the factors 7} — a, r] — b, . . . , t)—1 is divisible by p. Hence 77 coincides with one of the solutions a, b, c, . . . , I. That is, (1) can have only the n solutions already found. This completes the proof of the theorem. EXERCISES 1. Construct a congruence of the form aox n -\-a l x n ~ 1 -\-. . . -\-a n =omodm, a ^omodf», having more than n solutions and thus show that the limitation to a prime mod- ulus in the theorem of this section is essential. 2. Prove that x*-i=(x-i)(x-2)(x-3)(x-4)(x-s)(x-6) mod 7 for every integer x. 3. How many solutions has the congruence x 5 =i mod 11? the congruence £ 5 =2 mod n? § 22. Linear Congruences From the theorem of the preceding section it follows that the congruence ax =c mod p, a^o mod p, where p is a prime number, has not more than one solution. In this section we shall prove that it always has a- solution. More generally, we shall consider the congruence ax=c mod m where m is any integer. The discussion will be broken up into parts for convenience in the proofs. I. The congruence ax=\ mod m, (1) 44 THEORY OF NUMBERS in which a and m are relatively prime, has one and only one solu- tion. The question as to the existence and number of the solu- tions of (i) is equivalent to the question as to the existence and number of integer pairs x, y satisfying the equation, ax— my = i, (2) the integers x being incongruent modulo m. Since a and m are relatively prime it follows from theorem IV of § 9 that there exists a solution of equation (2). Let x=a and y = p be a particular solution of (2) and let x = a and y = ]3 be any solution of (2). Then we have aa — mP = i, aa—mfi=i; whence a(a — a)—m(p — ~(3) =0. Hence a — a is divisible by m, since a and m are relatively prime. That is, a = amodm. Hence a and a are representatives of the same solution of (1). Hence (1) has one and only one solution, as was to be proved. II. The solution x=a of the congruence w=imodw, in which a and m are relatively prime, is prime to m. For, if aa — 1 is divisible by m, a is divisible by no factor of m except 1. III. The congruence flx=cmodm (3) in which a and m and also c and m are relatively prime, has one and only one solution. Let x = y be the unique solution of the congruence a=i mod w. Then we have ayx=cy = imodm. Now* by I we see that there is one and only one solution of the con- gruence ayx = imo(m) positive integers not greater than m and prime to m. Let a be any integer prime to m and form the set of integers aai, aa 2 , . . . , aa^ m) . (B) No number aa t of the set (B) is congruent to a number aa$ unlessy = z; for, from aai^= aaj mod m we have Oi= a j mod. m\ whence a% = a h since both a\ and aj are positive and not greater than m. Theref ore j — i . Further- more, every number of the set (B) is congruent to some number of the set (A). Hence we have congruences of the form aai^a^ mod m, aa2 = a u mod m y 00*m each side of the foregoing congruence, we have (a + i) p -(> + i)=a p -arnod£. THE THEOREMS OF FERMAT AND WILSON 49 Hence if a v — a is divisible by p, so is (a + i) p — (a+i). But i p — i is divisible by p. Hence 2 P — 2 is divisible by p\ and then 3 P — 3; and so on. Therefore, in general, we have a p =a mod p. If a is prime to p this gives a p ~ x = 1 mod ^, as was to be proved. If instead of the Binomial Theorem one employs the Poly- nomial Theorem, an even simpler proof is obtained. For, from the latter theorem, we have readily '(ai+a 2 + • . . +a a ) p =ai p +a 2 p + . . . +a a p mod p. Putting ai=a 2 = . . . =a a =i we have a p =a mod p, from which the theorem follows as before. § 25. Wilson's Theorem From the simple Fermat theorem it follows that the con- gruence x p ~ 1 = i mod^ has the p — i solutions 1, 2, 3, . . . , p — i. Hence from the discussion in § 21 it follows that x p — i==(x — i)(x — 2) . . . (x — p — i) mod p, this relation being satisfied for every value of x. Putting x=o we have (_ I ) = (_ I )p-i. Iv2 . 3 , , . p- imo dp. If p is an odd prime this leads to the congruence i- 2-3 . . . p — i-\-i=omod p. Now for p = 2 this congruence is evidently satisfied. Hence we have the Wilson theorem : Every prime number p satisfies the relation i* 2*3 . . . p — i + i=omod^. 50 THEORY OF NUMBERS An interesting proof of this theorem on wholly different principles may be given. Let p points be distributed at equal intervals on the circumference of a circle. The whole number of ^-gons which can be formed by joining up these p points in every possible order is evidently i „ 2p p(p-i)(p-2) . . . 3-2-i; for the first vertex can be chosen in p ways, the second in p — i ways, . . . , the (p — i) th in two ways, and the last in one way; and in counting up thus we have evidently counted each polygon 2p times, once for each vertex and for each direction from the verfcqx around the polygon. Of the total number of polygons \{p — i) are regular (convex or stellated) so that a revolution through 360°/^ brings each of these into coin- cidence with Its former position. The number of remaining p-gons must be divisible by p\ for with each such ^>-gon we may associate the p — i ^-gons which can be obtained from it by rotating it through successive angles of 360°/^. That is, -^-p(p-i)(p-2) . . . 3-2-i--0-i)=omod/>. 2p 2 Hence (p — i)(p — 2) . . . 3-2-1 — />+i=o mod p; and from this it follows that 1-2 .. . ^—1 + 1=0 mod p, as was to be proved. § 26. The Converse of Wilson's Theorem Wilson's theorem is noteworthy in that its converse is also true. The converse may be stated as follows: Every integer n such that the congruence 1-2-3 . . . n— 1 + 1=0 mod n is satisfied is a prime number. THE THEOREMS OF FERMAT AND WILSON 51 For, if n is not prime, there is some divisor d of n different from i and less than n. For such a d w e have 1-2-3 • • • n— 1=0 mod d; so that 1-2 .. . w-i + i^omodi; and hence 1-2 . . . n— 1 + 1=^0 mod n. Since this, contradicts our hypothesis the truth of the theorem follows. Wilson's theorem and its converse may be combined into the following elegant theorem: A necessary and sufficient condition that an integer n is prime is that 1-2-3 • • • w-i + i=omodw. Theoretically this furnishes a complete and elegant test as to whether a given number is prime. But, practically, the labor of applying it is so great that it is useless for verifying large primes. §27. Impossibility of 1-2-3 • • • n ~ i + i=w* for n>$. In this section we shall prove the following theorem: There exists no integer k for which the equation i- 2 3 . . . n— i-\-i=n* is true when n is greater than 5. If n contains a divisor d different from 1 and n, the equa- tion is obviously false; for the second member is divisible by d while the first is not. Hence we need to prove the theorem only for primes n. Transposing 1 to the second member and dividing by n — 1 we have 1-2-3 • • • n — 2=n t ~ 1 +n t ~ 2 + . . . +n+i. If w>5 the product on the left contains both the factor 2 and the factor \{n — 1); that is, the first member contains the fac- tor n— 1. But the second member does not contain this fac- tor, since for n = i the expression w* _1 + . . . -\-n-\-i is equal to kj^o. Hence the theorem follows at once. 52 theory of numbers § 28. Extension of Fermat's Theorem The object of this section is to extend Fermat's general theorem and incidentally to give a new proof of it. We shall base this proof on the simple Fermat theorem, of which we have already given a simple independent proof. This theorem asserts that for every prime p and integer a not divisible by p, we have the congruence a p ~ 1 = i mod p. Then let us write a*- 1 = i+hp. (1) Raising each member of this equation to the p th power we may write the result in the form a viV-D =I+hl p2 ( 2 ) where hi is an integer. Hence ^-"simod^, By raising each member of (2) to the p power we can readily show that /^^imod^ 3 . It is now easy to see that we shall have in general wUere a is a positive integer; that is, a *(p a ) = 1 m0( i p« m For the special case when p is 2 this result can be extended. For this case (1) becomes a = 1 + 2/2. Squaring we have 2. That is, a 2 " = 1 mod 2 a a^ 2a) = i mod 2 a if «>2. Now in terms of the ^-function let us define a new function X(m) as follows: \(2 a ) = <£(2 a X if a = o, 1, 2; X(2«)=^(2 a ) if a>2- \(p a ) = (p a ) if p is an odd prime; \{2 a p^p 2 ^ . . . p n an ) =M, where M is the least common multiple of x( 2 «), x(/>!«0, x(/> 2 ««), . . . , X(/>.««), 2, ^1, p2, - . . , pn being different primes. Denote by m the number rn = 2 a p 1 a ip 2 a * . . . p n an . Let a be any number prime to m. From our preceding results we have #(*■>«! mod '?«." bWsi mod#i% a x(p 2 « 2 ) = x moc ] ^ 2 « s a X( P „«») = lmod ^a n> 54 THEORY OF NUMBERS Now any one of these congruences remains true if both of its members are raised to the same positive integral power, whatever that power may be. Then let us raise both members of the first congruence to the power \(m)/\(2 a ); both members of the second congruence to the power X(w) /Mpi" 1 ) 5 • • • J both members of the last congruence to the power \(m)/\(p n an ). Then we have a \(m) _ x mo( J 2 a } From these congruences we have immediately a \(m) m j moc J Mf We may state this result in full in the following theorem : // a and m are any two relatively prime positive integers, the congruence a Hm) s j m0( j m is satisfied. As an excellent example to show the possible difference between the exponent \(m) in this theorem and the exponent 4>(m) in Fermat's general theorem, let us take w = 2 6 -3 3 -5-7-i3-i7-i9'37-73. Here X(»=2 4 -3 2 , 4>0) = 2 21 -3 10 . In a later chapter we shall show that there is no exponent v less than \(m) for which the congruence a" = i mod m is verified for every integer a prime to m. From our theorem, as stated above, Fermat's general the- orem follows as a corollary, since X(m) is obviously a factor of 4>(m), i«0 • ■ • 4>(£» an ). THE THEOREMS OF FERMAT AND WILSON 55 EXERCISES i. Show that a 16 =i mod 16320, for every a which is prime to 16320. 2. Show that a 12 = i mod 65520, for every a which is prime to 65520. 3*. Find one or more composite numbers P such that a p ~ l = i modP for every a prime to P. (Compare this problem with the next section.) § 29. On the Converse of Fermat's Simple Theorem The fact that the converse of Wilson's theorem is a true proposition leads one naturally to inquire whether the con- verse of Fermat's simple theorem is true. Thus, we may ask the question: Does the existence of the congruence 2 n_1 = i mod n require that n be a prime number? The Chinese answered this question in the affirmative and the answer passed unchal- lenged among them for many years. An example is sufficient to show that the theorem is not true. We shall show that 2 34o = j moc j 241 although 341, = 11 -31, is not a prime number. Now 2 10 — i = 3-11-31. Hence 2 10 =imod34i. Hence 2 340 =i mod 341. From this it follows that the direct converse of Fermat's the- orem is not true. The following theorem, however, which is a converse with an extended hypothesis, is readily proved. If there exists an integer a such that a n ~ l = i mod n and if further there does not exist an integer v less than n—i such that a v =i mod n, then the integer n is a prime number. For, if n is not prime, (n)(n) we have a" = 1 mod n, contrary to the hypothesis of the theorem. 56 THEORY OF NUMBERS §30. Application of Previous Results to Linear Con- gruences The theorems of the present chapter afford us a ready means of writing down a solution of the congruence ax=c mod m. We shall consider only the case in which a and m are relatively prime, since the general case is easily reducible to this one, as we saw in the preceding chapter. Since a and m are relatively prime we have the congruences Hence either of the numbers x, is a representative of the solution of (1). Hence the following theorem : If ax=c mod m is any linear congruence in which a and m are relatively prime, then either of the numbers x, x = ca x{m) - 1 , x = ca^ m) -\ is a representative of the solution of the congruence. The former representative of the solution is the more con- venient of the two, since the power of a is in general much less in this case than in the other. EXERCISE Find a solution of ^x = ^ mod 2 6 -3«5-i7. Note the greater facility in apply- ing the first of the above representatives of the solution rather than the second. the theorems of fermat and wilson 57 § 31. Application of the Preceding Results to the Theory of Quadratic Residues In this section we shall apply the preceding results of this chapter to the problem of rinding the solutions of congruences of the form az 2 +/3z+Y=o mod /z where a, /3, 7, fi are integers. These are called quadratic con- gruences. The problem of the solution of the quadratic congruence (1) can be reduced to that of the solution of a simpler form of congruence as follows: Congruence (1) is evidently equivalent to the congruence 4« 2 2 2 -f 4^2+40:7 = mod 4.afi. (1) But this may be written in the form (2az+(3) 2 = (3 2 — 40:7 mod 4 2 . We shall now prove the following theorem : I. If a and m are relatively prime integers, a necessary con- dition that a is a quadratic residue modulo m is that a hMm) _ j mo( J m Suppose that the congruence x 2 = a mod m has the solu- tion x=a. Then a 2 = a mod m. Hence a X(m) positive integers not greater than m and prime to m; and let a denote any integer of the set (A). Now any positive integral power of a is prime to m and hence is congruent modulo w to a number of the set (A). Hence, among all the powers of there must be two, say a n and a v , n>v, which are congruent to the same integer of the set (A). These two powers are then congruent to each other; that is, n =a" mod m. Since 0" is prime to m the members of this congruence may be divided by 0". Thus we have a n ~"=i mod m. That is, among the powers of a there is one at least which is congruent to 1 modulo m. Now, in the set of all powers of a which are congruent to 1 modulo m there is one in which the exponent is less than in any other of the set. Let the exponent of this power be d, so that a d is the lowest power of a such that a d = 1 mod m. 61 62 THEORY OF NUMBERS We shall now show that if a a = i mod m, then a is a multiple of d. Let us write a = d8+p, o^(3(m) and \(m). § 33. Another Proof of Fermat's General Theorem In this section we shall give an independent proof of the theorem that the exponent d of a modulo m is a divisor of (m) ; from this result we have obviously a new proof of Fermat's theorem itself. We retain the notation of the preceding section. We shall first prove the following theorem : I. The numbers 1, a, a 2 , ... , a*- 1 (A) are incongruent each to each modulo m. For, if fl^^modw, where oft, we have a a ~^=i mod m, so that d is not the exponent to which a belongs modulo m, contrary to hypothesis. Now any number of the set (A) is congruent to some number of the set Hi, 42, ... , a*( TO ). (B) Let us undertake to separate the numbers (B) into classes after the following manner: Let the first class consist of the numbers (I) ao, ai, a 2 , . . . , «„_!, where a t is the number of the set (B) to which a i is congruent modulo m. If the class (I) does not contain all the numbers of the set (B), let a t be any number of the set (B) not contained in (I) and form the following set of numbers: (II r ) aoat, aiat, a2#«, . . . , a d _!a<. 64 THEORY OF NUMBERS We shall now show that no number of this set is congruent to a number of class (I) . For, if so, we should have a congruence of the form ataj^aic mod m\ hence (Ha* = a k mod m, so that aia d = a k+d ~ 3 mod m; or Po, 01, 02, . ■ • > Pd-1> 7o, 71, 72, • • • , 7d-l, ^-1- The set (5), which consists of 4>{m) integers, has thus been separated into classes, each class containing d integers. Hence we conclude that d is a divisor of (m). Thus we have a second proof of the theorem: II. If a and m are any two relatively prime integers and d is the exponent to which a belongs modulo m, then d is a divisor of (m). In our classification of the numbers (B) into the rectangular array above we have proved much more than theorem II; in fact, theorem II is to be regarded as one only of the con- sequences of the more general result contained in the array. If we raise each member of the congruence a d =i mod m to the (integral) power (m)/d, the preceding theorem leads immediately to an independent proof of Fermat's general theorem. § 34. Definition of Primitive Roots Definition. Let a and m be two relatively prime integers. If the exponent to which a belongs modulo m is (m), a is said to be a primitive root modulo m (or a primitive root of m). In a previous chapter we saw that the congruence a Hm) = j mod m 66 THEORY OF NUMBERS is verified by every pair of relatively prime integers a and m. Hence, primitive roots can exist only for such a modulus m as satisfies the equation (m)=\(m). (i) We shall show later that this is also sufficient for the existence of primitive roots. From the relation which exists in general between the ^-function and the X-function in virtue of the definition of the latter, it follows that (i) can be satisfied only when m is a prime power or is twice an odd prime power. Suppose first that m is a power of 2, say m = 2 a . Then (1) is satisfied only if a = o, 1, 2. For a = oor 1, 1 itself is a primitive root. For a = 2, 3 is a primitive root. We have therefore left to examine only the cases m = p a , m = 2p a where p is an odd prime number. The detailed study of these cases follows in the next sections. §35. Primitive Roots Modulo p. We have seen that if p is a prime number and d is the exponent to which a belongs modulo p, then J is a divisor of 0(^)=^-i. Now, let di, d2, d3, . . . , dr be all the divisors of p — 1 and let $(dl) denote the number of integers of the set 1, 2, 3, ... , p-i which belong to the exponent d%. If there is no integer of the set belonging to this exponent, then \p(di) =0. PRIMITIVE ROOTS MODULO m 67 Evidently every integer of the set belongs to some one and only one of the exponents d\, d2, . . . , d r . Hence we have the relation *(<*l) + *(*0 + • • • ++(d T )=p-I. (l) But *((d r )=p-I. (2) If then we can show that *(<*.)£*(<*.) (3) for i = i, 2, . . . , r, it will follow from a comparison of (i) and (2) that ${di) = {dt). Accordingly, we shall examine into the truth of (3). Now the congruence x d * = imodp (4) has not more than di roots. If no root of this congruence belongs to the exponent di, then \J/(di)=o and therefore in this case we have \p(di) <4>(di). On the other hand if a is a root of (4) belonging to the exponent di, then a, a\ a*, . . . , a d * (5) are a set of d t incongruent roots of (4) ; and hence they are the complete set of roots of (4). But it is easy to see that a* does or does not belong to the exponent di according as k is or is not prime to di, for, if a* belongs to the exponent /, then / is the least integer such that kt is a multiple of di. Consequently the number of roots in the set (5) belonging to the exponent di is (di). That is, in this case \j/(di) = 4>(di) . Hence in general ^(d t ) £^(J«). Therefore from (1) and (2) we conclude that t(di) = 4>(di), i=i, 2, . . . , r. 68 THEORY OF NUMBERS The result thus obtained may be stated in the form of the following theorem: I. If p is a prime number and d is any divisor of p — i , then the number of integers belonging to the exponent d modulo p is {p-i). §36. Primitive Roots Modulo p a , p an Odd Prime In proving that there exist primitive roots modulo p a , where p is an odd prime and a> 1, we shall need the following theorem: I. There always exists a primitive root y modulo p for which y p ~ l — 1 is not divisible by p 2 . Let g be any primitive root modulo p. If g p ~ 1 — 1 is not divisible by p 2 our theorem is verified. Then suppose that g v ~ x — 1 is divisible by p 2 , so that we have where k is an integer. Then put 7 = g+Xp where x is an integer. Then 7=g mod p, and hence y h = g h mod p; whence we conclude that 7 is a primitive root modulo p. But I ! 2 I = P ( kp+ tll r * x+ (P-*)(p-*) f -Z x 2 p+ . . Hence 7 p - 1 -i=^(-^" 2 x) mod^ 2 . PRIMITIVE ROOTS MODULO M t)9 Therefore it is evident that x can be so chosen that y p ~ 1 — i is not divisible by p 2 . Hence there exists a primitive root 7 modulo p such that 7 P_1 — 1 is not divisible by p 2 . Q. E. D. We shall now prove that this integer 7 is a primitive root modulo p a , where a is any positive integer. If 7*= 1 mod p, then k is a multiple of p — i, since 7 is a primitive root modulo p. Hence, if 7 l =imodf, then k is a multiple of p — 1 . Now, write yt-^j+kp. Since y p ~ 1 — 1 is not divisible by ^> 2 , it follows that h is prime to ^>. If we raise each member of this equation to the power (3p a ~ 2 , a>2 J we have where / is an integer. Then if y>p«-2( P -i)^ imod ^ |8 must be divisible by p. Therefore the exponent of the lowest power of 7 which is congruent to 1 modulo p a is divisible by p a ~ l . But we have seen that this exponent is also divisible by p — 1. Hence the exponent of 7 modulo p a is p a ~ 1 (p—i) since (j>(p a )=p a ~ 1 (p — i). That is, 7 is a* primitive root mod- ulo p a . It is easy to see that no two numbers of the set 7, 7 2 , T 3 , . • • , 7 pa " 1(p ~ 1) (A) are congruent modulo p a ; for, if so, 7 would belong modulo p a to an exponent less than p a ~ 1 (p~i) and would therefore not be a primitive root modulo p a . Now every number in the set 70 THEORY OF NUMBERS (-4) is prime to p a ; their number is (p a ) = p a ~ 1 (p — i). Hence the numbers of the set (A) are congruent in some order to the numbers of the set (B) : 0i, 02, as, ... , 0po-i( P _i), (B) where the integers (B) are the positive integers less than p a and prime to p a . But any number of the set (B) is a solution of the congruence /"^-"simodf. (i) Further, every solution of this congruence is prime to p a . Hence the integers (B) are a complete set of solutions of (i). Therefore the integers (A) are a complete set of solutions of (i). But it is easy to see that an integer 7* of the set (A) is or is not a primitive root modulo p a according as k is or is not prime to p a ~ 1 (p—i). Hence the number of primitive roots modulo The results thus obtained may be stated as follows: II. If p is any odd prime number and a is any positive integer, then there exist primitive roots modulo p a and their number is § 37. Primitive Roots Modulo 2p a , p an Odd Prime In this section we shall prove the following theorem : // p is any odd prime number and a is any positive integer, then there exist primitive roots modulo 2p a and their number is *U(2f)}. Since 2p a is even it follows that every primitive root modulo 2p a is an odd number. Any odd primitive root modulo p a is obviously a primitive root modulo 2p a . Again, if 7 is an even primitive root modulo p a then y-\-p a is a primitive root modulo 2p a . It is evident that these two classes contain (without repetition) all the primitive roots modulo 2p a . Hence the theorem follows as stated above. primitive roots modulo yyl 71 § 38. Recapitulation The results which we have obtained in §§ 34-37 inclusive may be gathered into the following theorem: In order that there shall exist primitive roots modulo m, it is necessary and sufficient that m shall have one of the values m=i, 2, 4, p a , 2p a where p is an odd prime and a is a positive integer. If m has one of these values then the number of primitive roots modulo m is {4>{m) } . §39. Primitive X-roots In the preceding sections of this chapter we have developed the theory of primitive roots in the way in which it is usually presented. But if one approaches the subject from a more general point of view the results which may be obtained are more general and at the same time more elegant. It is our purpose in this section to develop the more general theory. We have seen that if a and m are any two relatively prime positive integers, then a Hm) = j m0( J ^ Consequently there is no integer belonging modulo m to an exponent greater than \(m). It is natural to enquire if there are any integers a which belong to the exponent \(m). It turns out that the question is to be answered in the affirmative, as we shall show. Accordingly, we introduce the following defini- tion: Definition. If a Hm) is the lowest power of a which is congruent to 1 modulo m, a is said to be a primitive X-root modulo m. We shall also say that it is a primitive X-root of the congruence £ x(m) = 1 mod m. To distinguish we may speak of the usual primitive root as a primitive 0-root modulo m. 72 THEORY OF NUMBERS From the theory of primitive 0-roots already developed it follows that primitive X-roots always exist when m is a power of any odd prime, and also when m= i, 2, 4; for, for such values of m we have \(m) = (m). We shall next show that primitive X-roots exist when m = 2 a , a>2, .by showing that 5 is such a root. It is necessary and suf- ficient to prove that 5 belongs modulo 2 a to the exponent 2 a_2 = X(2 a ). Let d be the exponent to which 5 belongs modulo 2 a . Then from theorem II of § 32 it follows that d is a divisor of 2 a - 2 = X(2 a ). Hence if d is different from 2 a ~ 2 it is 2 a " 3 or is a divisor, of 2 a ~ 3 . Hence if we can show that f a " 3 is not congruent to 1 modulo 2 a we will have proved that 5 belongs to the exponent 2 a ~ 2 . But, clearly, 5 2«- 3 = ( I+2 2)2«-3 =I+2 «-l +/ . 2 a j where / is an integer. Hence 5 2a_ ^1 mod 2 a . Hence 5 belongs modulo 2 a to the exponent X(2 a ). By means of these special results we are now in position to prove readily the following general ,theorem which includes them as special cases: I. For every congruence of the form x x(m) = i mod m a solution g exists which is a primitive \-root, and for any such solution g there are 4>{\(m)\ primitive roots congruent to powers ofg- ^ . If any primitive X-root g exists, g v is or is not a primitive X-root according as v is or is not prime to \{m) ; and therefore the number of primitive X-roots which are congruent to powers of any such root g is {\(m) J . The existence of a primitive X-root in every case may easily be shown by induction. In case wis a power of a prime the theorem has already been established. We will suppose that it is true when m is the product of powers of r different primes PRIMITIVE ROOTS MODULO M 73 and show that it is true when m is the product of powers of r-f-i different primes; from this will follow the theorem in general. Put m = p 1 a 'p 2 a2 • • • pr ar p a r T ^, n = pi a ip 2 a2 . . . pr ar , and let h be a primitive X-root of x Hn) = i mod n. (i) Then h-\-ny is a form of the same root if y is an integer. Likewise, if c is any primitive X-root of ^r+V^imod^ 1 (2) a form of this root is where z is any integer. Now, if y and z can be chosen so that h+ny = c+p a r r + 1 1 z the number in either member of this equation will be a common primitive X-root of congruences (i) and (2); that is, a com- mon primitive X-root of the two congruences may always be obtained provided that the equation P fi . . . pSry-p + 1 has always a solution in which y and z are integers. That this equation has such a solution follows readily from theorem III of § 9; for, if c — h is replaced by 1, the new equation has a solution y, z; and therefore for y and z we may take y = y(c — h), z=~z(c — h). Now let g be a common primitive X-root of congruences (1) and (2) and write g v =i mod m, 74 THEORY OF NUMBERS where v is to be the smallest exponent for which the congruence is true. Since g is a primitive X-root of (i) v is a multiple of Mpi ai . • -'.pr ar ). Since g is a primitive X-root of (2) v is a multiple of X (^^j 1 ) . Hence it is a multiple of X(w). But g x(m) = imodm; therefore v = \(m). That is, g is a primitive X-root modulo m. The theorem as stated now follows at once by induction. There is nothing in the preceding argument to indicate that the primitive X-roots modulo m are all in a single set obtained by taking powers of some root g\ in fact it is not in general true when m contains more than one prime factor. By taking powers of a primitive X-root g modulo m one obtains 0{X(m)J different primitive X-roots modulo m. It is evident that if 7 is any one of these primitive X-roots, then the same set is obtained again by taking the powers of 7. We may say then that the set thus obtained is the set belonging to g. II. 7/ X(w)>2 the product of the {\(m)} primitive \-roots in the set belonging to any primitive \-root g is congruent to 1 modulo m. These primitive X-roots are 8> 8 ) 8 > • • • 5 8 where I, Ci, C2) • * • , Cft are the integers less than \(m) and prime to X(w). If any one of these is c another is \(m)—c, since \(m)>2. Hence 1+C1+C2+ • • • +c M = o mod X(ra). Therefore gi+ Cl + C2 +... +c ME = I mo d w . From this the theorem follows. Corollary. The product of all the primitive \-roots modulo m is congruent to 1 modulo m when \{m) > 2. PRIMITIVE ROOTS MODULO M 75 EXERCISES i. If *i is the largest value of x satisfying the equation \(x)=a, where a is a given integer, then any solution x 2 of the equation is a factor of X\. 2*. Obtain an effective rule for solving the equation \{x)—a. 3*. Obtain an effective rule for solving the equation (x)=a. 4. A necessary and sufficient condition that a p_1 = i mod P for every in- teger a prime to P is that P = i mod X(P). 5. If a p ~ l = i mod P for every a prime to P, then (1) P does not contain a square factor other than 1, (2) P either is prime or contains at least three dif- ferent prime factors. 6. Let p be a prime number. If a is a root of the congruence x d = 1 mod p and a is a root of the congruence x s = i mod p, then aa is a root of the congruence x ds = i mod p. If a is a primitive root of the first congruence and a of the second and if d and 5 are relatively prime, then aa is a primitive root of the congruence x db = i mod p. CHAPTER VI OTHER TOPICS § 40. Introduction The theory of numbers is a vast discipline and no single volume can adequately treat of it in all of its phases. A short book can serve only as an introduction; but where the field is so vast such an introduction is much needed. That is the end which the present volume is intended to serve; and it will best accomplish this end if, in addition to the detailed theory already developed, some account is given of the various direc- tions in which the matter might be carried further. To do even this properly it is necessary to limit the number of subjects considered. Consequently we shall at once lay aside many topics of interest which would find a place in an exhaustive treatise. We shall say nothing, for instance, about the vast domain of algebraic numbers, even though this is one of the most fascinating subjects in the whole field of mathe- matics. Consequently, we shall not refer to any of the exten- sive theory connected with the division of the circle into equal, parts. Again, we shall leave unmentioned many topics con- nected with the theory of positive integers; such, for instance, is the frequency of prime numbers in the ordered system of integers — a subject which contains in itself an extensive and elegant theory. In §§ 41-44 we shall speak briefly of each of the following topics: theory of quadratic residues, Galois imaginaries, arith- metic forms, analytical theory of numbers. Each of these alone would require a considerable volume for its proper development. All that we can do is to indicate the nature of the problem in each case and in some cases to give a few of the fundamental results. 76 OTHER TOPICS 77 In the remaining three sections we shall give a brief intro- duction to the theory of Diophantine equations, developing some of the more elementary properties of certain special cases. We shall carry this far enough to indicate the nature of the problem connected with the now famous Last Theorem of Fermat. The earlier sections of this chapter are not required as a preliminary to reading this latter part. §41. Theory of Quadratic Residues Let a and m he any two relatively prime integers. In § 31 we agreed to say that a is a quadratic residue modulo m or a quadratic non-residue modulo m according as the congruence x 2 = a mod m has or has not a solution. We saw that if m is chosen equal to an odd prime number p, then a is a quadratic residue modulo p or a quadratic non-residue modulo p according as a Kp-i) = ! or fl i(P-D=_ imo( J|,, This is known as Euler's criterion. It is convenient to employ the Legendre symbol -;) to denote the quadratic character of a with respect to p. This symbol is to have the value +1 or" the value — 1 according as a is a quadratic residue modulo p or a quadratic non-residue modulo p. We shall now derive some of the fundamental prop- erties of this symbol, understanding always that the numbers in the numerator and the denominator are relatively prime. From the definition of quadratic residues and non-residues it is obvious that ($)-( if a = b mod p. (1) Pi 78 THEORY OF NUMBERS It is easy to prove in general that (?)(!)-(t) (2) This comes readily from Euler's criterion. We have *to con- sider the three cases (I)-- ©-+« ©-+■. ©-< f)— • (|)—- The method will be sufficiently illustrated by the treatment of the last case. Here we have aiiP-D^^j mo dp, ^Kp-D=_ t mo d/>. Multiplying these two congruences together member by member we have O^-^imOd^, '. whence (f)--m- as was to be proved. If m is any number prime to p and we write m as the product of factors w = e.2*V i(P-i)(a-i) 80 THEORY OF NUMBERS This equation states the law which connects the quadratic character of q with respect to p with the quadratic character of p with respect to q. It is known as the Law of Quadratic Reciprocity. About fifty proofs of it have been given. Its history has been a very interesting one; see Bachmann's Niedere Zahlentheorie, Teil I, pp. 180-318, especially pp. 200-206. For a further account of this beautiful and interesting subject we refer the reader to Bachmann, loc. cit., and to the memoirs to which this author gives reference. § 42. Galois Imaginaries If one is working in the domain of real numbers the equation # 2 +i=o has no solution; for there is no real number whose square is — 1. If, however, one enlarges the " number system" so as to include not only all real numbers but all complex numbers as well, then it is true that every algebraic equation has a root. It is on account of the existence of this theorem for the enlarged domain that much of the general theory of algebra takes the elegant form in which we know it. The question naturally arises as to whether we can make a similar extension in the case of congruences. The congruence # 2 = 3 mod 5 has no solution, if we employ the term solution in the sense in which we have so far used it. But we may if we choose intro- duce an imaginary quantity, or mark, j such that jf 2 = 3 mod 5, just as in connection with trie equation # 2 +i=o we would introduce the symbol i having the property expressed by the equation ;2 = _ T OTHER TOPICS 81 It is found to be possible to introduce in this way a general set of imaginaries satisfying congruences with prime moduli; and the new quantities or marks have the property of combining according to the laws of algebra. The quantities so introduced are called Galois imaginaries. We cannot go into a development of the important theory which is introduced in this way. We shall be content with indicating two directions in which it leads. In the first place there is the general Galois field theory which is of fundamental importance in the study of certain finite groups. It may be developed from the point of view indicated here. An excellent exposition, along somewhat different lines, is to be found in Dickson's Linear Groups with an Exposition of the Galois Field Theory. Again, the whole matter may be looked upon from the geo- metric point of view. In this way we are led to the general theory of finite geometries, that is, geometries in which there is only a finite number of points. For a development of the ideas which arise here see Veblen and Young's Projective Geometry and the memoir by Veblen and Bussey in the Trans- actions of the American Mathematical Society, vol. 7, pp. 241-259. § 43. Arithmetic Forms The simplest arithmetic form is ax+b where a and b are fixed integers different from zero and x is a variable integer. By varying x in this case we have the terms of an arithmetic progression. We have already referred to Dirichlet's cele- brated theorem which asserts that the form ax+b has an infinite number of prime values if only a and b are relatively prime. This is an illustration of one type of theorem connected with arithmetic forms in general, namely, those in which it is asserted that numbers of a given form have in addition a given property. Another type of theorem is illustrated by a result stated in §41, provided that we look at that result in the proper way. We saw that the number 2 is a quadratic residue of 82 THEORY OF NUMBERS every prime of either of the forms Sk + 1 and &k + j and a quad- ratic non-residue of every prime of either of the forms 8^+3 and 8^ + 5. We may state that result as follows: A given prime number of either of the forms Sk-\-i and Sk + 7 is a divisor of some number of the form x 2 — 2, where x is an integer; no prime number of either of the forms 8^+3 and 8^ + 5 is a divisor of a number of the form x 2 — 2, where x is an integer. The result just stated is a theorem in a discipline of vast extent, namely, the theory of quadratic forms. Here a large number of questions arise among which are the following: What numbers can be represented in a given form? What is the character of the divisors of a given form? As a special case of the first we have the question as to what numbers can be represented as the sum of three squares. To this category belong also the following two theorems: Every positive integer is the sum of four squares of integers; every prime number of the form 4^+1 may be represented (and in only one way) as the sum of two squares. For an extended development of the theory of quadratic forms we refer the reader to Bachmann's Arithmetik der Quad- ratischen Formen of which the first part has appeared in a volume of nearly seven hundred pages. It is clear that one may further extend the theory of arith- metic forms by investigating the properties of those of the third and higher degrees. Naturally the development of this subject has not been carried so far as that of quadratic forms; but there is a considerable number of memoirs devoted to various parts of this extensive field, and especially to the consideration of various special forms. Probably the most interesting of these special forms are the following : n nn niQti ** P n-l_l_ »-2/d_i_ 1 pn-1 a +j8 , ^ = « +<* P + • • • +P > a — p where a and j8 are relatively prime integers, or, more generally, where a and are the roots of the quadratic equation x 2 — ux+v — o where u and v are relatively prime integers. A .. & n (i-* 2t ) fc=0 It is clear that we have p(*)= 00 ■ n 1 ) I— X 2 * = n (i+x 2t k=0 = 2 G(s)x s , 8=0 +X 2 ■ 2t +x 3 - where G(o) = 1 and G(s) (for 5 greater than o) is the number of ways in which the positive integer s may be separated into like or distinct summands each of which is a power of 2. We have readily (i-xy2G(s)x s = (i-x)P(x)=P(x 2 )= I G(s)x 2S ; 8=0 s=0 whence G(2s+i) =G(2s) =G(2s-i)+G(s), (A) as one readily verifies by equating coefficients of like powers of x. From this we have in particular G(o) = i, G(i) = i, G( 2 ) = 2 , G( 3 ) = 2, G( 4 )=4, G( 5 )=4, G(6)=6, G( 7 )=6. Thus in (-4) we have recurrence relations by means of which we may readily reckon out the values of the number theoretic function G(s). Thus we may determine the number of ways in which a given positive integer 5 may be represented as a sum of powers of 2. 84 THEORY OF NUMBERS We have given this example as an elementary illustration of the analytical theory of numbers, that is, of that part of the theory of numbers in which one employs (as above) the theory of a continuous variable or some analogous theory in order to derive properties of sets of integers. This general subject has been developed in several directions. For a systematic account of it the reader is referred to Bachmann's Analytische Zahlentheorie. § 45. Diophantine Equations If f(x, y,z, . . . ) is a polynomial in the variables x, y, z, . . . with integral coefficients, then the equation f(x, y, z, . . . )=o is called a Diophantine equation when we look at it from the point of view of determining the integers (or the positive in- tegers) x, y, z, . . . which satisfy it. Similarly, if we have several such functions /*(#, y, z, . . . ), in number less than the number of variables x, y, z, . . . , then the set of equations ft(x, y,z, . . .)=o, i = i, 2, . . . , is said to be a Diophantine system of equations. Any set of integers x, y, z, . . . which satisfies the equation [system] is said to be a solution of the equation [system]. We may likewise define Diophantine inequalities by replac- ing the sign of equality above by the sign of inequality. But little has been done toward developing a theory of Diophantine inequalities. Even for Diophantine equations the theory is in a rather fragmentary state. In the next two sections we shall illustrate the nature of the ideas and the methods of the theory of Dipohantine equa- tions by developing some, of the results for two important special cases. OTHER TOPICS 85 § 46. Pythagorean Triangles Definitions. If three positive integers x, y, z satisfy the relation x 2 +y 2 = z 2 (1) they are said to form a Pythagorean triangle or a numerical right triangle; z is called the hypotenuse of the triangle and x and y are called its legs. The area of the triangle is said to be \xy. We shall determine the general form of the integers x, y, z, such that equation (i) may be satisfied. Let us denote by v the greatest common divisor of x and y in a particular solution of (1). Then v is a divisor of z and we may write x = vu, y = w, z = vw. Substituting these values in (i) and reducing we have u 2 +v 2 =w 2 , (2) where u, v, w are obviously prime each to each, since u and v have the greatest common divisor i. Now an odd square is of the form 4& + 1. Hence the sum of two odd squares is divisible by 2 but not by 4; and therefore the sum of two odd squares cannot be a square. Hence one of the numbers u, v is even. Suppose that u is even and write equation (2) in the form u 2 = (w— v)(w+v). (3) Every common divisor oi w—v and w+v is a divisor of their difference 2V. Therefore, since w and v are relatively prime, it follows that 2 is the greatest common divisor oi w—v and w+v. Then from (3) we see that each of these numbers is twice a square, so that we may write w— V = 2b 2 , w+v = 2a 2 86 THEORY OF NUMBERS where a and b are relatively prime integers. From these two equations and equation (3) we have w = a 2 +b 2 , v = a 2 — b 2 , u = 2ab. (4) Since u and v are relatively prime it is evident that one of the numbers a, b is even and the other odd. The forms of u, v, w given in (4) are necessary in order that (2) may be satisfied. A direct substitution in (2) shows that this equation is indeed satisfied by these values. Hence we have in (4) the general solution of (2) where u is restricted to be even. A similar solution would be obtained if v were re- stricted to be even. Therefore the general solution of (1) is x = 2vab, y = v(a 2 — b 2 ), z = v(a 2 +b 2 ) and x = v(a 2 — b 2 ), y = 2vab, z = v(a 2 +b 2 ) where a, b, v are arbitrary integers except that a and b are rela- tively prime and one of them is even and the other odd. By means of this general solution of (1) we shall now prove the following theorem: I. There do not exist integers m, n, p, q, all different from zero, such that q 2 -\-n 2 = m 2 , m 2 -\-n 2 =p 2 . (5) It is obvious that an equivalent theorem is the following: II. There do not exist integers m, n, p } q, all different from zero such that p 2 +q 2 = 2m 2 , p 2 —q 2 — 2n 2 . (6) Obviously, we may without loss of generality take m, n, p, q to be positive; and this we do. The method of proof is to assume the existence of integers satisfying equations (5) and (6) and to show that we are thus led to a contradiction. The argument we give is an illustra- tion of Fermat's famous method of " infinite descent.' ' If any two of the numbers p, q, m, n have a common prime factor /, it follows at once from (5) and (6) that all four of them OTHER TOPICS 87 have this factor. For, consider an equation in (5) or in (6) in which these two numbers occur; this equation contains a third number, and it is readily seen that this third number is divisible by /. Then from one of the equations containing the fourth number it follows that this fourth number is divisible by /. Now let us divide each equation of system (6) through by t 2 ; the resulting system is of the same form as (6). If any two numbers in this resulting system have a common prime factor h, we may divide through by h 2 ; and so on. Hence if a pair of simultaneous equations (6) exists then there exists a pair of equations of the same form in which no two of the num- bers m, n, p, q have a common factor other than unity. Let this system of equations be pi 2 +qi 2 = 2Mi 2 , pi 2 -qi 2 = 2tii 2 . (7) From the first equation in (7) it follows that pi and q\ are both even or both odd; and, since they are relatively prime, it follows that they are both odd. Evidently pi>qi. Then we may write pi=qi + 2s, such that c = r 2 -\-s 2 , a = 2rs, b = r 2 —s 2 or c = r 2 +s 2 , a = r 2 — s 2 , b = 2rs. 88 THEORY OF NUMBERS Hence from (8) we see that we may write qi-\-a = 2rs, a=r 2 —s 2 (9) or qi+a = r 2 — s 2 , a = 2TS. (10) In either case we have pi 2 -qi 2 = (pi-qi)(pi+qi) = 2a-2(q 1 +a)=Srs(r 2 -s 2 ). If we substitute in the second equation of (7) and divide by 2 we have 4rs(r 2 — s 2 )=n\ 2 . From this equation and the fact that r and 5 are relatively prime it follows at once that r, s, r 2 — s 2 are all square numbers; say, r = u 2 , s = v 2 , r 2 —s 2 = w 2 . Now r—s and r+s can have no common factor other than 1 or 2 ; hence from w 2 = (y2 _ S 2^ — (y _ 5 ) (y + s ^ = ( u 2 _ v 2^ ( u 2 _^_ v 2^ we see that either U 2 ~\-V 2 = 2Wi 2 , U 2 — V 2 = 2W2 2 (11) or U 2 ~\-V 2 =Wi 2 , U 2 —V 2 = W2 2 . And if it is the latter case which arises, then Wi 2 -\-W2 2 = 2U 2 , Wi 2 — W2 2 = 2V 2 . (12) Hence, assuming equations of the form (6) we are led either to equations (n) or to equations (12); that is, we are led to new equations of the form with which we started. Let us write the equations thus: p2 2 +q2 2 = 2tn 2 2 , p2 2 -q2 2 = 2n 2 2 ; (13) that is, system (13) is identical with that one of systems (11), (12) which actually arises. OTHER TOPICS 89 Now from (9) and (10) and the relations pi=qi + 2a, r>s, we see that pi = 2rs+r 2 -s 2 >2s 2 +r 2 -s 2 = r 2 +s 2 = u*+v*. Hence u-roots, 71. Pythagorean triangles, 85-90. 93 94 INDEX Quadratic forms, 82. Quadratic reciprocity, 80. Quadratic residues, 57-60, 77-80. Relatively prime, 10. Residue, 37, 58. Scales of notation, 22-24. Sieve of Eratosthenes, 10. Totient, 30. Triangles, Numerical, 85. Unit, 8. Veblen, 81. Wilson's theorem, 49-81. Young, 81. r?////5 3 3S 4^47 7 3. TT NIVEF CT TY <^ CALIFORNIA T1B^at>v v 14 DAY USE RETURN TO DESK FROM WHICH BORROWED LOAN DEPT. This book is due on the last date stamped below, or on the date to which renewed. Renewed books are subject to immediate recall. ntrr ° a r^*? RECErvpo DFP 1 7 'fi7 n -,u i f \ 1 - , p ■~ », Due end of SUMMER P ertoa Ja «'» $$ subject To recall oft< WC'U LD JUI .1570 -3PM 5 6 LD 2!A-60m-2,'67 H2-llslO)476B General Library University of California Berkeley 2*4* .♦, » 3teo?2 2W UNIVERSITY. OF CALIFORNIA LIBRARY