NEW MERSENNE PRIMES By Alexander Hurwitz If p is prime, Mp = 2^p - 1 is called a Mersenne number. The primes M4253 and M4423 were discovered by coding the Lucas-Lehmer test for the IBM 7090. These two new primes are the largest prime numbers known; for other large primes see Robinson [4]. The computing was done at the UCLA Computing Facility. This test is described by the following theorem (see Lehmer [1, p. 443-4]). THEOREM. If S[1] = 4 and S[n+1] = S[n]^2 - 2 then Mp is prime if and only if S[p-1] == 0 (mod Mp). The test takes about 50 minutes of machine time for p = 4423. These results bring the number of known Mersenne primes to 20. The values of p for these twenty primes are listed in Table 1. If Mp is prime it is of interest to know the sign of the least absolute penultimate residue, that is, whether S[p-2] == +2^r (mod Mp) or S[p-2] == -2^r (mod Mp) where 2r = p+1. The Lucas-Lehmer test can also be used with S[1] = 10. The various penultimate residues of the known Mersenne primes were computed and the re- sults appear in Table 1 (see Robinson [3]). In addition to testing the above Mersenne primes each Mersenne number with p < 5000 was tested unless a factor of Mp was known. The residues of S[p-1] (mod Mp) are available for checking purposes. The results for 3300 < p < 5000 are sum- marized in Table 2. The computer program also found (see [3, p.844]) that M8191 is not prime. The residue S[p-1] (mod Mp) for p > 3300 is output from the computer in a modified octal notation. That is, the residue is stored in the computer in 35 bit binary words and the output is a word by word conversion of the 35 bit words into octal (base 8) numbers. Thus the leading digit of each is quaternary (base 4). For p < 3300 the residue was printed in hexadecimal notation (see Robinson [3] and Reisel [2]). TABLE 1 ------+--------------+-------------+-----------+--------------+----------- p | S[1] = 4 | S[1] = 10 | p | S[1] = 4 | S[1] = 10 ------+--------------+-------------+-----------+--------------+----------- 2 | | | 107 | - | + 3 | + | - | 127 | + | + 5 | + | - | 521 | - | + 7 | - | - | 607 | - | - 13 | + | + | 1279 | - | - 17 | - | + | 2203 | + | - 19 | - | + | 2281 | - | + 31 | + | + | 3217 | - | + 61 | + | + | 4253 | + | + 89 | - | + | 4423 | - | - ------+--------------+-------------+-----------+--------------+----------- TABLE 2 -------------------------------------------------------------------------- p R p R -------------------------------------------------------------------------- 3301 72013 4241 11012 3307 62061 4253 00000 3313 10050 4259 46007 3331 51270 4261 55632 3343 76415 4283 74774 3371 57040 4339 41356 3373 36120 4349 74465 3389 64705 4357 74271 3413 50261 4363 61114 3461 03241 4397 40174 3463 57665 4409 51070 3467 23046 4421 25131 3469 21765 4423 00000 3547 75574 4481 70216 3559 45350 4493 36053 3583 42507 4519 01571 3607 45062 4523 22235 3617 35431 4567 74267 3631 14530 4583 46556 3637 67413 4591 47243 3643 04606 4621 74601 3671 04031 4643 51444 3673 01626 4651 00707 3691 54715 4663 52442 3697 53743 4673 40333 3709 06427 4679 14305 3739 22413 4703 54013 3769 00747 4721 04420 3821 52075 4729 40137 3833 45453 4733 12774 3847 57652 4783 77350 3877 46507 4789 02364 3881 34503 4799 04305 3889 30737 4817 70020 3919 16520 4831 33213 3943 33442 4877 75412 4007 17770 4889 24410 4027 60265 4909 61113 4049 31260 4937 26525 4051 63236 4951 22271 4091 55650 4973 03354 4093 26670 4987 72275 4111 20437 ---------------- 4133 66046 8191 03624 4157 43640 4159 62544 4177 16076 4201 53211 4219 51756 5231 51457 -------------------------------------------------------------------------- The five least significant octal digits of the residue appear in Table 2 for each p > 3300 tested. If p (3300 < p < 5000) is omitted from Table 2 a factor of 2^p-1 is known. Some of these factors are not yet published but were communicated to the author by John Brillhart. My thanks to the Computing Facility for their help in this work, especially J. L. Selfridge and F. H. Hollander. University of California at Los Angeles Los Angeles, California 1. D. H. LEHMER, "An extended theory of Lucas' functions," Ann. of Math. v. 31, 1930, p. 419-448. 2. H. REISEL, "Mersenne numbers," MTAC, v. 12, 1958, p. 207-213. 3. R. M. ROBINSON, "Mersenne and Fermat numbers," Proc. Amer. Math. Soc. v. 5, 1954, p. 842-846. 4. R. M. ROBINSON, "A report on primes of the form k*2^n+1 and on factors of Fermat numbers," Proc. Amer. Math. Soc. v. 9, 1958, p. 673-681 Received November 3, 1964. The preparation of this paper was sponsored by the U. S. Research.