CHAPTER XV.

mersenne's numbers.
One of the unsolved riddles of higher arithmetic, to which I alluded in the second chapter, is the discovery of the method by which Mersenne or his contemporaries determined values of p which make a number of the form 2^ — 1 a prime. It is convenient to describe such primes as Mersennes Numbers, a name which I believe I introduced. In this chapter, for shortness, I use N to denote a number of the form 2^ — 1. In a memoir in the Messenger of Mathematics in 1891 I gave a brief sketch of the history of the problem. I here repeat the facts in somewhat more detail, and add some notes on methods used in attacking the problem.
Mersenne's enunciation of the results associated with his name is in the preface to his Cogitata*, The passage is as follows :
Vbi fuerit operae pretium aduertere xxvm numeros a Petro Bungo pro perfectis exhibitos, capite xxviii, libri de Numeris, non esse omnes Perfectos,
quippe 20 sunt imperfect!, adeovt [adeunt?] solos octo perfectos habeat qui
sunt 6 regione tabulae Bungi, 1, 2, 3, 4, 8, 10, 12, et 29 : quique soli perfecti sunt, vt qui Buugum habuerint, errori medicinam faciant.
Porr6 numeri perfecti adeo rari sunt, vt vndecim dumtaxat potueriut hac- tenus inueniri: hoc est, alii tres a Bongianis differentes: neque 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. Vndecimua denique, potestas 25^, minus 1, hoc est potestas 257, vnitate decurtata, multiplicata per potestatem 256.
• Cogitata Physico-MatJiemaiica, Paris, 1644, Praefatio Generalis, article 19.
334 mersenne's numbers [ch. xv
Qui vndecim alios repererit, nouerit se analysim omnem, quae fuerit hacte- nus, superasse: memineritque interea nullum esse perfectum a 17000 potestate ad 32000; & nullum potestatum interuallum tantum assignari posse, quin detur illud absque perfectis. Verbi gratia, si fuerit exponens 1050000, nullus erit Humerus progressionis duplae vsque ad 2000000, qui perfectis numeris seruiat, hoc est qui minor vnitate, primus existat.
Vnde clarum est quam rari sint perfecti numeri, fectis comparentur ; esseque vnam ex maximis totius Matheseos difficultatibus, praescriptam numerorum perfectorum multitudiuum exhibere ; quemadmodum necne, cum nequidem saeculum integrum huic examini, quocumque modo hactenus cognito, sufi&ciat.
It is evident that, if p is not a prime, then N is composite, and two or more of its factors can be written down by inspection. Hence we may confine ourselves to prime values of p. Mersenne, in effect, asserted that the only values of p, not greater than 257, which make N a prime, are 1, 2, 3, 5, 7, 13, 17, 19, 31, 67, 127, 257: to these numbers 89 must be added. I gave reasons, some years ago, for thinking that 67 here is a misprint for 61, and I assume this is so. With these cor- rections we have no reason to doubt the truth of the statement, but it has not been definitely established.
There are 56 primes not greater than 257. The deter- mination of the prime or composite character of N for the 9 cases when p is less than 20 presents no difficulty: in only one of them is N composite. For 2 of the remaining 47 cases (namely, when jo=23 and 37) the decomposition of N had been given by Fermat. For 9 of them (namely, when p — 29, 43, 73, 83, 131, 179, 191, 239, 251) the factors of N were given by Euler. He also proved that N was prime when p = 31. Reuschle gave the factors of N when p = 47, and Plana the factors when p — 41. Landry and Le Lasseur discovered the factors in 9 cases, namely, when p — 53, 59, 79, 97, 113, 151, 211, 223, and 233. Seelhoff showed that N was prime when p = 61, Cunningham gave the factors when p = 71, 163, 173, and 197, Cole the factors when p = 67, Woodall the factors when p = 181, and Powers proved that iV was prime when p = 89. It has been asserted that the prime character of N when p = 127 has been established, but the proof has not been published or verified.
CH. xv] mersenne's numbers 335
Thus there are 16 values of p for which Mersenne's state- ment still awaits verification. These are 101, 103, 107, 109, 127, 137, 139, 149, 157, 167, 193, 199, 227, 229, 241, 257. For these values N is (according to Mersenne) prime when j[) = 127 and 257, and is composite for the other values. If we admit that the character of N is known when p=12l, the number of cases yet to be verified is reduced to 15.
To put the matter in another way. According to Mersenne's statement (corrected by the substitution of 61 for 67 and with the addition of 89 to his list) 43 of the 56 primes less than 258 make N composite and the remaining 13 primes make N prime. In 29 out of the 43 cases in which N is said to be composite we know its factors, and in 14 cases the statement is still unverified. In 11 out of the 13 cases in wdiich it is said that N is prime the statement has been verified, and in 2 cases it is still unverified.
From the w^ording of the last clause in the above quotation it has been conjectured that the result had been communicated to Mersenne, and that he published it without being aware of how it was proved. In itself this seems probable. Pie was a good mathematician, but not an exceptional genius. It would be strange if he established a proposition which has baffled Euler, Lagrange, Legendre, Gauss, Jacobi, and other mathe- maticians of the first rank ; but if the proposition is due to Fermat, wdth whom Mersenne was in constant corresjoondence, the case is altered, and not only is the absence of a demon- stration explained, but we cannot be sure that we have attacked the problem on the best lines.
The known results as to the prime or composite character of N, and in the latter case its smallest factor, are given in the table on the next page. The cases that remain as yet unverified are marked with an asterisk.
Before describing the methods used for attacking the problem it will be convenient to state in more detail when and by whom these results were established.
The factors (if any) of such values of N as are less than a million can be verified easily: they have been known for a lonoj time, and I need not allude to them in detail.
336
MERSENNES NUMBERS
[CH. XV
TABLE OF MERSENNE'S NUMBERS.
1 2 3 5
7
11
13
17
19
23
29
31
37
41
43
47
53
59
61
87
71
73
79
83
89
97
101
103
107
109
113
127
131
137
139
149
151
157
163
167
173
179
181
191
193
197
199
211
223
227
229
233
239
241
251
357
Value of N=2r'-1
Character
Discoverer
1
prime
3
prime
7
prime
31
prime
127
prime
2047 = 23x89
composite
8191
prime
131071
prime
524287
prime
8388607 = 47x178481
composite
Fermat
536870911 = 233x1103x2089
composite
Euler
2147483647
prjiue
Euler
137438953471 = 223 x 616318177
composite
Fermat
2199023255551 = 13367 x 164511353
composite
Plana
8796093022207 = 431 x 9719 x 2099863
composite
Euler
2351 X 4513 X 13264529
composite
Eeuschle
6361 X 69431 x 20394401
composite
Landry
179951 X 3203431780337
composite
Landry
2305843009213693951
prime
Seelhoff
= 0(193707721)
composite
Cole
= 0 (228479)
composite
Cunningham
= 0(439)
composite
Euler
= 0 (2687)
composite
Le Lasseur
= 0(167)
composite
Euler
618970019G42690137449562111
prime
Powers
= 0 (11447)
composite
Le Lasseur
2535301200456458802993406410751
*
«
10141204801825835211973625G43007
»
»
162259276829213363391578010288127
»
•
(549037107316853453.366312041152511
*
»
= 0 (3391)
composite
Le Lasseur
170141183460469231731087303715884105727
♦
*
= 0 (2G3)
composite *
»
Euler
•
=o*('i8i2ij
♦
composite *
composite
* composite
»
Le Lasseur *
=o*(iV6287)
Cunningham *
s0(73d753)
Cunningham
= 0 (359)
composite
Euler
= 0(43441)
composite
\Voodall
= 0(383)
composite *
composite
*
composite
Euler
*
=0 (7487)
Cunningham *
=0(15193)
Le Lasseur
= 0(18287)
composite
*
* composite
Le Lasseur
»
= 0(1399)
Le Lasseur
= 0 (479)
composite
■ti-
composite
Euler
«
= 0 (503)
Euler
♦
»
CH. xv] meksenne's numbers 337
The factors of N when p = ll, 23, and 37 had been indicated by Fermat*, some four years prior to the publication of Mersenne's work, in a letter dated October 18, 1640. The passage is as follows:
En la progression double, si d'un nombre quarr6, g^n^ralement parlant, vous 6tez 2 ou 8 ou 32 Ac, les nombres premiers moindres de I'uuite qu'un multiple du quaternaire, qui mesureront le reste, feront I'effet requis. Comme de 25, qui est un quarr6, otez 2; le reste 23 mesurera la 11* puissance ~1; otez 2 de 49, le reste 47 mesurera la 23« puissance - 1. Otez 2 de 225, le reste 223 mesu- rera la 37° puissance - 1, &c.
Factors of N when p = 29, 43, and 73 were given by Eulerf in 1732 or 1733. The fact that N is composite for the values p = 83, 131, 179, 191, 239, and 251 follows from a proposition enunciated, at the same time, by Euler to the effect that, if 4/1 + 3 and 8n + 7 are primes, then 2'^''+^ -1 = 0 (mod. Sn + 7). This was proved by Lagrange | in his classical memoir of 1775. The proposition also covers the cases of ^ = 11 and p = 23. This is the only general theorem on the subject which has been yet established.
The fact that iV is prime when ^ = 31 w^as proved by Euler§ in 1771. Fermat had asserted, in the letter mentioned above, that the only possible prime factors of 2^ + 1, when p was prime, were of the form 7ip + 1, where n is an integer. This was proved by Euler || in 1748, who added that, since 2^ ± 1 is odd, every factor of it must be odd, and therefore if p is odd n must be even. But if ^ is a given number we can define n much more closely, and Euler showed that, if p = 31, the prime factors (if any) of N w^ere necessarily primes of the form 248?i + 1 or 248n + 63 ; also they must be less than ^JSf, that is, than
• Oeuvres de Fermat, Paris, vol. ii, 1894, p. 210; or Opera Blathematica, Toulouse, 1679, p. 164; or Brassiune's Precis, Paris, 1853, p. 144.
f Commentarii Academiae Scientiarum Petropolitanae, 1738, vol. vi, p. 105; or Commentationes Arithmeticae Collectae, vol. i, p. 2.
X Nouveaux Memoires de VAcademie des Sciences de Berlin, 1775, pp. 323 — 35G.
§ Histoire de VAcademie des Sciences for 1772, Berlin, 1774, p. 36. See also Legendre, Thiorie des Nombres, third edition, Paris, 1830, vol. i, pp. 222 — 229.
II Novi Commentarii Academiae Scientiarum Petropolltanae, vol. i, p. 20; or Commentationes Arithmeticae Collectae, St Petersburg, 1849, vol. i, pp. 55, 56.
B. s. 22
338 mersenne's numbers [ch. xv
46339. Hence it is necessary to try only forty divisors to see if N is prime or composite.
The factors when p = 4>'7; the factor 1433 when p = l79, and the factor 1913 when p = 239, were given by Reuschle in 1856*.
The factors of iV when ^ = 41 were given by Plana f in 1859. He showed that the prime factors (if any) are primes of the form 328n + l or 328w + 247, and lie between 1231 and ^/N, that is, 1048573. Hence it is necessary to try only 513 divisors to see if N is composite: the seventeenth of these divisors gives the required factors. This is the same method of attacking the problem which w^as used by Euler in 1771, but it would be laborious to employ it for values of p greater than 41. Plana J added the forms of the prime divisors of iV, if p is not greater than 101.
That N is prime when ^5 = 127 seems to have been verified by Lucas § in 1876 and 1877. The demonstration has not been published.
The discovery of factors of N for the values ^ = 53 and 59 is due apparently to F. Landry, who established theorems on the factors (if any) of numbers of certain forms. He seems to have communicated his results to Lucas, who quoted them in the memoir cited below ||.
Factors of N when p = 79 and 113 were given first by Le Lasseur, and were quoted by Lucas in the same memoir||.
A factor of N when p — 233 was discovered later by Le Lasseur, and was quoted by Lucas in 1882 IF.
* C. G. Eeuschle, Neue Zahlentheoretische Tdbellen, Stuttgart, 1856, pp. 21, 22, 42—53.
+ G. A. A. Plana, Memorie della Eeale Accademia delle Scienze di Torino, Series 2, vol. xx, 1863, p. 130.
X Ibid., p. 137.
§ Su/' la Theorie des Nomhres Premiers, Turin, 1876, p. 11; and Becherches sur les Ouvrages de Leonard de Pise, Rome, 1877, p. 26, quoted by A. J. C. Cunningham, Proceedings of the London mathematical Society, Nov. 14, 1895, vol. XXVII, p. 54.
II American Journal of Mathematics, 1878, vol. i, pp. 234 — 238.
H Recreations, 1882-8, vol. i, p. 241.
CH. xv] mersenne's numbers 339
Factors of N when p = 97, 151, 211, and 223 were deter- mined subsequently by Le Lasseur, and were quoted by Lucas* in 1883.
That N is prime when ^ = G1 had been conjectured by Landry and in 1886 a demonstration was offered by Seelhofff. His demonstration is open to criticism, but the fact has been verified by others J, and may be accepted as proved.
Cunningham showed in 1895 § that 7487 is a factor of N when p = 197: in 1908 1| that 150287 is a fector of N when p = 163; in 190911 that 228479 is a factor of N when _p=7l; and in 1912** that 730753 is a factor of i\^ when J3=173. The factors of iV when p=:7l were discussed independently by Ramesam in 1912 ff.
That iV'is not prime when ^=67 seems to have been verified by Lucas II in 1876 and 1877. The composite nature of N, when p = 67, was confirmed by E. Fauquembergue§§, and was also implied by Lucas in 1891. The fiactors were given by Cole|l|linl903.
A factor of N when 2^ = 181 was discovered by Woodall in 1911M.
♦ Recreations, 1882-3, vol. n, p. 230.
t P. H. H. Seelhoff, ZeiUcUrift fur Mathematik und Physik, 1886, vol. xxxi, p. 178.
X See Weber-Wellstein, Encyclopaedic der Elementar -Mathematik, p. 48; and F. N. Cole, Bulletin of the American Mathematical Society, December, 1903, p. 136.
§ A. J. C, CunningTiam, Proceedings of the London Mathematical Society^ March 14, 1895, vol. xxvi, p. 261.
II Ibid., April 30, 1908, vol. vi (2ad series), p. xxii.
% L'Intennediaire des Matheniaticiens, Paris, 1909, vol. xvi, p. 252.
** Proceedings of the London Mathematical Society, April 11, 1912, vol. xi, p. xxiv.
tt Nature, London, March 28, 1912, vol. lxxxix, p. 87.
XX Sur la Theorie des Nombres Premiers, Turin, 1876, p. 11, quoted bj A. J. C. Cunningham, Proceedings of the London Mathematical Society, Nov. 14, 1895, vol. xxvii, p. 54, and Recherches sur les Ouvrages de Leonard de Pise, Rome, 1877, p. 26.
§§ L' Intermediaire des Matheniaticiens, Paris, Sept. 1894, vol. i, p. 148.
nil F. N. Cole, "On the Factoring of Large Numbers," Bulletin of the American Mathematical Society, December, 1903, pp. 134 — 137.
nil H. J. Woodall, Nature, London, July 20, 1911, vol. lxxxvii, p. 73.
22—2
340 meksenne's numbers [ch. xv
That N is prime when ^ = 89 was proved by Powers in 1911*
Bickmore in the memoir i* cited below showed that 5737 is another factor of iV if p = 239. Cunningham has also shown that 55871 is another factor of iV if ^ = 151, and that 54217 is another factor of iV^ if ^ = 251.
I turn next to consider the methods by which these results can be obtained. It is impossible to believe that the statement made by Mersenne rested on an empirical conjecture, but the puzzle as to how it was discovered is still, after more than 250 years, unsolved.
I cannot offer any solution of the riddle. But it may be interesting to indicate some ways which have been used in attacking the problem. The object is to find a prime divisor q (other than iV and 1) of a number N when N is of the form 2P — 1 and p is a prime.
I may observe that Lucas J showed that if we find the residue (mod N) of each term of the series 4, 14, 194, ... -m^, constructed according to the law Un+i = tin — 2, then N is prime if the first residue which is zero lies between the (p— l)/2th and the ^th residues. If an earlier residue is zero the theorem does not help us, but if none of the p residues is zero, N is composite. The application of the theorem to high numbers is so laborious that for the cases still unverified we are driven to seek other methods.
It can be easily shown that the prime divisor q must be of the form 2pt + 1. Also q must be of one of the forms 8i ± 1 : for N is of the form 2A^ — B\ where A is even and B odd, hence § any factor of it must be of the form 2a^ — h\ that is, of the form 8i ± 1, and 2 must be a quadratic residue of q. The theory of residues is, however, of but little use in finding
* K. E. Powers, American Mathematical Monthly, November, 1911, vol. xvni,
pp. 195—197.
t C. E. Bickmore, Messenger of Mathematics, Cambridge, 1895, vol. xxv, p. 19.
:J: American Journal of Mathematics, 1878, vol. i, p. 316.
§ Legendre, Theorie des Nomhres, third edition, Paris, 1830, vol. i, § 143. In the case of Mersenne's numbers, B = h=l.
CH. XV] mersenne's numbers 341
factors of the cases that still await solution, though the possi- bility some day of finding a complete series of solutions by properties of residues must not be neglected*. Our present knowledge of the means of factorizing iV has been summed up in the statement f that a prime factor of the form 2pt-^l can be found directly by rules due to Legendre, Gauss, and Jacobi, when ^= 1, 3, 4, 8, or 12 ; and that a factor of the form 2ptt'-\-l can be found indirectly by a method due to Bickmore when ^ = 1, 3, 4, 8, or 12, and t' is an odd integer greater than 3. But this only indicates how little has yet been done towards finding a general solution of the problem.
First. There is the simple but crude method of trying all possible prime divisors q which are of the form 2pt-{-l as well as of one of the forms 8i ±1.
The chief known results for the smaller factors may be summarized by saying that a prime of this form, when t is odd, will divide N when ^=1, if p=ll, 23, 83, 131, 179, 191, 239^ or 251 ; when t = 3, if ^ = 37, 73, or 233 ; when t = 5,if p = 43 [ when t = 15, if ;? = 113; when ^ = 17, if p = 79; when ^=19' ifp = 29, or 197; when t=25, if p = 47; when ^ = 41, if p^22S; when t = 59,ifp = 97; when ^ = 163, if jt^ = 41 ; when t = 461, if p = 163 ; when t = 1525, if p = 59 ; when t = 1609, if i? = 71. Similarly for even values of t, a prime of this form will divide N when « = 4, if ^ = 11, 29, 179, or 239; when i = 8, if ^ = 11; when ^=12, if ;) = 239; when ^ = 36, if j9 = 29,' or 211; when ^ = 60, if p = 53, or 151; when t=120, if ^ = 181; when j5 = 2112, if |)=173; and when i= 1445580 if jo = 67.
Of the 29 cases in which we know that the statement of the composite character of i\r is correct all save 7 can be easily verified by trial in this way. For, neglecting all values of t not
* For methods of finding the residue indices of 2 see Bickmore, Messenger of Mathematics, Cambridge, 1895, vol. xxv, pp. 15-21; see also A. J. C. Cunning- ham on 2 as a 16-ic residue. Proceedings of the London Mathematical Society 1895-6, vol. xxvn, pp. 85-122; and on Haupt-exponents of 2, Quarterly Journal 0/ Pure and Applied Mathematics, Cambridge, 1906, vol. xxxvii, pp. 122—145.
t Transactions of the British Association for the Advaticemcnt of Science (Ipswich Meeting), 1895, p. 614.
342
mersenne's numbers [ch. XV
exceeding, say, 60 which make q either composite or not of one of the forms 8^ ± 1, we have in each case to try only a com- paratively small number of divisors. Of the 7 other cases m which Mersenne's statement of the composite character of N has been verified, one verification (p = 41) is due to Plana, who frankly confessed that the result was reached " par un heureux hasard"; and a second is due to Landry (^5 = 59), who did not explain how he obtained the factors. The third is due to Cole (p = 67) who established it by the use of quadratic residues of N, three others {p = 71, 163, and 173) are due to Cunningham and one is due to Woodall. The last five verifications involved laborious numerical work, and it is possible that the results would have been obtained as easily by trial of prime divisors of
the form 2^^ + 1.
Of the 11 cases in which we know that the statement ol the prime character of N is correct all save two (namely, when ^5=61 and p = 89) may be verified by trial in this way, for the number of possible factors is not large.
Thus practically we may say that simple empirical trials would at once lead us to all the conclusions known except m the cases of 2^ = 41 due to Plana, of ^9 = 59 due to Landry, of p = 61 due to Seelhoff, of p=67 due to Cole, of ;) = 71, 163, and 173 due to Cunningham, of p = 181 due to Woodall, and of ;> = 89 due to Powers. In fact, save for these nine results the conclusions of all mathematicians to date could be obtained by anyone by a few hours' arithmetical work.
As p increases the number of factors to be tried increases so fast that, if p is large, it would be practically impossible to apply the test to obtain large factors. This is an important point, for Colonel Cunningham has stated that in the cases still awaiting verification there are no factors less than 1,000,000. Hence, we may take it as reasonably certain that this cannot have been the method by which the result was originally obtained; nor, as here enunciated, is it likely to give many factors not yet known. Of course it is possible there may be ways by which the number of possible values of t might be further limited, and if we could find them we might thus
CH. XV] MERSENNES NUMBERS 343
diminish the number of possible factors to be tried, but it will be observed that the values of iV which still await verification are very large, for instance, when ^ = 257, N contains no less than 78 digits.
It is hardly necessary to add that if q is known and is not very large we can determine whether or not it is a factor of N without the labour of performing the division.
For instance, if we want to verify that q = 13367 is a factor of N v/hen p = 41, we proceed thus. Take the power of 2 nearest to q or to its square-root. We have, to the modulus g,
2'^ =16384 = 3017 = 7x431,
,-. 2^^ =49 (-1377) = -638,
.-. 2=' =-319,
.-. 2"+^ = (3017) (-319) = !,
.-. 2" =1.
Second. We can proceed by reducing the problem to the sdution of an indeterminate equation.
It is clear that we can obtain a factor of N if we can express it is the difference of the squares, or more generally of the Tith povers, of two integers ii and v. Further, if we can express a nultiple of N, say mN, in this form, we can find a factor of mJS and (with certain obvious limitations as to the value of ?/i) ihit will lead to a factor of N. It may be also added that if m can be found so that N/m is expressible as a continued fraction of a3ertain form, a certain continuant* defined by the form of the continued fraction is a factor of N.
Snce N can always be expressed as the difference of two squajes, this method seems a natural one by which to attack the poblem. If we put
iV = n^ + a = (71 + by - (6^ + 2hn - a), we cai make use of the known forms of u and v, and thus
* Set J. G. Birch in the Messenger of Mathematics ^ Cambridge, 1902, vol. XXII, pp.52 — 55.
344 mersenne's numbers [ch. xv
obtain an indeterminate equation between two variables x and y of the form
where H and K are numbers which can be easily calculated. Integral values of x and y where y of u and v, and thus give factors of N.
We can also attack the problem by indeterminate equations in another way. For the factors must be of the form 2pt + 1 and 8j9s + 1, hence
= 2P-1
= 2(2P-i-l) + l,
.'. As^-t + Spst = {2P-^-l)lp
= (say) a + 8/;/3.
Hence 45 + i = a4-8p^, and st-^ — x,
where x'if- ^ and t is odd. These results again lead to an indeterminate equation.
But, in both cases, unless p is small, the resulting equatiois are intractable.
Third. A not uncommon method of attacking problens such as this, dealing with the factorization of large numbers, is through the theory of quadratic forms*. At best this is a difficult method to use, and we have no reason to think tiat it would have been employed by a mathematician of the seventeenth century I here content myself with alludng to it.
Fourth, There is yet another way in which the prollem might be attacked. The problem will be solved if we can find an odd prime q so that to it as modulus ^P^y = Zy and ^ = z, Avhere y and z may have any values we like to choost. If such values of q, y, and z can be found, we have 2^ (2^ — T) = 0. Therefore 2^ = 1, that is, 5' is a divisor of N, \
* For a sketch of this see G. B. Mathev/s, Theory of Numbers, part '., Cam- bridge, 1891, pp. 261—271. See also F. N. Cole's paper, " On the Fact»ring of Large Numbers," Bulletin of the American Mathematical Society, Decembr, 1903, pp. 134 — 137; and Quadratic Partitions by A. J. C. Cunningham, Londai, 1904.
CH. xv] mersenne's numbers 345
For example, to the modulus 23, we have
2« =3,
Also 2' =32.
Therefore 2^*^ - 2^ = 0,
.-. 21^-1 =0.
Without going further into the matter we may say that the d priori determination of the values of q, y, and z introduces us to an almost untrodden field. It is just possible (though I should suppose unlikely) that the key to the riddle is to be found on methods of finding q, y, z, to satisfy the above con- ditions. For instance, if we could say what was the remainder when 2* was divided by a prime q of the form 2pt + 1, and if the remainders were the same when x = u and (v = v, then to the modulus q we should have 2^ = 2", and therefore 2"~" = 1.
It should however be noted that Jacobi's Canon Arithmeticus and the similar canon drawn up by Cunningham would, if carried far enough, enable us to solve the problem by this method. Cunningham's Canon gives the solution of the con- gruence 2^ = R for all prime moduli less than 1000, but it is of no use in determining factors of N larger than 1000. It is however possible that if i? or ^ have certain forms an extended canon of this kind might be constructed, and thus lead to a solution of the problem
Fifth. It is noteworthy that the odd values of p specified by Mersenne are primes of one of the four forms 2? + 1 or 2^ + 3, but it is not the case that all primes of these forms make N a prime, for instance, N is composite if ^ = 2^ + 3 = 11 or if p = 2^-3 = 29.
This fact has suggested to more than one mathematician the possibility that some test as to the prime or composite character of N when p is of one of these forms may be dis- coverable. Of course this is merely a conjecture. There is however this to say for it, that we know that Fermat* had paid attention to numbers of this form.
* For instance, see above, pp. 39, 40.
346 mersenne's numbers [ch. xv
Sixth. The number N when expressed in the binary scale consists of 1 repeated p times. This has suggested whether the work connected with the determination of factors of N might not with advantage be expressed in the binary scale. A method based on the use of properties of this scale has been indicated by G. de Longchamps*, but as there given it would be unlikely to lead to the discovery of large divisors. I am, however, inclined to think that greater advantages would be gained by working in a scale whose radix was ^p or may-be 8^ — the resulting numbers being then expressed by a reasonably small number of digits. In fact when expressed in the latter scale in only one out of the cases in which the factors of N are known does the smallest factor contain more than two digits.
Seventh. I have reserved to the last the description of the method which seems to me to be the most hopeful.
We know by Fermat's Theorem that if x-\-\ is a prime then 2^ — 1 is divisible by ^ + 1. Hence if 2pt + 1 is a prime we have, to the modulus 2pt -I- 1,
^~" 2*^« -1=0,
/. (2P - 1) (1 + 2^ + 2^^^ + . . . + 2(2«-i)p) = 0.
Hence, a divisor of 2^ — 1 will be kno^wn, if we can find a value of t such that ^pt + 1 is prime and the second factor is prime to it.
This method may be used to establish Euler's Theorem of 1732. For if we put ^ = 1, and if 2^ + 1 is a prime, we have, to the modulus 2p + 1,
(22>-l)(2^-|-l) = 0.
Hence 2^ = 1 if 2^ + 1 is prime to 2p + 1. This is the case if ^ = 4w + 3. Hence 2p + 1 is a factor of iV if ^ = 11, 23, 83, 131, 179, 191, 239, and 251, for in these cases 2p-\-l is prime.
The problem of Mersenne's Numbers is a particular case of the determination of the factors of a^—1. This has been
* Comptcs Rendns de VAcademie des Scierices, Paris, 1877, vol. lxxxv, pp. 950—952.
CH. xv] mersenne's numbers 347
the subject of investigations by many mathematicians : an outline of their conclusions has been given by Bickmore*. I ought also to add a reference to the general method suggested by Lawrence f for the factorization of any high number: it is possible that Fermat used some method analogous to this.
Finally, I should add that machines t have been devised for investigating whether a number is prime, but I do not know that any have been constructed suitable for numbers as large as those involved in the numbers in question.
* Messenger of Mathematics, Cambridge, 1895-6, vol. xxv, pp. 1 — 44; also 1896-7, vol. XXVI, pp. 1—38 ; see also a note by Mr E. B. Escott in the Messenger , 1903-4, vol. XXXIII, p. 49.
+ F. W. Lawrence, Messenger of Mathematics , Cambridge, 1894-5, vol. xxiv, pp. 100 — 109 ; Quarterly Journal of Mathematics , Cambridge, 1896, vol. xxviii, pp. 285 — 311; and Transactions of the London Mathematical Society, May 13, 1897, vol. XXVIII, pp. 465 — 475.
X F. W. Lawrence, Quarterly Journal of Mathematics, Cambridge, 1896, already quoted, pp. 310 — 311 ; see also C. A. Laisant, Comptes Rendus, Association Franqais pour I' Avanccmerit des Sciences, 1891 (Marseilles), vol. xx, pp. 165 — 168.
348