This book is DUE on last date stamped below
SOUTHERN BRANCH,
OF C7VLIF0RNIA,
HISTORY OF THE THEORY OF NUMBERS
VOLUME I
DIVISIBILITY AND PRIMALITY
By Leonard Eugene Dickson
Professor of Mathematics in the University of Chicago
Published by the Carnegie Institution of Washington Washington, 1919
/ 1 i 5 'J
CARNEGIE INSTITUTION OF WASHINGTON Publication No. 256, Vol. I
PRESS OF GIBSON BROTHERS WASHINGTON. D. C.
'fl
i
^
r^
, _ &!£:: steering*
'^vi-^ r7' Mathenrstical 2^H-j Sciences
:D/^ifii
PREFACE.
libraiy
The efforts of Cantor and his collaborators show that a chronological history of mathematics down to the nineteenth century can be written in four large volumes. To cover the last century with the same elaborateness, it has been estimated that about fifteen volumes would be required, so extensive is the mathematical literature of that period. But to retain the chronological order and hence devote a large volume to a period of at most seven years would defeat some of the chief purposes of a history, besides making it very inconvenient to find all of the material on a particular topic. In any event there is certainly need of histories which treat of particular branches of mathematics up to the present time.
The theory of numbers is especially entitled to a separate history on
account of the great interest which has been taken in it continuously through
the centuries from the time of Pythagoras, an interest shared on the one
extreme by nearly every noted mathematician and on the other extreme
^ by numerous amateurs attracted by no other part of mathematics. This
v history aims to give an adequate account of the entire literature of the
\ theory of numbers. The first volume presents in twenty chapters the
material relating to divisibility and primality. The concepts, results, and
Jl authors cited are so numerous that it seems appropriate to present here an
introduction which gives for certain chapters an account in untechnical
language of the main results in their historical setting, and for the remaining
• chapters the few remarks sufficient to clearly characterize the nature of their
v^, contents.
J' ' ' Perfect numbers have engaged the attention of arithmeticians of every *»>• century of the Christian era. It was while investigating them that Fermat discovered the theorem which bears his name and which forms the basis of a large part of the theory of numbers. A_perfect number is one, like 6 = 1+2+3, which equals the sum of its divisors other than itself . Euclid ,. proved that 2^~'^{2^ — \) is a perfect numbeflf 2^ — 1 is a prime. For p = 2, 3, 5, 7, the values 3, 7, 31, 127 of 2''-l are primes, so that 6, 28, 496, 8128 are perfect numbers, as noted by Nicomachus (about A. D. 100). A manu- script dated 1456 correctly gave 33550336 as the fifth perfect number; it cor- * ! responds to the value 13 of p. Very many early writers believed that 2^ — 1 I is a prime for every odd value of p. But in 1536 Regius noted that
2^-1 = 511 = 7-73, 211-1=2047 = 23-89
are not primes and gave the above fifth perfect number. Cataldi, who founded at Bologna the most ancient known academy of mathematics,
IV PREFACE.
noted in 1603 that 2'' — 1 is composite if p is composite and verified that it is a prime for p = 13, 17, and 19; but he erred in stating that it is also a prime for p = 23, 29, and 37. In fact, Fermat noted in 1640 that 2'-'-l has the factor 47, and 2^'-l the factor 223, while Euler observed in 1732 that 2'' — 1 has the factor 1103. Of historical importance is the statement made by Mersenne in 1644 that the first eleven perfect numbers are given by 2P-i(2P_i) for p = 2, 3, 5, 7, 13, 17, 19, 31, 67, 127, 257; but he erred at least in including 67 and excluding 61, 89, and 107. That 2" — 1 is com- posite was proved by Lucas in 1876, while its actual factors were found by Cole in 1903. The primality of 2^^ — 1, a number of 19 digits, was estab- lished by Pervusin in 1883, Seelhoff in 1886, and Hudelot m 1887. Both Powers and Fauquembergue proved in 1911-14 that 2^^ — 1 and 2^°^ — 1 are primes. The primality of 2'^ — 1 and 2™ — 1 had been estabhshed by Euler and Lucas respectively. Thus 2^— 1 is known to be a prime, and hence lead to a perfect number, for the twelve values 2, 3, 5, 7, 13, 17, 19, 31, 61, 89, 107 and 127 of p. Since 2^' — 1 is known (pp. 15-31) to be composite for 32 primes p ^257, only the eleven values p = 137, 139, 149, 157, 167, 193, 199, 227, 229, 241, 257 now remain in doubt.
Descartes stated in 1638 that he could prove that every even perfect number is of Euclid's type and that every odd perfect number must be of the form ps^, where p is a prime. Euler's proofs (p. 19) were published after his death. Xd. immediate proof of the former fact was given by Dickson (p. 30). According to Sylvester (pp. 26-27), there exists no odd perfect number with fewer than six distinct prime factors, and none with fewer than eight if not divisible by 3. But the question of the existence of odd perfect numbers remains unanswered.
A multiply perfect number, like 120 and 672, is one the sum of whose divisors equals a multiple of the number. They were actively investigated during the years 1631-1647 by IMersenne, Fermat, St. Croix, Frenicle, and Descartes. Many new examples hav^e been found recently by American writers.
Two numbers are called amicable if each equals the sum of the aliquot divisors of the other, where an aliquot divisor of a number means a divisor other than the number itself. The pair 220 and 284 was known to the Pythagoreans. In the ninth century, the Arab Thabit ben Korrah noted that 2"/!« and 2"s are amicable numbers if /j=3-2''-l, t = 2>'2'^^-l and s = 9.22"-! _i are all primes, and n> 1. This result leads to amicable numbers for n = 2 (giving the above pair), n = 4 and n = 7, but for no further value ^ 200 of n. The chief investigation of amicable numbers is that by Euler who listed (pp. 45, 46) 62 pairs. At the age of 16, Paganini announced in 1866 the remarkable new pair 1184 and 1210. A few new pairs of very large numbers have been found by Legendre, Seelhoff, and Dickson.
PREFACE. V
Interesting amicable triples and amicable numbers of higher order have been recently found by Dickson and Poulet (p. 50).
Although it had been employed in the study of perfect and amicable numbers, the explicit expression for the sum a{n) of all the divisors of n is reserved for Chapter II, in which is presented the history of Fermat's two problems to solve (T(x^)=y^ and <t{x^) =y^ and John Wallis's problem to find solutions other than a; = 4 and y = 5 oi (T{x^)=o-{y^).
Fermat stated in 1640 that he had a proof of the fact, now known as Fermat's theorem, that, if p is any prime and x is any integer not divisible by p, then x^~^ — l is divisible by p. This is one of the fundamental theo- rems of the theory of numbers. The case x = 2 was known to the Chinese as early as 500 B. C. The first published proof was given by Euler in 1736. Of first importance is the generalization from the case of a prime p to any integer n, published by Euler in 1760: if (/)(n) denotes the munber of positive integers not exceeding n and relatively prime to n, then x*^"^ — 1 is divisible . by n for every integer x relatively prime to n. Another elegant theorem states that, if p is a prime, l+jl-2-3. . . .{p — l)\ is divisible by p; it was first pubUshed by Waring in 1770, who ascribed it to Sir John Wilson. This theorem was stated at an earlier date in a manuscript by Leibniz, who with Newton discovered the calculus. But Lagrange was the first one to publish (in 1773) a proof of Wilson's theorem and to observe that its converse is true. In 1801 Gauss stated and suggested methods to prove the generali- zation of Wilson's theorem: if P denotes the product of the positive integers less than A and prime to A, then P+1 is divisible by A if A =4, p"" or 2p"*, where p is an odd prime, while P — 1 is divisible by A if A is not of one of these three forms. A very large number of proofs of the preceding theorems are given in the first part of Chapter III. Various generalizations are then presented (pp. 84-91). For instance, if iV = p/' . . . p/*, where Pi, ..., p« are distinct primes,
a^-(a^/P'+ . . . +a^/PO + (a^/P'P'+ ...)-••• . +(-l)''a^/^---P''
is divisible by N, a fact due to Gauss for the case in which a is a prime.
Many cases have been found in which o"~^ — 1 is divisible by n for a composite number n. But Lucas proved the following converse of Fermat's theorem : if a^ — 1 is divisible by n when x = n — l, but not when x is a divisor |<n — 1 of 71 — 1, then w is a prime.
Any integral symmetric function of degree d of 1, 2, . . ., p — 1 with I integral coefficients is divisible by the prime p if c^ is not a multiple of p — 1. A generalization to the case of a divisor p" is due to Meyer (p. 101) . Nielsen proved in 1893 that, if p is an odd prime and if k is odd and l<fc<p — 1, the sum of the products of 1, 2, . . ., p — 1 taken A; at a time is divisible by p^. Taking fc = p — 2, we see that if p is a prime > 3 the numerator of the fraction
A
VI PREFACE.
equal to 1 + 1/2+1/3+ . . . +l/(p — 1) is divisible by p'^, a result first proved by Wolstenholme in 1862. Sylvester stated in 1866 that the sum of all products of n distinct numbers chosen from 1, 2, . . . , w is divisible by each prime > n + 1 which is contained in any term of the set m — n + 1 , . . . , w, m + 1 . There are various theorems analogous to these.
In Chapter IV are given properties of the quotient {uP~^ — l)/p, which plays an important role in recent investigations on Fermat's last theorem (the impossibiUty of x'^-\-y^ = z^ if p>2), the history of which will be treated in the final chapter of Volume II. Some of the present papers relate to (w*^"^ — 1)/«, where n is not necessarily a prime.
TMiile Euler's ^-function was defined above in order to state his general- ization of Fermat's theorem, its numerous properties and generalizations are reserved for the long Chapter V. In 1801 Gauss gave the result that 4>{d^ + . . . -\-<i>{dk) = n, if di, . . . , d^ are the divisors of n; this was generalized by Laguerre in 1872, H. G. Cantor in 1880, Busche in 1888, Zsigmondy in 1893, Vahlen in 1895, Elliott in 1901, and Hammond in 1916. In 1808 Legendre proved a simple formula for the number of integers ^ n which are divisible by no one of any given set of primes. The asymptotic value of (f>{l)-\- . . . +0(G) for G large was discussed by Dirichlet in 1849, Mertens in 1874, Perott in 1881, Sylvester in 1883 and 1897, Cesaro in 1883 and 1886-8, Berger in 1891, and Kronecker in 1901. The solution of 4>{x)=g was treated by Cayley in 1857, Mmin in 1897, Pichler in 1900, Carmichael in 1907-9, Ranum in 1908, and Cunningham in 1915. H. J. S. Smith proved in 1875 that the m-rowed determinant, ha\ing as the element in the ith row and ji\i column any function fib) of the greatest common divisor 5 of i and j, equals the product of F{\), F{2),. . ., F(m), where
F(m)=/(m)-2/g)+2/(^J-...., m = py
In particular, F{m)=<t>{m) if f{8)=8. In several papers (pp. 128-130) Cesaro considered analogous determinants. The fact that 30 is the largest number such that all smaller numbers relatively prime to it are primes was first proved by Schatunowsky in 1893.
A. Thacker in 1850 evaluated the sum 4>k{n) of the kth. powers of the integers ^n which are prime to n. His formula has been expressed m^ various symbolic forms by Ces^o and generalized by Glaisher and Nielsen./ Crelle had noted in 1845 that <piin) = |n0( n). In 1869 Schemmel considered the number of sets of n consecutive integers each < m and prime to m. In connection with linear congruence groups, Jordan evaluated the number of different sets of k positive integers ^?i whose greatest common divisor is prime to n. This generalization of Euler's (^-function has properties as simple as the latter function and occurs in many papers under a variety of notations. It in turn has been generalized (pp. 151-4).
PREFACE. VII
The properties of the set of all irreducible fractions, arranged in order of magnitude, whose numerators are ^ m and denominators are ^ n (called a Farey series if m = n), have been discussed by many writers and applied to the approximation of numbers, to binary quadratic forms, to the composi- tion of linear fractional substitutions, and to geometry (pp. 155-8).
Some of the properties of periodic decimal fractions are already familiar tq the reader in view of his study of arithmetic and the chapter of alge- bra dealing with the sum to infinity of a geometric progression. For the generalization to periodic fractions to any base h, not necessarily 10, the length of the period of the periodic fraction for 1/d, where d is prime to h, is the least positive exponent e such that h^ — \ is divisible by d. Hence this Chapter VI, which reports upon more than 160 papers, is closely related to the following chapter and furnishes a concrete introduction to it.
The subject of exponents and primitive roots is one of the important topics of the theory of numbers. To present the definitions in the customary, compact language, we shall need the notion of congruence. If the differ- ence of two integers a and 6 is divisible by m, they are called congruent modulo m and we write a=& (mod m). For example, 8=2 (mod 6). If n'= 1 (mod m), but n*^ 1 (mod m) for 0<s<e, we say that n belongs to the exponent e modulo m. For example, 2 and 3 belong to the exponent 4 modulo 5, while 4 belongs to the exponent 2. In view of Euler's generaliza- tion of Fermat's theorem, stated above, e never exceeds 0(m). If n belongs to this maximum exponent ^(n) modulo m, n is called a primitive root of m. For example, 2 and 3 are primitive roots of 5, while 1 and 4 are not. Lam- bert stated in 1769 that there exists a primitive root of any prime p, and Euler gave a defective proof in 1773. In 1785 Legendre proved that there are exactly 4>{e) numbers belonging modulo p to any exponent e which divides p — 1. In 1801 Gauss proved that there exist primitive roots of m if and only if m = 2, 4, p* or 2p*, where p is an odd prime. In particular, for a primitive root a of a prime modulus p and any integer N not divisible by p, there is an exponent ind N, called the index of N by Gauss, such that N=a''"^^ (mod p). Indices play a role similar to logarithms, but we re- quire two companion tables for each modulus p. The extension to a power of prime modulus is immediate. For a general modulus, systems of indices were employed by Dirichlet in 1837 and 1863 and by Kronecker in 1870. Jacobi's Canon Arithmeticus of 1839 gives companion tables of indices for each prime and power of a prime < 1000. Cunningham's Binary Canon of 1900 gives the residues of the successive powers of 2 when divided by each prime or power of a prime < 1000 and companion tables showing the powers of 2 whose residues are 1, 2, 3, . . .. In 1846 Arndt proved that, if ^ is a primitive root of the odd prime p, g belongs to the exponent p"~"^(p — 1) modulo p'* if and only ii G = g^~^ — 1 is divisible by p^, but not by p^'^\ where
VIII PREFACE.
X<n; taking X= 1, we see that, if G is not divisible by p^, g' is a primitive root of p^ and of all higher powers of p. This Chapter VII presents many more theorems on exponents, primitive roots, and binomial congruences, and cites various lists of primitive roots of primes < 10000.
Lagrange proved easily that a congruence of degree n has at most n roots if the modulus is a prime. Lebesgue found the number of sets of solutions of 01^1"*+ • • • -\-akXk"=a (mod p), when p is a prime such that p — 1 is divisible by m. Konig (p. 226) employed a cyclic determinant and its minors to find the exact number of real roots of any congruence in one unknown; Gegen- bauer (p. 228) and Rados (p. 233) gave generalizations to congruences in several unknowns.
Galois's introduction of imaginary roots of congruences has not only led to an important extension of the theory of numbers, but has given rise to wide generalizations of theorems which had been obtained in subjects like linear congruence groups by applying the ordinary theory of numbers. Instead of the residues of integers modulo p, let us consider the residues of polynomials in a variable x with integral coefficients with respect to two moduH, one being a prime p and the other a polynomial f{x) of degree n which is irreducible modulo p. The residues are the p" polynomials in x of degree n — 1 whose coefficients are chosen from the set 0, 1, . . . , p — 1 . These residues form a Galois field within which can be performed addition, sub- traction, multiplication, and division (except by zero) . As a generahzation of Fermat's theorem, Galois proved that the power p" — 1 of any residue except zero is congruent to unity with respect to our pair of moduli p and f{x). He avoided our second modulus f{x) by introducing an undefined imaginary root i of f{x) = 0 (mod p) and considering the residues modulo p of polynomials in i; but the above use of the two moduH affords the only logical basis of the theory. In view of the fullness of the reports in the text (pp. 233-252) of the papers on this subject, further comments here are unnecessary. The final topics of this long Chapter VIII are cubic congru- ences and miscellaneous results on congruences and possess little general interest.
In Chapter IX are given Legendre's expression for the exponent of the highest power of a prime p which divides the factorial 1-2. . .m, and the generalization to the product of any integers in arithmetical progression; many theorems on the divisibility of one product of factorials by another product and on the residues of multinomial coefficients ; various determina- tions of the sign in 1-2... (p — l)/2==tl (mod p); and miscellaneous congruences involving factorials.
In the extensive Chapter X are given many theorems and formulas concerning the sum of the kth. powers of all the divisors of n, or of its even or odd divisors, or of its divisors which are exact sth powers, or of those divisors
PREFACE. IX
whose complementary divisors are even or odd or are exact sth powers, and the excess of the sum of the A;th powers of the divisors of the form 4m +1 of a number over the sum of the A;th powers of the divisors of the form 4m -f 3, as well as more technical sums of divisors defined on pages 297, 301-2, 305, 307-8, 314-5 and 318. For the important case k = 0, such a sum becomes the number of the divisors in question. There are theorems on the number of sets of positive integral solutions of UiU^. . .Uk = n or of x''y^ = n. Also Glaisher's cancellation theorems on the actual divisors of numbers (pp. ^' 310-11, 320-21). Scattered through the chapter are approximation and asymptotic formulas involving some of the above functions.
In Chapter XI occur Dirichlet's theorem on the number of cases in the
division of n by 1, 2, . . . , p in turn in which the ratio of the remainder to the
divisor is less than a given proper fraction, and the generalizations on pp.
330-1; theorems on the number of integers ^n which are divisible by no
,( exact sth power > 1 ; theorems on the greatest divisor which is odd or has
/ specified properties; many theorems on greatest coromon divisor and least
I common multiple ; and various theorems on mean values and probability.
' The casting out of nines or of multiples of 11 or 7 to check arithmetical
computations is of early origin. This topic and the related one of testing
the divisibility of one number by another have given rise to the numerous
elementary papers cited in Chapter XII.
The frequent need of the factors of numbers and the excessive labor required for their direct determination have combined to inspire the construction of factor tables of continually increasing limit. The usual method is essentially that given by Eratosthenes in the third century B. C. A special method is used by Lebon (pp. 355-6). Attention is called to Lehmer's Factor Table for the First Ten Millions and his List of Prime Numbers from 1 to 10,006,721, published in 1909 and 1914 by the Carnegie Institution of Washington. Since these tables were constructed anew with the greatest care and all variations from the chief former tables were taken account of, they are certainly the most accurate tables extant. Absolute accuracy is here more essential than in ordinary tables of continuous func- tions. Besides giving the history of factor tables and lists of primes, this Chapter XIII cites papers which enumerate the primes in various intervals, prime pairs (as 11, 13), primes of the form 4n+l, and papers listing primes written to be base 2 or large primes.
Chapter XIV cites the papers on factoring a number by expressing it as a difference of two squares, or as a sum of two squares in two ways, or by use of binary quadratic forms, the final digits, continued fractions. Pell equa- tions, various small moduli, or miscellaneous methods.
Fermat expressed his belief that Fn = 2^"+l is a prime for every value of n. While this is true if n = 1, 2, 3, 4, it fails forn = 5 as noted by Euler. Later,
X PREFACE.
Gauss proved that a regular polygon of m sides can be constructed by ruler and compasses if m is a product of a power of 2 and distinct odd primes each of the form Fn, and stated correctly that the construction is impossible if m is not such a product. In view of the papers cited in Chapter XV, F„ is composite if n = 5, 6, 7, 8, 9, 11, 12, 18, 23, 36, 38 and 73, while nothing is known for other values >4 of n. No conoment will be made on the next chapter which treats of the factors of numbers of the form o"±6" and of certain trinomials.
In Chapter XVII are treated questions on the divisors of terms of a recurring series and in particular of Lucas' functions
a — o
where a and h are roots oi x'^ — Px-\-Q = Q, P and Q being relatively prime integers. By use of these functions, Lucas obtained an extension of Euler's generaUzation of Fermat's theorem, which requires the correction noted by Carmichael (p. 406), as well as various tests for primality, some of which have been emploj^ed in investigations on perfect numbers. Many papers on the algebraic theory of recurring series are cited at the end of the chapter.
Euchd gave a simple and elegant proof that the number of primes is infi- nite. For the generalization that every arithmetical progression n, n+m, n-\-2m,. . ., in which n and m are relatively prime, contains an infinitude of primes, Legendre offered an insufficient proof, while Dirichlet gave his classic proof by means of infinite series and the classes of binary quadratic forms, and extended the theorem to complex integers. Mertens and others obtained simpler proofs. For various special arithmetical progressions, the theorem has been proved in elementary ways by many writers. Dirichlet also obtained the theorems that, if a, 26, and c have no common factor, ax'^+2hxy-\-cy^ represents an infinitude of primes, while an infinitude of these primes are representable by any given linear form Mx+N with M and N relatively prime, pro\^ded a, h, c, M, N are such that the quadratic and linear forms can represent the same number.
No complete proof has been found for Goldbach's conjecture in 1742 that every even integer is a sum of two primes. One of various analogous un- proved conjectures is that every even integer is the difference of two consec- utive primes in an infinitude of ways (in particular, there exists an infinitude of pairs of primes differing by 2). No comment will be made on the further topics of this Chapter XVIII: polynomials representing numerous primes, primes in arithmetical progression, tests for primality, number of primes between assigned limits, Bertrand's postulate of the existence of at least one prime between x and 2x — 2 for x>3, miscellaneous results on primes, diatomic series, and asymptotic distribution of primes.
PREFACE. XI
If F(m)=2/(d), summed for all the divisors d of m, we can express /(m) in terms of F by an inversion formula given in Chapter XIX along with generalizations and related formulas. Bougaief called F{m) the numerical integral of /(m).
The final Chapter XX gives many elementary results involving the digits of numbers mainly when written to the base 10.
Since the history of each main topic is given separately, it has been possible without causing confusion to include reports on minor papers and isolated problems for the sake of completeness. In the cases of books and journals not usually accessible, the reports are quite full with some indication of the proofs. In other cases, proofs are given only when necessary to differentiate the paper from others deriving the same result.
The references were selected mainly from the Subject Index of the Royal Society of London Catalogue of Scientific Papers, volume 1, 1908 (with which also the proof-sheets were checked), and the supplementary annual volumes forming the International Catalogue of Scientific Literature, Jahrbuch iiber die Fortschritte der Mathematik, Revue semestrielle des publications math^matiques, Poggendorff's Handworterbuch, Kliigel's Mathematische Worterbuch, Wolffing's Mathematischer Biicherschatz (a list of mathemat- ical books and pamphlets of the nineteenth century), historical journals, such as Bulletino di bibliografia e di storia delle scienze matematiche e fisiche, Bolletino . . . . , BibUotheca Mathematica, Abhandlungen zur Geschichte der mathematischen Wissenschaften, various histories and encyclopedias, including the Enclyclop^die des sciences mathematiques. Further, the author made a direct examination at the stacks of books and old journals in the libraries of Chicago, California, and Cambridge Universities, and Trinity College, Cambridge, and the excellent John Crerar Library at Chi- cago. He made use of G. A. Plimpton's remarkable collection, in New York, of rare books and manuscripts. In 1912 the author made an extended investigation in the libraries of the British Museum, Kensington Museum, Royal Society, Cambridge Philosophical Society, Bibliotheque Nationale, Universite de Paris, St. Genevieve, I'lnstitut de France, Uni- versity of Gottingen, and the Konigliche Bibhothek of Berlin (where there is a separate index of the material on the theory of numbers). Many books have since been borrowed from various libraries; the Ladies' and other Diaries were loaned by R. C. Archibald.
At the end of the volume is a separate index of authors for each of the twenty chapters, which will facilitate the tracing of the relation of a paper to kindred papers and hence will be of special service in the case of papers inaccessible to the reader. The concluding volume will have a combined index of authors from which will be omitted minor citations found in the chapter indices.
XII PREFACE.
The subject index contains a list of symbols; while [x] usually denotes the greatest integer ^x, occasionally such square brackets are used to inclose an addition to a quotation. The symbol * before an author's name signifies that his paper was not available for report. The symbol f before a date signifies date of death. Initials are given only in the first of several immediately successive citations of an author.
Although those volumes of Euler's Opera Omnia which contain his Com- mentationes Arithmeticae CoUectse have been printed, they are not yet available; a table showing the pages of the Opera and the corresponding pages in the present volume of this history will be given in the concluding volume.
The author is under great obligations to the following experts in the theory of numbers for numerous improvements resulting from their reading the initial page proofs of this volume: R. D. Carmichael, L. Chanzy, A. Cunningham, E. B. Escott, A. Gerardin, A. J. Kempner, D. N. Lehmer, E. Maillet, L. S. Shively, and H. J. Woodall; also the benefit of D. E. Smith's accurate and extensive acquaintance with early books and writers was for- tunately secured ; and the author's special thanl<:s are due to Carmichael and Kempner, who read the final page proofs with the same critical attention as the initial page proofs and pointed out various errors and obscurities. To these eleven men who gave so generously of their time to perfect this volume, and especially to the last two, is due the gratitude of every devotee of number theory who may derive benefit or pleasure from this history. In return, such readers are requested to further increase the usefulness of this work by sending corrections, notices of omissions, and abstracts of papers marked not available for report, for insertion in the concluding volume.
Finally, this laborious project would doubtless have been abandoned soon after its inception seven years ago had not President Woodward approved it so spontaneously, urged its completion with the greatest thoroughness, and given continued encouragement.
L. E. Dickson. November, 1918.
^ TABLE OF CONTENTS.
Chapter. page.
I. Perfect, multiply perfect, and amicable numbers 3
\ 11. Formulas for the number and simi of divisors, problems of Fermat
and Wallis 51
III. Fermat's and Wilson's theorems, generalizations and converses;
symmetric functions of 1, 2, . . . , p— 1, modulo p 59
IV. Residue of (wp~^ — l)/p modulo p 105
V. Euler's (^function, generalizations; Farey series 113
VI. Periodic decimal fractions; periodic fractions; factors of 10" =•=!... . 159
VII. Primitive roots, exponents, indices, binomial congruences 181
VIII. Higher congruences 223
IX. Divisibility of factorials and multinomial coefficients 263
X. Sum and number of divisors 279
XI. Miscellaneous theorems on divisibility, greatest common divisor,
least common multiple 327
XII. Criteria for divisibility by a given number 337
XIII. Factor tables, lists of primes 347
v^IV. Methods of factoring 357 •
XV. Fermat numbers F„ = 22"+l 375
XVI. Factors of a"±6« 381
XVII. Recurring series; Lucas' Un, Vn 393
^VIII. Theory of prime numbers 413
XIX. Inversion of functions; Mobius' function ix{n); numerical integrals
and derivatives 441
XX. Properties of the digits of numbers 453
Author index 467
Subject index 484
1
(.
CHAPTER I.
PERFECT. MULTIPLY PERFECT. AND AMICABLE NUMBERS. Perfect, Abundant, and Deficient Numbers.
By the aliquot parts or divisors of a number are meant the divisors, including unity, which are less than the number. A number, like 6 = 1 -h 2+3, which equals the sum of its aliquot divisors is called perfect (voll- kommen, vollstandig) . If the sum of the aliquot divisors is less than the number, as is the case with 8, the number is called deficient (diminute, defective, unvollkommen, unvollstandig, mangelhaft). If the sum of the aliquot divisors exceeds the number, as is the case with 12, the number is called abundant (superfluos, plus quam-perfectus, redundantem, exc^dant, iibervollstandig, iiberflussig, iiberschiessende) .
Euclid^ proved that, if p = 1+2+2^+ • • • +2" is a prime, 2"p is a perfect number. He showed that 2"p is divisible by 1, 2, . . . , 2", p, 2p, . . . , 2'*~^p, but by no further number less than itself. By the usual theorem on geometrical progressions, he showed that the sum of these divisors is 2"^.
The early Hebrews^" considered 6 to be a perfect number.
Philo Judeus^'' (first century A. D.) regarded 6 as the most productive of all numbers, being the first perfect number.
Nicomachus^ (about A. D. 100) separated the even numbers (book I, chaps. 14, 15) into abundant (citing 12, 24), deficient (citing 8, 14), and perfect, and dwelled on the ethical import of the three types. The perfect (I, 16) are between excess and deficiency, as consonant sound between acuter and graver sounds. Perfect numbers will be found few and arranged with fitting order; 6, 28, 496, 8128 are the only perfect numbers in the respective intervals between 1, 10, 100, 1000, 10000, and they have the property of ending alternately in 6 and 8. He stated that Euclid's rule gives all the perfect numbers without exception.
Theon of Smyrna^ (about A. D. 130) distinguished between perfect (citing 6, 28), abundant (citing 12) and deficient (citing 8) numbers.
^Elementa, liber IX, prop. 36. Opera, 2, Leipzig, 1884, 408. ^"S. Rubin, "Sod Hasfiroth" (secrets of numbers), Wien, 1873, 59; citation of the Bible,
Kings, II, 13, 19. **Treatise on the account of the creation of the world as given by Moses, C. D. Young's
transl. of Philo's works, London, 1854, vol. 1, p. 3. 'Nicomachi Gerasini arithmeticse Ubri duo. Nunc primdm typis excusi, in lucem eduntur.
Parisiis, 1538. In officina Christian! WecheU. (Greek.) Theologumena arithmeticae. Accedit Nicomachi Gerasini institutio arithmetica ad fidem
codicum Monacensium emendata. Ed., Fridericus Astius. Lipsiae, 1817. (Greek.) Nicomachi Geraseni Pythagorei introductionis arithmeticae libri ii. Recensvit Ricardus
Hoche. Lipsiae, 1866. (Greek.) 'Theonis Smymaei philosophi Platonici expositio rerum mathematicarum ad legendum
Platonem utiHum. Ed., Ed. Hiller, Leipzig, 1878, p. 45. Theonis Smymaei Platonici, Latin by Ismaele BuUialdo. Paris, 1644, chap. 32, pp. 70-72.
3
4 History of the Theory of Numbers. [Chap. I
lamblichus* (about 283-330) repeated in effect the remarks by Nico- machus on perfect, abundant, and deficient numbers, but made erroneous additions. He stated that there is one and but one perfect number in the successive intervals between 1, 10, 100,..., 100000, etc., to infinity. "Examples of a perfect number are 6, and 28, and 496, and 8128, and the like numbers, alternately ending in 6 and 8." He remarked that the Pythag- oreans called the perfect number 6 marriage, and also health and beauty (on account of the integrity of its parts and the agreement existing in it).
Aurelius Augustinus^ (354-430) remarked that, 6 being the first perfect number, God effected the creation in 6 daj's rather than at once, since the perfection of the work is signified by the number 6. The sum of the aUquot parts of 9 falls short of it; likewise for 10. But the sum of the aliquot parts of 12 exceeds it.
Anicius Manhus Severinus Boethius^ (about 481-524), in a Latin exposi- tion of the arithmetic of Nicomachus, stated that perfect numbers are rare, easily counted, and generated in a very regular order, while abundant (superfluos) and deficient (diminutos) numbers are found to an unlimited extent and not in regular order. The perfect numbers below 10000 are 6, 28, 496, 8128. And these numbers alwaj^s end alternately in 6 and 8.
Munyos^ stated that Boethius added to EucUd's idea of perfect number that of deficient (diminute) and abundant (redundantem) numbers.
Isidorus of Seville^ (570-636) distinguished even and odd numbers, perfect and abundant numbers, linear, flachen and Korper Zahlen (primes, products of two, products of three factors).
Alcuin^ (735-804) , of York and Tours, explained the occurrence of the number 6 in the creation of the universe on the ground that 6 is a perfect number. The second origin of the human race arose from the deficient number 8; indeed, in Noah's ark there were 8 souls from which sprung the entire human race, showing that the second origin was more imperfect than the first, which was made according to the number 6.
^lamblichus Chalcidensis ex Coele-Syria in Nicomachi Geraseni arithmeticam introduc-
tionem, et de Fato. Accedit Joachimi Camerarii explicatio in duos libros Nicomachi.
Ed., Samuel Tennulius. Amhemiae, 1668, pp. 43-47. (Greek text and Latin translation
in parallel columns.) lamblichi in Nicomachi arithmeticam introductionem Uber ad fidem codicis Florentini.
Ed., H. Pistelli. Lipsiae, 1894. (Greek.) *De Civitate Dei, hber XI, cap. XXX, ed., B. Dombart, Lipsiae, 1877, 1, p. 504. The reference
by Frizzo"' i' to lib. II, cap. 39. "Arithmetica boetij, Augsburg, 1488; Cologne, 1489; Leipzig, 1490; Venice, 1491-2, 1499;
Paris, [1496, 1501], 1503, etc.; lib. 1, cap. 20. "De generatione numeri perfecti." Opera Boetii, Venice, 1491-2, etc.; ed., Friedlein, Leipzig, 1867. "Institvtiones arithmeticae ad percipiendam astrologiam et mathematicas facultates neces-
sariae. Auctore Hieronymo Mimj'os, Valentiae, 1566, f. 5, verso. *Incipit epistola Isidori iunioris hispalensis . . . Finit Uber etymologiarum . . . [Augsburg,
1472]; Venice, 1483, etc. In this book of etymologies, arithmetic is treated very briefly
in Book 3, beginning f . 15. •Bibhotheca Rerum Germanicarum, tomus sextus: Monumenta Alcuiniana, Berlin, 1873,
epistolae 259, pp. 818-821. Cf. Migne, Patrologiae, vol. 100, 1851, p. 665; Hankel,
Geschichte Math., p. 311.
Chap. I] PERFECT, MULTIPLY PERFECT, AND AmICABLE NUMBERS. 5
Thabit ben Korrah,^° in a manuscript composed the last half of the ninth century, attributed to Pythagoras and his school the employment of perfect and amicable numbers in illustration of their philosophy. Let s = 1+2+ ... +2". Then (prop. 5), 2'*s is a perfect number if s is a prime; 2"p is abundant if p is a prime <s, deficient if p is a prime >s, and the excess or deficiency of the sum of all the divisors over the number equals the difference of s and p. Let (prop. 6) p' and p" be distinct primes >2; the sum of the divisors <N oi N = p'p"2" is
a = (2"+i-l)(l+p'+p") + (2"-l)py.
Hence N is abundant or deficient according as
a-iV=(2"+^-l)(l+p'+p")-py>0or <0.
Hrotsvitha,^^ a nun in Saxony, in the second half of the tenth century, mentioned the perfect numbers 6, 28, 496, 8128.
Abraham Ibn Ezra^^" (tll67), in his commentary to the Pentateuch, Ex. 3, 15, stated that there is only one perfect number between any two successive powers of 10.
Rabbi Josef b. Jehuda Ankin^^'', at the end of the twelfth century, recom- mended the study of perfect numbers in the program of education laid out in his book "Healing of Souls."
Jordanus Nemorarius^^ (tl236) stated (in Book VII, props. 55, 56) that every multiple of a perfect or abundant number is abundant, and every divisor of a perfect number is deficient. He attempted to prove (VII, 57) the erroneous statement that all abundant numbers are even.
Leonardo Pisano, or Fibonacci, cited in his Liber Abbaci^^ of 1202, revised about 1228, the perfect numbers
1 2^(2^-1) =6, i 2^(2^-1) =28, | 2^(2^-1) =496,
excluding the exponent 4 since 2^ — 1 is not prime. He stated that by pro- ceeding so, you can find an infinitude of perfect numbers.
i^Manuscript 952, 2, Suppl. Arabe, Bibliotheque imperiale, Paris. Textual transl., except of the proofs which are given in modem algebraic notation as foot-notes [as numbers were represented by line, in the manuscript], by Franz Woepcke, Journal Asiatique, (4), 20, 1852, 420-9.
"See Ch. Magnin, Theatre de Hrotsvitha, Paris, 1845.
""Mikrooth Gedoloth, Warsaw, 1874 ("Large Bible" in Hebrew). Samuel Ben Sdadias Ibn Motot; a Spaniard, wrote in 1370 a commentary on Ibn Ezra's commentary, Perush ai Perush Ibn Ezra, Venice, 1554, p. 19, noting the perfect numbers 6, 28, 496, 8128, and citing EucUd's rule. Steinschneider, in his book on Ibn Ezra, Abh. Geschichte Math. Wiss., 1880, p. 92, stated that Ibn Ezra gave a rule for finding all perfect numbers. As this rule is not given in the Mikrooth Gedoloth of 1874, Mr. Ginsburg of Columbia University infers the existence of a fuller version of Ibn Ezra's commentary. "^Quoted by Giideman, Das Jiidische Unterrichtswesen wahrend der Spanish Arabischen Periode, Wien, 1873.
*^In hoc opere contenta. Arithmetica decern libris demonstrata .... Epitome i libros arithmeticos diui Seuerini Boetij . . . , Paris, 1496, 1503, etc. It contains Jordanus' "Elementa arithmetica decern libris, demonstrationibus Jacobi Fabri Stapulensis," and "Jacobi Fabri Stapulenais epitome in duos Hbros arithmeticos diui Seuerini Boetij."
i^Il Liber Abbaci di Leonardo Pisano. Roma, 1857, p. 283 (Scritti, vol. 1).
6 History of the Theory of Numbers. [Chap. I
In the manuscripts^ Codex lat. Monac. 14908, a part dated 1456 and a part 1461, the first four perfect numbers are given (J. 33') as usual and the fifth perfect number is stated correctly to be 33550336.
Nicolas Chuquet^^ defined perfect, deficient, and abundant numbers, indicated a proof of EucHd's rule and stated incorrectly that perfect num- bers end alternately in 6 and 8.
Luca Paciuolo, de Borgo San Sepolcro,^^ gave (f. 6) Euclid's rule, saying one must find by experiment whether or not the factor 1+2+4+. . . is prime, stated (f. 7) that the perfect numbers end alternately in 6 and 8, as 6, 28, 496, etc., to mfinity. In the fifth article (ff. 7, 8), he illustrated the finding of the aliquot divisors of a perfect number by taking the case of the fourteenth perfect number 9007199187632128. He gave its half, then the half of the quotient, etc., until after 26 divisions by 2, the odd number 134217727, marked " Indi^dsibilis " [prime]. Dividing the initial number by these quotients, he obtained further factors [1,2,..., 2'^, but written at length]. The proposed number is said to be evidently perfect, since it is the sum of these factors [but he has not employed all the factors, since the above odd number equals 2'-'^ — 1 and has the factor 2^ — 1 = 7] . Although Paciuolo did not list the perfect numbers between 8128 and 90 . . .8, the fact that he called the latter the fourteenth perfect number imphes the error expressly committed bj^ Bo^illus.^"
Thomas Bradwardin^" (1290-1349) stated that there is only one perfect number (6) between 1 and 10, one (28) up to 100, 496 up to 1000, 8128 up to 10000, from which these numbers, taken in order, end alternately in 6 and 8. He then gave EucUd's rule.
Faber Stapulensis^^ or Jacques Lefevre (born at Etaples 1455, tl537) stated that all perfect numbers end alternately in 6 and 8, and that Euclid's rule gives all perfect numbers.
Georgius Valla^^ gave the first four perfect numbers and observed that
"The manuscript is briefly described by Gerhardt, Monatsber. Berlin Ak., 1870, 141-2.
See Catalogus codicum latinorum bibliothecae regiae Monacensis, Tomi II, pars II,
codices nuna. 11001-15028 complectus, Munich, 1876, p. 250. An extract of ff. 32-34
on perfect numbers was published by MaximiUan Curtze, BibUotheca Mathematica,
(2), 9, 1895, 39-42. "Triparty en la science des nombres, manuscript No. 1436, Fonds Fran^ais, BibliothSque
Nationale de Paris, written at Lyons. 1484. Published by Aristide Marre, Bull. Bibl.
Storia Sc. Mat. et Fis.. 13 (1880), 593-659, 693-814; 14 (1881), 417-460. See Part 1,
Ch. Ill, 3, 619-621, manuscript, ff. 20-21. "Summa de Arithmetica geometria proportioni et proportionalita. [Suma . . , Venice, 1494.]
Toscolano, 1523 (two editions substantially the same). "Arithmetica thome brauardini. Tractatus perutilis. In arithmetica speculativa a magistro
thoma Brauardini ex libris eucUdis boecij & ahorum qua optimne excerptus. Parisiis,
1495, 7th unnumbered page. Arithmetica Speculativa Thome Brauardini nuper mendis Plusculis tersa et diligenter Impressa,
Parisiis [1502], 6th and 7th unnumbered pages. Also undated edition [1510], 3d page. "Epitome (iii) of the arithmetic of Boethius in Faber's edition of Jordanus," 1496, etc.
Also in Introductio Jacobi fabri Stapulesis in Arithmecam diui Seuerini Boetij pariter
Jordani, Paris, 1503, 1507. Also in Stapulensis, Jacobi Fabri, Arithmetica Boethi
epitome, Basileae, 1553, 40. "De expetendis et fvgiendis rebvs opvs, Aldus, 1501. Liber I ( = Arithmeticae I), Cap. 12.
Chap. I] PERFECT, MULTIPLY PERFECT, AND AmICABLE NuMBERS. 7
"these happen to end in 6 or 8. . .and these terminal numbers will always be found alternately."
Carolus Bovillus^" or Charles de Bouvelles (1470-1553) stated that every perfect number is even, but his proof applies only to those of Euclid's type. He corrected the statement of Jordanus^^ that every abundant number is even, by citing 45045 [ = 5-9-7-ll-13] and its multiples. He stated that 2" — 1 is a prime if n is odd, expUcitly citing 511 [ = 7-73] as a prime. He listed as perfect numbers 2"~^(2'* — 1), n ranging over all the odd numbers ^ 39 [Cataldi^ later indicated that 8 of these are not perfect]. He repeated the error that all perfect numbers end alternately in 6 and 8. He stated (f. 175, No. 25) that if the sum of the digits of a perfect number >6 be divided by 9, the remainder is unity [proved for perfect numbers of Euclid's type by Cataldi,^^ p. 43]. He noted (f. 178) that any divisor of a perfect number is deficient, any multiple abundant. He stated (No. 29) that one or both of 6n=i=l are primes and (No. 30) conversely any prime is of the form 6n=t 1 [Cataldi,^ p. 45, corrects the first statement and proves the second]. He stated (f. 174) that every perfect number is triangular, being 2" (2'' — l)/2.
Martinus^^ gave the first four perfect numbers and remarked that they end alternately in 6 and 8.
Gasper Lax'^^ stated that the perfect numbers end alternately in 6 and 8.
V. Rodulphus Spoletanus^^ was cited by Cataldi,'*^ with the implication of errors on perfect numbers. [Copy not seen.]
Girardus Ruffus^^ stated that every perfect number is even, that most odd numbers are deficient, that, contrary to Jordanus,^^ the odd number 45045 is abundant, and that for n odd 2^* — 1 always leads to a perfect num- ber, citing 7, 31, 127, 511, 2047, 8191 as primes [the fourth and fifth are composite].
Feliciano^^ stated that all perfect numbers end alternately in 6 and 8.
Regius^^ defined a perfect number to be an even number equal to the sum of its aliquot divisors, indicated that 511 and 2047 are composite, gave correctly 33550336 as the fifth perfect number, but said the perfect numbers
^''Caroli Bouilli Samarobrini Liber De Perfectis Numeris (dated 1509 at end), one (ff. 172-180) of 13 tracts in his work, Que hoc volumine continetur: Liber de intellectu, . . . De Numeris Perfectis, . . . , dated on last page, 1510, Paris, ex ofEcina Henrici Stephani. Biography in G. Maupin, Opinions et Curiosit^s touchant la Math., Paris, 1, 1901, 186-94.
"Ars Arithmetica loannis Martini, Silicei: in theoricen & praxim. 1513, 1514. Arithmetica loannis Martini, Scilicei, Paris, 1519.
"Arithmetica speculatiua magistri Gasparis Lax. Paris, 1515, Liber VII, No. 87 (end).
*3De proportione proportionvm dispvtatio, Rome, 1515.
"Divi Severini Boetii Arithmetica, dvobvs discreta hbris, Paris, 1521; ff. 40-44 of the commen- tary by G. Ruffus.
"Libro di Arithmetica & Geometria speculatiua & praticale: Composto per maestro Fran- cesco FeUciano da Lazisio Veronese Intitulato Scala Grimaldelli: Nouamente stampato. Venice, 1526 (p. 3), 1527, 1536 (p. 4), 1545, 1550, 1560, 1570, 1669, Padoua, 1629, Verona, 1563, 1602.
*Vtrivsqve Arithmetices, epitome ex uariis authoribus concinnata per Hvdalrichum Regium. Strasburg, 1536. Lib. I, Cap. VI: De Perfecto. Hvdalrichvs Regius, Vtrivsque. . . ex variis . . . , Friburgi, 1550 [and 1543], Cap. VI, fol. 17-18.
8 History of the Theory of Numbers. [Chap. I
end alternately in 6 and 8. A multiple of an abundant or perfect number is abundant, a divisor of a perfect number is deficient.
Cardan^^ (1501-1576) stated that perfect numbers were to be formed by Euclid's rule and always end with 6 or 8; and that there is one between any two successive powers of ten.
De la Roche-^ stated in effect that 2""^ (2" — 1) is perfect for every odd n, citing in particular 130816 and 2096128, given by n = 9, n = ll. This erroneous law led him to believe that the successive perfect numbers end alternately in 6 and 8.
Noviomagus-^ or Neomagus or Jan Bronckhorst (1494-1570) gave Euclid's rule correctly and stated that among the first 10 numbers, 6 alone is perfect, . . . , among the first 10000 numbers, 6, 28,496, 8128 alone are perfect, etc., etc. [implying falsely that there is one and but one perfect number with any prescribed number of digits]. In Lib. II, Cap. IV, is given the sieve (or crib) of Eratosthenes, with a separate column for the multiples of 3, a separate one for the multiples of 5, etc.
WilUchius^'^ (tl552) listed the first four perfect numbers and stated that to these are to be added a very few others, whose nature is that they end either in 6 or 8.
Michael StifeP^ (1487-1567) stated that all perfect numbers except 6 are multiples of 4, while 4(8-1), 16(32-1), 64(128-1), 256(512-1), etc., to infinity, are perfect [error, Kraft^°]. He later^- repeated the latter error, listing as perfect
2X3, 4X7, 16X31, 64X127, 256X511, 1024X2047,
"& so fort an ohn end." Every perfect munber is triangular.
Peletier^^ (1517-1582) stated (1549, V left; 1554, p. 20) that the perfect numbers end in 6 or 8, that there is a single perfect number between any two successive powers of 10, and (1549, C III left; 1554, pp. 270-1) that 4(8-1), 16(32-1), 64(128-1), 256(511),. . .are perfect. The first two statements were also given later by Peletier.^
^'Hieronimi C. Cardani Medici Mediolanensis, Practica Arithmetice, & Mensurandi singu-
laris. Milan, 1537, 1539; Xiirnberg, 1541, 1542, Cap. 42, de proprietatibus numerorum
mirificis. Opera IV, Lyon, 1663. -*Larismetique & Geometrie de maistre Estienne de la Roche diet Ville Franche, Nouuelle-
ment Imprimee & des fautea corrigee, Lyon, 1538, fol. 2, verso. Ed. 1, 1520. '"De Nvmeris libri dvo .... authore loanne Nouiomago, Paris, 1539, Lib. II, Cap. III.
Reprinted, Cologne, 1544; Deventer, 1551. Edition by G. Frizzo, Verona, 1901, p. 132. '°Iodoci Vvillichii Reselliani, Arithmeticae libri tres, Argentorati, 1540, p. 37. '^Arithmetica Integra, Norimbergae, 1544, ff. 10, 11. "Die Cosa Cbristoffs Rudolffs Die schonen Exempeln der Coss Durch Michael Stifel Gebessert
vnd sehr gemehrt, Konigsperg in Preussen, 1553, Anbang Cap. I, f. 10 verso, f. 11 (f.
27 v.), and 1571. "L'Arithmetiqve de lacqves Peletier dv Mans, departie en quatre Liures, Poitiers, 1549,
1550, 1553. . . . , ff. 77 v, 78 r. Reviie e augmentee par 1' Auteur, Lion, 1554
Troisieme edition, reucue et augmentee, par lean de Tovmes, 1607. "Arithmeticae Practicae methodvs facilis, per Gemmam Frisivm, Medicvm, ac Mathematicum
conscripta .... In eandem loannis Steinii & lacobi Peletarii Annotationes. Antver-
piae, 1581, p. 10.
Chap. I] PERFECT, MULTIPLY PERFECT, AND AmICABLE NUMBERS. 9
Postello^^ stated erroneously that 130816 [ = 256-511] is perfect.
Lodoico Baeza^^ stated that Euchd's rule gives all perfect numbers.
Pierre Forcadel" (tl574) gave 130816 as the fifth perfect number, implying incorrectly that 511 is a prime.
Tartaglia^^ (1506-1559) gave an erroneous [Kraft ^^J list of the first twenty perfect numbers, viz., the expanded forms of 2"~^(2'* — 1), for n = 2 and the successive odd numbers as far as n = 39. He stated that the sums 1+2+4, 1+2+4+8, .. .are alternately prime and composite; and that the perfect numbers end alternately in 6 and 8. The third ''notable prop- erty" mentioned is that any perfect number except 6 yields the remainder 1 when divided by 9.
Robert Recorde^^ (about 1510-1558) stated that all the perfect numbers under 6-10^ are 6, 28, 496, 8128, 130816, 2096128, 33550336, 536854528 [the fifth, sixth, eighth of these are not perfect].
Petrus Ramus^° (1515-1572) stated that in no interval between succes- sive powers of 10 can you find more than one perfect number, while in many intervals you will find none. At the end of Book I (p. 29) of his Arith- meticae libri tres, Paris, 1555, Ramus had stated that 6, 28, 496, 8128 are the only perfect numbers less than lOOpOO.
Franciscus Maurolycus*^ (1494-1575) gave an argument to show that every perfect number is hexagonal and hence triangular.
Peter Bungus^^ (fieoi) gave (1584, pars altera, p. 68) a table of 20 numbers stated erroneously to be the perfect numbers with 24 or fewer digits [the same numbers had been given by Tartaglia^^]. In the editions of 1591, etc., p. 468, the table is extended to include a perfect number of 25 digits, one of 26, one of 27, and one of 28. He stated (1584, pp. 70-71 ; 1591, pp. 471-2) that all perfect numbers end alternately in 6 and 28; employing Euclid's formula, he observed that the product of a power of 2 ending in 4 by a number ending in 7 itself ends in 28, while the product of one ending in 6 by one ending in 1 ends in 6. He verified (1585, pars
^"Theoricae Arithmetices Compendium h Guilielmo Postello, Lutetiae, 1552, a syllabus on one
large sheet of arithmetic definitions. "Nvmerandi Doctrina, Lvtetiae, 1555, fol. 27-28.
''L'Arithmeticqve de P. Forcadel de Beziers, Paris, 1556-7. Livre I (1556), fol. 12 verso. 3*La seconda Parte del General Trattato di Nvmeri, et Misvre di Nicolo Tartagha, Vinegia,
1556, f. 146 verso. L' Arithmetiqve de Nicolas Tartagha Brescian .... Recueillie, & traduite d'ltalien en
FranQois, par Gvillavme Gosselin de Caen, .... Paris, 1578, f. 98 verso, f. 99. '®The Whetstone of witte, whiche is the seconde parte of Arithmetike, London, 1557, eighth
unnumbered page. ^''Petri Rami Scholarum Mathematicarum, Libri unus et triginta, k Lazaro Schonero recog-
niti & emendati, Francofvrti, 1599, Libr. IV (Arith.), p. 127, and Basel, 1578. "Arithmeticorvm hbri dvo, Venetiis, 1575, p. 10; 1580. Published with separate paging, at
end of Opuscula mathematica. *^Mysticae nvmerorvm significationis liber in dvas divisvs partes, R. D. Petro Bongo Canonico
Bergomate avctore. Bergomi. Pars prior, 1583, 1585. Pars altera, 1584. Petri Bungi Bergomatis Numerorum mysteria, Bergomi, 1591, 1599, 1614, Lutetiae Parisio-
rum, 1618, all four with the same text and paging. Classical and biblical citations on
numbers (400 pages on 1, 2, . . , 12). On the 1618 edition, see Font^s, M6m. Acad. So.
Toulouse, (9), 5, 1893, 371-380.
10 History of the Theory of Numbers. [Chap, i
prior, p. 238; 1591, p. 343) for the first seven numbers of his table [two being imperfect, however] that the sum of the digits of a perfect number exceeds by unity a multiple of 9. Every perfect number is triangular (1591, p. 270). Every multiple of a perfect number is abundant, every divisor deficient (1591, p. 464).
Unicornus^^ (1523-1610) cited Bungus and repeated his error that 2"- 1 (2^ — 1) is always perfect for n odd and that all perfect numbers end alternately in 6 and 8.
Cataldi"^ (1548-1626) noted in his Preface that Paciuolo's^^ fourteenth per- fect number 90. . .8 is in fact abundant since it arose from 1+2+4+ • ■ • +2^^ = 134217727, which is divisible by 7,whereas Paciuolo said it was prime. Citing the error of the latter, Bovillus,^° and others, that all perfect num- bers end alternately in 6 and 8, Cataldi observed (p. 42) that the fifth per- fect number is 33550336 and the sixth is 8589869056, from 8191 =2'^- 1 and 131071=2^^ — 1, respectively, proved to be primes (pp. 12-17) by actually trying as possible divisor every prime less than their respective square roots. He gave (pp. 17-22) the corresponding work showing 2^^ — 1 to be prime. He stated (p. 11) that 2'*-! is a prime forn = 2, 3, 5, 7, 13, 17, 19, 23, 29, 31, 37, remarking that the prime n = ll does not yield a perfect number since (p. 5) 2^^ — 1=2047 = 23*89, while it is composite if n is composite. He proved (p. 8) that the perfect numbers given by Euclid's rule end in 6 or 8. He gave (pp. 28-40, 48) a table of all divisors of all even and odd numbers ^ 800, and a table of primes < 750.
Georgius Henischiib^^ (1549-1618) stated that the perfect numbers end alternately in 6 and 8, and that one occurs between any two successive powers of 10. He applied Euclid's formula without restricting the factor 2"—! to primes.
Johan Rudolff von Graff enried"*^ stated that all perfect numbers are given by Euclid's rule, which he applied without restricting 2" — 1 to primes, expressly citing 256X511 as the fifth perfect number. Every perfect number is triangular.
Bachet de Mezirac''^ (1581-1638) gave (f. 102) a lengthy proof of Euclid's theorem that 2'*p is perfect if p = l+2+ . . . +2^* is a prime, but
"De I'arithmetica vniversale del Sig. loseppo Vnicorno, Venetia, 1598, f. 57.
"Trattato de nvmeri perfetti di Pierto Antonio Cataldo, Bologna, 16C3. According to the Preface, this work was composed in 1588. Cataldi founded at Bologna the Academia Erigende, the most ancient known academy of mathematics; his interest in perfect numbers from early youth is shown by the end of the first of his "due lettioni fatte nell' Academia di Perugia" (G. Libri, Hist. Sc. Math, en ItaUe, 2d ed., vol. 4, Halle, 1865, p. 91). G. Wertheim, BibHotheca Math., (3), 3, 1902, 76-83, gave a summary of the Trattato.
"Arithmetica Perfecta et Demonstrata, Georgii Henischiib, Augsburg [1605], 1609, pp. 63-64.
"Arithmeticae Logistica Popularis Librii IIII. Jn welchen der Algorithmus in gantzen Zahlen u. Fracturen . . . . , Bern, 1618, 1619, pp. 236-7.
*^Elementorum arithmeticorum libri XIII auctori D . . . , a Latin manuscript in the Biblio- thfeque de I'lnstitut de France. On the inside of the front cover is a comment on the sale of the manuscript by the son of Bachet to DaUbert, treasurer of France. A general account of the contents of the manuscript was given by Henry, Bull. Bibl. Storia Sc. Mat. e Fis., 12, 1879, pp. 619-641. The present detailed account of Book 4, on perfect numbers, was taken from the manuscript.
Chap. I] PERFECT, MULTIPLY PERFECT, AND AMICABLE NUMBERS. 11
(f. 103, verso) is abundant if p is composite. Every multiple of a perfect or abundant number is abundant, every divisor of a perfect number is deficient (ff. 104 verso, 105). The product of two primes, other than 2X3, is deficient (f. 105 verso). The odd number 945 is abundant, the sum of its ahquot divisors being 975 (f. 107). Commenting (f. Ill verso, f. 112) on the statement of Boethius^ and Cardan^^ that the perfect numbers end alternately in 6 and 8, he stated that the fourth is 8128 and the fifth is 2096128 [an error], the fifth not being 130816 = 256X511, since 511 =7X73.
Jean Leurechon^^ (about 1591-1670) stated that there are only ten perfect numbers between 1 and 10^^, listed them (noting the admirable property that they end alternately in 6 and 8) and gave the twentieth per- fect number. [They are the same as in Tartaglia's^^ list.]
Lantz^^ stated that the perfect numbers are 2(4-1), 4(8-1), 16(32-1), 64(128-1), 256(512-1), 1024(2048-1), etc.
Hugo Sempilius^° or Semple (Scotland, 1594-Madrid, 1654) stated that there are only seven perfect numbers up to 40,000,000; they end alternately in 6 and 8.
Casper Ens^^ stated that there are only seven perfect numbers <4-10'', viz., 6, 28, 496, 8128, 130816, 1996128 [for 2096128], 33550336, and that they end alternately in 6 and 8.
Daniel Schwenter^^ (1585-1636) made the same error as Casper Ens.^^
Erycius Puteanus^^ quoted from Martiano Capella, lib. VII, De Nuptiis Philologiae, to the effect that the perfect number 6 is attributed to Venus; for it is made by the union of the two sexes, that is, from triad, which is male since it is odd, and from diad, which is feminine since it is even. Puteanus said that the perfect numbers in order are 6, 28, 496, 8128, 130816, 2096128, 33550336, and gave all their divisors [implying that 511, 2047, 8191 are primes], and stated that these seven and all the remaining end alternately in 6 and 8. Between any two successive powers of 10 is one perfect number. That they are all triangular adds perfection to the perfect.
Joannes Broscius^"^ or Brocki remarked that there is no perfect number between 10000 and 10000000, contrary to Stifel,^^ Bungus,^^ Sempilius.^" Puteanus,^^ and the author of Selectarum Propositionum Mathematicarum, quas propugnavit, Mussiponti, Anno 1622, Maximilianus Willibaldus, Baro
^^Recreations math^matiques, Pont-^-Mousson, 1624; London, 1633, 1653, 1674 (these three EngUsh editions by Wm. Oughtred), p. 92. The authorship is often attributed to Leurechon's pupil Henry Van Etten, whose name is signed to the dedicatory epistle. Cf. Poggendorff, Handworterbuch, 1863, 2, p. 250 (under C. Mydorge); Bibliotheque des 6crivains de la compagnie de Jesus, par A. de Backer, 2, 1872, 731; Biograpliie Generale, 31, 1872, 10.
"Institutionum Arithmeticarum hbri quatuor h loanne Lantz, Coloniae Agrippinae, 1630, p. 54.
"De Mathematicis Disciphnis hbri Duodecim, Antverpiae, 1635, Lib. 2, Cap. 3, N. 10, p. 46. There is (pp. 263-5) an index of writers on geometry and one for arithmetic.
"Thaumaturgus Math., Munich, 1636, p. 101; Coloniae. 1636, 1651; Venice, 1706.
"Dehciae Physico-Mathematicae oder Mathemat: vnd Philosophische Erquickstunden, part I (574 pp.), Numberg, 1636, p. 108.
"De Bissexto Liber: nova temporis facula qua intercalandi arcana .... Lovanii, 1637; 1640, pp. 103-7. Reproduced by J. G. Graevius, Thesaurus Antiquitatum Romanarum (12 vols., 1694-9), Lugduni Batavorum, vol. 8.
12 History of the Theory of Numbers. [Chap, i
in Waldpurg. WTiile they considered 511X256 and 2047X1024 as perfect, 511 has the factor 7, and (as pointed out to him by Stanislaus Pudlowski) 2047 has the factor 23. Broscius stated that
2^-1 has the factor 3 5 7 11 13 17 19 23 29 31 if n is a multiple of 2 4 3 10 12 8 18 11 28 5.
The contents of the second dissertation are given below under the date 1652.
Ren^ Descartes,^^ in a letter to Mersenne, November 15, 1638, thought he could prove that every even perfect number is of Euclid's type, and that every odd perfect number must have the form ps^, where p is a prime. He saw no reason why an odd perfect number may not exist. For p = 22021, s = 3'7-ll-13, ps^ would be perfect if p were prime [but p = 61-19^]. In a letter to Frenicle, January 9, 1639, Oeuvres, 2, p. 476, he expressed his belief that an odd perfect number could be found by replacing 7, 11, 13 in s by other values.
Fermat^^ stated that he possessed a method of solving all questions relating to aliquot parts. Citing this remark, Frenicle^' challenged Fermat to find a perfect number of 20 or 21 digits. Fermat^^ replied that there is none with 20 or 21 digits, contrary to the opinion of those who believe that there is a perfect number between any two consecutive powers of 10.
Fermat,^^ in a letter to Mersenne, June (?), 1640, stated three proposi- tions which he had proved not without considerable trouble and which he called the basis of the discovery of perfect numbers: if n is composite, 2" — 1 is composite; if n is a prime, 2" — 2 is divisible by 2n, and 2" — 1 is divisible by no prime other than those of the form 2kn-\-l [cf . Euler^']. For example, 2"-l = 23-89, 2^^-l has the factor 223. Also 2"^^-! has the factor 47, Oeuvres, 2, p. 210, lett-er to Frenicle, October 18, 1640.
Mersenne^° (1588-1648) stated that, of the 28 numbers* exhibited by
"De numeris perfectis disceptatio qua ostenditur a decern millibus ad centies centena millia, nullum esse perfectum numenim atque ideo ab unitate usque ad centies centena millia quatuor tantum perfectos numerari, Amsterdam, 1638. Reproduced as the first (pp. 115-120) of two dissertations on perfect numbers, they forming pp. 111-174 of Apologia pro Aristotele & Evchde, contra Petrvm Ramvm, & aUos. Addititiae sunt Dvae Discep- tationes de Nvmeris Perfectis. Authore loanne Broscio, Dantiaci, 1652 (with a some- what different title, Amsterdam, 1699).
"Oeuvres de Descartes, II, Paris, 1898, p. 429.
s«Oeuvres de Fermat, 2, Paris, 1894, p. 176; letter to Mersenne, Dec. 26, 1638.
*'Oeuvres de Fermat, 2, p. 185; letter to Mersenne, March, 1640.
osQeuvres, 2, p. 194; letter to Mersenne, May (?), 1640.
"Oeuvres de Fermat, 2, pp. 198-9; Varia Opera Math. d. Petri de Fermat, Tolosae, 1679, p. 177; Precis des Oeuvres math, de P. Fermat et de 1' Arithmdtique de Diophante, par E. Brassinne, M6m. Ac. Imp. Sc. Toulouse, (4), 3, 1853, 149-150.
•°F. Marini Mersenni minimi Cogitata Physico Mathematica, Parisiis, 1644. Praefatio Generahs, No. 19. C. Henry (Bull. Bibl. Storia Sc. Mat. e Fis., 12, 1879, 524-6) beheved that these remarks were taken from letters from Fermat and Frenicle, and that Mersenne had no proof. A similar opinion was expressed by W. W. Rouse Ball, Messenger Math., 21, 1892, 39 (121). On documents relating to Mersenne see Tinterm^diaire des math., 2, 1895, 6; 8, 1901, 105; 9, 1902, 101, 297; 10, 1903, 184. Cf. Lucas."*
*Only 24 were given by Bungus. While his table has 28 lines, one for each number of digits, there are no entry of numbers of 5, 11, 17, 23 digits.
Chap. I] PERFECT, MULTIPLY PERFECT, AND AMICABLE NUMBERS. 13
Bungus,^^ chap. 28, as perfect numbers, 20 are imperfect and only 8 are perfect :
6, 28, 496, 8128, 23550336 [for 33. . .], 8589869056, 137,438691328, 2305843008139952128,
which occur at the lines marked 1, 2, 3, 4, 8, 10, 12 and 29 [for 19] of Bungus' table [indicating the number of digits]. Perfect numbers are so rare that only eleven are known, that is, three different from those of Bungus; norf is there any perfect number other than those eight, unless you should surpass the exponent 62 in 1+2+2^+ .. . The ninth perfect number is the power with the exponent 68 less 1; the tenth, the power 128 less 1 ; the eleventh, the power 258 less l,i.e., the power 257, decreased by unity, multiplied by the power 256. [The first 11 perfect numbers are thus said to be 2"-'(2"-l) for n = 2, 3, 5, 7, 13, 17, 19, 31, 67, 127, 257, in error as to n = 61, 67, 89, 107 at least.] He who would find 11 others will know that all analysis up to the present will have been exceeded, and will remember in the meantime that there is no perfect number from the power 17000 to 32000, and no interval of powers can be assigned so great but that it can be given without perfect numbers. For example, if the exponent be 1050000, there is no larger exponent n up to 2090000 for which 2" — 1 is a prime. One of the greatest difficulties in mathematics is to exhibit a prescribed number of perfect numbers; and to tell if a given number of 15 or 20 digits is prime or not, all time would not suffice for the test, what- ever use is made of what is already known.
Mersenne" stated that 2^ — 1 is a prime if p is a prime which exceeds by 3, or by a smaller number, a power of 2 with an even exponent. Thus 2^-1 is a prime since 7 = 2^3; again, since 67 = 3+2*^, 2^^ + 1 = 1... 7 [for 2®^ — 1] is a prime and leads to a perfect number [error corrected by Cole^^^]. Understand this only of primes 2^ — 1. Wherefore this property does not belong to the prime 5, but to 3, 7, 31, 127, 8191, 131071, 524287, 2147483647, and all such. Numbers expressible as the sum or difference of two squares in several ways are composite, as 65 = 1+64 = 16+49. As he speaks of Frenicle's knowledge of numbers, at least part of his results are doubtless due to the latter.
In 1652, J. Broscius (Apologia,^^ p. 121) observed that while perfect numbers were deduced by Euclid from geometrical progressions, they may be derived from arithmetical progressions:
6 = 1+2+3, 28 = 1+2+3+4+5+6+7, 496 = 1+2+3+ ... +31.
fNeque enim vllus est alius perfectus ab illis octo, nisi superes exponentem numerum 62, progressionis duplae ab 1 incipientis. Nonus enim perfectus est potestas exponentis 68, minus 1. Decimus, potestas exponentis 128, minus 1. Vndecimus denique, potestas 258, minus 1, hoc est potestas 257, unitate decurtata, multiplicata per potestatem 256.
*T. Marini Mersenni Novarvm Observationvm Physico-Mathematicarum^ Tomvs III, Parisiis, 1647, Cap. 21, p. 182. The Reflectiones Physico-Math. begin with p. 63; Cap. 21 is quoted in Oeuvres de Fennat, 4, 1912, pp. 67-8.
14 History of the Theory of Numbers. [Chap, i
He stated that while perfect numbers end with 6 or 28, the proof by Bungus*' does not show that they end alternately with 6 and 28, since Bungus included imperfect as well as perfect numbers. The numbers 130816 and 2096128, cited as perfect by Puteanus,^^ are abundant. After giving a table of the expanded form of 2" forn = 0, 1, . . . , 100, Broscius (p. 130, seq.) gave a table of the prime divisors of 2" — 1 (n = 1, . . . , 100), but showing no prime factor when n is any one of the primes, other than 11 and 23, less than 100. For n = ll, the factors are 23, 89; for n = 23, the factor 47 is given. Thus omitting unity, there remain only 23 numbers out of the first hundred which can possibly generate perfect numbers. Contrary to Car- dan,^^ but in accord with Bungus,^^ there is (p. 135) no perfect number between 10* and 10\ Of Bungus' 24 numbers, only 10 are perfect (pp. 135-140): those with 1, 2, 3, 4, 8, 10, 12, 18, 19, 22 digits, and given by 2'-i(2'*-l) for n = 2, 3, 5, 7, 13, 17, 19, 29, 31, 37, respectively. The pri- maUty of the last three was taken on the authority of unnamed predecessors.
There are only 21 abundant numbers between 10 and 100, and all of them are even; the only odd abundant number <1000 is 945, the sum of whose aliquot di\isors is 975 (p. 146). The statement by Lucas, Th^orie des nombres, 1, Paris, 1891, p. 380, Ex. 5, that 3^-5-79 [deficient] is the smallest abundant number is probably a misprint for 945 = 3^-5-7. This error is repeated in Encyclopedic Sc. Math., I, 3, Fas. 1, p. 56.
Johann Jacob Heinlin^- (1588-1660) stated that the only perfect num- bers <4-10' are 6, 28, 496, 8128, 130816, 2096128, 33550336, and that all perfect numbers end alternately in 6 and 8.
Andrea Tacquet^^ (Antwerp, 1612-1660) stated (p. 86) that Euclid's rule gives all perfect numbers. Referring to the 11 numbers given as perfect by Mersenne,^^ Tacquet said that the reason why not more have been found so far is the greatness of the numbers 2^ — 1 and the vast labor of testing their primaUty.
Frenicle^ stated in 1657 that EucUd's formula gives all the even perfect numbers, and that the odd perfect numbers, if such exist, are of the form p/c^, where p is a prime of the form 4n+l [cf. Euler^^].
Frans van Schooten^^ (the younger, 1615-1660) proposed to Fermat that he prove or disprove the existence of perfect numbers not of Euclid's type.
Joh. A. Leuneschlos^^ remarked that the infinite multitude of numbers contains only ten perfect numbers; he who will find ten others will know
'*Joh. Jacobi Heinlini, Synopsis Math, praecipuas totius math .... Tubmgae, 1653. Synopsis
Math. Universalis, ed. Ill, Tubingae, 1679, p. 6. English translation of last by Venterus
Mandey, London, 1709, p. 5. "Arithmeticae Theoria et Praxis, Lovanii, 1656 and 1682 (same paging), [1664, 1704]. Hia
opera math., Antwerpiae, 1669, does not contain the Arithmetic. "Correspondence of Chr. Huygens, No. 389; Oeuvres de Fermat, 3, Paris, 1896, p. 567. "Oeuvres de Huygens, II, Correspondence, No. 378, letter from Schooten to J. Wallis, Mar. 18,
1658. Oeuvres de Fermat, 3, Paris, 1896, p. 558. "Mille de Quantitate Paradoxa Sive Admiranda, Heildelbergae, 1658, p. 11, XLVI, XLVII.
Chap. I] PERFECT, MULTIPLY PERFECT, AND AmICABLE NUMBERS. 15
that he has surpassed all analysis up to the present. Goldbach" called Euler's attention to these remarks and stated that they were probably taken from Mersenne, the true sense not being followed.
Wm. Leybourn^^ hsted as the first ten perfect numbers and the twentieth those which occur in the table of Bungus.^^ "The number 6 hath an emi- nent Property, for his parts are equal to himself."
Samuel Tennulius, in his notes (pp. 130-1) on lamblicus,^ 1668, stated that the perfect numbers end alternately in 6 and 8, and included 130816 = 256-511 and 2096128 = 1024-2047 among the perfect numbers.
Tassius®^ stated that all perfect numbers end in 6 or 8. Any multiple of a perfect or abundant number is abundant, any divisor of a perfect number is deficient. He gave as the first eight known perfect numbers the first eight listed by Mersenne.^"
Joh. Wilh. Pauli^° (Philiatrus) noted that if 2" — 1 is a prime, n is, but not conversely. For n = 2, 3, 5, 7, 13, 17, 19, 2"-l is a prime; but 2^^-l is divisible by 23, 2^^ — 1 by 47, and 2*^ — 1 by 83, the three divisors being 2n+l.
G. W. Leibniz'^^ quoted in 1679 the facts stated by Pauli and set himself the problem to find the basis of these facts. Returning about five years later to the subject of perfect numbers, Leibniz implied incorrectly that 2^^ — 1 is a prime if and only if p is.
Jean Prestet^^ (tl690) stated that the fifth, . . . , ninth perfect numbers are
23550336 [for 33. . .], 8589869056, 137438691328, 238584300813952128 [for
2305. . .39952128], 2''^-2^'\
[Hence 2'*-^(2'*-l) for 7i = 13, 17, 19, 31, 257. The numerical errors were noted by E. Lucas,i24 p 7g4 j
Jacques Ozanam^^ (1640-1717) stated that there is an infinitude of perfect numbers and that all are given by Euclid's rule, which is to be applied only when the odd factor is a prime.
Charles de Neuveglise^^ proved that the products 3-4, . . ., 8-9 of two consecutive numbers are abundant. All multiples of 6 or an abundant number are abundant.
"Correspondence Math. Phy8.,ed.,Fus8, 1, 1843; letters to Euler, Oct. 7, 1752 (p. 584), Nov. 18
(p. 593). '^Arithmetical Recreations; or Enchriridion of Arithmetical Questions both Delightful and
Profitable, London, 1667, p. 143. "Arithmeticae Empiricae Compendium, Johannis Adolfi Tassii. Ex recensione Henrici Siveri,
Hamburgi, 1673, pp. 13, 14. ^"De nvmiero perfecto, Leipzig, 1678, Magister-disputation. "Manuscript in the Hannover Library. Cf. D. Mahnke, Bibhotheca Math., (3), 13, 1912-3,
53-4, 260. "Nouveaux elemens des Mathematiques, ou Principes generaux de toutes les sciences, Paris,
1689, I, 154-5. "Recreations mathematiques et physiques, Paris and Amsterdam, 2 vols., 1696, I, 14, 15. "Traits methodique et abreg6 de toutes les mathematiques, Trevoux, 1700, tome 2 (L'arith-
m^tique ou Science des nombres), 241-8.
16 History of the Theory of Numbers. [Chap, i
John Harris,"^ D. D., F. R. S., stated that there are but ten perfect numbers between unity and one million of millions.
John Hiir^ stated that there are only nine perfect numbers up to a hundred thousand million. He gave (pp. 147-9) a table of values of 2" forn = l,. . ., 144.
Christian Wolf" (1679-1754) discussed perfect numbers of the form y"x [where x, y are primes]. The sum of its aliquot parts is
l+y+ . . . +i/"+a:+?/x+ . . . +i/""'x, which must equal y'^x. Thus
x = {l-\-y+ . . . +2/")M d = y^-l-y- . . . -7/""^
He stated* that x is an integer only when d = l, and that this requires y = 2, x = l +2+ . . . +2". Then if this x is a prime, 2"x is a perfect number. This is said to be the case forn = 8 and n = 10, since 2^ — 1 = 51 1 and 2^' — 1 = 2047 are primes, errors pointed out bj^ Euler.^^ A. G. Kastner^^ was not satisfied with the argument leading to the conclusion y = 2. Jacques Ozanam^^ listed as perfect numbers
2(4-1), 4(8-1), 16(32-1), 64(128-1), 256(512-1), 1024(2048-1),. . .
without expUcit mention of the condition that the final factor shall be prime, and stated that perfect numbers are rare, only ten being known, and all end in 6 and 8 alternately. [Criticisms by Montucla,®^ Gruson.-^°°]
Johann Georg Liebnecht^° said there were scarcely 5 or 6 perfect num- bers up to 4.10"; they always end alternately in 6 and 8.
Alexander ]Malcolm^^ observed that it is not yet proved that there is no perfect number not in Euclid's set. He stated that, if pA is a perfect number, where p is a prime, and if M<p and M is not a factor of A, then MM is an abundant number [probably a misprint for MA, as the condi- tions are satisfied when p = 7, .4=4, M = 5, and MA =20 is abundant, while Af^ = 25 is deficient].
Christian Wolf^- made the same error as Casper Ens.^^
^'Lexicon Technicum, or an Universal English Dictionarj' of Arts and Sciences, vol. I, London, 1704; ed. 5, vol. 2, London, 1736.
"Arithmetik, London, ed. 2, 1716, p. 3.
^'Elementa Matheseos Universae, Halae Magdeburgicae, vol. I, 1730 and 1742, pp. 383-^, of the five volume editions [first printed 1713-41]; vol. I, 1717, 315-6, of the two volume edition. Quoted, with other errors, Ladies' Diary, 1733, Q. 166; Leybourn's ed., 1, 1817, 218; Button's ed., 2, 1775, 10; Diarian Repository, by Soc. Math., 1774, 289.
*"Jam ut X sit numerus integer, nee in casu speciali, si y per numerum explicetur, numerus partium aliquotarum diversus sit a numero earundem in formula general!; necesse est ut d = l."
"Math. Anfangsgrlinde, I, 2 (Fortsetzung der Rechnenkunst, ed. 2, 1801, 546-8).
"Recreations math., new ed. of 4 vols., 1723, 1724, 1735, etc., I, 29-30.
'"Grund-Satze der gesammten Math. Wiss. u. Lehren, Giessen u. Franckfurt, 1724, p. 21.
*iA new system of arithmetik, theoretical & practical, London, 1730, p. 394.
"Mathematisches Lexicon, I, 1734 (under Vollkommen Zahl).
Chap. Il PERFECT, MULTIPLY PERFECT, AND AmICABLE NUMBERS. 17
Leonard Euler^^ (1707-1783) noted that 2'' — 1 may be composite for n a prime; for instance, 2^' — 1 = 23-89, contrary to Wolf.'^^ If n = 4m — 1 and 8m — 1 are primes, 2" — 1 has the factor 8m — 1, so that 2^-1 is com- posite for n = ll, 23, 83, 131, 179, 191, 239, etc. [Proof by Lucas.^^sj Furthermore, 2^^-l has the factor 223, 2^^-l the factor 431, 22^-1 the factor 1103, 2"^ — 1 the factor 439, etc. ''However, I venture to assert that aside from the cases noted, every prime less than 50, and indeed than 100, makes 2"~^(2" — 1) a perfect number, whence the eleven values 1, 2, 3, 5, 7, 13, 17, 19, 31, 41, 47 of n yield perfect numbers. I derived these results from the elegant theorem, of whose truth I am certain, although I have no proof: aJ^ — V is divisible by the prime n+1, if neither a nor h is." [For later proofs by Euler, see Chapter III on Fermat's theorem.] Euler's errors as to n = 41 and 47 were corrected by Winsheim,®^ Euler^^ himself, and Plana.i^o
Michael Gottlieb Hansch^ stated that 2^*— 1 is a prime if n is any of the twenty- two primes ^79 [error, Winsheim,^^ Kraft^^].
George Wolfgang Kraft^^ corrected Stifel's^^ error that 511-256 is per- fect and the error of Ozanam (Elementis algebrae, p. 290) that the sum of all the divisors of 2*" is a prime, by noting that the sum forn = 2 is 511 = 7-73 ; and n6ted that false perfect numbers were listed by Ozanam.'^^ Kraft presented (pp. 9-11) an incomplete proof, communicated to him by Tobias Maier [cf. Fontana^^^], that every perfect number is of Euclid's type. Let 1, m, n, . . .,p, A,. . .be the aliquot parts of any perfect number pA, where p and A are the middle factors [as 4 and 7 jn 28]. Then
q r n m
Solving for A, he stated that the denominator must be unity, whence 'p = 2q/D, D = q — l—q/r — q/n — q/m. Again, D = l, whence g = 2r/D', D' = r — l—r/n—r/m. From I>' = 1, r = 2n/I)", D" = n — l—n/m. From D" = l, n = 2m/(m — 1), m — 1 = 1, m = 2, n = 4, r = 8, etc. Thus the aliquot parts up to the middle must be the successive powers of 2, and A must be a prime, since otherwise there would be new divisors. For p = 2"~\ we get A =2" — 1. Kraft observed that if we drop from Tartaglia's^^ list of 20 numbers those shown to be imperfect by Euler's^^ results, we have left only eight perfect numbers 2"-^(2"-l) for n^39, viz., those for n = 2, 3, 5, 7, 13, 17, 19, 31. For these, other than the first, as well as for the false ones of Tartaglia, if we add the digits, then add the digits of that sum, etc., we finally get unity (p. 14) [proof by WantzeP^^]. All perfect numbers end in 6 or 28.
*3Comm. Acad. Petropol., 6, 1738, ad annos 1732-3, p. 103. Commentationes Arithmeticae
Collectae, I, Petropoli, 1849, p. 2. ^Epistola ad mathematicos de theoria arithmetices nouis a se inuentis aucta, Vindobonae
[Vienna], 1739. "De numeris perfectis, Comm. Acad. Petrop., 7, 1740, ad annos 1734-5, 7-14.
18 History of the Theory of Numbers. [Chap, i
Johann Christoph Heilbronner^^ stated that the perfect numbers up to 4-10' are 6, 28, 496, 8128, 130816,2096128. "The fathers of the early church and many wTiters always held this number 6 in high esteem. God com- pleted the creation in 6 days and since all things created by Him came out perfect, he wished the work of creation completed according to the number 6 as being a perfect number."
L. Euler" deduced from Fermat's theorem, which he here proved by use of the binomial theorem, the result* that, if m is a prime, 2"* — 1, when composite, has no prime factors other than those of the form wn+l.
J. Landen^^ noted that 196 is the least number 4a;'*, where x is prime, the sum of whose ahquot parts exceeds the number by 7.
L. Euler^^ gave a table of the prime factors of 2" — 1 for n^37.
C. N. de Winsheim^° noted that 2^'^ — 1 has the factor 2351, and stated that 2" — 1 is a prime for n = 2, 3, 5, 7, 13, 17, 19, 31, composite for the remaining n<48, but was doubtful as to n = 41, thus reducing the Hst of perfect numbers given by Euler^ by one or perhaps two. He suspected that n = 41 leads to an imperfect number since it was excluded by the acute Mersenne,^° who gave instead 2^^(2^" — 1) as the ninth perfect number. He remarked that the basis of Mersenne's assertion is doubtless to be found in the stupendous genius of Mersenne which perhaps recognized more truths than he could demonstrate. He discussed the error of Hansch^ that 2" — ! is a prime if n is a prime ^ 79.
G. W. Kraft^^ considered perfect numbers AP, where P is a prime [not dividing A]. Thus a{P-\-l)=2AP, where a is the sum of all the divisors of A. Hence a/ {2 A— a) equals the prime P. Let 2A— a = l, a property holding for A =2"". Then P = 2"'+^ — 1 and the resulting numbers are of Euchd's type.
L. Euler,^- in a letter to Goldbach, October 28, 1752, stated that he knew only seven perfect numbers, viz., 2p~^(2^ — 1) for p = 2, 3, 5, 7, 13, 17, 19, and was uncertain whether 2^^ — 1 is prime or not (a factor is necessarily of the form 64n+l and none are <2000).
^^Historia matheseos universae. Accedit recensio elementorum compendiorum et openim math, atque historia arithmetices ad nostra tempora, Lipsiae, 1742, 755-6. There is a 63-page Ust of arithmetics of the 16th century.
«^^ovi Comm. Ac. Petrop., 1, 1747-8, 20; Comm. .\rith., I, 56, §39.
*We may simpUfy the proof by using the fact that 2 belongs to an e.xponent e modulo p (p a prime) such that e divides p — 1. For, if p is a factor of 2'"— 1, m is a multiple of e, whence e equals the prime m. Thus p — 1 =n7«. If we take m>2, we see that n is even since p is odd and conclude with Fermat^' that, if m is an odd prime, 2"»— 1 is divisible by no primes other than those of the form 2km + l.
"•Ladies' Diary, 1748, Question 305. The Diarian Repository, Collection of all the mathe- matical questions from the Ladies' Diary, 1704-1760, by a society of mathematicians, London, 1774, 509. Button's The Diarian Miscellany (from Ladies' Diarj-, 1704-1773), London, 1775, vol. 2, 271. Leyboiu-n's Math. Quest, proposed in Ladies' D., 2, 1817, 9-10.
"Opuscula varii argumenti, Berlin, 2, 1750, 25; Comm. Arith., 1, 1849, 104.
•"Novi Comm. Ac. Petrop., 2, 1751, ad annum 1749, mem., 68-99.
"/bid., mem., 112-3.
•^Corresp. Math. Phys. (ed., Fuss), I, 1843, 590, 597-8.
Chap. I] PERFECT, MULTIPLY PERFECT, AND AmICABLE NUMBERS. 19
G. W. Kraft^^ stated (p. 114) that Euler had communicated to him pri- vately in 1741 the fact that 2*^-1 is divisible by 2351. He stated (p. 121) that if 2^ — 1 is composite {p being prime), it has a factor of the form 2q'^p + l, where g is a prime [including unity], using as illustrations the factorizations noted by Euler. ^^ Of the numbers 2" — 1, n a prime ^71, stated to be prime by Hansch,^^ six are composite, while the cases 53, . . . , 71 are in doubt (p. 115).
A. Saverien^^ repeated the remarks by Ens^^ without reference.
L. Euler^^ stated in a letter to Bernoulli that he had verified that 2^^ — 1 is a prime by examining the primes up to 46339 which are contained in the possible forms 248n+l and 248n+63 of divisors.
L. Euler^^ gave a prime factor of 2"=»= 1 for various values of n, but no new cases 2^—1 with n a prime.
L. Euler,^^ in a posthumous paper, proved that every even perfect number is of Euclid's type. Let o = 2"6 be perfect, where b is odd. Let B denote the sum of the divisors of b. The sum {2'*^^ — l)B of the divisors of a must equal 2a. Thus 6/5 = (2"+^-l)/2"+\ a fraction in its lowest terms. Hence 6 = (2^+^ — 1 )c. If c = l, 6 = 2"'*'^ — 1 must be a prime since the sum of its divisors is 5 = 2""^^ whence Euclid's formula. If c>l, the sum B of the divisors of b is not less than 6+2""''^ — 1+c+l; hence
^^2"+nc+l) 2"+' 6= h '^2"+^-l'
contrary to the earlier equation. The proof given in another posthumous paper by Euler^^ is not complete.
L. Euler^^ proved that any odd perfect number must be of the form y.4x+ip2^ where r is a prime of the form 4nH-l [Frenicle®^]. Express it as a product ABC. . . of powers of distinct primes. Denote by a, b, c, . . .the sums of the divisors oi A, B,C,. . ., respectively. Then abc . . . = 2 ABC .... Thus one of the numbers a, b, . . . , say a, is the double of an odd number, and the remaining ones are odd. Thus B, C,. . . are even powers of primes, while A =r*^"^^ In particular, no odd perfect number has the form 4n+3. Amplifications of this proof have been given by Lionnet,^^^ Stern, ^^'^ Syl- vester, ^^^ Lucas. ^" See also Liouville^° in Chapter X.
Montucla^^ remarked that Euclid's rule does not give as many perfect numbers as believed by various writers; the one often cited [Paciuolo^®] as the fourteenth perfect number is imperfect; the rule by Ozanam^^ is false since 511 and 2047 are not primes.
"Novi Comm. Ac. Petrop., 3, 1753, ad annos 1750-1.
"Dictionnaire universel de math, et physique, two vols., Paris, 1753, vol. 2, p. 216. »^Nouv. Mim. Acad. BerUn, ann6e 1772, hist., 1774, p. 35; Euler, Comm. Arith., 1, 1849, 584. "Opusc. anal., 1, 1773, 242; Comm. Arith., 2, p. 8.
"De numeris amicabihbus, Comm. Arith., 2, 1849, 630; Opera postuma, 1, 1862, 88. '^Tractatus de numerorum doctrina, Comm. Arith., 2, 514; Opera postuma, 1, 14-15. "Recreations math, et physiques par Ozanam, nouvelle 6d. par M., Paris, 1, 1778, 1790, p. 33. Engl, transl. by C. Hutton, London, 1803, p. 35.
/
20 History of the Theory of Numbers. [Chap. I
Johann Philipp Griison^^'' made the same criticism of Ozanam"^ and noted that, if 2"x is perfect and x is an odd prime,
1+2+ . . .+2'' = 2'*x-a:-2x-. . .-2'*-^x = x.
M. Fontana^"^ noted that the theorem that all perfect numbers are triangular is due to Maurolycus^^ and not to T. Maier (cf. Kraft^^).
Thomas Taylor^"- stated that only eight perfect numbers have been found so far [the 8 listed are those of Mersenne^^j.
J. Struve^^^ considered abundant numbers which are products ahc of three distinct primes in ascending order; thus
ob+o+M-l 2 ^ .-
— ; ; >C, >C + 1.
ah-a-h-1 ' i_i_l_jL
a h ab
The case a^3 is easily excluded, also a = 2, 6^5 [except 2-5'7]. For a = 2, 6 = 3, c any prime > 3, 6c is abundant. Next, abed is abundant if
^"^' >d+i.
a6c — (a6+ac+6c+a+6+c+l)'
For a = 2, 6 = 3, c = 5 or 7, and for a = 2, 6 = 5, c = 7, abed is abundant for any prime d [>c]. Of the numbers ^ 1000, 52 are abundant.
J. Westerberg^*^ gave the factors of 2"='=1 for n = l,..., 32, and of 10''±l,n = l,..., 15.
O. Terquem^°^ Usted 2*^-1 and 2*^-1 as primes.
L. WantzeP"® proved the remark of Kraft*^ that if A^i be the sum of the digits of a perfect number N>6 [of Euclid's type], and N2 the sum of the digits of A^i, etc., a certain iV, is unity. Since iV=l(mod 9), each Ni=l (mod 9), while the NiS decrease.
V. A. Lebesgue^°^ stated that he had a proof that there is no odd perfect number with fewer than four distinct prime factors. For an even perfect number 2"?/ V . . . ,
y'^" ■ ■ • +prrY = (1 +y+ ■ ■ ■ +y') d +^+ • • • +^') ■ • • »
""Enthiillte Zaubereyen und Geheimnisse der Arithmetik, erster Theil, Berlin, 1796, p. 85, and
Zusatz (end of Theil I). »<»Memorie dell' Istituto Nazionale Ital., mat., 2, pt. 1, 1808, 285-6. '°*The elements of a new arithmetical notation and of a new arithmetic of infinites, with an
appendix .... of perfect, amicable and other numbers no less remarkable than novel,
London, 1823, 131. ^''Ueber die so gennannten numeri abundantes oder die Ueberfluss mit sich fiihrenden Zahlen,
besonders im ersten Tausend unsrer Zahlen, Altona, 1827, 20 pp. *'**De factoribus numerorum compositorum dignoscendis, Disquisitio Acad. CaroUna, Lundae,
1838. In the volume, Meditationum Math publice defendent C. J. D. Hill, Pt. II,
1831. i^Nouv. Ann. Math., 3, 1844. 219 (cf. 553). ^<*Ibid., p. 337. i"76id., 552-3.
Chap. I] PERFECT, MULTIPLY Perfect, and Amicable Numbers. 21
the impossibility of which is evident when the exponents j3, 7, . . . are other than 1, 0, 0, . . ., a case giving Euclid's solution [cf. Desboves^^'].
C. G. Reuschle^^* gave in his table C the exponent to which 2 belongs modulo p, for each prime p<5000. Thus 2" — 1 has the factor 1399 for n = 233, the factor 2687 forn = 79, and 3391 for n = 113 [as stated exphcitly by Le Lasseur^^^'^^^]. ^iso 23514513 for n = 47, 1433 for w = 179, and 1913 for n = 239. In the addition (p. 22) to Table A, he gave the prime factors of 2^* — 1 for various n's to 156, 37 being the least n for which the decomposition is not given completely, while 41 is the least n for which no factor is known. For 34 errata in Table C, see Cunningham^^° of Ch. VII.
F. Landry^^^ gave a new proof that 2^^ — 1 is a prime.
Jean Plana^^° gave (p. 130) the factorization into two primes:
2*^-1 = 13367X 164511353.
His statement (p. 141) that 2^^ — 1 has no factor < 50033 was corrected by Landry^^^ (quoted by Lucas, "^ p. 280) and Gerardin."'
Giov. Nocco^" showed that an odd perfect number has at least three distinct prime factors. For, if a"*6'* is perfect,
2a- = V-T^' 6" = ^ -^,
0—1 a— 1
whence
^ ^ Q^""^^ _(a-l)b"+l 2(5-1)" 2(6 -l)a"»" 6"+^-l '
a+fe(a6"+26"-'+2)=2+6(26"+2a6"-^).
But the minunum values of a, h are 3, 5. Thus 6(a— 2)>2a — 2,
a6''-26" = 6"-^-6(a-2)>6'*-^(2a-2), a6'»+26"-'>26"+2a6''-\
contrary to the earlier equation. In attempting to prove that every even perfect number 2'"6Vd' ... is of EucUd's type, he stated without proof that
2-+16V. . . =(2"'+^-l)J5C. . ., B= \ /, C = - -,.. .
0 — 1 c — 1
require that 2"*+^ = B, 6" = 2^"+^ - 1 , d' = C, . . . (the first two of which results yield Euclid's formula).
F. Landry^^^ stated (p. 8) that he possessed the complete decomposi- tion of 2"±l(n^64) except for 2^^±1, 2«Hl, and gave (pp. 10-11) the factors of 2^^-l and of 2"+l for n = 65, 66, 69, 75, 90, 105.
"^Mathematische Abhandlung, enthaltend neue Zahlentheoretische Tabellen sammt einer dieselben betreflfenden Correspondenz mit dem verewigten C. G. J. Jacobi. Prog., Stutt- gart, 1856, 61 pp. Described by Kummer, Jour, fur Math., 53, 1857, 379.
^°'Proc6des nouveaux pour demontrer que le nonabre 2147483647 est premier. Paris, 1859. Reprinted in SpLinx-Oedipe, Nancy, 1909, 6-9.
""Mem. Reale Ac. Sc. Torino, (2), 20, 1863, dated Nov. 20, 1859.
'"Alcune teorie su'numeri pari, impari, e perfetti, Lecce, 1863.
"^Aux math^maticiens de toutes les parties du monde: communicatidn but la decomposition des nombres en leurs facteurs simples, Paris, 1867, 12 pp.
22 History of the Theory of Numbers. [Chap. I
F. Landry"^ soon published his table. It includes the entries (quoted
byLucas^2o.i22).
2«-l=431-9719-2099863, 2*^-1=23514513.13264529, 253-1 = 6361.69431-20394401, 2^^-1 = 179951.3203431780337,
the least factors of the first two of which had been given by Euler.^' •' This table was republished by Lucas^-^ (p. 239), who stated that only three entries remain in doubt: 2^^ — 1, (2^^ + l)/3, 2^*+l, each being conjectured a prime by Landry. The second was believed to be prime by Kraitchik.^^^" Landr>''s factors of 2"+l, for 28^n^64 were quoted elsewhere."^''
Jules Carvallo^^* announced that he had a proof that there exists no odd perfect number. Without indication of proof, he stated that an odd per- fect number must be a square and that the ratio of the sum of the divisors of an odd square to itself cannot be 2. The first statement was abandoned in his published erroneous proof, ^^^ while the second follows at once from the fact that, when p is an odd prime, the sum of the 2n+l divisors, each odd, of p^" is odd.
E. Lucas^^^ stated that long calculations of his indicated that 2°^ — 1 and 2^^ - 1 are composite [cf . Cole,^" Powers^^^]. See Lucas-° of Ch. XVII.
E. Lucas^^^ stated that 2^^ — 1 and 2^^^ — 1 are primes.
E. Catalan^^^ remarked that, if we admit the last statement, and note that 2^ — 1, 2^ — 1, 2^ — 1 are primes, we may state empirically that, up to a certain limit, if 2" — 1 is a prime p, then 2^ — 1 is a prime g, 2^ — 1 is a prime, etc. [cf. Catalan^^^].
G. de Longchamps^^'^ suggested that the composition of 2"±1 might be obtained by continued multiplications, made by simple displacements from right to left, of the primes written to the base 2.
E. Lucas^^^ verified once only that 2^^^ — 1, a number of 39 digits, is a prime. The method will be given in Ch. XVII, where are given various results relating indirectly to perfect numbers. He stated (p. 162) that he had the plan of a mechanism which will permit one to decide almost instan- taneously whether the assertions of Mersenne and Plana that 2" — 1 is a prime for n = 53, 67, 127, 257 are correct. The inclusion of n = 53 is an error of citation. He tabulated prime factors of 2" — 1 for n^40.
E. Lucas^^^ gave a table of primes with 12 to 16 digits occurring as a factor in 2"-l for n = 49, 59, 65, 69, 87, and in 2''+l forn = 43, 47, 49, 53, 69, 72, 75, 86, 94, 98, 99, 135, and several even values of n>100. The
'"Decomposition des nombres 2"=!= 1 en leurs facteurs premiers de n = 1 ^ n = 64, moins quatre,
Paris, 1869, 8 pp. "3<»Sphinx-0edipe, 1911, 70, 95. "'^L'interm^diaire des math., 9, 1902, 186. '"Comptes Rendus Paris, 81, 1875, 73-75.
"'Sur la th^orie des nombres premiers, Turin, 1876, p. 11; TWorie des nombres, 1891, 376. "«Nouv. Corresp. Math., 2, 1876, 96. i^Comptes Rendus Paris, 85, 1877, 950-2.
"sBull. Bibl. Storia Sc. Mat. e Fis.; 10, 1877, 152 (278-287). Lucas"- " of Ch. XVII. "'Atti R. Ac. Sc. Torino, 13, 1877-8, 279.
Chap. I] PERFECT, MULTIPLY PERFECT, AND AmICABLE NUMBERS. 23
verification of the primality was made by H. Le Lasseur. To the latter is attributed (p. 283) the factorization of 2'*-! for n = 73, 79, 113. These had been given without reference by Lucas. ^^°
E. Lucas^^^ proposed as a problem the proof that if 8q+7 is a prime, 24a+3_i is not.
E. Lucas^^^ stated as new the assertion of Euler^^ that if 4m — 1 and 8m — 1 are primes, the latter divides A = 2*"*~^ — 1.
E. Lucas^^^ proved the related fact that if 8m — 1 is a prime, it divides A. For, by Fermat's theorem, it divides 2^"*"^ — 1 and hence divides A or 2^~^H-1. That the prime 8m — 1 divides A and not the latter, follows from Euler's criterion that 2^^"^^''^ — 1 is divisible by the prime p if 2 is a quad- ratic residue of p, which is the case if p = 8m='=l. No reference was made to Euler, who gave the first seven primes 4m — 1 for which 8m — 1 is a prime. Lucas gave the new cases 251, 359, 419, 431, 443, 491. Lucas^^^ elsewhere stated that the theorem results from the law of reciprocity for quadratic residues, again without citing Euler. Later, Lucas^^^ again expressly claimed the theorem as his own discovery.
T. Pepin^^^ noted that if p is a prime and q = 2^ — 1 is a quadratic non- residue of a prime 4n + 1 = a^ + 6^, then qisa, prime if and only if (a — hi) / (o + hi) is a quadratic non-residue of q.
A. Desboves^^^ amplified the proof by Lebesgue^^^ that every even per- fect number is of Euclid's type by noting that the fractional expression in Lebesgue's equation must be an integer which divides y^z'^ . . . and hence is a term of the expansion of the second member. Hence this expansion produces only the two terms in the left member, so that (j8+l)(7+l) . . . = 2. Thus one of the exponents, say /3, is unity and the others are zero. The same proof has been given by Lucas^^^ (pp. 234-5) and Th^orie des Nombres, 1891, p. 375. Desboves (p. 490, exs. 31-33) stated that no odd perfect number is divisible by only 2 or 3 distinct primes, and that in an odd perfect number which is divisible by just n distinct primes the least prime is less than 2".
F. J. E. Lionnet^^* amplified Euler's^^ proof about odd perfect numbers. F. Landry^^^ stated that 2^^=*= 1 are the only cases in doubt in his table."' Moret-Blanc^^° gave another proof that 2^^ — 1 is a prime.
""Assoc. franQ. avanc. sc, 6, 1877, 165.
»2iNouv. Corresp. Math., 3, 1877, 433.
i"Mess. Math., 7, 1877-8, 186. AJso, Lucas.""
i«Amer. Jour. Math., 1, 1878, 236.
i^^BuU. Bibl. Storia Sc. Mat. e Fis., 11, 1878, 792. The results of this paper will be cited in Ch.
XVI. ^Recreations math., ed. 2, 1891, 1, p. 236. "^Comptes Rendus Paris, 86, 1878, 307-310. "'Questions d'algebre 616mentau-e, ed. 2, Paris, 1878, 487-8. '"Nouv. Ann. Math., (2), 18, 1879, 306.
"sBull. Bibl. Storia Sc. Mat., 13, 1880, 470, letter to C. Henry. "«Nouv. Ann. Math., (2), 20, 1881, 263. Quoted, with Lucas' proof, Sphinx-Oedipe, 4,
1909, 9-12.
24 History of the Theory of Numbers. [Chap, i
H. LeLasseur found after^^^ 1878 and apparently just before^^^ 1882 that 2'*-l has the prime factor 11447 if n = 97, 15193 if n = 211, 18121 if 71 = 151, 18287 if n = 223, and that there is no divisor <30000 of 2"-l for the 24 prime values of n, n^257, which remain in doubt, viz. [cf. Lucas^^^],
61, 67, 71, 89, 101, 103, 107, 109, 127, 137, 139, 149, 157, 163, 167, 173, 181, 193, 197, 199, 227, 229, 241, 257.
J. Carvallo^^^ attempted again^^* to prove the non-existence of odd perfect numbers y^'z^ . . .u\ where y,. . .u are distinct odd primes. He began by noting that one and only one of the exponents n, . . ., r is odd [Euler^^]. Let y<z< . . .<u, and call their number jjl. From the definition of a perfect number,
y — l "' u — 1 ' y — l'u — l
The fractions in this inequality form a decreasing series. Hence
fe)'>^. ^<A' -~i>^' H^r
Thus w(2 — A;)<2. By a petitio principii (the division by 2— A:, not known to be positive), it was concluded (p, 10) that
^<2i:^' ^^<2, y>2i/(M-i)_i-
[This error, repeated on p. 15, was noted by P. Mansion. ^^] For a given n, there is at most one prime between the two limits (of difference < 2) for y. A superior limit is found for 2 as a function of y. An incomplete computation is made to show that, if /x>8, z <y-\-l.
It is shown (p. 7) that an odd perfect number has a prime factor greater than the prime factor w entering to an odd power, since w+l divides the sum of the divisors. In a table (p. 30) of the first ten perfect numbers, 2^^ — 1 and 2*^ — 1 are entered as primes [contrary to Euler^^ and Plana^^°].
E. Catalan^^^ stated that 2^ — 1 is a prime if p is a prime of the form 2^ — 1. If correct this would imply that 2^^^ — 1 is a prime [cf. Catalan^^^].
E. Lucas^^^ repeated the remark of LeLasseur^^^ on the 24 prime values of n^257 for which the composition of 2^ — 1 is in doubt. According to a
"iSince these four values of n are included in the list by Lucas^** of the 28 values of n ^ 257 for which the composition of 2"—! is unknown. Cf. Lucas^^^ p. 236.
"2Lucas, Recreations math., 1, 1882, 241; 2, 1883, 230. Later, Lucas^^s credited LeLasseur with these four cases as well as n = 73 [Eulers^] and n = 79, 113, 233 [cf. Reuschlei"]. The last four cases were given by Lucas"*, while the last three do not occur in the table (Lucasi24^ pp 7gg_9) by LeLasseur of the proper divisors of 2"— 1 for each odd n, n<79, and for a few larger composite n's. The last three were given also by Lucas"^ (p. 236) without reference.
'"Th^orie des nombres parfaits, par M. Jules Carvallo, Paris, 1883, 32 pp.
"<Mathesis, 6, 1886, 147.
'"Melanges Math., Bruxelles, 1, 1885, 376.
'"Mathesis, 6, 1886, 146.
Chap. IJ PERFECT, MULTIPLY PERFECT, AND AMICABLE NUMBERS. 25
communication from Pellet, 2" — 1 is divisible by 6n+l if n and 6n+l are primes such that 6n+l =4L^+27M^ [provided* n= 1 (mod 4), i. e., L is odd].
M. A. Stern^" amplified Euler's^^ proof concerning odd perfect numbers.
E. Lucas^^^ repeated the statement [Desboves^^^] that an odd perfect number must contain at least four distinct primes.
G. Valentin^^^ gave a table, computed in 1872, showing factors of 2"— 1 for n = 79, 113, 233, etc., but not the new cases of LeLasseur.^^^
The primality of iV = 2®^ — 1, a number of 19 digits, considered composite by Mersenne and prime by Landry, was established by J. Pervusin"° and P. Seelhoff ^^^ independently. The latter claimed to verify that there is no factor <N^'^ of the form 8?i+7, abbreviating the work by use of various numbers of which iV is a quadratic residue; thus iV is a prime or the product of two primes. Since iV = 2(2^°)^ — 1, 2 is a quadratic residue of any prime factor of N, so that the factor is 8n=i= 1. It was verified that 3^= 1 (mod N), where i8 = (iV — 1)/9. If N=fF, where F is the prime factor 8n-|-l, then 3^^1(mod F) and, by Fermat's theorem, 3^~^=l(mod F). It is stated without proof that one of the exponents /S and F — 1 divides the other. Cole^^^ regarded the proof as unsatisfactory.
Seelhoff proved that a perfect number of the form pV is of Euclid's type if p and r are primes and p<r. The condition is
r''+\2-p)-2r''{l-p)-p If p > 2, the denominator is negative. Hence p = 2 and
^'=2K^' 2'+' = r+;j-j, p = l, r=2-+'-l.
His statements (p. 177) about the factors of 2" — 1, n = 37, 47, 53, 59, were corrected by him {ibid., p. 320) to accord with Landry.^^^
P. Seelhoff ^^^ obtained the known factors of these 2" — 1 and proved that 2^^ — 1 is a prime, by use of his method of quadratic residues.
H. Novarese^^^ proved that every perfect number of Euclid's type ends in 6 or 28, and that each one > 6 is of the form 9A;+1.
Jules Hudelot"^ verified in 54 hours that 2^^ — 1 is a prime by use of the test by Lucas, Recreations math., 2, 1883, 233.
♦Correction by Kraitchik, Sphinx-Oedipe, 6, 1911, 73; Pellet, 7, 1912, 15. "'Mathesis, 6, 1886, p. 248. "8/6td., p. 250.
""Archiv Math. Phys., (2), 4, 1886, 100-3. ""Bull. Acad. Sc. St. Petersb., (3), 31, 1887, p. 532; Melanges math. astr. ac. St. P^tersb., 6,
1881-8, 553; communicated Nov. 1883. "iZeitschr. Math. Phys., 31, 1886, 174-8.
»"Archiv Math. Phys., (2), 2, 1885, 327; 5, 1887, 221-3 (misprint forn = 41). *«Jomal de sciencias math, e astr., 8, 1887, 11-14. [Servais"*.] "♦Mathesis, 7, 1887, 46. Sphinx-Oedipe, 1909, 16.
26 History of the Theory of Numbers. [Chap, i
CI. Servais"^ republished the proofs by Novarese^"*^ and proved that a'"6'* is not perfect if a and h are odd primes. For, by the equations [Nocco"^]
a-+i_l = 6"(a-l), b''+^-l=2a"'(6-l),
we obtain, by subtraction,
Thus2a'">6". Since a^3, a'"+^^3a"'>a'"+6'*>a+6-l. He next proved that, if an odd perfect number is divisible by only three distinct primes a, h, c, two of them are 3 and 5, since [as by Carvallo^^^]
04)04)04)<l
Taking a = 3, 6 = 5, we have c<16, whence c = 7, 11, or 13. He quoted from a letter from Catalan that the sum of the reciprocals of the divisors of a perfect number equals 2.
E. Cesaro^*^ proved that in an odd perfect jiumber containing n distinct prime factors, the least prime factor is ^n\/2.
CI. Servais^^^ showed that it does not exceed n since, if a<h<c< . . . ,
b a+1 c a-\-2
6 — 1 a c — \ a+1
ah a a+1 a+2 a-\-n — \
2i^. . . ^ . . . . >
a—lb—1 ' a— r a a+1 a+n— 2
whence 2(a — l)<a+n — 1, a<n+l. If I is the (m — l)th prime factor and s is the 772th, and if
a b
a-l'b-l"l-l then
^L<2,
s+1 s+n—m _. ^L{n—m)-\-2
>2, s<
s — l s ' ' ' s-\-n—m-\-l ' 2—L
J. J. Sylvester ^'^^ reproduced Euler's^^ proof that every even perfect number is of EucUd's type. From the fact that ■|.|-<2, he concluded that there is no odd perfect number a'"6'*. For the case of three prime factors he obtained the result of Servais^'*^ in the same manner. He proved that no odd perfect number is divisible by 105 and stated that there is none with fewer than six distinct prime factors.
Sylvester^^^ and Servais^^*^ gave complete proofs that there exists no odd perfect number with only three distinct prime factors.
i«Mathesis, 7, 1887, 228-230. »«/6id., 245-6. "'Mathesis, 8, 1888, 92-3. "8Nature, 37, Dec. 15, 1887, 152 (minor correction, p. 179); Coll. Math. Papers, 4, 1912, 588. "'Comptes Rendus Paris, 106, 1888, 403-5 (correction, p. 641); reproduced with notes by P. Mansion, Mathesis, 8, 1888, 57-61. Sylvester's Coll. Math. Papers, 4, 1912, 604, 615. ""Mathesis, 8, 1888, 135.
Chap. I] PERFECT, MULTIPLY PERFECT, AND AMICABLE NUMBERS. 27
Sylvester ^^^ proved there is no odd perfect number not divisible by 3 with fewer than eight distinct prime factors.
Sylvester^^^ proved there is no odd perfect number with four distinct prime factors.
Sylvester^^^ spoke of the question of the non-existence of odd perfect numbers as a "problem of the ages comparable in difficulty to that which previously to the labors of Hermite and Lindemann environed the subject of the quadrature of the circle." He gave a theorem useful for the investi- gation of this question: For r an integer other than 1 or —1, the sum l+r+r^+ . . . -\-r^~^ contains at least as many distinct prime factors as p contains divisors >1, with a possible reduction by one in the number of prime factors when r= — 2, p even, and when r = 2, p divisible by 6.
E. Catalan ^^^ proved that if an odd perfect number is not divisible by 3, 5, or 7, it has at least 26 distinct prime factors and thus has at least 45 digits. In fact, the usual inequality gives
lTl3-- I ^2 ^^^^"3 5 7 11 • I <2 3 5 7<^-^^^^-
By Legendre's table IX, Theorie des nombres, ed. 2, 1808; ed. 3, 1830, of the values of P{w) up to w; = 1229, we see that I ^ 127. But 127 is the 27th prime >7.
R. W. D. Christie^^^ erroneously considered 2^^ — 1 and 2^^ — 1 as primes.
E. Lucas^^® proved that every even perfect number, aside from 6 and 496, ends with 16, 28, 36, 56, or 76; any one except 28 is of the form 7k='= 1 ; any one except 6 has the remainder 1,2, 3, or 8 when divided by 13, etc.
E. Lucas^" reproduced his^^^ proofs and the proof by Euler,^^ and gave (p. 375) a list of known factorizations of 2" — 1.
Genaille^^^ stated that his machine "piano arithm^tique " gives a prac- tical means of applying in a few hours the test by Lucas {ibid., 5, 1876, 61) for the primality of 2" — 1 .
J. Fitz-Patrick and G. ChevreP^^ stated that 2^8(229-1) is perfect.
E. Fauquembergue^®^ found that 2®'' — 1 is composite by a process not yielding its factors [cf. Mersenne,^" Lucas,^^^ Cole^'^^].
A. Cunningham^^^ called 2^ — 1 a Lucassian if p is a prime of the form 4A;+3 such that also 2p+l is a prime, stating that Lucas^^^ had proved that 2'' — 1 has the factor 2p+l. Cunningham listed all such primes p<2500
i"Comptes Rendus Paris, 106, 1888, 448-450; Coll. M. Papers, IV, 609-610.
^mid., 522-6; Coll. M. Papers, IV, 611-4.
""Nature, 37, 1888, 417-8; Coll. M. Papers, IV, 625-9.
""Mathesis, 8, 1888, 112-3. M6m. soc. sc. Ukge, (2), 15, 1888, 205-7 (Melanges math., III).
»*Math. Quest. Educat. Times, 48, 1888, p. xxxvi, 183; 49, p. 85.
"«Mathe8is, 10, 1890, 74-76.
"'Theorie des nombres, 1891, 424-5.
"'Assoc, frang. avanc. sc, 20, I, 1891, 159.
"'Exercices d'Arith., Paris, 1893, 363.
""L'interm^diaire des math., 1, 1894, 148; 1915, 105, for representations by u*+67t;*.
""British Assoc. Reports, 1894, 563.
28 History of the Theory of Numbers. [Chap, i
and considered it probable that primes of the forms 2''±1, 2'^S (if not yielding Lucassians) generally yield prime values of 2^ — 1, and that no other primes will. All known and conjectured primes 2^ — 1, with p prime, fall under this rule.
In a letter to Tannery/^- Lucas stated that Mersenne^°'^^ implied that a necessary and sufficient condition that 2^—1 be a prime is that p be a prime of one of the forms 2^"+l, 2^''±3, 2^"+^ — 1. Tannery expressed his behef that the theorem was empirical and due to Frenicle, rather than to Fermat, and noted that the sufficient condition would be false if 2^' — 1 is composite [as is the case, Fauquembergue^^°].
Goulard and Tannery^^^ made minor remarks on the subject of the last two papers.
A. Cunningham^^ found that 2^^' - 1 has the factor 7487. This contra- dicts LeLasseur's^^- statement on di visors < 30000 of Mersenne's numbers.
A. Cunningham^^^ found 13 new cases (317, 337, 547, 937, . . .) in which 2^—1 is composite, and stated that for the 22 outstanding primes 5^257 [above list^^- except 61, 197] 2^ — 1 has no divisor < 50,000 (error as to q = lSl, see Woodall^^). The factors obtained in the mentioned 13 cases were found after much labor by the indirect method of Bickmore,^^^ who gave the factors 1913 and 5737 of 2-^^-1.
A. Cunningham^" gave a factor of 2^-1 for g = 397, 1801, 1367, 5011 and for five larger primes q.
C. Bourlet"^ proved that the sum of the reciprocals of all the divisors di of a perfect number n equals 2 [Catalan ^^^], by noting that n/di ranges with di over the divisors of n, so that 2n = 'Zn/di. The same proof occurs in II Pitagora, Palermo, 16, 1909-10, 6-7.
M. Stuyvaert^^^ remarked that an odd perfect number, if it exists, is a sum of two squares since it is of the form pk^, where p is a prime 4n+l [Frenicle,^ Euler^sj
T. Pepin^"° proved that an odd perfect number relatively prime to 3-7, 3-5 or 3-5-7 contains at least 11, 14 or 19 distinct prime factors, respectively, and can not have the form 6/cH-5.
F. J. Studnicka^^^ called Ep = 2''-\2''-l) an Euclidean number if 2^-1 is a prime. The product of all the divisors <Ep of Ep is E/~'^. When Ep is written in the diadic system (base 2), it has 2p — l digits, the first p of which are unity and the last p — 1 are zero.
"^L'interm^diaire des math., 2, 1895, 317.
i«/6Mi., 3, 1896, 115, 188, 281.
^"Nature, 51, 1894-5, 533; Proc. Lond. Math. Soc, 26, 1895, 261; Math. Quest. Educat. Times,
5, 1904, 108, last footnote. i«British Assoc. Reports, 1895, 614. i«On the numerical factors of a"-l, Messenger Math., 25, 1895-6, 1-44; 26, 1896-7, 1-38.
French transl. by Fitz-Patrick, Sphinx-Oedipe, 1912, 129-144. 155-160. "Troc. London Math. Soc, 27, 1895-6, 111. "8Nouv. Ann. Math., (3), 15, 1896, 299. "•Mathesis, (2), 6, 1896, 132.
''"Memou-e Accad. Pont. Nuovi Lincei, 13, 1897, 345-420. "'Sitzungsber. Bohm. Gesell., Prag, 1899, math, nat., No. 30.
Chap. I] PERFECT, MULTIPLY PERFECT, AND AmICABLE NUMBERS. 29
Mario Lazzarini^" attempted to prove that there is no odd perfect num- ber a'^b^c'^, but made the error of thinking that a is relatively prime to 6^+. . .+6+1. He attempted to show that p = 2" — 1 is a prime if and only if p divides iV = 3*^+1, where fc = 2"~^ — 1 [false for a = 2, since p = S, N = 4:]. He restricted his argument to the case a odd, whence p = 1 (mod 3) . Then, if p is a prime, —3 is a quadratic residue of p, so that (— 3)^^~^^^^=1 (mod p), whence p divides N. Conversely, when this congruence holds, he concluded falsely that z^=—3 (mod p) has two and only two roots, so that p is expressible in a single way as a sum of a square and the triple of a square and hence is prime. To show the error, let p = ab, where a = 23, 6 = 3851 are primes; then
g-l 6-1
(-3)11 + 1= _2a6,(-3) 2 =-l(mod5),(-3) ^ =(-3)^^-^^^= -1 (mod a),
whence (—3)^^"^^^^=! (mod p). Cipolla remarked (p. 288) that we may deduce from a result of Lucas^^° that p is a prime if it divides N without dividing 3*+l for any divisor 8 of p=2"~^ — 1.
F. N. Cole^'^ found that 2^"^ - 1 is the product of the two primes 193707721 , 761838257287. In the footnote to p. 136, he criticized the proof by Seel- hoff"^ of the primality of A^ = 2^^ — 1 and stated he had verified that N is prime by an actual computation of a series of primes of which iV is a quadratic residue.
R. D. Carmichael^^^ proved that any even perfect number Tp2\ . .p/" is of Euclid's type. Write d for 2'*+^ — 1. Then, as usual,
d pf d \ p/
If n>2. Pi is less than d, being an aliquot divisor of it, so that 1 + 1/p, exceeds the left member of the inequality. Hence n = 2, p2 = d.
A. Cunningham^^^ gave the residues of A; =2^"*, 2*, etc., modulo 2^ — 1 for primes g^lOl.
A. Turcaninov^"^ (Turtschaninov) proved that an odd perfect number has at least four distinct prime factors and exceeds 2000000.
A. Gerardin^^^ noted the error by Plana. ^^°
A. Gerardin^^^ stated the empirical laws: If n is a prime of the form 24a^+ll and if 2" — 1 is composite, the least factor is of the form 24?/ +23
"^Periodico di mat. insegn. sec, 18, 1903, 203; criticized by C. Ciamberlini, p. 283, and by M.
Cipolla, p. 285. i"Bull. Amer. Math. Soc, 10, 1903-4, 134-7. French transl., Sphinx-Oedipe, 1910, 122-4.
Cf. Fauquembergue.^^" i^^Annals of Math., (2), 8, 1906-7, 149. I'sproc. London Math. Soc, (2), 5, 1907, 259 [250]. i'6 Vest, opytn. fiziki (Spaczinskis Bote), Odessa, 1908, No. 461 (pp. 106-113), No. 463 (162-3),
No. 465-6 (213-9), No. 470 (314-8). In Russian. Cf. Bourlet.is* '"L'interm^diaire des math., 15, 1908, 230-1. '"Sphinx-Oedipe, Nancy, 3, 1908-9, 113-123; Assoc, frang. avanc sc, 1909, 145-156. In Wis-
kundig Tijdschrift, 10, 1913, 61, he added that in the remaining three cases <257, n = 107,
167, 227, the least divisor (necessarily >1 mUlion) is respectively 5136 y+2783,
8016 y+335, 10896 J/+5903.
30 History of the Theory of Numbers. [Chap, i
{e. g., n = ll, 59, 83, 131, 179, 251). If n is a prime 24a:+23 and 2'*-l is composite, the least factor is of the form 48?/ +47 (e. g., n = 47, ?/ = 48, factor 2351; n = 23, 71, 191, 239). Gerardin^^^ gave tables of the possible, but (unverified, factors of 2" — 1, n<257.
A. Cunningham^^o gave the factor 150287 of 2^^^-\.
A. Cunningham^^^ found the factor 228479 of 2^^-l.
T. M. Putnam^^^ proved that not all of the r distinct prime factors of a perfect number exceed 1 +r/loge2 and hence do not all equal or exceed 1 +3r/2.
L. E. Dickson^^^ gave an immediate proof that every even perfect num- ber is of Euclid's type. Let 2"g be perfect, where q is odd and n > 0. Then (2"+^ — l)s = 2'^'^^q, where s is the sum of all the divisors of q. Thus s = q-\-d, where d = q/{2''^^ — l). Hence d is an integral divisor of q, so that q and d are the only divisors of q. Hence d = \ and 5 is a prime.
H. J. WoodalP^^ obtained the factor 43441 of 2^^^-l.
R. E. Powers^^^ verified that 2^^ — 1 is a prime by use of Lucas' test on the series 4, 14, 194, .... H. Tarry^^^ made an incomplete examination. E. Fauquembergue^^^ proved that 2^^ — 1 is a prime by writing the residues of that series to base 2.
A. Cunningham^^^ noted that 2^ — 1 is composite for three primes of 8 digits. On the proof-sheets of this history, he noted that the first two should be
g = 67108493, p = 134216987; 5 = 67108913, p = 134217827.
A G^rardin^^^'' observed that 2'^''+^-\=F^-2(?, F = 2"+^±l = 2m+l, G = 2"±l, G2 = m2+(m+l)2-(2")2.
H. Tarry^^^^ verified for the known composite numbers 2^—1, where p is a prime, that, if a is the least factor, 2" — 1 is composite.
A. Gerardin added empirically that, if p is any number and a any di- visor of 2^ — 1 , a = 8m =t 1 not being of the form 2" — 1 then 2" — 1 is composite.
A. Cunningham^^^ noted that, if g is a prime,
M^ = 2^-\ = T^-2{quY={qtf-2U\
If Mq is a prime it can be expressed in the forms A^-]-?>B^ — G'^-\-QH'^, and in one or the other of the pairs of forms f^au^ {ci = '^, 14, 21, 42). He discussed M^ to the base 2.
>'»Sphinx-Oedipe, 3, 1908-9, 118-120, 161-5, 177-182; 4, 1909, 1-5, 158, 168; 1910, 149, 166. ""Proc. London Math. Soc, (2), 6, 1908, p. xxii.
"iL'intermddiaire des math., 16, 1909, 252; Sphinx-Oedipe, 4, 1909, 4e Trimestre. 36-7. "2Amer. Math. Monthly, 17, 1910, 167. ^^Ibid., 18, 1911, 109.
'"Bull. Amer. Math. Soc, 16, 1910-11, 540 (July, 1911). Proc. London Math. Soc, (2), 9,
1911, p. xvi. Mem. and Proc. Manchester Literary and Phil. Soc, 56, 1911-12, No. 1, 5 pp.
Sphinx-Oedipe, 1911, 92. Verification by J. Hammond, Math. Quest. Solutions, 2,
1916, 30-2. i«Bull. Amer. Math. Soc, 18, 1911-12, 162 (report of meeting Oct., 1911). Amer. Math.
Monthly, 18, 1911, 195. Sphinx-Oedipe, Feb., 1912, 17-20. "«Sphinx-Oedipe, Dec, 1911, p. 192; 1912, 15. (Proc. London Math. Soc, (2), 10, 1912,
Records of Meetings, 1911-12, p. ii.) ^"Ibid., 1912, 20-22. "^Messenger Math., 41, 1911, 4.
"saBuU. Soc. Philomatiquesde Paris, (10), 3, 1911, 221. isseSphinx-Oedipe, 6, 1911, 174 186, 192. ""Math. Quest. Educ Times, (2), 19, 1911, 81-2; 20, 1911, 90-1, 105-6; 21, 1912, 58-9, 73.
Chap.i] Perfect, Multiply Perfect, and Amicable Numbers. 31
A. Cunningham^^o found the factor 730753 of 2^^^-l.
V. Ramesam^^i verified that the quotient of 2"^-l by the factor 228479 [Cunningham^^^] is the product of the primes 48544121 and 212885833.
A. Aubry^^^ stated erroneously that ''Mersenne affirmed that 2" — 1 is a prime, for n^257, only for n = l, 2, 3, 4, 8, 10, 12, 29, 61, 67, 127, 257 (which has now been almost proved) ; this proposition seems to be due to Frenicle.^'" What Mersenne^" actually stated was that the first 8 perfect numbers occur at the lines marked 1, 2, 3, 4, 8, etc., in the table by Bungus.
A. Cunningham^^^'' noted that M113, M151, M251 have the further factors 23279-65993, 55871, 54217, respectively. Cf. Reuschle^o^ Lucas^^s
A. Gerardin^^-^ noted that there is no divisor < 1000000 of the composite Mersenne numbers not already factored. Let d denote the least divisor of 2«- 1, g a prime ^257. li q = 60z^+43, then d=47 (mod 96), except for the cases given by Euler's^^ theorem (verified for 43, 163, 223). If 5 = 40w+33, d=7 (mod 24), verified for 73, 113, 233. If 5 = 30m+l, d=l (mod 24), verified for 31, 61, 151, 181, 211.
E. Fauquembergue^^^'' proved that 2^°^ — 1 is composite by means of Lucas' test with 4, 14, 194,. . ., written to base 2 (Ch. XVII).
L. E. Dickson^^^ called a non-deficient number primitive if it is not a multiple of a smaller non-deficient number, and proved that there is only a finite number of primitive non-deficient numbers having a given number of distinct odd prime factors and a given number of factors 2. As a corollary, there is not an infinitude of odd perfect numbers with any given number of distinct prime factors. There is no odd abundant number with fewer than three distinct prime factors; the primitive ones with three are
3^5-7, 32527, 325.72, 3^5211, 3^13, 3*5^13, 3*52132, 3^5^132.
There is given a list of the numerous primitive odd abundant numbers with four distinct prime factors and lists of even non-deficient numbers of certain types. In particular, all primitive non-deficient numbers < 15000 are determined (23 odd and 78 even). In view of these lists, there is no odd perfect number with four or fewer distinct prime factors (cf . Sylvester^*^"^^^) . A. Cunningham^^* gave a summary of the known results on the composi- tion of the 56 Mersenne numbers Mq = 2^ — 1, q a prime ^257. Of these, 12 have been proved prime: M^, 5 = 1, 2, 3, 5, 7, 13, 17, 19, 31, 61, 89, 127; while 29 of them have been proved composite. Thus only 15 remain in
""British Assoc. Reports, 1912, 406-7. Sphinx-Oedipe, 7, 1912, 38 (1910, 170, that 730753
is a possible factor). Cf. Cunningham"*. i"Nature, 89, 1912, p. 87; Sphinx-Oedipe, 1912, 38. Jour, of Indian Math. Soc, Madras, 4
1912, 56. "K)euvres de Fermat, 4, 1912, 250, note to p. 67. "2" Mem. and Proc. Manchester Lit. and Phil. Soc, 56, 1911-2, No. 1. i«* Sphinx-Oedipe, 7, 1912, num^ro special, 15-16. "'•^ Ibid., Nov., 1913, 176. i«Amer. Jour. Math., 35, 1913, 413-26. "*Proc. Fifth International Congress, I, Cambridge, 1913, 384-6. Proc. London Math. Soc,
(2), 11, 1913, Record of Meeting, Apr. 11, 1912, xxiv. British Assoc. Reports, 1911,
321. Math. Quest. Educat. Times, (2), 23, 1913, 76.
32 History of the Theory of Numbers. [Chap. I
doubt: M„ q = 101, 103, 107, 109, 137, 139, 149, 157, 167, 193, 199, 227, 229, 241, 257. The last has no factor under one million, as verified by R. E. Powers. ^^^^ No one of the other 14 has a factor under one milhon, as verified t^dce with the collaboration of A. G^rardin. Up to the present three errors have been found in Mersenne's assertion; Mqj has been proved composite (Lucas,^^° Cole^^^), while Mqi and Mgg have been proved prime (Pervusin,"° Seelhoff,^*^ Cole,^"^ Powers^^^). It is here announced that M^^ has the factor 730753, found with the collaboration of A. Gerardin.
J. ]McDonnell^^^ commented on a test by Lucas in 1878 for the primality of 2"-l.
L. E. Dickson^^® gave a table of the even abundant numbers <6232.
R. Niewiadomski^^^ noted that 2^^^ — 1 has the factor 4567 and gave known factors of 2'* — 1. He gave the formula
2^'"+^-l = (2^'"+2"*-l)^+(22"'-2'"-l)^ + l.
G. Ricalde^^^ gave relations between the primes p, q and least solutions of 22«+i_i = pg, al-2h^ = p, c'-2dr = q.
R. E. Powers^^^ proved that 2^°" — 1 is a prime by means of Lucas'^^ test in Ch. XVII.
E. Fauquembergue^'''' proved that 2^ — 1 is prime for p = 107 and 127, composite for p = 101, 103, 109.
T. E. Mason-°^ described a mechanical de\'ice for applying Lucas'"^ method for testing the primality of 2^^'*'^ — 1.
R. E. Powers^°^ proved that 2^°^ — 1 and 2^°^ — 1 are composite by means of Lucas' tests with 3, 7, 47, . . .and 4, 14, 194. . . (Ch. XVII), respectively.
A. Gerardin^°^ gave a history of perfect numbers and noted that 2^—1 can be factored if we find t such that m = 2pt-\-\ is a prime not dividing 8 = 1+2^+22^+ . . . +2^2'-^^^ since 2-p'-1= (2^-1)8 (mod m). Or we may seek to express 2^—1 in two ways in the form x^—2y'.
On tables of exponents to which 2 belongs, see Ch. VII, Cunningham and Woodam'^ Kraitchik.^-^
Additional Papers of a Merely Expository Character.
E. Catalan, Mathesis, (1), 6, 1886, 100-1, 178.
W. W. Rouse Ball, Messenger Math., 21, 1891-2, 34-40, 121. - Pontes (on Bovnius^"), Mem. Ac. Sc. Toulouse, (9), 6, 1894, 155-67.
J. Bezdicek, Casopis Mat. a Fys., Prag, 25, 1896, 221-9.
Hultsch (on lamblichus), Nachr. Kgl. Sachs. Gesell., 1895-6.
H. Schubert, Math. Mussestunden, I, Leipzig, 1900, 100-5.
M. Nasso, Revue de math. (Peano), 7, 1900-1, 52-53.
i»*'Sphinx-Oedipe, 1913, 49-50.
i«*London Math. Soc, Records of Meeting, Dec, 1912, v-vi.
"«Quart. Jour. Math., 44, 1913, 274-7.
'"L'interm^diaire des math., 20, 1913, 78, 167.
"s/btd., 7-8, 149-150; cf. 140-1.
'"Proc. London Math. Soc, (2), 13, 1914, Records of meetings, xxxi.x. Bull. Amer. Math.
Soc, 20, 1913^, 531. Sphinx-Oedipe, 1914, 103-8. 20<>Sphinx-Oedipe, June, 1914, 85; I'interm^diaire des math., 24, 1917, 33. -"Proc Indiana Acad. Science, 1914, 429-431.
2«Proc London Math. Soc, (2), 15, 1916, Records of meetings, Feb. 10, 1916, xxii. »"Sphinx-Oedipe, 1909, 1-26.
Chap. I] PERFECT, MULTIPLY PERFECT, AND AMICABLE NUMBERS. 33
G. Wertheim, Anfangsgriinde der Zahlentheorie, 1902.
G. Giraud, Periodico di Mat., 21, 1906, 124-9.
F. Ferrari, Suppl. al Periodico di Mat., 11, 1908, 36-8, 53, 75-6 (Cipolla).
P. Bachmann, Niedere Zahlentheorie, II, 1910, 97-101.
A. Aubry, Assoc, frang. avanc. sc, 40, 1911, 53-4; 42, 1913; Tenseignement
math., 1911, 399; 1913, 215-6, 223. *M. Kiseljak, Beitrage zur Theorie der vollkommenen Zahlen, Progr. Agram,
1911. *J. Vaes, Wiskundig Tijdschrift, 8, 1911, 31, 173; 9, 1912, 120, 187. J. Fitz-Patrick, Exercices Math., ed. 3, 1914, 55-7.
Multiply Perfect Numbers.
A multiply perfect or pluperfect number n is one the sum of whose divisors, including n and 1, is a multiple of n. If the sum is mn, m is called the multiplicity of n. For brevity, a multiply perfect number of multi- plicity m shall be designated by P^. Thus an ordinary perfect number is a P2. Although Robert Recorde^^ in 1557 cited 120 as an abundant number, since the sum of its parts is 240, such numbers were first given names and investigated by French writers in the seventeenth century. As a P3 equals one-half of the sum of its aliquot divisors or parts (divisors KPs), it was called a sous-double; a P4 equals one-third of the sum of its aliquot parts and was called a sous-triple; a P5 a sous-quadruple; etc.
F. Marin Mersenne proposed to R. Descartes^°^ the problem to find a sous-double other than P^^^^ = 120 = 2^3-5. The latter did not react on the question until seven years later.
Mersenne^"^ mentioned (in the Epistre) the problem to find a P4, a P5 or a P^, a P3 besides 120, and a rule to find as many as one pleases. He remarked (p. 211) that the P3 120, the P4 240 [for 30240?] and all other abundant numbers can signify the most fruitful natures.
Pierre de Fermat^"- referred in 1636 to his former [lost] letter in which he gave "the proposition concerning aliquot parts and the construction to find an infinitude of numbers of the same nature." He^^^ found the second P3, viz., P3<2) = 672 = 2^3-7.
Mersenne^°* stated that Fermat found the 1 3 7 15 . . . P3 672 and knew infallible rules and analysis 2 4 8 16 . . . to find an infinitude of such numbers. He^°^ 3 5 9 17 . . . later gave [Fermat's] method of finding such P3: Begin with the geometric
'""Oeuvres de Descartes, 1, Paris, 1897, p. 229, line 28, letter from Descartes to Mersenne, Oct
or Nov., 1631. ^"iLes Preludes de I'Harmonie Universelle ou Questions Curiouses, Utiles aux Predicateurs, aux
Theologiens, Astrologues, Medecins, & Philosophes, Paris, 1634. '•"Oeuvres de Fermat, 2, Paris, 1894, p. 20, No. 3, letter to Mersenne, June 24, 1636. "^Oeuvres de Fermat, 2, p. 66 (French transl. 3, p. 288), 2, p. 72, letters to Mersenne and
Roberval, Sept., 1636. '"Harmonic Universelle, Paris, 1636, Premiere Preface Generale (preceded by a preface of two
pages), imnumbered page 9, remark 10. Extract in Oeuvres de Fermat, 2, 1894, 20-21. "'Mersenne, Seconde Partie de I'Harmonie Universelle, Paris, 1637. Final subdivision: Nou-
velles Observations Physiques et Math^matiques, p. 26, Observation 13. Extract in
Oeuvres de Fermat, 2, 1894, p. 21. ,
34 History of the Theory of Numbers. [Chap. I
progression 2, 4, 8, ... . Subtract unity and place the remainders above the former. Add unity and place the sums below. Then if the quotient of the (n+3)th number of the top line by the nth number of the bottom line is a prime, its triple multiplied by the (n+2)th number of the middle line is a P3. Thus if ?i = l, 15/3 is a prune and 3-5-8 = 120 is a P3. For n = 3, 63/9 is a prime and 3-7-32 = 672 is a P3. [This rule thus states in effect that 3-2"+2p is a P3 if p = (2'»+3-l)/(2"+l) is a prune.]
The third P3, discovered by Andr6 Jumeau, Prior of Sainte-Croix, is
P3^'^ = 523776 = 29311-31.
In April, 1638, he communicated it to Descartes^°^ and asked for the fourth P3 (the fifth and last of St. Croix's challenge problems).
Descartes^*^^ stated that the rule ^^^ of Fermat furnishes no P3 other than 120 and 672 and judged that Fermat did not find these numbers by the formula, but accommodated the formula to them, after finding them by trial.
Descartes^^^ answered the challenge of St. Croix with the fourth P3,
P3^'^ = 1476304896 = 2^33.1143.127.
Soon afterwards Descartes^ °^ announced the following six P4:
P4^i) = 30240 = 2^335.7, P4(2) =32760 = 2^325.7.13, P^^^^ = 23569920 = 2^335. 1 1 -31 , P4(*) = 142990848 = 2^327.11.13.31, P4(^> = 66433720320 = 2^^335. 1 1 .43. 1 27, P4^®^ =403031236608 = 2^3327.11.13.43.127,
and the sous-quadruple
Ps^^^ = 14182439040 = 2^3^5.7-11217.19.
He stated that his analysis had led him to a method which would require time to explain in the form of a rule, but that he could find, for example, a sous-centuple, necessarily very large.
Fermat apparently responded to the fifth challenge problem of St. Croix on the fourth P3. Without warrant, Descartes^^" suspected that Fermat had not found independently the fourth P3, but had learned from some one in Paris of its earlier discovery by Descartes. Fermat^^^ indicated that he possessed an analytic method by which he could solve all questions con-
'"^Oeuvres de Descartes, 2, Paris, 1898, p. 428, p. 167 (latter without name of St. Croix); cf.
Oeuvres de Fermat, 2, 1894, pp. 63-64. "'Oeuvres de Descartes, 2, 1898, p. 148, letter to Mersenne, May 27, 1638. ^osQeuvres de Descartes, 2, 1898, 167, letter to Mersenne, June 3, 1638. '"'Oeuvres de Descartes, 2, 1898, 2.50-1, letter to Mersenne, July 13, 1638. In June, 1645,
Descartes, 4, 1901, p. 229, again mentioned the first two of these Pt. ""Oeuvres de Descartes, 2, 1898, 273, letter to Mersenne, July 27, 1638. "^Oeuvres de Fermat, 2, 1894, p. 165, No. 4; p. 176, No. 1; letters to Mersenne, Aug. 10 and
Dec. 26, 1638.
Chap. I] PERFECT, MULTIPLY PERFECT, AND AmICABLE NUMBERS. 35
cerning aliquot parts, apart from the testing of the primaUty of a number n, knowing no method except the trial of each number < \/n as a divisor. Descartes"^ gave the following rules for multiply perfect numbers:
I. If n is a P3 not divisible by 3, then 3n is a P4. II. If a P3 is divisible by 3, but by neither 5 nor 9, then 45P3 is a P4.
III. If a P3 is divisible by 3, but not by 7, 9 or 13, then 3-7-13 P3 is a P4.
IV. If n is divisible by 2^ but by no one of the numbers 2^°, 31, 43, 127,
then 31n and 16-43-127n are proportional to the sums of their aliquot parts. V. If n is not divisible by 3 and if 3n is a P^k, then n is a Ps^.
By applying rule II to P3^^\ Ps^^\ P3^*^ Descartes obtained his P^^^^ P4<3^ P^^^K By applying rule III to Ps^'\ Ps^^\ Ps^''\ he obtained his
p (2) p (4) p (6) ^4 ) ^4 5 ^4 •
In the same letter, Descartes expressed to Mersenne a desire to know what Frenicle de Bessy had found on this subject. Frenicle wrote direct to Descartes, who in his reply^^^ expressed his astonishment that Frenicle should regard as sterile the above rules for finding P4, since Descartes had deduced by them six P4 from four P3, at a time when Mersenne had stated to Descartes that it was thought to be impossible to find any at all. Des- cartes stated that, since one can find an infinity of such rules, one has the means of finding an infinitude of P^- From one of Frenicle's P5 (com- municated to Descartes by Mersenne),
Ps^^) = 30823866178560 = 2i°3^5-72l3- 19-23-89,
Descartes (p. 475) derived the smaller P5:
Pg^^) = 31998395520 = 2^3^5.72.13.17.19.
Mersenne^^^ listed various P^ due to his correspondents, without cita- tion of names. He listed the above Ps^'^ (^ = 1, 2, 3, 4) and remarked that "un excellent esprit "^^^ found that when
P3^'^ = 459818240 = 2^5.7.19.37.73
is multiplied by 3, the product is a P4:
P4(^ = 2^3.5.7.19.37.73,
attributed to Lucas^^^ by Carmichael.^^^
"^Oeuvres, 2, 1898, 427-9, letter to Mersenne, Nov. 15, 1638.
"'Oeuvres de Descartes, 2, 1898, 471, letter to Frenicle, Jan. 9, 1639.
'"Les Nouvelles Pensees de Galilei, traduit d'ltalien en Frangois, Paris, 1639, Preface, pp. 6-7.
Quoted in Oeuvres de Descartes, 10, Paris, 1908, pp. 564-6, and in Oeuvres de Fermat, 4,
1912, pp. 65-66. '"Frenicle de Bessy, according to the editors of the Oeuvres de Fermat, 2, 1894, p. 255, note 2;
4, 1912, p. 65, note 2 (citing Oeuvres de Descartes, 2, letter Descartes to Mersenne, Nov.
15, 1638, pp. 419-448 [p. 429]). It is clear that the discoverers Fermat, St. Croix, and
Descartes of the P|^*) (i = 2, 3,4) are not meant. It is attributed to Legendre"" by
Carmichael.*'*
36 History of the Theory of Numbers. [Chap, i
There are listed Descartes' six P^ and P^^^^ Frenicle's Ps^\ and also
P4^«) =45532800 = 2^3^5217.31,
P4^^^ = 43861478400 = 2^°3^5223.31.89,
and the erroneous P5 508666803200 (not divisible by 5^+5-|-l), probably a misprint for the correct P5 (in the list by Lehmer^'^) :
P5^'^ = 518666803200 = 2^^3'5-72l3- 19-31 .
A part of these Pm, but no new ones, were mentioned by Mersenne^" in 1644; the least P3 is stated to be 120. (Oeuvres de Fermat, 4, 66-7.) In 1643 Fermat^ ^^ cited a few of the P^ he had found:
Ps^^^ = 51001 180160 = 2^*5.7.19.31.151 ,
P4^'^) = 14942123276641920 = 2^3^5.17.23.137.547.1093, P5(^) = 1802582780370364661760 = 22°335.72l32l9.31.61. 127.337, Ps^®^ = 87934476737668055040 = 2^^3^5.7313. 19-37.73. 127, Pg(i) = 223375374113133^7231.41.^1.241.307.467.2801, Pg(2) = 22735537.11.13219.29.31.43.61.113.127.
He stated that he possessed a general method of finding all P^n-
Replying to Mersenne's query as to the ratio of
Pg(3) = 22^3^5^11.13219.31243.61.83.223.331.379.601.757
X 1201.7019.823543-616318177:100895598169
to the sum of its aUquot parts, Fermat^^^ stated that it is a Pq, the prime
factors of the final factor being 112303 and 898423 [on the finding of these
factors, see Ch. jXIV, references 23, 92, 94, 103]. Note that 823543 = 7^
Descartes^^^ constructed P3^2) = 572 = 21.32 by starting with 21 and noting that (r(21) =32, o-(32) =63 = 3.21, for a defined as on p. 53.
Mersenne^^ noted that if a P3 is not divisible by 3, then 3P3 is a P4 [rule I of Descartes^^-]; if a P5 is not divisible by 5, then 5P5 is a Pq, etc. He stated that there had been found 34 P4, 18 P5, 10 Pg, 7 P7, but no Pgso far.
In 1652, J. Broscius (Apologia,^* p. 162) cited the P4^'^ [of Descartes^"^]. The P3 120 and 672 are mentioned in the 1770 edition of Ozanam's'^ Recreations, I, p. 35, and in Hutton's translation of Montucla's^^ edition, I, p. 39.
A. M. Legendre^^^ determined the Pm of the form 2"a/37 . . . , where a, /3, 7, . . .are distinct odd primes, for 7n = 3, n^8; ?n=4, n = 3, 5; m = 5, n = 7. No new P„ were found.
"*Oeuvres, 2, 1894, p. 247 (261), letter to Carcavi; Varia opera, p. 178; Pr^cia des oeuvres math, de Fermat, par E. Brassinne, Toulouse, 1853, p. 150.
3'^Oeuvers de Fermat, 2, 1894, 255, letter to Mersenne, April 7, 1643. The editors (p. 256, note) explained the method of factoring probably used by Fermat. The sum of the aliquot parts of 23« is 223iV, where N = 616318177, and the sum of the aliquot parts of N is 2-7? M iVf = 898423. As M does not occur elsewhere in Pe., it is to be expected as a factor of the final factor of Pe.
"8Manuscript published by C. Henry, Bull. Bibl. Storia Sc. Mat. e Fis., 12, 1879, 714.
'^•Thor^ie des nombres, 3d ed., vol. 2, Paris, 1830, 146-7; German transl. by H. Maser, Leipzig, 2, 1893, 141-3. The work for n? =3 was reproduced by Lucas'^" without reference.
Chap. I] PERFECT, MULTIPLY PERFECT, AND AmICABLE NUMBERS. 37
E. Lucas^^o ga^g a table of P^ of the form 2''-\2''-l)N which includes only 15 of the 26 Pm given above and no additional P^, m>2, except two erroneous P5 :
2^°3^5-72.1l2.19.23.89, 2i^5-72l3.19237-73-127,
attributed elsewhere^^^ by him to Fermat. If we replace 7^ by 7 in the former, we obtain a correct P5 listed by Carmichael 'P"^
P5(7> = 2'°3*5-7. 11219.23-89.
If in the second, we replace 5-7^ by 3^-5-7^ we obtain Fermat's P^-^K
A. Desboves^^^ noted that 120 and 672 are the only P3 of the form
2"-3-p, where p is a prime.
D. N. Lehmer^^^ gave the additional P„:
p^(i2) ^22325.7213.19,
P^(i3) = 2«3272l3.19237.73-127,
P5® =2213^527.19.23231.79.89.137.547.683.1093,
Pg(4) =2193^5^7211. 13.19.23.31.41. 137.547.1093,
Pg(5) =22^3^5.7211.13.17.19231.43.53.127.379.601.757.1801.
He readily proved that a P3 contains at least 3 distinct prime factors, a P4 at least 4, a P5 at least 6, a Pq at least 9, a P^ at least 14.
J. Westlund324 proved that 2^3.5 and 2^3.7 are the only P3 of the form V\'V2Vzy where the p's are primes and Pi<P2<P3. He^^^ proved that the only P3 = Pi"p2P3P4, Pi<P2<P3<P„ is P3^'^ =293.11.31.
A. Cunningham^^^ considered P^ of the form 2^ \2^—l)F, where F is to be suitably determined. There exists at least one such P^ for every q up to 39, except 33, 35, 36, and one for g = 45, 51, 62. Of the 85 P^ found, the only one published is the largest one, viz., for q = Q2, giving Pq^^^ with
F = 3^5'72ll. 13.19223.59.71.79.127.157.379.757.43331.3033169;
while none have m>6, and for m = 3 at most one has a given q. He found in 1902 (but did not publish) the two P7 = 2^H2^^-1)P, where
F = C.192127 or 0.19^51-911,
C = 3i^-5^.7^.1M3.17-23.31-37-41.43.61.89.97-193.442151.
R. D. CarmichaeP^^ has shown that there exists no odd P^ with only three distinct prime factors; that 2^3-5 and 2^3.7 are the only P^ with only
'20Bull. Bibl. e Storia Mat. e Fis., 10, 1877, 286. In 253-5-7, listed as a Pt, 3 is a misprint for 3». '"Lucas, Theorie des Nombres, 1, Paris, 1891, 380. Here the factor 11^ IS^ of Fermat's P«(')
is given erroneously as lllS^, while the Pe^i^ of Descartes is attributed to Fermat. '^Questions d'Algebre, 2d ed., 1878, p. 490, Ex. 24. '^'Annals of Math., (2), 2, 1900-1, 103-4. "^Annals of Math., (2), 2, 1900-1, 172-4. '"Annals of Math., (2), 3, 1901-2, 161-3. '"British Association Reports, 1902, 528-9. '"American Math. Monthly, 13, Feb., 1906, 35-36.
717 8 5
38 History of the Theory of Numbers. [Chap, i
three distinct prime factors ;^^^ that those with only four distinct prime fac- tors are^^" the P^^^^ of St. Croix^"^ and the P4^'^ of Descartes f°^ and that the even P„ with five^^^ distinct prime factors are P3^^\ Pi^\ Pi^^ of Des- cartes^"^' ^"^ and P^^^^ of Mersenne.^"
CarmichaeP^^'* stated and J. Westlund proved that if n>4, no P„ has only n distinct prime factors.
Carmichael's^^^ table of multiply perfect numbers contains the misprint 1 for the final digit 0 of Descartes' Pi^\ and the erroneous entry 919636480 in place of its half, viz., P^-^^ of Mersenne.^^^ The only new P^ is
Pg(7) = 2^^3^527211. 13-17.19-3143.257.
All P,;,< 10^ were determined; only known ones were found. CarmichaeP^^ gave an erroneous P5 and the new P^:
p^(i4)^2"3272l3-1923M27.151,
p^(i5)^2253^52l9-31.683.2731-8191,
p^(i6)^225365-19-23-137-547-683-1093-2731-8191.
Carmichael and T. E. Mason^^ gave a table which includes the above hsted 10 P2, 6 P3, 16 P4, 8 P5, 7 Pq, together with 204 new multiply perfect numbers P, (i = 3, . . . , 7) . Of the latter, 29 are of multiplicity 7, each having a very large number of prime factors. No P7 had been previously published.
[As a generalization, consider numbers n the sum of the kth. powers of whose divisors < n is a multiple of n. For example, n = 2p, where p is a prime 8/1 ±3 and k is such that 2*^+1 is divisible by p; cases are p = 3, k = l; p = 5, k = 2; p = ll, k = 5; p = 13, A; = 6.]
Amicable Numbers.
Two numbers are called amicable* if each equals the sum of the aliquot divisors of the other.
According to lamblichus^ (pp. 47-48), "certain men steeped in mistaken opinion thought that the perfect number was called love by the Pythago- reans on account of the union of different elements and affinity which exists in it; for they call certain other numbers, on the contrary, amicable num- bers, adopting virtues and social quahties to numbers, as 284 and 220, for the parts of each have the power to generate the other, according to the rule of friendship, as Pythagoras affirmed. WTien asked what is a friend, he replied, 'another I,' which is shown in these numbers. Aristotle so defined a friend in his Ethics."
«»Aimalsof Math., (2), 7, 1905-6, 153; 8, 1906-7, 49-56; 9, 1907-8, 180, for a simpler proof that
there is no Pa = Pi^p^Vi^t c> 1. ""Annals of Math., (2), 8, 1906-7, 149-158.
"'Bull. Amer. Math. Soc, 15, 1908-9, pp. 7-8. Fr. transl., Sphinx-Oedipe, Nancy, 5, 1910, 164-5. wi^Amer. Math. Monthly, 13, 1906, 165.
»«Bull. Amer. Math. Soc, 13, 1906-7, 383-6. Fr. transl., Sphinx-Oedipe, Nancy, 5, 1910, 161-4. »"Sphinx-Oedipe, Nancy, 5, 1910, 166. »"Proc. Indiana Acad. Sc, 1911, 257-270. *Amiable, agreeable, befreundete, verwandte.
Chap. I] PERFECT, MULTIPLY PERFECT, AND AMICABLE NUMBERS. 36
In the ninth century the Arab Thabit ben Korrah^° (prop. 10) noted that 2'*/i^ and 2"s are amicable numbers if
(1) /i = 3-2"-l, f=3-2"-i-l, s = 9'2^''-'-l
are primes > 2, literally, if
/l = 2+2^ t = z-2''-\ 3 = H-2+...+2^ s = (2"+^+2'*-2)2''+^-l.
The term used for amicable numbers was se invicem amantes. In the article in which F. Woepcke^'^ translated this Arabic manuscript into French, he noted that a definition of these numbers, called congeneres, occurs in the 51st treatise (on arithmetic) of Ikhovan Algafa, manuscript 1105, anciens fonds arabes, p. 15, of the National Library of Paris.
Among Jacob's presents to Esau were 200 she-goats and 20 he-goats, 200 ewes and 20 rams (Genesis, XXXII, 14). Abraham Azulai^^^ (1570- 1643), in commenting on this passage from the Bible, remarked that he had found written in the name of Rau Nachshon (ninth century A. D.): Our ancestor Jacob prepared his present in a wise way. This number 220 (of goats) is a hidden secret, being one of a pair of numbers such that the parts of it are equal to the other one 284, and conversely. And Jacob had this in mind; this has been tried by the ancients in securing the love of kings and dignatories.
Ibn Khaldoun^^° related "that persons who have concerned themselves with talismans affirm that the amicable numbers 220 and 284 have an influence to establish a union or close friendship between two individuals. To this end a theme is prepared for each individual, one during the ascend- ency of Venus, when that planet is in its exaltation and presents to the moon an aspect of love or benevolence; for the second theme the ascendency should be in the seventh. On each of these themes is written one of the specified numbers, the greater (or that with the greater sum of its aliquot parts?) being attributed to the person whose friendship is sought."
The Arab El Madschriti,^^! or el-Magriti, (flOOT) of Madrid related that he had himself put to the test the erotic effect of ''giving any one the smaller number 220 to eat, and himself eating the larger number 284."
Ibn el-Hasan^"'' (tl320) wrote several works, including the "Memory of Friends," on the explanation of amicable numbers.
Ben Kalonymos^^^^ discussed amicable numbers in 1320 in a work written for Robert of Anjou, a fragment of which is in Munich (Hebr. MS. 290, f. 60). A knowledge of amicable numbers was considered necessary by Jochanan Allemanno (fifteenth century) to determine whether an aspect of the planets was friendly or not.
^^^Baale Brith Abraham [Commentary on the Bible], Wilna, 1873, 22. Quotation suppUed by
Mr. Ginsburg. '^oProlegomenes hist. d'Ibn Khaldoun, French transl. by De Slane, Notices et Extraits des
Manuscrits de la Bibl. Imperiale, Paris, 21, I, 1868, 178-9. "^'Manuscript Magriti; Steinschneider, Zur pseudoepigraphischen Literatur inbesondere der
geheimen Wissenschaften des Mittelalters, Berlin, 1862, p. 37 (cf. p. 41). '""H. Suter, Abh. Gesch. Math. Wiss., 10, 1900, 159, § 389. »"*Hebr. Bibl., VII, 91. Steinschneider, Zeitschrift der Morgenlandischen Ges., 24, 1870, 369.
|
5 |
11 |
23 |
47 |
|
2 |
4 |
8 |
16 |
|
6 |
12 |
24 |
48 |
|
71 |
287 |
1151 |
40 History of the Theory of Numbers. [Chap, i
Alkalacadi,^" a Spanish Arab (tl486), showed the method of finding the least amicable numbers 220, 284.
Nicolas Chuquet^^ in 1484 and de la Roche^^ in 1538 cited the amicable numbers 220, 284, "de merueilleuse familiarite lung auec laultre." In 1553, Michael StifeP^ (folios 26v-27v) mentioned only this pair of amicable num- bers. The same is true of Cardan, ^^ of Peter Bungus^- (Mysticae numerorum signif., 1585, 105), and of TartagUa.^^ Reference may be made also to Schwenter."
In 1634 Mersenne^"^ (p. 212) remarked that "220 and 284 can signify the perfect friendship of two persons since the sum of the aliquot parts of 220 is 284 and conversely, as if these two numbers were only the same thing."
According to Mersenne's^"^ statement in 1636, Fermat^^ found the second pair of amicable numbers
17296 = 2'.23.47, 18416 = 2^-1151,
and communicated to Mersenne^°^ the general rule: Begin with the geo- metric progression 2, 4, 8, ... , write the prod- ucts by 3 in the line below; subtract 1 from the products and enter in the top row. The bottom row is 6-12-1, 12-24-1,. . .When a mmiber of the last row is a prime (as 71) and the one (11) above it in the top row is a prime,
and the one (5) preceding that is also a prime, then 71.4 = 284, 5-11-4 = 220 are amicable. Similarly for
1151-16 = 18416, 23-47-16 = 17296,
and so to infinity. [The rule leads to the pair 2"/i<, 2'*s, where h, t, s are given by (1).]
Descartes^^^ gave the rule: Take (2 or) any power of 2 such that its triple less 1, its sextuple less 1, and the 18-fold of its square less 1 are all primes;* the product of the last prime by the double of the assumed power of 2 is one of a pair of amicable numbers. Starting with the powers 2, 8, 64, we get 284, 18416, 9437056, whose aliquot parts make 220, etc. Thus the third pair is
9363584 = 2^-191-383, 9437056 = 2"-73727.
Descartes^^^ stated that Fermat's rule agrees exactly with his own.
Although we saw that Mersenne quoted in 1637 the rule in Fermat's form and expressly attributed it to Fermat, curiously enough Mersenne^ ^^ gave in 1639 the rule in Descartes' form, attributing it to "un excellent Geometre" (meaning without doubt Descartes, according to C. Henry^"),
''^Manuscript in Biblioth^que Nationale Paris, a commentary on the arithmetic Talkhys of Ibn Albanna (13th cent.). Cf. E. Lucas, L'arithm^tique amusante, Paris, 1895, p. 64.
'"Quesiti et Inventione, 1554, fol. 98 v.
'^♦Oeuvres de Fermat, 2, 1894, p. 72, letter to Roberval, Sept. 22, 1636; p. 208, letter to Frenicle, Oct. 18, 1640.
»^euvre8 de Descartes, 2, 1898, 93-94, letter to Mersenne, Mar. 31, 1638. •Evidently the numbers (1) if the initial power of 2 be 2""^
"•Oeuvres de Descartes, 2, 1898, 148, letter to Mersenne, May 27, 1638.
"'Bull. Bibl. Storia So. Mat. e Fis., 12, 1879, 523.
Chap. I) PERFECT, MULTIPLY PERFECT, AND AmICABLE NUMBERS. 41
and derived as did Descartes the first three pairs of amicable numbers from 2, 8, 64. We shall see that various later writers attributed the rule to Descartes.
Mersenne^^ again in 1644 gave the above three pairs of amicable num- bers, the misprints in both^^^ of the numbers of the third pair being noticed at the end of his book, and stated there are others innumerable.
Mersenne®^ in 1647 gave without citation of his source the rule in the form 2-2% 2-2"/i<, where 1 = 3-2'' -1, h = 2t+l, s = ht+h-i-t are primes [as in (1)].
Frans van Schooten,^^^ the younger, showed how to find amicable numbers by indeterminate analysis. Consider the pair 4a:, 4yz [x, y, z odd primes]; then
7+3a: = 4i/0, 7-\-7y+7z+Syz = 4x.
Eliminating x, we get 2 = 34-16/(2/ — 3). The case ^ = 5 gives 2;= 11, ^' = 71, yielding 284, 220. He proved that there are none of the type 2x, 2yz, or 8x, Syz, and argued that no pair is smaller than 284, 220. For 16.x, 16yz, he found 2=15-l-256/(i/ — 15), which for y = 47 yields the second known pair. There are none of the type 32a;, S2yz, or type 64a:, Myz. For 128a:, 1281/2, he got 2= 127-^16384/(1/ -127), which for 2/ = 191 yields the third known pair. Finally, he quoted the rule of Descartes.
W. Leyboum^^ stated in 1667 that ''there is a fine harmony between these two numbers 220 and 284, that the aliquot parts of the one do make up the other . . . and this harmony is not to be found in many other numbers."
In 1696, Ozanam''^ gave in great detail the derivation of the three known pairs of "amiable" numbers by the rule as stated by Descartes, whose name was not cited. Nothing was added in the later editions.'^' ^^
Paul Halcke^^" gave Stifel's^^ rule, as expressed by Descartes.^^^
E. Stone^^^ quoted Descartes' rule in the incorrect form that 2^''pq and 3-2"p are amicable if p = 3-2'*— 1 and g = 6-2'*— 1 are primes.
Leonard Euler^^^ remarked that Descartes and van Schooten found only three pairs of amicable numbers, and gave, without details, a fist of 30 pairs, all included in the later paper by Euler.^^^
G. W. Kraft^^^ considered amicable numbers of the type APQ, AR, where P, Q, R are primes not dividing A. Let a be the sum of all the divi- sors of A . Then
R+1 = {P+1){Q+1), {R-{-l)a = APQ-^AR.
Assuming prime values of P and Q such that the resulting R is prime, he sought a number A for which A /a has the derived value. For P = 3, Q = 1 1 ,
"'Not noticed in the correction (left in doubt) in Oeuvres de Fermat, 4, 1912, p. 250 (on pp.
66-7). One error is noted in Broscius*^, Apologia, 1652, p. 154. "'Exercitationum mathematicarum libri quinque, Ludg. Batav., 1657, liber V : sectiones triginta
miscellaneas, sect. 9, 419-425. Quoted by J. Landen.*^ ""Deliciae Mathematicae, oder Math. Sinnen-Confect, Hamburg, 1719, 197-9. *"New Mathematical Dictionary, 1743 (under amicable) . "'De numeria amicabilibus. Nova Acta Eruditorum, Lipsiae, 1747, 267-9; Comm. Arith. Coll.,
II, 1849, 637-8. -•»Novi Comm. Ac. Petrop., 2, 1751, ad annum 1749, Mem., 100-18.
42 History of the Theory of Numbers. [Chap, i
then A:a = S:5; he took A = 3B, S^B, 3^5, but found no solution. For p = 5, Q = 41, we have 72 = 251, 38A = 21a; set A = 495, whence 3-576 = 38-75, where b is the sum of the divisors of B; set B = 9C, whence C:c = 13:14, C=13, yielding the amicable numbers 5-41A., 251A, where A = 3^-7213 = 5733 [the pair VII in Euler's^'^^ ijgt and (7) in the table below]. Again, to make A/a = 3/8, set A = 35, whence a = 46 and the condition is 6 = 25, whence 5 is a perfect number prime to 3. Using 5 = 28, we get A = 84. For use in such questions, Kraft gave a table of the sum of the divisors of each number^ 150. He quoted the rule of Descartes.
L. Euler^*^^ obtained, in addition to two special pairs, 62 pairs [including two false pairs] of amicable numbers of the type am, an, in which the common factor a is relatively prime to both vi and n. He wrote jm for the sum of all the divisors of m. The conditions are therefore
jm=jn, fa-jm = a{m-{-n).
If m and n are both primes, then 7n = n and we have a repeated perfect number. Euler treated five problems.
(1) Euler's problem 1 is to find amicable numbers apq, ar, where p, q, r, are distinct primes not dividing the given number a. From the first con- dition we have r = xy — \, where x — p-\-\, y = q-\-\. From the second,
xyi a = a{2xy —x — y).
Let a/{2a— \a) equal 6/c, a fraction in its lowest terms. Then
y = bx/{cx — b), {cx — b){cy — b)=b^.
Thus x and y are to be found by expressing 6^ as a product of two factors, increasing each by 6, and dividing the results by c.
(li) Fu-st, takea = 2". Then6 = 2^ c=l, x, 2/ = 2"**+2^ Letri-A; = m. Then
p = 2"»(22*=+2*)-l, g = 2'"(l+2*)-l, r = 2^"'(2^''+^+2^''+2'')-l.
When these three are primes, 2"*"^^'^^ and 2'"''"^ are amicable. Euler noted that the rule communicated by Descartes to van Schooten is obtained by taking A:= 1, and stated that 1, 3, 6 are the only values ^ 8 of m which yield amicable numbers (above^^^). For k = 2 or 4, Euler remarked that r is divisible by 3; for k = 3, vi<Q, and for k = 5, mS2, p, q, or r is composite.
(I2) Take a = 2J, where /=2"+^+e is a prune. Then 2a-fa = e+l. If e+1 divides a, we have c = l. Set e+ 1 = 2^, A;^?n, n = m+A:. Then
/=2*(2'"+^ + l)-l, a = 2"'+i, 6 = 27, b""={x-b){y-b).
For k = l, /=2'"+2+l is to be a prime, whence m+2 is a power of 2. If w = 0, 6=/=5, and either x = y, p = q; or x, y = Q,30; p, q = 5, 29, whereas p and q are to be distinct and prime to 10. If m = 2, /=17, 68^ is to be resolved into distinct even factors; in the four resulting cases, p, q, r are
'"De numeris amicabilibus, Opuscula varii argumenti, 2, 1750, 23-107, Berlin; Comm. Arith., 1, 1849, 102-145. French transl. in Sphinx-Oedipe, Nancy, 1, 1906-7, Supplement I-LXXVI.
Chap. I] PERFECT, MULTIPLY PERFECT, AND AMICABLE NUMBERS. 43
not all prime. In the next case w = 6, /=257, Euler examined only the case* x — 6 = 2^-257, finding q composite.
For A; = 2, Euler excluded m = 1, 3 [m = 4 is easily excluded].
(13) For k^n in (I2), 0 = 2*", where m = k—n. Then
6 = 2"+i+2"'+"-l=/ must be a prime. Thus we must take as the factors of 6^
2'"x-6 = l, 2"'2/-fe = 62,
whence z = 2" +2"+^"'", y-=hx. If m = 1, one of
/=2'»+2-l, p = 2^+'-l
has the factor 3 and yet must be a prime; hence n=l, g = 27. If m = 2, Euler treated the cases n^5 and found (for n = 2) the pair (4) of the table. [For 6^n^l7, / or p is composite.] For m odd and >1, / or p has the factor 3. For m = 4, n^ 17, no solution results.
(14) For a = 2"(gr— l)(/i — 1), where the last two factors are prime, set d = 2a-fa. Then
ig - 2^*+^) {h - 2^^+^) =d- 2"+^ + 2^""+^ Euler treated the cases n^3, d = 4, 8, 16, finding only the pair (9).
(15) Special odd values of a led (§§56-65) to seven pairs (5)-(8), (11)-(13). The cases a = 3^.5, 32-72-13-19 were unfruitful.
(2) Euler's problem 2 is to find amicable numbers apq, ars, where p, q, r, s are distinct primes not dividing the given number a. Since jP'j2 — ['>''] s, we may set
p = ax — l, q = ^y — l, r = /3x — 1, s = ay — l.
We set fa:a = 2b—c:h, where b and c are relatively prime. The second condition fa- fpq = a{pq+rs) gives
ca/3x2/ = 6(a+iS) (x+2/) -26. Multiply it by ca^. Then
[ca^x-h{a+^)][ca^y-b(a+^)] = h\a+^y-2hca^. Given a, ^, a and hence b, c, we are to express the second member as a prod- uct of two factors and then find x, y.
For a = l, i3 = 3, 0 = 2^ Euler obtained the pairs (a), (28). For a = 2, ^ = 3, a = 32-5-13, he got (32); for a = l, /3 = 4, a = 3^-5, (30). The ratio a:^ may be more complex, as 5 :21 or 1 :102, in (7). As noted by K. Hunrath,^^^* the numbers (7) are not amicable. Nor are the ratios as given, although these ratios result if we replace 8563 by 8567 = 13-659. This false pair occurs as XIII in Euler's^^^ list.
(3) Problem 3 is derived from problem 2 by replacing s by a number / not necessarily prime. Let h be the greatest common divisor of ff=hg andp+l = ^x. Thenr-{-l=xy, q-{-l = gy. Also
ghxyfa=f{afr)=a(pq+fr)^a\{hx-l){gy-l)+f{xy-l)\.
*A11 the remaining cases are readily excluded. "♦"BibUotheca Math., (3), 10, 1909-10, 80-81.
44 History of the Theory of Numbers. [Chap, i
Multiply by 6/a and replace bja by 2ab — ac [see case (1)]. Thus exy — bhx — hgy = b{f—l), e=bf—bgh-{-cgh.
Thus L^b'^gh+be{f—l) is to be expressed as the product PQ of two factors and they are to be equated to ex—bg, ey — bh. The case a = 2 is unfruitful. (3i) Let a = 4. Then 6 = 4, c = l, e = 4/— 3^/i. The case/= 3 is excluded since it gives e = 0. For/ =5, g = 2, h = S, we again get (a) and also (j3). For/=5, ^ = 1, h = 6, we get only the same two pairs. For a prime /^ 7, no new solutions are found. For /= 5-13, (51) results.
(32) Let a = 8, whence 6 = 8, c = L The cases /= 11, 13 are fruitless, while /= 17 yields (16). The least composite/ yielding solutions is 11-23, giving (44), (45), (46). This fruitful case led Euler to the more convenient notations (§88) M = hP, N = gQ, L = PQ. The problem is now to resolve L ff into two factors, Af , N, such that
M+bff N+bff
are integers and primes, while in r+1 = {p+l){q+l)/jf, r is a prime.
(33) Let a = 16. For/=17, we obtain the pairs (21), (22); for/=19, (23); for/=23, (17), (19), (20); for/=47, (18); for/= 17-167, (49). Cases /=31, 17-151 are fruitless [the last since 129503 has the factor 11, not noticed by Euler].
(34) For a = 3^-5 or 32.7-13, 6 = 9, c = 2; the first a with/=7 yields (30).
(4) Problem 4 relates to amicable numbers agpq, ahr, where p, q, r are primes. Eventually he took also g and h as primes. We may then set g-\-l — km, h-\-\ = kn. For m = \, n = 3, a = 4 or 8, no amicables are found. Form = 3, n = l, the cases a =10, A: = 8 and a = 3^-5, ^' = 8, yield (38), (55).
(5) Euler's final problem 5 is of a new type. He discussed amicable numbers zap, zbq, where a and 6 are given numbers, p and q are unknown primes, while z is unknown but relatively prime to a, 6, p, q. Set JoM 6 = m:n, where m and n are relatively prime. Since(p-fl)j a = (54-l)j6, we may set p-\-\=^nx, q-{-\=mx. The usual second condition gives
r r / K 7 / ^ — nxfa
nx\a'{z = za{nx — l)-j-zb{mx — l), C —-, 1^ r*
■^ -^ j^ {na-\-mb)x — a — b
Let the latter fraction in its lowest terms be r/s. Then z = kr, jz = k$. Since f{kr)'^kCr, we have s'^ff. Hence we have the useful theorem: if z:Cz = r':s', s'<\r', then r' and s' have a common factor > 1.
(5i) The unfruitful case a = 3, 6 = 1, was treated like the next.
(52) Let 0 = 5, 6=1, whence w = 6, n = l, 2:J z = 6a::llx — 6. By the theorem in (5), x must be divisible by 2 or 3. Euler treated the cases x = 3(3^+1), x = 2{2t+\). But this classification is both incomplete and
Chap. I] PERFECT, MULTIPLY PERFECT, AND AMICABLE NUMBERS.
45
overlapping. Since p = x — l is to be prime, x is even (since a; = 3 makes z divisible by p = 2) . Hence x = 2P,z:fz = QiP:llP—S. By the theorem in (5) , QP and IIP — 3 have a common factor 2 or 3, so that P is either odd or divis- ible by 6. For P = Ql, the ratio is that of 126 to 22Z — 1 , which as before must have the common factor 3, whence l = 3t-\-l. Then z:fz = 4:{St-{-l) :22t-\-7, a ratio of relatively prime numbers, whence 22t+7'^f 4(31+1), and hence t = 2k, k = 0 or k>3. For A; = 0, we obtain the pair 220, 284. The next value >3 of A; for which p = x — l and q = Qx—l are primes is k = Q, giving p = 443, g = 2663, numbers much larger than those in the (unnecessary) cases treated by Euler. Then z:jz = 4-37:271; set z = S7''d, d not divisible by 37; the cases e = 1, 2, 3 are excluded by the theorem in (5). For the remaining case P odd, P = 2Q-\-l, Euler treated those values ^100 of Q, and also Q = 244, for which p and q are primes and obtained the pair in (I3), two pairs in (I5), and (14), (15).
(53) Euler treated in §§112-7 various sets a, b, and obtained (a) and nine new pairs given in the table.
In the following table of the 64 pairs of amicable numbers obtained by Euler, the numbering of any pair is the same as in Euler's list, but the pairs have been rearranged so that it becomes easy to decide if any proposed pair is one of Euler's. As noted by F. Rudio,^^^'' (37) contained the mis- print 3^ for 3^, w^hile (7) and (34) are erroneous, 220499 being composite (311-709); he checked that all other entries are correct.
(4) 22-23{^27^^
(9) 2M3.17{3||09
(47) 23/11-29-239 ^*'^ "^ 1191449
^4»; ^ \29-47-59
(21) 2417'5119
(^)2^{83lo39(f-l««)
(18) 2^{i:?^
(27) o«/79- 11087 ^^^^ ^ \383-2309
(37) s^-sgi'ig''
(15) 32.7-13-4M63< (35) 32.5.19{7^227
5-977 5867
(38) 2-5{7:
(a)22
60659 23-29-673 5-131 17-43
^•' ^ 1647-719
(43) 2' (60)
11-59-173 47-2609 2^-19-41 26-199 (oo\ 94/17-10303
(2) 2^
[23-47 \1151
(19) 2^{i:t2?
(25) 2»P-12671 K^Q) z ^227-2111
,3. 27/191-383
(5) 32-7-13[
(14) 32-72-13-97
5-17 107
5193 1163
(8) 3^-5-7{i?2S
251 107
(1) 22{^jll
i3) 2^(^32
,45. 23(ll-23-1871 V4^) ^ \467-1151
.4Q. 23/11-163-191 ^4u; z 131.11807
,r.,. /23-41-467 ^^^1 \25-19-233
(23) 2^{}9gl439
(50) 2423-47-9767 \tM) z |i583.7io3
,17s 24/23-1367 ^^'^ "^153-607
(26) 2^{^|JJ^f
/90X r,8/383-9203 K^-6) z |ii5i.3067
(7) 32-72-13{|5Y (10) 32-5- 19-37 (710^ (6) 3^-5-13gl9l9
(51) 2^^^^
•131187 -2267 (29) 2^-ll{17:263
,,,. 23/11-23-2543 ^**^ ^ 1383-1907
(16) 2^(M:^^
(49) 24/17-167-13679 KV6) z I809.51071
(36) 2^-67{|72411
.24) 26/59-1103 (.Z4J L J79.827
{b2)Z^-l-\Z^^lll]f
'"^Bibliotheca Math., (3), 14, 1915, 351-4.
46 History of the Theory of Numbers. [Chap, i
(31) S^-5'13{ll:]f (54) 3«.5^{}1:^9.179 ^g^ ^,_^_^^,^^l29.5m
(33) 33.5.13.19^/2711 (32) 3^-5-13{^^:^J (12) S^.r-lVlsl^lf^^'
(41)33.7.13.23|JJ;1%367 ^g^^ 3,.-,. ^g.^gjl 1-220499 ^^^^^^
(30) 33.5{[7^1j (55) ■S^-5{',lll%^ (42) 33.5.23(11 -.J^SIT
(11) 3^.5.1l{29g89 (56) 3^.7.11M9{g97019 (57)3^.7.11M9{^3^6959^
(53) 3».7M3.53{ll4211 (53) 3s.7M3.19{4™19 (59^ 3^.7M3.19{53g6959^
Euler's final list of 61 pairs did not include the pairs a, jS, 7, although he had obtained a four times in the body of his paper, viz., in (2), (3i), (63); jS twice in (3i); 7 in (2). Moreover, these three unlisted pairs occur as VIII, IX, and XIII among the 30 pairs in Euler's^^^ earlier list, a fact noted on p. XXVI and p. LVIII of the Preface by P. H. Fuss and N. Fuss to Euler's Comm. Arith. Coll., who failed to observe that these three pairs occur in the text of Euler's present paper. Nor did these editors note that the fourth mentioned case of divergence between the two lists is due merely to the misprint^^^'' of 57 for 47 in (43) of the present list, so that the correctly printed pair XXVIII of the list of 30 is really this (43) and not a new pair, as supposed by them.
From the fact that Euler obtained in his posthumous tract®^ on amicable numbers the pairs a, jS (once on p. 631 and again on p. 633 and finally on p. 635), the editors inferred, p. LXXXI of the Preface, that the tract differs in analysis from the long paper just discussed. But no new pairs are found, while the cases treated on pp. 631-2 are merely problems 1 and 2 of Euler's preceding paper. It is different with p. 634, where Euler started with two numbers like 71 and 5-11 which, by his table, have the same sum, 72, of divisors, and required a number a relatively prime to them such that 71a and 55o are amicable. The single condition is 72J a=(71+55)o, whence ja:a = 7A. Thus a has the factor 4. If a = 46, where b is odd, then Ch = h = l, and the pair 284, 220 results. The case a = 86 is impossible. This method was used in a special way by Kraft^^^ who limited the numbers from which one starts to a prime and a product of two primes.
In the Encyclopedie Sc. Math., I, 3i, p. 59, note 320, it is stated that this posthumous tract contains four pairs not in Euler's list of 61, two pairs being those of Fermat^^^ and Descartes.^^^ But these were fisted as (2) and (3) by Euler and were obtained by him in case (li) and attributed to Descartes.
E. Waring^^^ noted that 2'*x, 2''yz are amicable if
2"'?/z_2"+^ + l 2^"
2"-l ' i/-2"+l
where x^ y, z are primes and ?/ — 2"H-1 divides 2^**. He cited the first two such pairs of amicable numbers.
3"«G. Enestrom, Bibliotheca Math., (3), 9, 1909, 263. 3«*Meditationes algebraicae, 1770, 201; ed. 3, 1782, 342-3.
Chap. I] PERFECT, MULTIPLY PERFECT, AND AmICABLE NUMBERS. 47
The first three pairs were given in an anonymous work.^^®
In 1796, J. P. Gruson^°° (p. 87) gave the usual rule (1) leading to the three first known amicable pairs (verwandte Zahlen).
A. M. Legendre^^^ attributed the rule (1) to Descartes.
G. S. KliigeP^^ gave a process leading to the choice of P and Q, left arbitrary by Kraft.^^^ ^^ ^ave A:a = R+l:PQ-\-R = 2R-P-Q. Thus P-(-Q= \R{2A—a)—a\ /A, while PQ is given by Kraft's second equation. Hence P and Q are the roots of a quadratic equation. For example, if
A = 4, then
8P, SQ = R-7±VR^-Q2R-QS.
The positive root of a;^ — 62a: — 63 = 0 lies between 60 and 61. Thus we try primes ^ 61 for R, such that i^ — 7 is divisible by 8. The first available R is 71, giving P=ll, Q — 5 and the amicable pair 220, 284. In general, the quantity a^R^+2^R-\-y under the radical sign can be made equal to the square of ai^+P ip arbitrary) by choice of R.
John Gough^^^ considered amicable numbers ax, ayz, where x, y, z are distinct primes not dividing a. Let q be the sum of the aliquot divisors
of a. Then
a+q-\-qx = ayz, x+l = {y+l){z+l).
If q^a/i, the first gives ayz< (l+a:)a/4, while 2y-2z>x-\-l by the second, Thusg'>a/4. Let a = r", where r is a prime > 1 . Then Q'=(a — l)/(r' — 1), which with g>a/4 implies a(5— r)>4, r = 2 or 3. He proved that Tt^S. whence r = 2, the case treated by van Schooten.^^^
J. Struve^^^ cited his Osterprogramm, 1815, on amicable numbers.
A. M. Legendre^^° discussed the amicable numbers of the type (li) of Euler^^^ (with Euler's m, k replaced by m—iJi,,fx). Legendre noted that r = 2^'""''^ (2*^+1)^ — 1 is of the form s^ — 1 and hence composite, if k is even; also that, if A: = 3, p = 9-2'"+3-l, g = 9-2"'-l, one of which is of the form s^ — 1. He considered the new case k = 7 and found for m = l that p = 33023, q = 257, r = 8520191, stating that if r be a prime we have the amicable num- bers 2^pq, 2V. This is in fact the case.^^^ For ^ = 1, we have the ancient rule (1); he proved that for n^l5 it gives only the known three pairs of amicable numbers.
Paganini^'^^, at age 16, announced the amicable numbers 1184 = 2^37, 1210 = 2.5.11"^, not in the list by Euler^^'*, but gave no indication of the method of discovery.
^^'EncyclopMie methodique. . .Amusemens des Sciences Math, et Phys., nouv. 6d., Padoue, 1793, I, 116. Cf. Les amusemens math., Lille, 1749, 315.
»"Th6orie des nombres, 1798, 463.
«8Math. Worterbuch, 1, 1803, 246-252 [5, 1831, 55].
«»New Series of the Math. Repository (ed., Th. Leyboum), vol. 2, pt. 2, 1807, 34-39. He cited Button's Math. Diet., article Amicable Numbers, taken from van Schooten^^'.
""Theorie des nombres, ed. 3, 1830, II, §472, p. 150. German transl. by H. Maser, Leipzig, 1893, II, p. 145.
"iTchebychef, Jour, de Math., 16, 1851, 275; Werke, 1, 90. T. Pepin, Atti Ace. Pont. Nuovi Lincei, 48, 1889, 152-6. Kraitchik, Sphinx-Oedipe, 6, 1911, 92. Also by Lehmer's Fac- tor Table or Table of Primes.
'"B. Nicol6 I. Paganini, Atti deUa R. Accad. Sc. Torino, 2, 1866-7, 362. Cf. Cremona's Ital. transl. of Baltzer's Mathematik, pt. III.
48 History of the Theory of Numbers. (Chap, i
P. Seelhoff^^^ treated Euler's^^ problems 1 and 2 by Euler's methods (though the contrary is implied), and gave about 20 pairs of amicable numbers due to Euler, with due credit for only three pairs. The only new- pairs (pp. 79, 84, 89) are
Q2721Q in oQf83-1931 ^ef 139-863
6 i A^-Ay'^'^|i62287 "^1167.719.
E. Catalan^^^ stated empirically that if ??i is the sum of the divisors <n of n, and n2 is the sum of the divisors <ni of ?ii, etc., then n, nj, n2, . . . have a limit X, where X is unity or a perfect number.
J. Perrott"^ [Perott] noted that there is no limit for n = 220, since
^1 = 713= . . . =284, n2 = n4= . . . =220.
H. LeLasseur^^*^ found that for n< 35 the numbers (1) are all odd primes, and hence give amicable numbers, only when n = 2, 4, 7.
Josef Bezdicek^^^ gave a translation into Bohemian of Euler,^^ without credit to Euler, and a table of 65 pairs of amicable numbers.
Aug. Haas"^ proved that, if M and A^ are amicable numbers,
l/S-+l/si=l, m n
where m and n range over all divisors of M and iV, respectively. For,
2w = Sn = M+iV, so that
m~ M ~ M ' n~ N ~ N
If M = N, N is perfect and the result becomes that of Catalan. ^"'^
A. Cunningham^'^ considered the sum s{n) of the divisors <n of ?i and wrote s^{n) for s]s(??)}, etc. For most numbers, s^(n) = l when A; is suffi- ciently large. There is a small class of perfect and amicable numbers, and a small class of numbers n (even when n< 1000) for which s''{n) increases beyond the practical power of calculation [cf. Catalan^'^].
A. Gerardin^^" proved that the only pairs 2^-5a;, 2-yz of amicable num- bers, where x, y, z are odd primes, are Euler's (a), (^3) ; the only pairs 2*-23x, 2^yz are Euler's (17), (19), (20). He cited the Exercices d'arithm^tique of Fitz-Patrick and Chevrel; also Dupuis' Table de logarithmes, which gives 24 pairs of amicable numbers.
G^rardin^^^ proved that the only pair Sxy, S2z is Euler's (60). He made an incomplete examination of 16-53a;, IQyz, but found no new pairs.
3"Archiv Math. Phys., 70, 1884, 75-89.
"*Bull. Soc. Math. France, 16, 1887-8, 129. Mathesis, 8, 1888, 130.
'"76id., 17, 1888-9, 155-6.
"•Lucas, Theorie dcs nombres, 1, 1891, 381.
"'Casopis mat. a fys., Praze (Prag), 25, 1896, 129-142, 209-221.
"8/6id., 349-350.
"«Proc. London Math. Soc, 35, 1902-3, 40.
""Matheshs, 6, 1906, 41^4.
"'Sphinx-Oedipe, Nancy, 1906-7, 14-15, 53.
Chap. I] PERFECT, MULTIPLY PERFECT, AND AmICABLE NUMBERS. 49
G^rardin^^^ proved that the three numbers (1) with n = m-f 2 are not all primes if 34< m^ 60, the cases m = 38 and 53 not being decided. Replacing m by m+1 and A; by 2^+1 in case (li) of Euler^^'*, we get the pair 2"pg, 2"r, where n = m+2g-]-2,
p = 2"*+2''+^P-l, 5 = 2"*+^P-l, ^ = 22'"+2''+3p2_i^
with P = 2^^'*"^ + l. For 9^ = 0, we have the case (1) just mentioned; all values m^200 are excluded except m = 38, 74, 98, 146, 149, 182, 185, 197. The case gr= 1 is excluded since i/ or 2 is a difference of two squares. For g = 2, all values m ^ 60 are excluded except m= 29, 34, 37, 49. For g = 3, all values <100 are excluded except m = 8, 15, 23, 92.
0. Meissner,^^^ using the notation of Cunningham,^^^ noted that n and s{n) are amicable if s^(n)=n and raised the question of the existence of numbers n for which s''{n)—n for k^S, so that n, s{n),. . .,s*~^(n) would give amicable numbers of higher order. He asked if the repetition of the operation s, a finite number (k) of times always leads to a prime, a perfect or amicable number; also if k increases with n to infinity. On these ques- tions, see Dickson^^^ and Poulet.^^^
A. Gerardin^^^ stated that the only values n<200 for which the numbers (1) are all primes are the three known to Descartes.
L. E. Dickson^^^ obtained the two new pairs of amicable numbers
2*-12959-50231, 2*- 17- 137-262079; 2*- 10103-735263, 2^-17-137-2990783,
by treating the type IQpq, 16-17-137r, where p, q, r are distinct odd primes. These are amicable if and only if
p = m+9935, g = w+9935, r = 4(w+n) +88799, wn = 2^3*7-23-73.
Although Euler^^ mentioned this type (33) in §95, he made no discussion of it since r always exceeds the limit 100000 of the table of primes accessible to him. An examination of the 120 distinct cases led only to the above two amicable pairs.
Dickson^^® proved that there exist only five pairs of amicable numbers in which the smaller number is <6233, viz., (1), (a), (^), (60) in Euler's^^* table, and Paganini's^^^ pair. In the notation of Cunningham,^^^ the chain n, s{n), s^{n), . . .is said to be of period k if s^(n) =n. The empirical theorem of Catalan'^* is stated in the corrected form that every non-periodic chain contains a prime and verified for a wide range of values of n. In particular, if n<6233, there is no chain of period 3, 4, 5, or 6. For k odd and > 1, there is no chain arii, an2, . . . , aUk of period k in which /ii, . . . , n^ have no common factor and each rij is prime to a> 1.
'^^Sphinx-Oedipe, 1907-8, 49-56, 65-71 ; some details are inaccurate, but the results correct. 'S'Archiv Math. Phys., (3), 12, 1907, 199; Math.-Naturw. Blatter, 4, 1907, 86 (for k=3). '** Assoc, frang. avanc. sc, 37, 1908, 36-48; I'intenn^diaire des math., 1909, 104. '8*Amer. Math. Monthly, 18, 1911, 109. "•Quart. Jour. Math., 44, 1913, 264-296.
50 History of the Theory of Numbers. [Chap, i
P. Poulet'^' discovered the chain of period five,
71 = 12496 = 24-11.71, s(n)= 2^- 1947, s\n) = 2^-967, s\n) =2^-23-79,
sHn) =2^.1783,
with s^{n) =n; and noted that 14316 leads a chain of 28 terms. Generalizations of Amicable Numbers.
Daniel Schwenter^^ noted in 1636 that 27 and 35 have the same sum of ahquot parts. Kraft^^^ noted in 1749 that this is true of the pairs 45, 3-29; 39, 55; 93, 145; and 45, 13-19. In 1823, Thomas Taylor^^^ called two such numbers imperfectly amicable, citing the pairs 27, 35; 39, 55; 65, 77; 51, 91; 95, 119; 69, 133; 115, 187; 87, 247. George Peacock^°o used the same term.
E. B. Escott^"^ asked if there exist three or more numbers such that each equals the sum of the [aliquot] divisors of the others.
A. G^rardin^°^ called numbers with the same sum of aliquot parts nombres associes, citing 6 and 25; 5-19, 7-17, and 11-13, and many more sets. An equivalent definition is that the n numbers be such that the product of n — 1 by the sum of the aliquot divisors of any one of them shall equal the sum of the aliquot divisors of the remaining n — 1 numbers.
L. E. Dickson^°^ defined an amicable triple to be three numbers such that the sum of the aliquot divisors of each equals the sum of the remaining two numbers. After developing a theory analogous to that by Euler^®* for amicable numbers, Dickson obtained eight sets of amicable triples in which two of the numbers are equal, and two triples of distinct numbers:
293-3370, 5- 16561a, 99371o (a = 25.3-13),
3-896, 11-296, 3596 (6 = 2i*.5-19-31-151).
^L'intermddiaire des math., 25. 1918, lOO-l. ♦""Encyclopaedia Metropolitana, London, I, 1845, 422. «"L'interm6diaire des math., 6, 1899, 152. ♦""Sphinx-Oedipe, 1907-8, 81-83. ♦MAmer. Math. Monthly, 20, 1913, 84-92.
CHAPTER II.
FORMULAS FOR THE NUMBER AND SUM OF DIVISORS. PROBLEMS OF
FERMAT AND WALLIS.
Formula for the Number of the Divisors of a Number.
Cardan^ stated that a product P oi k distinct primes has 1+2+2^+ . . -\-2^~'^ aUquot parts (divisors <P).
Michael StifeP proved this rule and found^ the number of divisors of 2*3^52p, where P = 7-11.13-17-19-23-29, by first noting that there are 1+2+ . . .+64 divisors <P oi P according to Cardan's rule and hence 128 divisors of P. The factor 5^ gives rise to 128+128 more divisors, so that we now have 384 divisors. The factor 3^ gives 3.384 more, so that we have 1536. Then the factor 2* gives 4.1536 more.
Mersenne* asked what number has 60 divisors; since 60 = 2-2-3-5, sub- tract unity from each prime factor and use the remainders 1, 1, 2, 4 as exponents; thus 3^-2*-7-5 = 5040 (so much lauded by Plato) has 60 divisors. It is no more difficult if a large number of aliquot parts is desired.
I. Newton^ found all the divisors of 60 by dividing it by 2, the quotient 30 by 2, and the new quotient 15 by 3. Thus the prime divisors are 1, 2, 2, 3, 5. Their products by twos give 4, 6, 10, 15. The products by threes give 12, 20, 30. The product of all is 60. The commentator J. Castillionei, of the 1761 edition, noted that the process proves that the number of all divisors of a'"6'*. . .is (m+l)(n+l) . . .if a, 6, . . .are distinct primes.
Frans van Schooten^ devoted pp. 373-6 to proving that a product of k distinct primes has 2'''— 1 aliquot parts and made a long problem (p. 379) of that to find the number of divisors of a given number. To find (pp. 380-4) the numbers having 15 aliquot parts, he factored 15+1 in all ways and subtracted unity from each factor, obtaining abed, a^bc, a%^, a^b, a^^. By comparing the arithmetically least numbers of these various types, he found (pp. 387-9) the least number having 15 aliquot parts.
John Kersey'^ cited the long rule of van Schooten to find the number of aliquot parts of a number and then gave the simple rule that Oi" . . . a^" has (6i+l) . . . (e„+l) divisors in all if ai, . . . , a„ are distinct primes.
John Wallis^ gave the last rule. To find a number with a prescribed number of divisors, factor the latter number in all possible ways; if the
iPractica Arith. & Mensurandi, Milan, 1537; Opera, IV, 1663.
*Arithmetica Integra, Norimbergae, 1544, lib. 1, fol. 101.
'Stifel's posthumous manuscript, fol. 12, preceding the printed text of Arith. Integra; cf. E. Hoppe, Mitt. Math. Gesell. Hamburg, 3, 1900, 413.
*Cogitata Physico Math., II, Hydravhca Pnevmatica, Preface, No. 14, Paris, 1644. (Quoted by Winsheim, Novi Comm. Ac. Petrop., II, ad annum 1749, Mem., 68-99). Also letter from Mersenne to Torricello, June 24, 1644, Bull. Bibl. Storia Sc. Mat., 8, 1875, 414-5.
•Arithmetica UniversaUs, ed. 1732, p. 37; ed. 1761, I, p. 61. De Inventione Divisorum.
•Exercitationum Math., Lugd. Batav., 1657.
^The Elements of Algebra, London, vol. 1, 1673, p. 199.
•A Treatise of Algebra, London, 1685, additional treatise, Ch. III.
61
52 History of the Theory of Numbers. [Chap, ii
factors are r, s, . . ., the required number is p''~^q'~^ . . ., where p, q,. . are any distinct primes. WTien the number of divisors is odd, the number itself is a square, and conversely. The number of ways A^ = a^b^ . . . can be expressed as a product of two factors is A = |(a+l)(j3+l) . . .or \-\-k, according as N is not or is a square.
Jean Prestet^ noted that a product of k distinct primes has 2'' divisors, while the ?ith power of a prime has n+1 divisors. The divisors of a^h^c^ are the 12 divisors of or}?, their products by c and by c^, the general rule not being stated explicitly.
Pierre R^mond de Montmort^° stated in words that the number of divisors of Oi**. . .a„*" is (ci+l) . . .(e„+l) if the a's are distinct primes.
Abb^ Deidier^^ noted that a product of k distinct primes has
^+^+(2) + (3)+ •
divisors, treating the problem as one on combinations (but did not sum the series and find 2*"). To find the number of divisors of 2*3^5^ he noted that five are powers of 2 (including unity). Since there are three divisors of 3^, multiply 5 by 3 and add 5, obtaining 20. In view of the two divisors of 5^, multiply 20 by 2 and add 20. The answer is 60.
E. Waring^- proved that the number of divisors of a"'?)". . .is (m+1) (n+1) . . .if a, 6, . . are distinct primes, and that the number is a square if the number of its divisors is odd.
E. Lionnet^^ proved that if a, b, c, . . .are relatively prime in pairs, the number of divisors of abc. . .equals the product of the number of divisors of a by the number for b, etc. According as a number is a square or not, the number of its divisors is odd or even.
T. L. Pujo^^ noted the property last mentioned.
Emil Hain^^ derived the last theorem from a"* = (<i . . . t„y, where <i, . . . , <„ denote the divisors of a.
A. P. Minin^^ determined the smallest integer with a given number of divisors.
G. Fontene'" noted that, if 2"3^. . .mV (a^/S^ . . . ^n^v) is the least number with a given number of di\4sors, then I'+l is a prime, and /x+1 is a prime except for the least number 2^3 ha\'ing eight di\'isors.
Formula for the Sum of the Divisors of a Number. '
R. Descartes,^^ in a manuscript, doubtless of date 1638, noted that, if p is a prim6, the sum of the aliquot parts of p" is (p"— l)/(p — 1). If 6 is the
"Nouv. Elemens des Math., Paris, 1689, vol. 1, p. 149.
loEssay d'analyse sur les jeux de hazard, ed. 2, Paris, 1713, p. 55. Not in ed. 1, 1708. "Suite de I'arithm^tique des g^om^tres, Paris, 1739, p. 311. i^Medit. Algebr., 1770, 200; ed. 3, 1782, 341. "Nouv. Ann. Math., (2), 7, 1868, 68-72. "Les Mondes, 27, 1872, 653-4. "Archiv Math. Phys., 55, 1873, 290-3. "Math. Soc. Moscow (in Russian), 11, 1883-4, 632. "Nouv. Ann. Math., (4), 2, 1902, 288; proof by Chalde, 3, 1903, 471-3. *'"De partibus ahquotis numerorum," Opuscula Posthuma Phys. et Math., Amstelodami, 1701, p. 5; Oeuvres de Descartes (ed. Tannery and Adams, 1897-1909), vol. 10, pp. 300-2.
23 3
13
Chap. II] FORMULAS FOR NUMBER AND SUM OF DiVISORS. 53
sum of the aliquot parts of a, the sum of the ahquot parts of ap is 6p+a+6. If b is the sum of the ahquot parts of a and if x is prime to a, the sum of the aUquot parts of ax"" is
— ^n — [=^'+^K-j^)-^^\'
Descartes^^ stated a result which may be expressed by the formula
(1) <j{nm)=(T{n)(T{m) (n, m relatively prime),
where (T{n) is the sum of the divisors (including 1 and n) of w. Here he solved n : (T(n) = 5 : 13. Thus n must be divisible by 5. Enter 5 in column A and (r(5) = 6 in column B. Then enter the factor A B 2 in column A and (r(2) =3 in column B. Having two threes in column B, we enter 9 in column A and cr(9) = 13 in B. Every 5 number except 13 in column B is in column A. Hence the 2 product 5-2-9 = 90 is a solution n. Next, to solve n : a- (n) = 5 : 14, 9 we enter also 13 in column A and 14 in B, and obtain the solu- tion 90-13. If ?i is a perfect number, 5n: (7(5n) = 5: 12 and, if n?^6, 15n: (r(15n) = 5:16.
Descartes^^ stated that he possessed a general rule [illustrated above] for finding numbers having any given ratio to the sum of their aliquot parts.
Fermat^^ had treated the same problem. Replying to Mersenne's remark that the sum of the aliquot parts of 360 bears to 360 the ratio 9 to 4, Fermat^^ noted that 2016 has the same property.
John Wallis^^ noted that Frenicle knew formula (1).
Wallis^^ knew the formula
(2) ^(a•6^...) = 211^1-*^^....
a— 1 0—1
Thus these formulae were known before 1685, the date set by Peano,^^ who attributed them to Wallis.^^
G. W. Kraft^^ noted that the method of Newton^ shows that the sum of the divisors of a product of distinct primes P, . . ., S is (P+1) . . .(S+1). He gave formula (1) and also (2), a formula which Cantor^" stated had probably not earlier been in print. To find a number the sum of whose divisors is a square, Kraft took PA, where P is a prime not dividing A. If (r(A)=a, then (r(PA) = (P-f-l)a will be the square of (P+l)5 if P =
^^"De la fagon de trouver le nombres de parties aliquotes in ratione data," manuscript Fonds- frangais, nouv. acquisitions, No. 3280, ff. 156-7, Bibliothfeque Nationale, Paris. Pub' Ushed by C. Henry, BuU. Bibl. Storia Sc. Mat. e Fis., 12, 1879, 713-5.
^Oeuvres, 2, p. 149, letter to Mersenne, May 27, 1638.
K)euvre8 de Fermat, 2, top of p. 73, letter to Roberval, Sept. 22, 1636.
"Oeuvres, 2, 179, letter to Mersenne, Feb. 20, 1639.
''^ommercium Epistolicum, letter 32, April 13, 1658; French transl. in Oeuvres de Fermat, 3, 553.
"Commercium Epist., letter 23, March, 1658; Oeuvres de Fermat, 3, 515-7.
"Formulaire Math., 3, Turin, 1901, 100-1.
"Novi Comm. Ac. Petrop., 2, 1751, ad annum 1749, 100-109.
"Geschichte Math., 3, 595; ed. 2, 616.
54 History of the Theory of Numbers. [ChapII
a/S^ — 1; for A = 14, take B = 2, whence P = 5. Again, the sum of the aUquot parts of 3P~ is (2+-P)^. The numbers AP and BPQ have the same sum of divisors if a(P+l) = 6(P+1)(Q+1), i. e., if Q = a/6-l; takmg a = 24, 6 = 6, we have Q = 3, a prime, .4 = 14, B = 5 (by his table of the sum of the divisors of 1,. . ., 150); this problem had been solved otherwise by Wolff."
L. Euler^^ gave a table of the prime factors of o-(p), a(p^), and <t(p^) for each prime p<1000; also those of aip") for various a's for p^23 (for instance, a ^36 when p = 2). He proved formulas (1) and (2) here and in his^ posthumous tract, where he noted (p. 514) all the cases in which a{n) =a-(?70 = 60.
E. Waring^2 proved formula (2). He^ noted that if P = arir. . .and Q = a'^h^ . . . , where m — a,n — ^,... are large, then a{PQ)/a{P) is just greater than Q. If A = {1-1)\, <t{IA)/(t{A)^1-^1. If a'br..=A and (x+l) (2/+ 1) . . . is a maximum, then a'"''"^ = 6""^^ = . . . For a, 6, . . . distinct primes, a{A) is not a maximum. He cited numbers with equal sums of divisors: 6 and 11, 10 and 17, 14 and 15 and 23.
L. Kronecker^^ derived the formulas for the number and sum of the divisors of an integer by use of infinite series and products.
E. B. Escott^^ listed integers whose sum of divisors is a square.
Problems of Fer\la.t and Wallis on Sums of Divisors.
Fermat'*^ proposed January 3, 1657, the two problems: (i) Find a cube which when increased by the sum of its aUquot parts becomes a square;* for example, 7^ + ( 1 + 7 + 7^) = 20^. (ii) Find a square which when increased by the sum of its aliquot parts becomes a cube.
John WalUs^^ replied that unity is a solution of both problems and pro- posed the new problem: (m) Find two squares, other than 16 and 25, such that if each is increased by the sum of its ahquot parts the resulting sums are equal.
Brouncker*^ gave 1/n^ and 343/n^ as solutions (!) of problem (i).
"Elementa Analyseos, Cap. 2, prob. 87.
«Opuscula varii argumenti, 2, Berlin, 1750, p. 23; Comm. Arith., 1, 102 (p. 147 for table to 100).
Opera postuma, I, 1862, 95-100. F. Rudio, Bibl. Math., (3), 14, 1915, 351, stated that
there are fully 15 errors. "Comm. Arith., 2, 512, 629. Opera postuma, I, 12-13. «Meditationea Algebr., ed. 3, 1782, 343. (Not in ed. of 1770.) "Vorlesungen iiber Zahlentheorie, I, 1901, 265-6. ^Amer. Math. Monthly, 23, 1916, 394.
*Erroneou8ly given as "cube" in the French tr., Oeuvres de Fermat, 3, 311. '"OeuvTes, 2, 332, "premier d6fi aux mathdmaticiens;" also, pp. 341-2, Fermat to Digby, June
6, 1657, where 7' is said to be not the only solution. These two problems by Fermat
were quoted in a letter by the Astronomer Jean H6v4hus, Nov. 1, 1657, pubhshed by C.
Henry, Bull. Bibl. Storia Sc. Mat. e Fis., 12, 1879, 683-5, along with extracts from the
Commercium EpistoUcum. Cf. G. Wertheim, Abh. Geschichte Math., 9, 1899, 558-561,
570-2 ( = Zeitschr. Math. Phys., 44, Suppl. 14). "Commercium Epistohcum de Wallis, Oxford, 1658; Walhs, Opera, 2, 1693. Letter II, from
WaUis to Brouncker, Mar. 17, 1657; letter XVI, Walhs to Digby, Dec. 1, 1657. Oeuvres
de Fermat, 3, 404, 414, 427, 482-3, 503-4, 513-5. **Commercium, letter IX, Wallis to Digby; Fermat'e Oeuvres, 3, 419.
Chap. II] PkOBLEMS ON SUMS OF DiVISORS. 55
Frenicle^^ expressed his astonishment that experienced mathematicians should not hesitate to present, for the third time, unity as a solution.
Wains'*^ tabulated <r{x^) for each prime a:<100 and for low powers of 2, 3, 5, and then excluded those primes a: for which (T(rc^)has a prime factor not occurring elsewhere in the table. By similar eliminations and successive trials, he was led to the solutions^^ of (i) :
a=3^5-lM3-41-47, 6=2-3-5-13-41-47; 7a, 7b,
adding that they are identical with the four numbers given by Frenicle.*'' Note that o-(a) is the square of 2^3^5-7-lM3-17-29-61, while a{b) is the square of 2^3V7-13-17-29. Wallis^^ gave the further solutions of a{x^) = y^:
a:=17-3147-191, ?/=2^°325-13-17-29-37,
2-3-5-13-17.314M91, 2^^33527. i3.;^7.29237^
3'5-lM3-17-31-4M91, 2'23^5-7-lM3-17-29237-61,
and the products of each x by 7.
Wallis^^ gave solutions of his problem (m) :
2^3.37, 2-19-29; 223-1M9-37, 2'7-29.67;
29-67, 2-3-5-37; 2^7.29.67, 3-5-1M9-37.
Frenicle*^ gave 48 solutions of WalUs' problem (m), including 2-163 11-37; 3-11-19, 7-107; 2-5-151, 3^-67; also 83 sets of three squares having the same sum of divisors, for example, the squares of
2^11.37-151, 3^67-163, 5-11-37-151, (7 = 3^7^19-31-67-1093;
also various such sets of n squares (with prime factors <500) for n^l9, for example, the squares of ac, ad, 4:bd, 46c, 5bd, and 56c, where
a = 2-5-29-47-67-139, 6 = 13-37-191-359, c = 7.107, d = 3-ll-19.
Frans van Schooten^" made ineffective attempts to solve problems (i), (n).
Frenicle^^ gave the solution
a: = 225-7.11-37-67-163-191-263-439-499, t/ = 327^3- 19-31^67- 109
of problem (n), a{x^)=y^; also a new solution of a{x^)=y^: a; = 255-7-31-73-241-243-467, i/ = 2i23253ii. 13217.37.41. 113.193.257.
^'Letter XXII, to Digby, Feb. 3, 1658. Cf. Leibnitii et BernouUii Commercium philos. et
math., I, 1795, 263, letter from Johann Bernoulli to Leibniz, Apr. 3, 1697. "Letter XXIII, to Digby, Mar. 14, 1658. "The same tentative process for finding this solution a was given by E.Waring, Meditationes
Algebraicae, 1770, pp. 216-7; ed. 3, 1782, 377-8. The solution 6 = 751530 was quoted
by Lucas, Thiorie des nombres, 1891, 380, ex. 3. **Solutio duorum problematum circa numeros cubos . . . 1657, dedicated to Digby [lost work].
See Oeuvres de Fermat, p. 2. 434, Note; WaUis." "Letter XXVIII, March 25, 1658; WaUis, Opera, 2, 814; Wallia". ««Letter XXIX, Mar. 29, 1658; WaUis^^. "Letter XXXI, Apr. 11, 1658. "Letter XXXIII, Feb. 17, 1657 and Mar. 18, 1658. "Letter XLIII, May 2, 1658.
56 History of the Theory of Numbers. [Chap, ii
Wallis^'^ for use in problem (ii) gave a table showing the sum of the divisors of the square of each number < 500. Excluding numbers in whose divisor sum occurs a prime entering the table only once or twice, there are left the squares of 2, 4, 8, 3, 5, 7, 11, 19, 29, 37, 67, 107, 163, 191, 263, 439, 499. By a very long process of exclusion he found only two solutions within the limits of the table, viz., Frenicle's" and
(rj(7.11-29.163-191439)2[ = ]3.7-13-19-31-67(^
Jacques Ozanam" stated that Fermat had proposed the problem to find a square which with its aliquot parts makes a square (giving 81 as the answer) and the problem to find a square whose aliquot parts make a square. For the latter, Ozanam found 9 and 2401, whose aliquot parts make 4 and 400, and remarked that he did not believe that Fermat ever solved these questions, although he proposed them as if he knew how.
Ozanam^ noted that the sum of 961 = 31^ and its aliquot parts 1 and 31 is 993, which equals the sum of the aliquot parts of 1 156 = 34". As examples of two squares with equal total sums of divisors [WaUis' problem (m)], he cited 16 and 25, 326^ and 407^, while others may be derived by multiplying these by an odd square not divisible by 5. The sum of all the divisors of 9^ is 11^ that of 20^ is 31l The numbers 99 and 63 have the property that the sum 57 of the aliquot parts of 99 exceeds the sum 41 of the aliquot parts of 63 by the square 16; similarly for 325 and 175.
E. Lucas^^ noted that the problem to find all integral solutions of
(1) l-\-x+z^-\-x^ = y^ is equivalent to the solution of the system
(2) l+x = 2w2, l+x2 = 2t;2, y = 2uv,
and stated that the complete solution is given by that of 2y^— x^ = l. E. Gerono^^ proved that the only solutions of (1) are
(x, 2/) = (-l, 0), (0, ±1), (1, ±2), (7, ±20).
E. Lucas^^ stated that there is an infinitude of solutions of Fermat's problem (i); the least composite solution is the cube of 2-3-5-13'41-47, the sum of whose divisors is the square of 2^3^5^7- 13- 17-29. [This solution was given by Frenicle.^®] For the case of a prime, the problem becomes (1).
A. S. Bang^^ gave for problem (i) the first of the three answers by Wallis;*' for (it), (7(43098^) = 1729^ for {in), 29-67, 2-3-5-37 of Wallis^* and the first two by Frenicle;^^ all without references.
"A Treatise of Algebra, 1685, additional treatises, Ch. IV.
"Letter to De Billy, Nov. 1, 1677, published by C. Henry, Bull. Bibl. Storia Sc. Mat. e Fia., 12,
1879, 519. Reprinted in Oeuvres de Fermat, 4, 1912, p. 140. "Recreations Math6matiques et Phys., new ed., 1723, 1724, 1735, etc., Paris, I, 41-43. "Nouv. Corresp. Math., 2, 1876, 87-8. ••Nouv. Ann. Math., (2), 16, 1877, 230-4. "Bull. Bibl. Storia Sc. Mat. e Fis., 10, 1877, 287. "Nyt Tidsskrift for Mat., 1878, 107-8; on problems in 1877, 180.
Chap. II] PROBLEMS ON SUMS OF DiVISORS. 57
E. Fauquembergue,^^ after remarking that (1) is equivalent to the sys- tem (2), cited Fermat's^" assertion that the first two equations (2) hold only for a: = 7 [aside from the evident solutions a: = ± 1, 0], which has been proved by Genocchi.^^
H. Brocard^^ thought that Fermat's assertion that 7^ is not the only solution of problem (i) implied a contradiction with Genocchi.^^ G. Vacca {ihid., p. 384) noted the absence of contradiction as (i) leads to equation (1) only if a: be a prime.
C. Moreau®^ treated the equation, of type (1),
While he used the language of extracting the square root of X = x*+ . . . written to the base x, he in effect put X={x^-\-a)^, 0<a<x. Then a^ = x+1, 2ax^ = x^-\-x^, whence 2a = a^, a = 2, x = 3, y = ll.
E. Lucas®^ stated that {x^-\-y^)/{x+y) =^ has the solutions
(3,-1, 11), (8, 11, 101), (123, 35, 13361),. . .
Moret-Blanc^^ gave also the solutions (0, 1, 1), (1, 1, 1). E. Landau^^ proved that the equation
— T=y^
x — 1 is impossible in integers (aside from x = 0, ?/ = =fc 1) for an infinitude of values of n, viz., for all n's divisible by 3 such that the odd prime factors of n/3, if any, are all of the form 6y— 1 (the least such n being 6). For, setting n = 3m, we see that y^ is the product of x^+x+1 and F = x^"'~^-{- . . . +a:^+l. These two factors are relatively prime since x^=l gives F=m (mod x^+ a: + 1 ) . Hence x^+x+lis Si square, which is impossible for a; f^ 0 since it lies between x^ and (a:+l)^.
Brocard^^ had noted the solution a: = 1, y=m, if n = mP.
A. Gerardin^^ obtained six new solutions of problem (i) :
a: = 2.47.193.239.701, 2/ = 2^3l5M3M7.97.149.
x = 2.5.23.41.83.239, y = 2\S\5\7.1S\29.53.
x = 3.13.23.47.83.239, y = 2^^3^517.13117.53.
X = 2.3.13.23.83.193.701, y = 2^3^5^7.13.17.53.97.149.
a; = 3.5.13.41.193.239.701, 2/ = 2^3l5l7.13M7.29.97.149.
a; = 2.5.13.43.191.239.307, ?/ = 2i^32.5MlM7.29.37.53.113.197.241.257.
Also <t{N^)=S^ for Ar = 3-7-ll-29-37, ^ = 3-7-13-19-67.
"Nouv. Ann. Math., (3), 3, 1884, 538-9.
'"Oeuvres, 2, 434, letter to Carcavi, Aug., 1659.
"Nouv. Ann. Math., (3), 2, 1883, 30&-10. Cf. Chapter on Diophantine Equations of order 2.
"L'intermMiaire des math., 7, 1900, 31, 84.
"Nouv. Ann. Math., (2), 14, 1875, 335.
»Ibid., 509.
«76id., (2), 20, 1881, 150.
"L'interm^diaire des math., 8, 1901, 149-150.
"Ibid., 22, 1915, 111-4, 127.
58 History of the Theory of Numbers. [Chap.ii
G^rardin^^ gave five new solutions of (i) :
X = 3.11.31.443.499, i/ = 2^3.5M3.37.61.157.
x = 2.3^31.443.449, 2/ = 2^3.5ni. 13.37.61.157.
a; = 1 1 . 17.41 .43.239.307.443.499,
2/ = 2^2 3^5'.7.11. 13^29^.37.61. 157. x = 2.11. 17.23.41.211.467.577.853,
t/ = 2^''.3^5l7.13M7.292.53.61. 113.193.197. x = 3ni. 13.23.83.193.701,
?/ = 293'537.11. 13.17.53.61.97.149, the last following from his*^^ fourth pair in \'iew of
a{SnV): a{2'S') = 2'3.nm^: 233.52 = 2=11-612; 5=.
A. Cunningham and J. Blaikie^^ found solutions of the form x = 2'p of s{x) =g^, where s{n) is the sura of the divisors <n of n.
product of aliquot parts.
Paul Halcke'^^ noted that the product of the aliquot parts of 12, 20, or 45 is the square of the number; the product for 24 or 40 is the cube; the product for 48, 80 or 405 is the biquadrate.
E. Lionnet"^ defined a perfect number of the second kind to be a number equal to the product of its aliquot parts. The only ones are p^ and pq, where p and q are distinct primes.
"L'interm^diaire des math., 24, 1917, 132-3.
"Math. Quest. Educ. Times, (2), 7, 1905, 68-9.
"Dehciae Math, oder Math. Sinnen-Confect, Hamburg, 1719, 197, Exs. 150-2.
"Nouv. Ann. Math., (2), 18, 1879, 306-8. Lucas, Th6orie des nombres, 1891, 373, Ex. 6
I
CHAPTER III.
FERMAT'S AND WILSON'S THEOREMS, GENERALIZATIONS AND
CONVERSES; SYMMETRIC FUNCTIONS OF
1,2 P-\ MODULO P.
Fermat's and Wilson's Theorems; Immediate Generalizations.
The Chinese^ seem to have known as early as 500 B. C. that 2^—2 is divisible by the prime p. This fact was rediscovered by P. de Fermat^ while investigating perfect numbers. Shortly afterwards, Fermat^ stated that he had a proof of the more general fact now known as Fermat's theorem: If p is any prime and x is any integer not divisible by p, then x^~^ — 1 is divisible by p.
G. W. Leibniz^ (1646-1716) left a manuscript giving a proof of Fermat's theorem. Let p be a prime and set x = a+6+c+. . .. Then each multi- nominal coefficient appearing in the expansion of x^ — 2a^ is divisible by p. Take a = 6 = c=...=l. Thus a;^ — a: is divisible by p for every integer x.
G. Vacca^ called attention to this proof by Leibniz.
Vacca^ cited manuscripts of Leibniz in the Hannover Library showing that he proved Fermat's theorem before 1683 and that he knew the theorem now known as Wilson's^^ theorem: If p is a prime, l + (p — 1)! is divisible by p. But Vacca did not explain an apparent obscurity in Leibniz's state- ment [cf. Mahnke'^].
D. Mahnke'' gave an extensive account of those results in the manuscripts of Leibniz in the Hannover Library which relate to Fermat's and Wilson's theorems. As early as January 1676 (p. 41) Leibniz concluded, from the expressions for the ^th triangular and yth. pyramidal numbers, that
(2/+l)2/=2/'-2/=0 (mod 2), {y+2){y+l)y=y'-y=0 (mod 3),
and similarly for moduU 5 and 7, whereas the corresponding formula for modulus 9 fails for y = 2, — thus forestalling the general formula by Lagrange.^* On September 12, 1680 (p. 49), Leibniz gave the formula now known as Newton's formula for the sum of like powers and noted (by incomplete induction) that all the coefficients except the first are divisible by the exponent p, when p is a prime, so that
a''+h''+c''-{- . . . = {a+h+c+ . . .Y (mod p).
Taking a = b= . . . =1, we obtain Fermat's theorem as above.'* That the binomial coefficients in (1 + 1)^ — 1 — 1 are divisible by the prime p was
^G. Peano, Formulaire math., 3, Turin, 1901, p. 96. Jeans.^^"
''Oeuvres de Fermat, Paris, 2, 1894, p. 198, 2°, letter to Mersenne, June (?), 1640; also p. 203,
2; p. 209. "Oeuvres, 2, 209, letter to Frenicle de Bessy, Oct. 18, 1640; Opera Math., Tolosae, 1679, 163. *Leibnizens Math. Schriften, herausgegeben von G. J. Gerhardt, VII, 1863, 180-1, "nova
algebrae promotio." »Bibliotheca math., (2), 8, 1894, 46-8. •Bolletino di BibUografia Storia Sc. Mat., 2, 1899, 113-6. 'Bibliotheca math., (3), 13, 1912-3, 29-61.
69
60 History of the Theory of Numbers. [Chap, hi
proved in 1681 (p. 50). Mahnke gave reasons (pp. 54-7) for believing that Leibniz rediscovered independently Fermat's theorem before he became acquainted, about 1681-2, with Fermat's Varia opera math, of 1679. In 1682 (p. 42), Leibniz stated that (p-2)!=l (mod p) if p is a prime [equivalent to Wilson's theorem], but that {p—2)l=m (mod p), if p is composite, m ha\dng a factor > 1 in common wdth p.
De la Hire^ stated that if k-'"^^ is divided by 2(2r+l) we get A; as a remainder, perhaps after adding a multiple of the divisor. For example, if kr' is divided by 10 we get the remainder k. He remarked that Carr^ had observed that the cube of any number /:<6 has the remainder k when divided by 6.
L. Euler^ stated Fermat's theorem in the form: If n+1 is a prime divid- ing neither a nor h, then a" — 6" is divisible by n+1. He was not able to give a proof at that time. He stated the generaUzation : If e = p'"~Hp — 1) and if p is a prime, the remainder obtained on dividing a* by p"" is 0 or 1 [a special case of Euler^^]. He stated also that ii m, n, p,. . . are distinct primes not dividing a and if A is the 1. c. m. of m — 1, n — 1, p — 1, . . ., then o"* — 1 is divisible by mnp . . . [and a* — 1 by m'' n\ . .ii k = A rrC~^n^~^ . . .].
Euler^° first published a proof of Fermat's theorem. For a prime p,
2'' = (l + l)^ = l+p-h(^)H-...+p+l = 2+mp, 3P = (l+2)P = l+A:p+2^ 3^-3- (2^-2) = A:p,
(1+0)"= 1+np+aP, (l+o)P-(l+a)-(aP-a)=np.
Hence if a^—a is divisible by p, also (1+a)" — (1+a) is, and hence also (a+2)''-(a+2),. . ., (a+6)P-(a+6). For a = 2, 2" - 2 was proved divisible by p. Hence, wTiting x for 2+6, we conclude that x^—x is divisible by p for any integer x.
G. W. Kraft^^ proved similarly that 2" — 2 = 7np.
L. Euler's^- second proof is based, hke his first, on the binomial theorem. If a, 6 are integers and p is a prime, (a+6)"— a" — 6" is divisible by p. Then, if a^ — a and 6^ — 6 are di\'isible by p, also (a+6)" — a — 6 is di\4sible by p. Take h = \. Thus (a+1)"— a— 1 is divisible by p if a^—a is. Taking a = 1, 2, 3, ... in turn, we conclude that 2''— 2, 3"— 3, . . . , c^ — c are divisible by p.
L. Euler^^ preferred his third proof to his earlier proofs since it avoids the use of the binomial theorem. If* p is a prime and a is any integer not
*Hist. Acad. Sc. Paris, annee 1704, pp. 42-4; ra4m., 358-362.
»Comm. Ac. Petrop., 6, 1732-3, 106; Coram. Arith., 1, 1849, p. 2. [Opera postuma, I, 1862,
167-8 (about 1778)]. ^••Comm. Ac. Petrop., 8, ad annum 1736, p. 141; Comm. Arith., 1, p. 21. "Novi Comm. Ac. Petrop., 3, ad annos 1*50-1, 121-2. "Novi Comm. Ac. Petrop., 1, 1747-8, 20; Comm. Arith., 1, 50. Also, letter to Goldbach,
Mar. 6, 1742, Corresp. Math. Phys. (ed. Fuss), I, 1843, 117. An extract of the letter is
given in Nouv. Ann. Math., 12, 1853, 47. "Novi Comm. Ac. Petrop., 7, 1758-9, p. 70 (ed. 1761, p. 49); 18, 1773, p. 85; Comm. Arith., 1,
260-9, 518-9. Reproduced by Gauss, Disq. Arith., art. 49; Werke, 1, 1863, p. 40.
Chap. Ill] FerMAt's AND WiLSON's THEOREMS. 61
divisible by y, at most p — 1 of the positive residues < p, obtained by dividing 1, a, a^, . . . by p, are distinct. Let, therefore; a" and a", where ix^v, have the same residue. Then a""" — 1 is divisible by p. Let X be the least positive integer for which a^ — \ is divisible by p. Then \,a,a^,..., a^~^ have dis- tinct residues when divided by p, so that X^p — L IfX = p — 1, Fermat's theorem is proved. If X<p — 1, there exists a positive integer k ik<p) which is not the residue of a power of a. Then k, ak, a^k, . . ., a^~^k have distinct residues, no one the residue of a power of a. Since the two sets give 2X distinct residues, we have 2X^ p — 1. If X< (p — 1)/2, we start with a new residue s and see that s, as, a^s, . . ., a^~^s have distinct residues, no one the residue of a power of a or of a^k. Hence X^ (p — 1)/3. Proceeding in this manner, we see that X divides p — L Thus d^~^ — 1 is divisible by a'' — 1 and hence by p.
L. Euler^^ soon gave his fundamental generalization of Fermat's theorem from the case of a prime to any integer N:
Euler's theorem: If n=(f){N) is the number of positive integers not exceeding N and relatively prime to N, then x" — 1 is divisible by N for every integer x relatively prime to N.
Let V be the least positive integer for which x" has the residue 1 when divided by N. Then the residues of 1, a:, a:^, ... , x"'^ are distinct and prime to N. Thus v^n. If v<n, there is an additional positive integer a less than A'' and prime to N. Then, when a, ax, ax^, . . ., ax"'^ are divided by N, the residues are distinct from each other and from those of the powers of x. Thus, 2v^n. Similarly, if 2v<n, then Zv^n. It follows in this manner that V divides n.
J. H. Lambert^^ gave a proof of Fermat's theorem differing shghtly from the first proof by Euler.^" If h is not divisible by the prime p, 6^"^ — 1 is divisible by p. For, set 6 = c+L Then
6^-^-1 =-l+c''-i + (p-l)c^-2+...+l
= -l+c^-'-c^-2 +0^"^- . . . +1+Ap,
where A is an integer. The intermediate terms equal
Hence
c+1 c+1
-fA-/, /='
P p ' P(c+1)
The theorem will thus follow by induction if / is shown to be integral. [Take p>2, so that p — 1 is even.] Then c^"^ — 1 is divisible by c+l, and by the hypothesis for the induction, by p. Since c-\-l = h is relatively prime to p, / is an integer.
"Novi Comm. Ac. Petrop., 8, 1760-1, p. 74; Comm. Arith., 1, 274-286; 2, 524-6. "Nova Acta Eruditorum, Lipsiae, 1769, 109.
62 History of the Theory of Numbers. [Chap, hi
E. Waring^^ first published the theorem that [Leibniz®] l + (p — 1)! is divisible by the prime p, ascribing it to Sir John Wilson^^ (1741-1793). Waring (p. 207; ed. 3, p. 356) proved that if a^ — a is divisible by p, then (a+1)''— a — 1 is, since {a+iy = a^-\-pA-\-l, "a, property first invented by Dom. Beaufort and first proved by Euler."
J. L. Lagrange^^ was the first to publish a proof of Wilson's theorem. Let
(x+l)(x+2) . . . (x+p-l) =x''-^+AiX^-'+ . . . -h^p-i.
R eplace x by x + 1 and multiply the resulting equation by x + 1 . Comparing with the original equation multiplied by x+p, we get
{x+p){x^-'+. . . +A,_,) = {x+ir+Ai{x+ir-' + . . . +^p_i(x+l).
Apply the binomial theorem and equate coefl5cients of like powers of x. Thus
Let p be a prime. Then, for 0<k<p, (j) is an integer divisible by p. Hence Ai, 2A2, . . . , {p—2)Ap_2 are divisible by p. Also,
(P-1)4,..= (P + (PI})A:+(P-2)^+... = 1+^+A,+ ...+^,.2.
Thus 1+Ap_i is divisible by p. By the original equation, Ap_i = (p — 1)!, so