On square divisors of Mersenne numbers

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

Introduction

It has often been asked whether Mersenne numbers, i.e. numbers of the form M_p = 2^p − 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.

Gerono [2] layed the groundwork for the study of this problem with his proof that M_p can never be a perfect power. A general condition for divisibility of Mersenne numbers is Euler’s well-known criterion 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 M₄₃. The correct statement is that the factorization contains an odd number of divisors 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 M_p, the earlier, obtained by very elementary methods, is that q must satisfy the Wieferich congruence [9]

2^{q − 1} ≡ 1 (mod q²),

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·10¹⁵ [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 3511² | 2¹⁷⁵⁵ − 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·10¹⁵ in [10], with no further examples being found.]

The other of the strongest results relating to the possible 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 M_p is greater than (πp/log p)².

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, we shall for the sake of brevity write ||| between two expressions to indicate that they are divisible by precisely the same power of 2.

A condition on q and its cofactor

In this section, we write 2^p − 1 = q²·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 M_p 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 M_p has only two divisors the signs must be unlike, as otherwise M_p + 1, which is by definition a pure power of 2, would be of the form (8k₁ ± 1)(8k₂ ± 1) + 1 = 64k₁k₂ ± 8k₁ ± 8k₂ + 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 (8k₁ + 1)(8k₂ − 1) + 1 = 8(8k₁k₂ − k₁ + k₂). Since the parenthetic expression must be a pure power of 2, by the Lemma, (8k₁k₂ − k₁) ||| k₂ —> k₁(8k₂ − 1) ||| k₂ —> k₁ ||| k₂. This argument may be easily adapted to prove the following:

Theorem: We may group the divisors of a Mersenne number into two sets, A, congruent to +1 (mod 8), and B, is congruent to −1 (mod 8). These 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 the divisor-sets, 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).

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

(q² − 1) ||| (c + 1).

(2)

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

q² + c ≡ 0 (mod 32),

(3)

while by the second corollary,

c ≡ q² − 2 (mod 256)    (p > 8).

(4)

This can also be written

(q² − c)/2 ≡ 1 (mod 128)    (p > 8)

(5)

to emphasize that the difference of q² and c is oddly even.

As the right-hand side of (2) is divisible by 16, we have c ≡ −1 (mod 16); and more specifically, (4) is solved 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 (= 2⁸) be replaced with a higher power of 2. Let us write 2^p − 1 = q²·c as c ≡ −1/q² (mod 2^p). In order to make the right-hand side tractable, we seek an expression which is congruent to −1 modulo 2^p and capable of absorbing the denominator q². A suitable candidate is {(q² − 1)^{p − 1} − 1}, which upon division by q² yields the expression

(q² − 2){1 + (q² − 1)² + (q² − 1)⁴ + … + (q² − 1)^{p − 3}}.

(6)

Since 16|(q² − 1), all the terms in the curly braces except 1 vanish modulo 2⁸, so that (6) reduces to (4), while a simple calculation confirms that this is generally false modulo higher powers of 2.

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 q² 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 (yⁿ∓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.

2. C.G. Gerono, “Note sur la résolution en nombres entiers et positifs de l’équation x^m = yⁿ + 1,” Nouvelles Annales de Mathématiques, ser. 2, 9 (1870): 469−10 (1871): 204−6, cited by Wacław Sierpiski, Elementary Theory of Numbers (Warszawa, 1964; 2^nd 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 n² | 2ⁿ − 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 × 10¹⁵ [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 4 February 2010