PG26839.B00043
[PDF page 42] 26 ARITHMETICAL RECREATIONS. [CH. I where m = n = 4, there are70 such routes; while on a common chess- board, where m = n = 8, there are no less than 12870 such routes. A similar theorem can be enunciated for a parallelopiped. Another problem of a somewhat similar type is the determination of the number of closed routes throughmn points arranged inm rows and n columns, following the lines of the quadrilateral net-work, and passing once and only once through each point*. Permutation Problems. As other simple illustrations of the very large number of ways in which combinations of even a few things can be arranged, I may note that as many as 19, 958400 distinct skele- ton cubes can be formed with twelve differently coloured rods of equal length†; again there are 3, 979614, 965760 ways of arranging a set of twenty-eight dominoes (i.e. a set from double zero to double six) in a line, with like numbers in contact‡; while there are no less than 53644, 737765, 488792, 839237, 440000 possible different distributions of hands at whist with a pack of fifty-two cards§. Voting Problems. Here is a simple example on combinations deal- ing with the cumulative vote as affecting the representation of a mi- nority. If there are p electors each having r votes of which not more than s may be given to one candidate, andn men are to be elected, then the least number of supporters who can secure the election of a candidate must exceed pr/(ns + r). Exploration Problems. Another common question is concerned with the maximum distance into a desert which could be reached from a frontier settlement by the aid of a party ofn explorers, each capa- ble of carrying provisions that would last one man fora days. The answer is that the man who reaches the greatest distance will occupy na/(n + 1)days before he returns to his starting point. If in the course of their journey they may make depôts, the longest possible journey will occupy 1 2 a(1 + 1 2 + 1 3 + · · · + 1/n) days. Further extensions by the use of horses and cycles will suggest themselves. Here I conclude my account of such of these easy problems on * See C.F. Sainte-Marie in L’Intermédiaire des mathématiciens, Paris, vol. xi, March, 1904, pp. 86–88. † Mathematical Tripos, Cambridge, Part I, 1894. ‡ Reiss inAnnali di matematica, Milan, November, 1871, vol.v, pp. 63–120. § That is (52!)/(13!)4.

PG26839.B00044
[PDF page 43] CH. I] BACHET’S WEIGHTS PROBLEM. 27 numbers or elementary algebra as seemed worth reproducing. It will be noticed that the majority of them either are due to Bachet or were collected by him in his classical Problèmes; but it should be added that besides the questions I have mentioned he enunciated, even if he did not always solve, some other problems of greater interest. One instance will suffice. Bachet’s Weights Problem*. Among the more difficult problems proposed by Bachet was the determination of the least num- ber of weights which would serve to weigh any integral number of pounds from 1 lb. to 40 lbs. inclusive. Bachet gave two solutions: namely, (i) the series of weights of1, 2, 4, 8, 16, and 32 lbs.; (ii) the series of weights of1, 3, 9, and 27 lbs. If the weights may be placed in only one of the scale-pans, the first series gives a solution, as had been pointed out in 1556 by Tartaglia†. Bachet, however, assumedthatanyweightmightbeplacedineither of the scale-pans. In this case the second series gives the least possible number of weights required. His reasoning is as follows. To weigh1 lb. we must have a1 lb. weight. To weigh2 lbs. we must have in addition either a2 lb. weight or a3 lb. weight; but, if we are confined to only one new weight (in addition to the1 lb. we have got already), then with no weight greater than3 lbs. could we weigh2 lbs.: if we use a2 lb. weight we then can weigh1 lb., 2 lbs., and 3 lbs., but if we use a3 lb. weight we then can weigh1 lb., (3 − 1) lbs., 3 lbs., and (3 + 1) lbs.; hence a 3 lb. weight is preferable. Similarly, to enable us to weigh5 lbs. we must have another weight not greater than9 lbs., and a weight of9 lbs. enables us to weigh every weight from1 lb. to 13 lbs.; hence it is the best to choose. The next weight required will be2(1+3+9)+1 lb., that is, will be27 lbs.; and this enables us to weigh from1 lb. to40 lbs. Thus only four weights are required, namely,1 lb., 3 lbs., 32 lbs., and 33 lbs. We can show similarly that the series of weights of1, 3, 32, . . ., 3n−1 lbs. will enable us to weigh any integral number of pounds from 1 lb. to(1 + 3 + 32 + · · ·3n−1) lbs., that is, to1 2(3n − 1) lbs. This is the least number with which the problem can be effected. To determine the arrangement of the weights to weigh any given mass we have only to express the number of pounds in it as a number in the ternary scale of notation, except that in finding the successive * Bachet, Appendix, problem v, p. 215. † Trattato de’ numeri e misure, Venice, 1556, vol.ii, bk. i, chap. xvi, art. 32.

