On square divisors of Mersenne numbers

By John Blythe Dobson (j.dobson@uwinnipeg.ca)

Although the author is employed by the University of Winnipeg, he has no affiliation with the Mathematics Department or with any other academic department.

Introduction

It has often been asked whether Mersenne numbers, i.e. numbers of the form Mp = 2p − 1 with p prime, can have square divisors. These notes are merely a brief review of the more important literature on the subject, and make little claim to originality.

The groundwork for the study of this problem was laid by Lebesgue [2a], who proved in 1850 that Mp cannot be a perfect square, and by Gerono [2b], who proved in 1870 that Mp cannot be a perfect power. A general condition for divisibility of Mersenne numbers is Euler’s well-known criterion that a divisor have 2 as a quadratic residue, and thus be ≡ ±1 (mod 8). It should be noted that the statement in [1, p. xiii] that “every composite [Mersenne number] contains at least one factor of each form 8i ∓ 1” is erroneous, as revealed by the work’s own factorization of M43. The correct statement is that the factorization of a composite Mersenne number contains an odd number of divisors of the form 8i − 1, and any number of divisors — or none — of the form 8i + 1.

Of the two strongest previous results relating to the specific question of the existence of a square divisor q of Mp, the earlier, obtained by very elementary methods, is that q must satisfy the Wieferich congruence [9]

2q − 1 ≡ 1 (mod q2),

which had made its first appearance in connection with the first case of Fermat’s Last Theorem. This was proved in 1965 by Rotkiewicz [6] and independently rediscovered in 1967 by Warren and Bray [7]. This congruence, which has been tested to q = 1.25·1015 [3], has as its only known solutions the numbers 1093, which being ≡ 5 (mod 8), does not have the required linear form (and thus the required quadratic character) to divide a Mersenne number, and 3511, for which, although 35112 | 21755 − 1, the associated exponent 1755 is not a prime number. These numbers are discussed further in our Note on the two known Wieferich Primes.

[Note added 28 February 2009: The search-limit for Wieferich primes has since been extended to 6.7·1015 in [10], with no further examples being found.]

The other of the strongest results relating to the existence of a square divisor of a Mersenne number is the much more recent one of Le Maohua [4], obtained by analytical methods, that the squarefree part of Mp, with p ≥ 11, is greater than (πp/log p)2.

However, while each of these contributions places a severe constraint on possible square divisors of Mersenne numbers, the situation remains essentially the same as summarized by Daniel Shanks in 1965 [8]: “Heuristically, the probability of a multiple factor here is quite low. Such a [factor] q has not been previously found, but on the other hand, no convincing argument has ever been offered for the conjecture that they do not exist.” A number of erroneous purported proofs of the squarefreeness of Mersenne numbers (including one cited by Shanks) have appeared over the years, their crucial error generally being an ignorance of the existence of Wieferich primes.

We shall next consider, from a strictly elementary point of view, a congruence which must be satisfied for q to be a square divisor of a Mersenne number. The possibility that this line of development could contribute anything significant to a solution of the question at hand seems remote, and we offer it here simply as a minor comment on an interesting problem.

Lemma: We shall require the following Lemma: If the sum or difference of two even numbers is a pure power of two, the two numbers have the same 2-adic valuation (that is, they are both divisible by precisely the same power of 2); otherwise, the expression, when divided by the lower power of 2, would contain an odd factor. In what follows, rather than using the standard notation v2(n) for the 2-adic valuation of n, we shall find it convenient to write ||| between two expressions to indicate that they have the same 2-adic valuation.

A condition on q and its cofactor

In this section, we write 2p − 1 = q2·c (we intend c to stand for “cofactor,” and do not assume that it is necessarily squarefree, or free of the divisor q). We first recall the criterion observed by Fermat and proved by Euler [1b], that the divisors of Mp are all of the form 2kp + 1 (Euler does not actually write the coefficient 2, but clearly as the expression must be odd we may do so without loss of generality). Furthermore, Euler’s criterion that such a divisor be ≡ ±1 (mod 8) ensures that k ≡ 0 or −p (mod 4).

Since all divisors of Mersenne numbers are of the form 8k ± 1, in the case where Mp has only two divisors the signs must be unlike, as otherwise Mp + 1, which is by definition a pure power of 2, would be of the form (8k1 ± 1)(8k2 ± 1) + 1 = 64k1k2 ± 8k1 ± 8k2 + 2, which upon division by 2 leaves a quotient which is clearly odd. We may therefore assume without loss of generality that the expression is of the form (8k1 + 1)(8k2 − 1) + 1 = 8(8k1k2k1 + k2). Since the parenthetic expression must be a pure power of 2, by the Lemma, (8k1k2k1) ||| k2 —> k1(8k2 − 1) ||| k2 —> k1 ||| k2. This argument may be easily adapted to prove the following:

Theorem: We may group the divisors of a Mersenne number (possibly in more than one way) into two sets, the product of one being congruent to +1 (mod 8) and the other congruent to −1 (mod 8). Call these products A and B respectively. Then they satisfy the relation

(A − 1) ||| (B + 1).

(1)

Two corollaries easily follow:

Corollary 1: (A − 1) and (B + 1) are by definition odd multiples of the same power of two. Hence their sum is divisible by a higher power of 2 than that which divides either. This has been noticed by Pérez-Cacho ([5], p. 51) who writes (in our notation) that A + B ≡ 0 (mod 16).
Corollary 2: The product of (A − 1) and (B + 1), AB + A − B − 1, is divisible by the square of the power of 2 which divides either side of (1), which is therefore an even power of 2; and since AB + 1 is by definition divisible by 256 when p > 8, with this proviso we have A − B − 2 ≡ 0 (mod 256). This condition is stronger than that of Pérez-Cacho.

