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
2p - 1,
where p is a prime. See , 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
. Furthermore the number
is a perfect number, if
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
for one value of p of this order takes several hours on the
BESK, a special program for calculating the smallest factor of
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
(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
2p 1 (mod q).
Since p is a prime, since all numbers
n for which 2n = 1 (mod q)
form a module, and since
2p 1 (mod q),
this module consists of all integral multiples of
the prime p. Now
2q-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
x2 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 Mp
the values of
Mp (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 · 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
10 · 220,
have been printed in the table. On checking the values against other
sources, a misprint in Archibald's note  was detected. This misprint,
which concerns the value of the smallest factor of
M163, seems to have
come from Kraïtchik , 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
primes p, for which no factor
< 10 · 220
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 , was printed out in hexadecimal form. On September 8th,
1957, a run indicated that the number
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
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.
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.