PG26839.B00045
[PDF page 44] 28 ARITHMETICAL RECREATIONS. [CH. I digits we must make every remainder either0, 1, or −1: to effect this a remainder 2 must be written as 3 − 1, that is, the quotient must be increased by unity, in which case the remainder is −1. This is explained in most text-books on algebra. Bachet’s argument does not prove that his result is unique or that it gives the least possible number of weights required. These omissions have been supplied by Major MacMahon, who has discussed the far more difficult problem (of which Bachet’s is a particular case) of the determination of all possible sets of weights, not necessarily unequal, which enable us to weigh any integral number of pounds from1 to n inclusive, (i) when the weights may be placed in only one scale-pan, and (ii) when any weight may be placed in either scale-pan. He has investigated also the modifications of the results which are necessary when we impose either or both of the further conditions (a) that no other weighings are to be possible, and (b) that each weighing is to be possible in only one way, that is, is to be unique*. The method for case (i) consists in resolving1 + x + x2 + · · · + xn into factors, each factor being of the form1 +xa + x2a + · · ·+ xma; the number of solutions depends on the composite character ofn + 1. The method for case (ii) consists in resolving the expressionx−n+x−n+1+· · · + x−1 + 1 + x + · · · + xn−1 + xn into factors, each factor being of the form x−ma + · · · + x−a + 1 + xa + · · · + xma; the number of solutions depends on the composite character of2n + 1. Bachet’s problem falls under case (ii),n = 40. MacMahon’s anal- ysis shows that there are eight such ways of factorizingx−40 + x−39 + · · · + 1 + x39 + x40. First, there is the expression itself in whicha = 1, m = 40 . Second, the expression is equal to (1 − x81)/x40(1 − x), which can be resolved into the product of (1 − x3)/x(1 − x) and (1 − x81)/x39(1 − x3); hence it can be resolved into two factors of the form given above, in one of whicha = 1, m = 1, and in the other, a = 3, m = 13. Third, similarly, it can be resolved into two such factors, in one of whicha = 1, m = 4, and in the othera = 9, m = 4. Fourth, it can be resolved into three such factors, in one of whicha = 1, m = 1, in anothera = 3, m = 1, and in the other,a = 9, m = 4. Fifth, it can be resolved into two such factors, in one of whicha = 1, m = 13, * See his article in theQuarterly Journal of Mathematics, 1886, vol.xxi, pp. 367– 373. An account of the method is given in Nature, Dec. 4, 1890, vol. xlii, pp. 113–114.

PG26839.B00046
[PDF page 45] CH. I] PROBLEMS IN HIGHER ARITHMETIC. 29 and in the othera = 27, m = 1. Sixth, it can be resolved into three such factors, in one of whicha = 1, m = 1, in another a = 3, m = 4, and in the othera = 27, m = 1. Seventh, it can be resolved into three such factors, in one of whicha = 1, m = 4, in another a = 9, m = 1, and in the othera = 27, m = 1. Eighth, it can be resolved into four such factors, in one of whicha = 1, m = 1, in another a = 3, m = 1, in another a = 9, m = 1, and in the othera = 27, m = 1. These results show that there are eight possible sets of weights with which any integral number of pounds from1 to 40 can be weighed subject to the conditions (ii), (a), and (b). If we denotep weights each equalto w by wp, theseeightsolutionsare 140; 1, 313; 14, 94; 1, 3, 94; 113, 27; 1, 34, 27; 14, 9, 27; 1, 3, 9, 27. The last of these is Bachet’s solution: not only is it that in which the least number of weights are employed, but it is also the only unique one in which all the weights are unequal. Problems in Higher Arithmetic. At the commencement of this chapter I alluded to the special interest which many mathemati- cians find in the theorems of higher arithmetic: such, for example, as that every prime of the form4n + 1 and every power of it is ex- pressible as the sum of two squares*, and the first and second powers can be expressed thus in only one way. For instance,13 = 3 2 + 22, 132 = 12 2 + 52, 133 = 46 2 + 92, and so on. Similarly 41 = 5 2 + 42, 412 = 40 2 + 92, 413 = 236 2 + 1152, and so on. Propositions such as the one just quoted may be found in text- books on the theory of numbers and therefore lie outside the limits of this work, but there are one or two questions in higher arithmetic involving points not yet quite cleared up which may find a place here. Primes. The first of these is concerned with the possibility of determining readily whether a given number is prime or not. Euler and Gaussattachedgreatimportancetothisproblem, butfailedtoestablish any conclusive test. It would seem, however, that Fermat possessed some means of finding from its form whether a given number (at any rate if one of certain known forms) was prime or not. Thus, in answer to Mersenne who asked if he could tell without much trouble whether the number 100895, 598169 was a prime, Fermat wrote on April 7, 1643, that it was the product of 898423 and 112303, both of which were * Fermat’sDiophantus, Toulouse, 1670, bk.iii, prop. 22, p. 127; or Brassinne’s Précis, Paris, 1853, p. 65.

