Mersenne Numbers

By Hans Riesel

    During 1957 the author of this note had the opportunity of running the Swedish electronic digital computer BESK in order to examine Mersenne numbers. The intention of the author's investigation on the BESK was to check some known results, and to examine some Mersenne numbers not previously examined.

    Mersenne numbers are numbers Mp = 2p - 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 2p-1Mp is a perfect number, if Mp 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 Mp 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 Mp for one value of p of this order takes several hours on the BESK, a special program for calculating the smallest factor of Mp, if this factor is < 10 · 220 = 10485760, was worked out. This special program is based on the following well-known theorem:

    All prime factors q of Mp (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 Mp, 2p congruent to 1 (mod q). Since p is a prime, since all numbers n for which 2n = 1 (mod q) form a module, and since 2p congruent to 1 (mod q), this module consists of all integral multiples of the prime p. Now 2q-1 congruent to 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 x2 congruent to 2 (mod q) has the solution x congruent to 2(p+1)/2 (mod q), we see that 2 is quadratic residue mod q, hence q congruent to ± 1 (mod 8).

    By the above mentioned special program for small factors of Mp the values of Mp (mod q) for all primes q of the theorem were now calculated. When this residue was congruent to 0, the factor q was printed out. When no factor q < 10 · 220 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 M67, and Robinson's factors of M109 and M157, though greater than 10 · 220, 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 M163, 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 Mp. Those primes p, for which no factor < 10 · 220 of Mp 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 M3217 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 M3217 took about 5h30m on the BESK, for one run.

    A table of the smallest factor of 2p - 1, p prime follows. Primes 2p - 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.

    Received 8 November 1957.

Table omitted

Return to this paper's entry in Luke's Mersenne Library and Bibliography