# 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.

The groundwork for the study of this problem was laid by Lebesgue [2a], who proved in 1850 that M_{p} cannot be a perfect square, and by Gerono [2b], who proved in 1870 that M_{p} 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 8*i* ∓ 1” is erroneous, as revealed by the work’s own factorization of *M*_{43}. The correct statement is that the factorization of a composite Mersenne number contains an *odd number* of divisors of the form 8*i* − 1, and any number of divisors — or none — of the form 8*i* + 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*^{2}),

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^{15} [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} | 2^{1755} − 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^{15} 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 M_{p}, 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 *v _{2}*(

*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 ^{p} − 1 = *q*^{2}·*c**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 2*kp* + 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 8*k* ± 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 *k*_{1} ± 1)(8*k*_{2} ± 1) + 1*k*_{1}*k*_{2} ± 8*k*_{1} ± 8*k*_{2} + 2*k*_{1} + 1)(8*k*_{2} − 1) + 1*k*_{1}*k*_{2} − *k*_{1} + *k*_{2})*k*_{1}*k*_{2} − *k*_{1}) ||| *k*_{2}*k*_{1}(8*k*_{2} − 1) ||| *k*_{2}*k*_{1} ||| *k*_{2}

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 *q*^{2} in the role of the “A” set so defined, because a square cannot be congruent to −1 (*mod* 8). Thus,

(*q*^{2} − 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 (*q*^{2} − 1) ≡ 0 (mod 16), both sides of (**2**) are divisible by 16. Thus, by the first corollary,

*q*^{2} + *c* ≡ 0 (mod 32),

(3)

while by the second corollary,

*c* ≡ *q*^{2} − 2 (mod 256) (*p* > 8).

(4)

This can also be written

(*q*^{2} − *c*)/2 ≡ 1 (mod 128) (*p* > 8),

(5)

which shows that the difference *q*^{2} − *c* is oddly even.

As the right-hand side of (2) is divisible by 16, we have *c* ≡ −1 (mod 16)*c* ≡ ±2*q* −(−1)^{(q2−1)/16}∙32 + 29*q* ≡ ±1*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 ^{8})^{p} − 1 = *q*^{2}·*c**c* ≡ −1/*q*^{2} (mod 2^{p})*modulo* 2^{p} and capable of absorbing the denominator *q*^{2}. For *p* > 2 a suitable candidate is {(*q*^{2} − 1)^{p − 1} − 1}, which upon division by *q*^{2} yields the expression

(*q*^{2} − 2){1 + (*q*^{2} − 1)^{2} + (*q*^{2} − 1)^{4} + … + (*q*^{2} − 1)^{p − 3}}.

(6)

Since 16|(*q*^{2} − 1), all the terms in the curly braces except 1 vanish *modulo* 2^{8}, so that (6) reduces to (4). However, the terms in the curly braces do not generally vanish *modulo* 2^{9}.

### 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*^{2} 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^{n}∓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 *x ^{m}* =

*y*

^{2}+ 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 *x ^{m}* =

*y*+ 1,”

^{n}*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; 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^{n} − 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^{15} [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