PG26839.B00047
[PDF page 46] 30 ARITHMETICAL RECREATIONS. [CH. I primes. I have indicated elsewhere one way by which this result can be found, and Mr F.W. Laurence has indicated another which may have been that used by Fermat in this particular case. Mersenne’s Numbers*. Another illustration, confirmatory of the opinion that Fermat or some of his contemporaries had a test by which it was possible to find out whether certain numbers were prime, may be drawn from Mersenne’sCogitata Physico-Mathematicawhich was published in 1644. In the preface to that work it is asserted that in order that 2p − 1 may be prime, the only values ofp, not greater than 257, which are possible are1, 2, 3, 5, 7, 13, 17, 19, 31, 67, 127, and 257: I conjecture that the number67 is a misprint for61. With this correction the statement appears to be true, and it has been verified for all except nineteen values of p: namely, 71, 101, 103, 107, 109, 137, 139, 149, 157, 163, 167, 173, 181, 193, 199, 227, 229, 241, and 257. Of these values, Mersenne asserted that p = 257 makes 2p − 1 a prime, and that the other values make2p − 1 a composite number. The demonstrations for the cases when p = 89, 127 have not been published; nor have the actual factors of2p − 1 when p = 89 been as yet determined: the discovery of these factors may be commended to those interested in the theory of numbers. Mersenne’s result could not be obtained empirically, and it is im- possible to suppose that it was worked out for every case; hence it would seem that whoever first enunciated it was acquainted with cer- tain theorems in higher arithmetic which have not been re-discovered. Perfect Numbers†. The theory of perfect numbers depends directly on that of Mersenne’s Numbers. A number is said to be per- fect if it is equal to the sum of all its integral subdivisors. Thus the subdivisors of 6 are 1, 2, and 3; the sum of these is equal to6; hence 6 is a perfect number. It is probable that all perfect numbers are included in the formula 2p−1(2p − 1), where 2p − 1 is a prime. Euclid proved that any num- ber of this form is perfect; Euler showed that the formula includes all even perfect numbers; and there is reason to believe—though a rigid demonstration is wanting—that an odd number cannot be perfect. If * For references, see chapter ix below. † On the theory of perfect numbers, see bibliographical references by H. Brocard, L’Intermédiaire des mathématiciens, Paris, 1895, vol.ii, pp. 52–54; and 1905, vol. xii, p. 19.

PG26839.B00048
[PDF page 47] CH. I] GOLDBACH’S THEOREM. 31 we assume that the last of these statements is true, then every perfect number is of the above form. It is easy to establish that every number included in this formula (except whenp = 2) is congruent to unity to the modulus 9, that is, when divided by9 leaves a remainder1; also that either the last digit is a6 or the last two digits are28. Thus, if p = 2, 3, 5, 7, 13, 17, 19, 31, 61, then by Mersenne’s rule the corresponding values of2p − 1 are prime; they are 3, 7, 31, 127, 8191, 131071, 524287, 2147483647, 2305843009213693951; and the cor- responding perfect numbers are6, 28, 496, 8128, 33550336, 8589869056, 137438691328, 2305843008139952128, and 2658455991569831744654692615953842176. Goldbach’s Theorem. Another interesting problem in higher arithmetic is the question whether there are any even integers which cannot be expressed as a sum of two primes. Probably there are none. The expression of all even1 integers not greater than5000 in the form of a sum of two primes has been effected*, but a general demonstration that all even integers can be so expressed is wanting. Lagrange’s Theorem†. Another theorem in higher arith- metic which, as far as I know, is still unsolved, is to the effect that every prime of the form4n − 1 is the sum of a prime of the form4n + 1 and of double a prime of the form4n + 1; for example,23 = 13 + 2× 5. Lagrange, however, added that it was only by induction that he ar- rived at the result. Fermat’s Theorem on Binary Powers. Fermat enriched mathematics with a multitude of new propositions. With two excep- tions all these have been proved subsequently to be true. The first of these exceptions is histheorem on binary powers, in which he asserted that all numbers of the form2m + 1, wherem = 2n, are primes‡, but he added that, though he was convinced of the truth of this proposition, he could not obtain a valid demonstration. * Transactions of the Halle Academy (Naturforschung), vol. lxxii, Halle, 1897, pp. 5–214: see alsoL’Intermédiaire des mathématiciens, 1903, vol.x, and 1904, vol. xi. † Nouveaux Mémoires de l’Académie Royale des Sciences, Berlin, 1775, p. 356. ‡ Letter of Oct. 18, 1640,Opera, Toulouse, 1679, p. 162: or Brassinne’sPrécis, p. 143. 1. ‘even’ inserted as per errata sheet