We may cast the square divisor q2 in the role of the “A” set so defined, because a square cannot be congruent to −1 (mod 8). Thus,

(q2 − 1) ||| (c + 1),

(2)

or equivalently,

2 (q ∓ 1) ||| (c + 1)

(2b)

according as q ≡ ± 1 (mod 8). This is possibly the strongest result that can be obtained by so naïve a method. But we note the consequence that since (q2 − 1) ≡ 0 (mod 16), both sides of (2) are divisible by 16. Thus, by the first corollary,

q2 + c ≡ 0 (mod 32),

(3)

while by the second corollary,

cq2 − 2 (mod 256)    (p > 8).

(4)

This can also be written

(q2c)/2 ≡ 1 (mod 128)    (p > 8),

(5)

which shows that the difference q2c is oddly even.

As the right-hand side of (2) is divisible by 16, we have c ≡ −1 (mod 16); and more specifically, it may be worked out with a little effort that (4) is characterized by c ≡ ±2q −(−1)(q2−1)/16∙32 + 29 (mod 256) according as q ≡ ±1 (mod 8). We certainly do not mean to suggest that any of statements (2) through (4) has any value for computational purposes, as of course these statements only describe the relationship holding between q and c and reveal nothing about their actual values, or even about their linear forms (other than determining the residue class to which c belongs modulo 16). [Note added 21 June: in a sequel to the present note it is shown that c ≡ 31 (mod 48).]

It is possible to show that statement (4) is optimal in the sense that it is generally false if the modulus 256 (= 28) be replaced with a higher power of 2. Let us write 2p − 1 = q2·c as c ≡ −1/q2 (mod 2p). In order to make the right-hand side tractable, we seek an expression which is congruent to −1 modulo 2p and capable of absorbing the denominator q2. For p > 2 a suitable candidate is {(q2 − 1)p − 1 − 1}, which upon division by q2 yields the expression

(q2 − 2){1 + (q2 − 1)2 + (q2 − 1)4 + … + (q2 − 1)p − 3}.

(6)

Since 16|(q2 − 1), all the terms in the curly braces except 1 vanish modulo 28, so that (6) reduces to (4). However, the terms in the curly braces do not generally vanish modulo 29.

Conclusion

It seems doubtful whether so elementary an argument can be pursued further to any useful end. Working out the above calculations with greater attention to the fact that q2 is a perfect square makes no difference to the end result, because the only critical point is that for a divisor which is congruent to 1 mod 8, its square is quaranteed to be congruent to 1 mod 16.

References

1. Allan J.C. Cunningham & H.J. Woodall, Factorization of (yn∓1) … up to high powers…. London, 1925.

1b. Leonhard Euler, “Theoremata circa divisores numerorum,” Novi Commentarii Academiæ Scientiarum Petropolitanæ 1 (for 1747−48; published 1750): 20−48, theorem 9, corollarium 5, available online at http://gallica.bnf.fr/scripts/ConsultationTout.exe?O=N006952. An English translation by Jordan Bell is available at http://arxiv.org/PS_cache/math/pdf/0606/0606057v1.pdf. Cf. Leonard E. Dickson, History of the Theory of Numbers, 3 vols. (Washington, 1919−23), 1:18.

2a. M. Lebesgue, “Sur l’impossibilité, en nombres entiers, de l’équation xm = y2 + 1,” Nouvelles Annales de Mathématiques, ser. 1, 9 (1850): 178–81.

2b. C.C. Gerono, “Note sur la résolution en nombres entiers et positifs de l’équation xm = yn + 1,” Nouvelles Annales de Mathématiques, ser. 2, 9 (1870): 469–71; 10 (1871): 204–6; see the first installment. We first learned of this paper from by Wacław Sierpiski, Elementary Theory of Numbers (Warszawa, 1964; 2nd ed. Amsterdam, &c., 1988), cap. X, §1, theorem 2.

3. Joshua Knauer and Jörg Richstein, “The continuing search for Wieferich primes,” Mathematics of Computation 74 (2005): 1559-1563.

4. Le Maohua, “On Mersenne Numbers” [in Chinese], Journal of Jishou University (Natural Science Edition) 20(1) (March 1999): 17-19.

5. Laureano Pérez-Cacho, “El último teorema de Fermat y los números de Mersenne,” Revista de la Real Academia de Ciencias Exactas, Fisicas y Naturales de Madrid 40 (1946): 39-57.

6. A. Rotkiewicz, “Sur les nombres de Mersenne dépourvus de diviseurs carrés et sur les nombres naturels n tels que n2 | 2n − 2,” Matematički Većnik / Matematicki Vesnik 2(17) (1965): 78−80. We first learned of this little-known paper through various writings of Paulo Ribenboim.

7. Le Roy J. Warren and Henry G. Bray, “On the Square-Freeness of Fermat and Mersenne Numbers,” Pacific Journal of Mathematics 22 (1967): 563−4. Available online at http://projecteuclid.org/handle/euclid.pjm/1102992105.

8. Daniel Shanks, review no. 113, Mathematics of Computation 19 (1965): 686.

9. A. Wieferich, “Zum letzten Fermatschen Theorem,” Journal für die Reine und Angewandte Mathematik 136 (1909): 293−302. Available online at http://gdzdoc.sub.uni-goettingen.de/sub/digbib/loader?ht=VIEW&did=D255696.

10. F.G. Dorais and D.W. Klyve, Near Wieferich Primes up to 6.7 × 1015 [PDF]. Dated November 27, 2008. Available online at http://www-personal.umich.edu/~dorais/docs/wieferich.pdf.

First published 12 August 2007
With minor revisions through 6 August 2017