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-1M_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^h30^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