Mersenne numbers are numbers M _p = 2 ^p  - 1, where p is a prime. See [1], which contains a more complete list of references. The Mersenne numbers have attained interest in connection with digital computers because there is a simple test to decide whether they are prime or composite. This is Lucas's test [1]. Furthermore the number 2 ^p-1 M _p is a perfect number, if M _p is a prime, and all known perfect numbers are of this form.

    In the beginning of 1957 a program for testing the primeness of the Mersenne numbers on the BESK was worked out by the author. This program, using Lucas's test, works for all p < 10000. As a test, this program was run for the following values of p: 2, 3, 5, 7, 13, 17, 19, 31, 61, 89, 107, 127, 521, 607, 1279, 2203, and 2281. The result was that the numbers M _p are prime for these values of p, thus confirming known results.

    After these tests, values of p > 2300 were to be tested. These values had not been tested before. But since the testing of M _p for one value of p of this order takes several hours on the BESK, a special program for calculating the smallest factor of M _p , if this factor is < 10 · 2 ²⁰ = 10485760, was worked out. This special program is based on the following well-known theorem:

    All prime factors q of M _p (p > 2) are of the form q = 2 kp + 1, and of one of the two forms q = 8l ± 1.

    The proof of the theorem is quite simple. If q is a factor of M _p , 2 ^p   1 (mod q). Since p is a prime, since all numbers n for which 2 ⁿ  = 1 (mod q) form a module, and since 2 ^p   1 (mod q), this module consists of all integral multiples of the prime p. Now 2 ^q-1   1 (mod q) if q is a prime, and hence q - 1 is a multiple of p, and in fact an even multiple (since q must be an odd number). This is the first part of the theorem: q - 1 = 2kp (k = 1, 2, 3, ...). The second part follows immediately from the theory of quadratic residues. Since x ²   2 (mod q) has the solution x  2 ^(p+1)/2  (mod q), we see that 2 is quadratic residue mod q, hence q  ± 1 (mod 8).

    By the above mentioned special program for small factors of M _p the values of M _p  (mod q) for all primes q of the theorem were now calculated. When this residue was  0, the factor q was printed out. When no factor q < 10 · 2 ²⁰ was found, the BESK turned to the next value of p. This program was run for all values of p < 10000. The running time on the BESK for one value of p lay between 0 and 2 minutes, depending on the size of the smallest factor. These smallest factors are given below in a table. The known Mersenne primes are also included in the table. Finally, Cole's factor of M ₆₇ , and Robinson's factors of M ₁₀₉ and M ₁₅₇ , though greater than 10 · 2 ²⁰ , have been printed in the table. On checking the values against other sources, a misprint in Archibald's note [2] was detected. This misprint, which concerns the value of the smallest factor of M ₁₆₃ , seems to have come from Kraïtchik [3], p. 24 and p. 92. As a further check, all factors in our table have been looked up in Lehmer's Prime Tables, except a few, which are too large, and a separate calculation was made, to check that they are of the form 2kp + 1. Since, however, there are disturbances in digital computers, it is not absolutely sure that all these numbers really are factors of the corresponding Mersenne numbers M _p . Those primes p, for which no factor < 10 · 2 ²⁰ of M _p was found, are, except the known Mersenne primes, omitted in the table.

    When this table had been calculated, the BESK examined the omitted values of p with Lucas's test. This was done for all values of p between 2300 and 3300. Since the available running time for testing Mersenne numbers on the BESK was limited, every value of p was tested only once. The final remainder, see [1], was printed out in hexadecimal form. On September 8th, 1957, a run indicated that the number M ₃₂₁₇ is prime. This result was repeated on September 12th. All other numbers tested turned out to be composite; however, this result could be false, since the running time is very long. The testing of M ₃₂₁₇ took about 5 ^h 30 ^m on the BESK, for one run.

    A table of the smallest factor of 2 ^p  - 1, p prime follows. Primes 2 ^p  - 1, p are indicated by a dash.

Ormangsgatan 67C
Stockholm-Vallingby, Sweden

    1. R. M. ROBINSON, "Mersenne and Fermat numbers," Amer. Math. Soc., Proc., v. 5, p. 842-846.
    2. R. C. ARCHIBALD, "Mersenne's numbers," Scripta Mathematica, v. 3, 1935, p. 112-119.
    3. M. KRAÏTCHIK, Recherches sur la Théorie des Nombres, Gauthier-Villars, Paris, 1952.

Table omitted