Wieferich primes and Mersenne primes

For elMath.org: Miroslav Kures
Institute of Mathematics, Brno University of Technology
Contact:
Creation date: 2007-12-28

1  Introduction

Let n ∈ N; Mersenne numbers are defined by Mn=2n−1. A binary expression of Mersenne numbers consists of units only.

Proposition 1 If Mn is a prime number, then n is a prime number. (The reverse implication need not hold.)

Let n=kl be a composite number. Then 2n−1=2kl−1=(2l−1)(2l(k−1)+2l(k−2)+...+2l+1), i.e. 2n−1 is a composite number, too. On the other hand, 211−1=2047=23·89.

Thus, we monitor especially Mersenne numbers Mp, where p is a prime number. If such Mp is also a prime, we call it the Mersenne prime. It is not known, how many Mersenne primes exist not even if it is a finite number. Up to now, 44 Mersenne primes are known, the latest one is M32582657, it was discovered in 2006 and it represents a greatest known prime at all.

2  Perfect numbers

A number n ∈ N is called a perfect number if it is equal to the sum of all its divisors, excluding n itself. (For example, 6 and 28 are perfect numbers.)

Proposition 2 n is an even perfect number if and only if it has form n=2p−1(2p−1) and 2p−1=Mp is a (Mersenne) prime. (It is not known whether or not there exists an odd perfect number.)

3  Are Mersenne numbers square free?

We call a Mersenne number Mn divisible by square, if there exists a prime q such that q2 divides Mp. If there is no such a prime, we call Mn square free. If n is a composite number, then Mn can be divisible by square, e.g. for n=6 we have M6=63=32·7. It is remarkable that M1092 is divisible by 10932 and M3510 is divisible by 35112, see [1]. (1093 and 3511 are Wieferich primes satisfying 2q−1 ≡ 1  ( mod q2).)

If p is a prime, then the question if Mp is square free is open. However, the following result is known.

Proposition 3 Let p,q be primes. If q2 divides Mp, then q is a Wieferich prime.

Evidently, p and q must be odd. Let q2 divides Mp, i.e.

2p ≡ 1   ( mod q2),
it follows q also divides Mp, i.e.
2p ≡ 1   ( mod q).

It follows from this equation, that p must be the order of 2 (in Fq), because p is a prime. From the Little Fermat Theorem follows that

2q−1 ≡ 1   ( mod q)

and it means that p divides q−1. However, q−1 is even and that is why q−1=2kp for some k ∈ N. Hence

2p = 2[(q−1)/2k] ≡ 1     ( mod q2);

after the exponentiation to the 2k-th power

2q−1 ≡ 1   ( mod q2);

it means q is a Wieferich prime. Nevertheless, it was proved that squares of Wieferich primes 1093 and 3511 never divide Mp. Therefore aspirants for it are only squares of possible new Wieferich primes.

4  Wieferich primes and ECC

The interesting application in elliptic curve cryptography is indicated by the following theorem from [2].

Proposition 4 For a Mersenne prime q=Mp=2p−1, binomials xp+2s and xp−2s, where s ≠ 0 ( mod p), is irreducible in Fq[x] if p is not a Wieferich prime.

References

[1]
Guy, R. K., The primes 1093 and 3511, The Mathematics Student 35 (1967), 204-206
[2]
Baktir, S., Sunar, B., Frequency domain finite field arithmetic for elliptic curve cryptography, preprint

Author: Miroslav Kures