PG26839.B00049
[PDF page 48] 32 ARITHMETICAL RECREATIONS. [CH. I It may be shown that2m + 1 is composite if m is not a power of 2, but of course it does not follow that2m + 1 is a prime if m is a power of2. As a matter of fact the theorem is not true. In 1732 Euler* showed that ifn = 5 the formula gives4294, 967297, which is equal to 641 ×6, 700417: curiously enough, these factors can be deduced at once from Fermat’s remark on the possible factors of numbers of the form 2m ± 1, from which it may be shown that the prime factors (if any) of 232 + 1 must be primes of the form64n + 1. During the last thirty years it has been shown† that the resulting numbers are composite when n = 6, 9, 11, 12, 18, 23, 36, and 38: the two last numbers contain many thousands of millions of digits. I believe that Eisenstein asserted that the number of primes of the form 2m + 1, where m = 2 n, is infinite: the proof has not been published, but perhaps it might throw some light on the general theory. Fermat’s Last Theorem.I pass now to the only other asser- tionmadebyFermatwhichhasnotbeenprovedhitherto. This, whichis sometimes known asFermat’s Last Theorem, is to the effect‡that no in- tegral values ofx, y, z can be found to satisfy the equationxn+yn = zn, if n is an integer greater than2. This proposition has acquired extraor- dinary celebrity from the fact that no general demonstration of it has been given, but there is no reason to doubt that it is true. Fermat seems to have discovered its truth first§ for the casen = 3, and then for the casen = 4. His proof for the former of these cases is lost, but that for the latter is extant∥, and a similar proof for the case of n = 3 was given by Euler¶. These proofs depend upon showing that, if three integral values ofx, y, z can be found which satisfy the equation, * Commentarii Academiae Scientiarum Petropolitanae, St Petersburg, 1738, vol. vi, p. 104; see alsoNovi Comm. Acad. Sci. Petrop., St Petersburg, 1764, vol. ix, p. 101: orCommentationes Arithmeticae Collectae, St Petersburg, 1849, vol. i, pp. 2, 357. † For the factors and bibliographical references, see the memoir by A.J.C. Cun- ningham and A.E. Western,Transactions of the London Mathematical Society, May 14, 1903, series 2, vol.i, p. 175. ‡ Fermat’s enunciation will be found in his edition ofDiophantus, Toulouse, 1670, bk. ii, qu. 8, p. 61; or Brassinne’sPrécis, Paris, 1853, p. 53. For bibliographical references, seeL’Intermédiaire des mathématiciens, 1905, vol.xii, pp. 11, 12. § See a letter from Fermat quoted in myHistory of Mathematics, London, chap- ter xv. ∥ Fermat’sDiophantus, note on p. 339; or Brassinne’sPrécis, p. 127. ¶ Euler’s Algebra (English trans. 1797), vol.ii, chap. xv, p. 247.

PG26839.B00050
[PDF page 49] CH. I] FERMAT’S LAST THEOREM. 33 then it will be possible to find three other and smaller integers which also satisfy it: in this way finally we show that the equation must be satisfied by three values which obviously do not satisfy it. Thus no integral solution is possible. It would seem that this method is inapplicable except when n = 3 and n = 4. Fermat’s discovery of the general theorem was made later. An easy demonstration can be given on the assumption that every number can be resolved into prime (complex) factors in one and only one way. That assumption has been made by some writers, but it is not universally true. It is possible that Fermat made some such supposition, though it is perhaps more probable that he discovered a rigorous demonstra- tion. At any rate he asserts definitely that he had a valid proof— demonstratio mirabilis sane—and the fact that every other theorem on the subject which he stated he had proved has been subsequently veri- fied must weigh strongly in his favour; especially as in making the one statement in his writings which is not correct he was scrupulously care- ful to add that he could not obtain a satisfactory demonstration of it. It must be remembered that Fermat was a mathematician of quite the first rank who had made a special study of the theory of numbers. That subject is in itself one of peculiar interest and elegance, but its conclusions have little practical importance, and since his time it has been discussed by only a few mathematicians, while even of them not many have made it their chief study. This is the explanation of the fact that it took more than a century before some of the simpler results which Fermat had enunciated were proved, and thus it is not surprising that a proof of the theorem which he succeeded in establishing only towards the close of his life should involve great difficulties. In 1823 Legendre* obtained a proof for the case ofn = 5; in 1832 LejeuneDirichlet †gaveonefor n = 14, andin1840LaméandLebesgue ‡ gave proofs for n = 7. The proposition appears to be true universally, and in 1849 Kum- mer§, by means of ideal primes, proved it to be so for all numbers except those (if any) which satisfy three conditions. It is not known * Reprinted in his Théorie des Nombres, Paris, 1830, vol.ii, pp. 361–368: see also pp. 5, 6. † Crelle’s Journal, 1832, vol.ix, pp. 390–393. ‡ Liouville’s Journal, 1841, vol.v, pp. 195–215, 276–9, 348–9. § References to Kummer’s Memoirs are given in Smith’s Report to the British Association on the Theory of Numbers, London, 1860.

PG26839.B00051
[PDF page 50] 34 ARITHMETICAL RECREATIONS. [CH. I whether any number can be found to satisfy these conditions, but it seems unlikely, and it has been shown that there is no number less than 100 which does so. The proof is complicated and difficult, and there can be little doubt is based on considerations unknown to Fermat. I may add that to prove the truth of the proposition whenn is greater than 4, it obviously is sufficient to confine ourselves to cases wheren is a prime, and the first step in Kummer’s demonstration is to show that in such cases one of the numbersx, y, z must be divisible byn. Naturally there has been much speculation as to how Fermat ar- rived at the result. The modern treatment of higher arithmetic is founded on the special notation and processes introduced by Gauss, who pointed out that the theory of discrete magnitude is essentially different from that of continuous magnitude, but until the end of the last century the theory of numbers was treated as a branch of algebra, and such proofs by Fermat as are extant involve nothing more than el- ementary geometry and algebra, and indeed some of his arguments do notinvolveanysymbols. ThishasledsomewriterstothinkthatFermat used none but elementary algebraic methods. This may be so, but the following remark, which I believe is not generally known, rather points to the opposite conclusion. He had proposed, as a problem to the En- glish mathematicians, to show that there was only one integral solution of the equationx2 + 2 = y3: the solution evidently beingx = 5, y = 3. On this he has a note* to the effect that there was no difficulty in finding a solution in rational fractions, but that he had discovered an entirely new method—sane pulcherrima et subtilissima—which enabled him to solve such questions in integers. It was his intention to write a work†on his researches in the theory of numbers, but it was never completed, and we know but little of his methods of analysis. I venture however to add my private suspicion that continued fractions played a not unimportant part in his researches, and as strengthening this conjecture I may note that some of his more recondite results—such as the theorem that a prime of the form4n + 1is expressible as the sum of two squares—may be established with comparative ease by properties of such fractions. * Fermat’sDiophantus, bk. vi, prop. 19, p. 320; or Brassinne’sPrécis, p. 122. † Fermat’sDiophantus, bk. iv, prop. 31, p. 181; or Brassinne’sPrécis, p. 82.

PG26839.B00052
[PDF page 51] CHAPTER II. SOME GEOMETRICAL QUESTIONS. In this chapter I propose to enumerate certain geometrical ques- tions the discussion of which will not involve necessarily any consider- able use of algebra or arithmetic. Unluckily no writer like Bachet has collected and classified problems of this kind, and I take the following instances from my note-books with the feeling that they represent the subject but imperfectly. The first part of the chapter is devoted to questions which are of the nature of formal propositions: the last part contains a description of various trivial puzzles and games, which the older writers would have termed geometrical, but which the reader of to-day may omit without loss. In accordance with the rule I laid down for myself in the preface, I exclude the detailed discussion of theorems which involve advanced mathematics. Moreover(withonepossibleexception)Iexcludealsoany mention of the numerous geometrical paradoxes which depend merely on the inability of the eye to compare correctly the dimensions of figures when their relative position is changed. This apparent deception does not involve the conscious reasoning powers, but rests on the inaccurate interpretation by the mind of the sensations derived through the eyes, and I do not consider such paradoxes as coming within the domain of mathematics. Geometrical Fallacies. Most educated Englishmen are ac- quainted with the series of logical propositions in geometry associated 35

PG26839.B00053
[PDF page 52] 36 SOME GEOMETRICAL QUESTIONS. [CH. II with the name of Euclid, but it is not known so generally that these propositions were supplemented originally by certain exercises. Of such exercises Euclid issued three series: two containing easy theorems or problems, and the third consisting of geometrical fallacies, the errors in which the student was required to find. The collection of fallacies prepared by Euclid is lost, and tradition has not preserved any record as to the nature of the erroneous reasoning or conclusions; but, as an illustration of such questions, I append two or three demonstrations, leading to obviously impossible results, which perhapsmayamuseanyonetowhomtheyarenew. Ileavethediscovery of the errors to the ingenuity of my readers. First Fallacy. To prove that a right angle is equal to an angle which is greater than a right angle.Let ABCD be a rectangle. FromA draw a lineAE outside the rectangle, equal toAB or DC and making an acute angle with AB, as indicated in the diagram. Bisect CB in A BC D E O H K H, and throughH draw HO at right angles toCB. Bisect CE in K, and through K draw KO at right angles toCE. Since CB and CE are not parallel the linesHO and KO will meet (say) atO. Join OA, OE, OC, and OD. The triangles ODC and OAE are equal in all respects. For, since KO bisects CE and is perpendicular to it, we haveOC = OE. Simi- larly, since HO bisects CB and DA and is perpendicular to them, we have OD = OA. Also, by construction,DC = AE. Therefore the three sides of the triangleODC are equal respectively to the three sides of
