Mersenne Primes in Real Quadratic Fields

Sushma Palimar and B. R. Shankar Department of Mathematical and Computational Sciences National Institute of Technology Karnataka, Surathkal Mangalore India

                    sushmapalimar@gmail.com
                      shankarbr@gmail.com

Abstract The concept of Mersenne primes is studied in real quadratic fields with class number one. Computational results are given. The field ℚ(\sqrt{2}) is studied in detail with a focus on representing Mersenne primes in the form x^{2} + 7y^{2}. It is also proved that x is divisible by 8 and y ≡ ±3 (mod 8), generalizing a result of F. Lemmermeyer, first proved by H. W. Lenstra and P. Stevenhagen using Artin’s reciprocity law.

1 Introduction

It is well known that a^{d} − 1 divides a^{n} − 1 for each divisor d of n, and if n = p, a prime, then

a^{p} − 1 = (a − 1)(1 + a + a^{2} + ⋯ + a^{p−1})

and if a^{p} −1 is a prime, then a = 2. Number theorists of all persuasions have been fascinated by prime numbers of the form 2^{p} − 1 ever since Euclid used them for the construction of perfect numbers. In modern times, they are named after Marin Mersenne (1588-1648). A well known result due to Euclid is that, if 2^{p} −1 is a prime then 2^{p−1}(2^{p} −1) is perfect. Much later Euler proved the converse, every even-perfect number has this form.

Mersenne primes have been studied by amateurs as well as specialists. Mersenne primes are used in cryptography too in generating pseudorandom numbers. By far, the most widely used technique for pseudorandom number generation is an algorithm first proposed by Lehmer, known as the linear congruential method. It is generated by the recursion X_{n+1} ≡ aX_{n} (mod M_{31}), where M_{31} is the Mersenne prime 2^{31} −1. Of the more than two billion choices for a, only a handful of multipliers are useful. One such value is a = 7^{5} = 16807, which was originally designed for use in the IBM 360 family of computers, Stallings [10].

On March 3, 1998, the birth centenary of Emil Artin was celebrated at the Universiteit van Amsterdam. The paper Lenstra and Stevenhagen [5] is based on two lectures given on the occasion. We quote from Lenstra and Stevenhagen [5]: “Artin’s reciprocity law is one of the cornerstones of class field theory. To illustrate its usefulness in elementary number theory, we shall apply it to prove a recently observed property of Mersenne primes.” The property of Mersenne primes referred to is the following: if M_{p} = 2^{p} − 1 is prime and p ≡ 1 (mod 3), then M_{p} = x^{2} + 7y^{2} for some integers x, y and one always has x ≡ 0 (mod 8) and y ≡ ±3 (mod 8). This was first observed by Franz Lemmermeyer.

Many have attempted to generalize the notion of Mersenne primes and even-perfect numbers to complex quadratic fields with class number 1. One reason is that they have only finitely many units. Indeed, with the exception of ℚ(\sqrt{−1}) and ℚ(\sqrt{−3}), the other seven complex quadratic fields with class number 1 have only two units, ±1. Spira [9] defined Mersenne primes over ℚ(\sqrt{−1}) to give a useful definition of even-perfect numbers over ℤ[i], the ring of Gaussian integers. His work was continued later by McDaniel [6, 7] to give an analogue of Euclid-Euler theorem over ℚ(\sqrt{−1}) and ℚ(\sqrt{−3}). In both the papers the concept of Mersenne primes is used to give a valid definition of even-perfect numbers.

Recently Berrizbeitia and Iskra [1] studied Mersenne primes over Gaussian integers and Eisenstein integers. The primality of Gaussian Mersenne numbers and Eisenstein Mersenne numbers are tested using biquadratic reciprocity and cubic reciprocity laws respectively.

In this paper the concept of Mersenne primes is studied in real quadratic fields 𝕂 = ℚ(\sqrt{d}) with class number 1, so that unique factorization holds and irreducibles are always prime.

We denote the ring of integers of 𝕂 by O_{K},

O_{K} = \begin{cases}ℤ[\sqrt{d}], & if d ≡ 2, 3 (mod 4); \\ ℤ[\frac{1+\sqrt{d}}{2}], & if d ≡ 1 (mod 4). \end{cases}

Since 𝕂 is a unique factorization domain, irreducibles are primes in these domains. Hence for any η ∈ 𝕂 the two factorings

η = π_{1}^{k_{1}}π_{2}^{k_{2}} ⋯ π_{r}^{k_{r}} and η = ϵ_{1}π_{1}^{k_{1}}ϵ_{2}π_{2}^{k_{2}} ⋯ ϵ_{r}π_{r}^{k_{r}}

are considered to be one and the same, where ϵ_{i} are units and π_{i} are irreducibles.

We define M_{p,α} = \frac{α^{p}−1}{α−1} such that α ∈ O_{K} is irreducible and u = α−1 is a unit other than ±1. Then M_{p,α} may be called as an analog of Mersenne prime if the norm of M_{p,α} namely N(M_{p,α}) = N(\frac{α^{p}−1}{a−1}) is a rational prime. Condition for the irreducibility of α = 1 + u ∈ O_{K} such that α − 1 is a unit (other than ±1) is derived in the next section. For this we study the case N(α − 1) = N(u) = ±1 separately. We also give a list of such quadratic fields and a few Mersenne primes in those fields. Computational results show that, among real quadratic fields, Mersenne primes in ℚ(\sqrt{2}) have a definite structure.

The special property of the usual Mersenne primes observed by Franz Lemmermeyer and proved in Lenstra and Stevenhagen [5] admits a generalization to Mersenne primes over ℚ(\sqrt{2}). This property appears to be special only to ℚ(\sqrt{2}). Some interesting properties of Mersenne primes and recent primality tests to check the primality of Mersenne numbers in ℚ(\sqrt{2}) are given. Also, the usual Mersenne primes given by M_{p} = 2^{p} − 1, can be obtained from the field 𝕂 = ℚ(\sqrt{2}) without altering the conditions on M_{p,α}.

2 Basic Results

Below we consider various cases under which α is irreducible.

Theorem 1. Let d ≡ 2, 3 (mod 4) and N(α − 1) = −1. Then α is irreducible if and only if d = 2 and u ∈ \{1 + \sqrt{2}, 1 − \sqrt{2}, −1 + \sqrt{2}, −1 − \sqrt{2}\}.

Proof. Let α be irreducible and u = a + b\sqrt{d}. Then α = (a + 1) + b\sqrt{d}. Hence N(α) = (a + 1)^{2} − 2b^{2} = N(u) + 2a + 1 = 2a. Since α is irreducible, 2a should be a rational prime. Hence a = ±1. With a = 1, u = 1 + b\sqrt{d} and N(u) = −1 = 1 − b^{2}d. i.e., b^{2}d = 2. Since d is square-free, d = 2 and b = ±1. Similarly with a = −1, we get b = ±1 and d = 2.

Conversely let d = 2 and u = a+b\sqrt{2} be any unit in ℚ(\sqrt{2}). Then α = (a+1)+b\sqrt{2} and N(α) = (a+1)^{2}−2b^{2} = a^{2}−2b^{2}+2a+1 = N(u)+2a+1 = 2a, is a rational prime, if and only if a = ±1. As before, we get b = ±1. Hence different choices of u for which α is irreducible are respectively, 1 + \sqrt{2}, 1 − \sqrt{2}, −1 + \sqrt{2} and −1 − \sqrt{2}. As 1 + \sqrt{2} is the fundamental unit, these values are, u, −u^{−1}, u^{−1}, −u. Corresponding α values are, 2 + \sqrt{2}, 2 − \sqrt{2}, \sqrt{2} and −\sqrt{2}.

Since 2 − \sqrt{2} and −\sqrt{2} are the conjugates of 2 + \sqrt{2} and \sqrt{2} respectively, we compute M_{p,α} with α = 2 + \sqrt{2} and \sqrt{2}.

For α = 2 + \sqrt{2} a few Mersenne primes in ℚ(\sqrt{2}) are given below:

\begin{matrix}p & M_{p,α} & N(M_{p,α}) \\ 2 & 3 + \sqrt{2} & 7 \\ 3 & 9 + 5\sqrt{2} & 31 \\ 5 & 97 + 67\sqrt{2} & 431 \\ 7 & 1121 + 791\sqrt{2} & 5279 \\ 11 & 152193 + 107615\sqrt{2} & 732799 \end{matrix}

Table 1: Mersenne primes in ℚ(\sqrt{2}).

The next three Mersenne primes are found at p = 73, with

N(M_{p,α}) = 851569055172258793218602741480913108991,

p = 89 with

N(M_{p,α}) = 290315886781191681464330388772329064268797313023,

and at p = 233 with

N(M_{p,α}) = 18060475427282023033368001231166441784737806891537

806547065314167911959518498581747712829157156517940837234519177963497324543.

With α = \sqrt{2}, M_{p,α} = \frac{(\sqrt{2})^{p}−1}{\sqrt{2}−1}. Thus N(M_{p,α}) = 2^{p} − 1, giving all the usual Mersenne numbers.

Theorem 2. Let d ≡ 1 (mod 4) and α − 1 = u = \frac{a+b\sqrt{d}}{2} be a unit such that, N(u) = N(α − 1) = −1. Then α is irreducible if and only if a is a rational prime and b is some odd integer.

Proof. By hypothesis, N(α) = \frac{(a+2)^{2}−db^{2}}{4} = a, since N(u) = −1. For α to be irreducible a should be an odd rational prime. Indeed if a = 2 then u = \frac{2+b\sqrt{d}}{2} and N(u) = \frac{4−db^{2}}{4} = −1 ⇒ b^{2}d = 8. This is impossible since d ≡ 1 (mod 4). Hence it is clear that b is some odd integer. Thus the analogs of Mersenne primes are defined for d ≡ 1 (mod 4) whenever units are of the form u = ^{\frac{p+(2n+1)\sqrt{d}}{2}}, where n ∈ ℤ and p is an odd rational prime. The converse is straightforward since the norm of α is a = p, a rational prime by assumption.

Table 2 shows the values of d ≡ 1 (mod 4), d < 500 for which the class number is 1, N(u) = −1 and α is irreducible.

\begin{matrix}ℚ(\sqrt{d}) & u & α & N(α) \\ ℚ(\sqrt{13}) & (\frac{3+\sqrt{13}}{2}) & (\frac{5+\sqrt{13}}{2}) & 3 \\ ℚ(\sqrt{29}) & (\frac{5+\sqrt{29}}{2}) & (\frac{7+\sqrt{29}}{2}) & 5 \\ ℚ(\sqrt{53}) & (\frac{7+\sqrt{53}}{2}) & (\frac{9+\sqrt{53}}{2}) & 7 \\ ℚ(\sqrt{149}) & (\frac{61+5\sqrt{149}}{2}) & (\frac{63+5\sqrt{149}}{2}) & 61 \\ ℚ(\sqrt{173}) & (\frac{13+\sqrt{173}}{2}) & (\frac{15+\sqrt{173}}{2}) & 13 \\ ℚ(\sqrt{293}) & (\frac{17+\sqrt{293}}{2}) & (\frac{19+\sqrt{293}}{2}) & 17 \end{matrix}

Table 2: d ≡ 1 (mod 4) N(u) = −1 ; α is irreducible.

Theorem 3. Let d ≡ 2, 3 (mod 4) and u = a + b\sqrt{d} be a unit, such that N(u) = 1. Then α is always reducible.

Proof. By hypothesis, α = (a + 1) + b\sqrt{d} and N(α) = 2(1 + a), which is prime only if a = 0, which contradicts N(u) = 1. Hence α is not irreducible.

Theorem 4. Let d ≡ 1 (mod 4) and u = \frac{a+b\sqrt{d}}{2} be a unit such that N(u) = 1. Then, α is irreducible if and only if a + 2 is a rational prime and b is some odd integer.

Proof. By hypothesis, N(α) = \frac{(a+2)^{2}−db^{2}}{4} = a + 2, since N(u) = 1. For α to be irreducible a + 2 should be a rational prime. Clearly a ≠ 0 and a^{2} ≡ 1 (mod 4). Since d ≡ 1 (mod 4) it is clear that b is some odd integer. Thus the analogs of Mersenne primes are defined for d ≡ 1 (mod 4) whenever units are of the form u = ^{\frac{a+(2n+1)\sqrt{d}}{2}}, where n ∈ ℤ and a + 2 is an odd rational prime. Converse is straightforward as in theorem 2.

Table 3 below shows the values of d ≡ 1 (mod 4), d < 500 for which the class number is 1, N(u) = 1 and α is irreducible.

\begin{matrix}ℚ(\sqrt{d}) & u & α & N(α) \\ ℚ(\sqrt{21}) & \frac{5+\sqrt{21}}{2} & \frac{7+\sqrt{21}}{2} & 7 \\ ℚ(\sqrt{77}) & \frac{9+\sqrt{77}}{2} & \frac{11+\sqrt{77}}{2} & 11 \\ ℚ(\sqrt{93}) & \frac{29+3\sqrt{93}}{2} & \frac{31+3\sqrt{93}}{2} & 31 \\ ℚ(\sqrt{237}) & \frac{77+5\sqrt{237}}{2} & \frac{79+5\sqrt{237}}{2} & 79 \\ ℚ(\sqrt{437}) & \frac{21+\sqrt{437}}{2} & \frac{23+\sqrt{437}}{2} & 23 \\ ℚ(\sqrt{453}) & \frac{149+7\sqrt{453}}{2} & \frac{151+7\sqrt{453}}{2} & 151 \end{matrix}

Table 3: d ≡ 1 (mod 4); N(u) = 1; α is irreducible.

As an illustration we consider the following table.

\begin{matrix}p & N(M_{p,α}) \\ 17 & 223358425353211 \end{matrix}

Table 4: Mersenne primes in ℚ(\sqrt{21}), u = \frac{5+\sqrt{21}}{2}.

The next Mersenne prime is found at p = 47. Similar calculations are obtained for ℚ(\sqrt{77}), the fundamental unit is u = \frac{9+\sqrt{77}}{2} and

α = \frac{11+\sqrt{77}}{2}.

\begin{matrix}p & N(M_{p,α}) \\ 2 & 23 \\ 7 & 10248701 \end{matrix}

Table 5: Mersenne primes in ℚ(\sqrt{77}), u = \frac{9+\sqrt{77}}{2}.

The next Mersenne prime is found at p = 71. The values of u for Tables 2 and 3 are taken from Cohen [3].

2.1 Observations

1. In Tables 2 and 3 above, we have chosen only the fundamental unit u in ℚ(\sqrt{d}). However it is possible that α = 1 + u is not irreducible with u as fundamental unit and yet α′ = 1 + u′ is irreducible for some other unit u′ in ℚ(\sqrt{d}).

As an illustration we consider ℚ(\sqrt{5}). Here u = \frac{1+\sqrt{5}}{2} is the fundamental unit. But, α = 1 + u = \frac{3+\sqrt{5}}{2} = u^{2} is again a unit! However, with u′ = u^{2} = \frac{3+\sqrt{5}}{2}, we get α′ = 1 + u′ = \frac{5+\sqrt{5}}{2} and N(α′) = 5, so α′ is irreducible. Another choice is u^{5} = u′′ = \frac{11+5\sqrt{5}}{2} and α′′ = 1 + u′′ = \frac{13+5\sqrt{5}}{2} is irreducible since N(α′′) = 11.

2. Theorems 1 and 3 imply the following: Among all fields ℚ(\sqrt{d}), d ≡ 2, 3 (mod 4) ℚ(\sqrt{2}) is the only field where α = 1 + u is irreducible. There are essentially only two choices for α, namely \sqrt{2} and 2 + \sqrt{2}.

Similar to usual Mersenne primes in ℤ, quadratic Mersenne norms have the following properties:

2.2 Properties of N(M_{p,α})

1. If N(M_{n,α}) is prime, then n is prime.

2. The sequence {N(M_{n,α})}_{n=1}^{∞} is an increasing sequence of integers that starts at 1.

3. If d divides n then M_{d,α} divides M_{n,α} in ℚ(\sqrt{d}) and N(M_{d,α}) divides N(M_{n,α}).

4. If d and n are relatively prime then M_{d,α} is relatively prime to M_{n,α} in ℚ(\sqrt{d}) and N(M_{n,α}) is relatively prime to N(M_{d,α}).

Experimental evidence shows that Mersenne primes are sparse in ℚ(\sqrt{d}) for d ≡ 1 (mod 4). Some interesting properties of Mersenne primes in ℚ(\sqrt{2}) are given below.

2.3 Properties of N(M_{p,α}) in ℚ(\sqrt{2})

1. Since α = 1 + u = 2 + \sqrt{2} = u\sqrt{2}, where u is the fundamental unit, we have α^{n} = a_{n} + b_{n}\sqrt{2} = u^{n}(\sqrt{2})^{n}, for any integer n > 0 and a_{n}, b_{n} ∈ ℤ. A small calculation also reveals that

α^{n} = \begin{cases}(2^{\frac{n−1}{2}} \sqrt{2})u^{n}, & if n is odd; \\ 2^{\frac{n}{2}} u^{n}, & if n is even. \end{cases}

Rewriting this,

α^{n} = \begin{cases}(2^{\frac{n−1}{2}} \sqrt{2})(v_{n} + w_{n}\sqrt{2}), & if n is odd, w_{n}, v_{n} ∈ ℤ; \\ 2^{\frac{n}{2}} (v′_{n} + w′_{n}\sqrt{2}), & if n is even, v′_{n}, w′_{n} ∈ ℤ. \end{cases}

It can be noted that w_{n}, the coefficient of \sqrt{2} in u^{n} is odd if n is odd. Further, 2^{\frac{n+1}{2}} w_{n} = a_{n} and 2^{\frac{n−1}{2}} v_{n} = b_{n}.

And w′_{n}, the coefficient of \sqrt{2} in u^{n} is even if n is even. Further, 2^{\frac{n}{2}} v′_{n} = a_{n} and 2^{\frac{n}{2}} w′_{n} = b_{n}.

For n odd, we have N(u)^{n} = −1, so

N(α^{n}) = N(2^{\frac{n−1}{2}} \sqrt{2})N(u)^{n} = N(2^{\frac{n−1}{2}} )N(\sqrt{2})(−1)^{n} = 2^{n−1}(−2)(−1) = 2^{n}.

For n even, N(u)^{n} = 1, and

N(α^{n}) = N(2^{\frac{n}{2}} )N(u)^{n} = N(2^{\frac{n}{2}} )(1) = 2^{n}.

2. For any odd prime p, let α^{p} = (2^{\frac{p−1}{2}} \sqrt{2})(v_{p} + w_{p}\sqrt{2}).

Then

N(α^{p} − 1) = (2^{\frac{p+1}{2}} w_{p} − 1)^{2} − 2(2^{\frac{p−1}{2}} v_{p})^{2}
= (2^{p+1}w_{p}^{2} + 1 − 2^{\frac{p+3}{2}} w_{p}) − 2^{p}v_{p}^{2}
= 2^{p}(2w_{p}^{2} − v_{p}^{2}) − 2^{\frac{p+3}{2}} w_{p} + 1
= 2^{p} − 2^{\frac{p+3}{2}} w_{p} + 1.

Thus,

N(M_{p,α}) = 2^{\frac{p+3}{2}} w_{p} − 2^{p} − 1.

3. As already pointed out, a_{p} has a factor of 2^{\frac{p+1}{2}} . Hence 2a_{p} ≡ 0 (mod 4). This further implies that, N(M_{p,α}) ≡ −1 (mod 4) for p ≥ 2 and N(M_{p,α}) ≡ −1 (mod 8) for p > 2.

The next three properties are consequences of quadratic reciprocity, and (\frac{·}{·}) denotes the Legendre symbol.

4. Let p be an odd prime and p ≡ ±1 (mod 8. Then

2^{\frac{p+3}{2}} = 2^{2}2^{\frac{p−1}{2}} ≡ 4 (mod p).

If p ≡ ±3 (mod 8), then

2^{\frac{p+3}{2}} = 2^{2}2^{\frac{p−1}{2}} ≡ −4 (mod p).

Combining the above we get

N(M_{p,α}) ≡ \begin{cases}4w_{p} − 3 (mod p), & if p ≡ ±1 (mod 8); \\ −4w_{p} − 3 (mod p), & if p ≡ ±3 (mod 8). \end{cases}

5. If N(M_{p,α}) is a rational prime and q is any other prime then

(\frac{N(M_{p,α})}{q}) (\frac{q}{N(M_{p,α})}) = \begin{cases}1, & if q ≡ 1 (mod 4); \\ −1, & if q ≡ 3 (mod 4). \end{cases}

6. If N(M_{p,α}) is a rational prime then (\frac{2}{N(M_{p,α})}) = 1 since N(M_{p,α}) ≡ −1 (mod 8). Hence

\sqrt{2} ∈ 𝔽_{N(M_{p,α})} the finite field with N(M_{p,α}) elements.

3 Testing for primality

Several primality tests are available and some are specially designed for special numbers, an example being the famous Lucas-Lehmer test for the usual Mersenne primes. We show that the generalized Mersenne numbers of ℚ(\sqrt{2}) can be put in a special form, so that, recent primality tests can be used to determine whether they are prime. Now,

N(M_{p,α}) = 2^{\frac{p+3}{2}} w_{p} − 2^{p} − 1,

or

N(M_{p,α}) = 2^{\frac{p+3}{2}} (w_{p} − 2^{\frac{p−3}{2}} ) − 1.

Since w_{p} is odd, (w_{p} − 2^{\frac{p−3}{2}} ) is odd for p > 3.

For p > 3,

N(M_{p,α}) = h.2^{\frac{p+3}{2}} − 1, where h = (w_{p} − 2^{\frac{p−3}{2}} ), odd.

An algorithm to test the primality of numbers of the form h · 2^{n} ± 1, for any odd integer h such that, h ≠ 4^{m} − 1 for any m is described in Bosma [2]. It can be noted that, h is not equal to 4^{m} − 1 in M_{p,α} for any m. Hence this algorithm can be used to test the primality of M_{p,α}.

4 Primes of the form x^{2} + 7y^{2}

The problem of representing a prime number by the form x^{2} + ny^{2}, where n is any fixed positive integer dates back to Fermat. This question was best answered by Euler who spent 40 years in proving Fermat’s theorem and thinking about how they can be generalized, he proposed some conjectures concerning p = x^{2}+ny^{2}, for n > 3. These remarkable conjectures, among other things, touch on quadratic forms and their composition, genus theory, cubic and biquadratic reciprocity. Refer Cox [4] for a thorough treatment.

Euler became intensely interested in this question in the early 1740’s and he mentions numerous examples in his letters to Goldbach. One among several of his conjectures stated in modern notation is

(\frac{−7}{p}) = 1 ⟺ p ≡ 1, 9, 11, 15, 23, 25 (mod 28).

The following lemma gives necessary and sufficient condition for a number m to be represented by a form of discriminant D.

Lemma 5. Let D ≡ 0, 1 (mod 4) and m be an integer relatively prime to D. Then m is properly represented by a primitive form of discriminant D if and only if D is a quadratic residue modulo m.

As a corollary, we have the following:

Corollary 6. Let n be an integer and p be an odd prime not dividing n. Then (\frac{−n}{p}) = 1 if and only if p is represented by a primitive form of discriminant −4n.

In 1903, Landau proved a conjecture of Gauss (theorem 7 below).

Let h(D) denote the number of classes of primitive positive definite forms of discriminant D, i.e., h(D) is equal to the number of reduced forms of discriminant D.

Theorem 7. Let n be a positive integer. Then

h(−4n) = 1 ⇔ n = 1, 2, 3, 4 or 7.

One may note that, x^{2} + ny^{2} is always a reduced form with discriminant −4n.

In this paper we consider the case n = 7 and represent N(M_{p,α}) in the form x^{2} + 7y^{2} whenever M_{p,α} is a Mersenne prime in ℚ(\sqrt{2}).

x^{2} + 7y^{2} is the only reduced form of discriminant −28, and it follows that

p = x^{2} + 7y^{2} ⟺ p ≡ 1, 9, 11, 15, 23, 25 (mod 28).

for primes p ≠ 7.

The special property of the usual Mersenne primes over ℤ referred to in the beginning, Lenstra and Stevenhagen [5], has the following generalization over ℚ(\sqrt{2}):

Theorem 8. If N(M_{p,α}) is a rational prime, with α = 2 + \sqrt{2}, then N(M_{p,α}) is always a quadratic residue (mod 7), and hence it can be written as x^{2} + 7y^{2}. Also, x is divisible by 8, and y ≡ ±3 (mod 8).

The detailed proof is given in Palimar [8], using Artin’s reciprocity law.

Here we prove the theorem in two stages: first we show that N(M_{p,α}) is always a quadratic residue (mod 7). Next, we give an outline of the proof that x is divisible by 8, and y ≡ ±3 (mod 8).

The first few Mersenne primes in ℚ(\sqrt{2}) with α = 2 + \sqrt{2}, as well as the representations of their norms as x^{2} + 7y^{2} is given in Table 6.

\begin{matrix}p & M_{p,α} & x^{2} + 7y^{2} \\ 5 & 431 & 16^{2} + 7 · 5^{2} \\ 7 & 5279 & 64^{2} + 7 · 13^{2} \\ 11 & 732799 & 856^{2} + 7 · 3^{2} \end{matrix}

Table 6: Norms of Mersenne primes in ℚ(\sqrt{2}) in the form x^{2} + 7y^{2}.

For p = 73,

N(M_{p,α}) = 851569055172258793218602741480913108991 =
(28615996544447548272)^{2} + 7 · (2161143775888286749)^{2}

For p = 89,

N(M_{p,α}) = 290315886781191681464330388772329064268797313023 =
(363706809248848497658560)^{2} + 7 · (150253711001099458172317)^{2}

For p = 233,

N(M_{p,α}) = 1806047542728202303336800123116644178473780689153780654706531416

7911959518498581747712829157156517940837234519177963497324543.

The corresponding representation is

(86527345603258677818378326573842407929031070590321223524182584)^{2}+
7 · (38865140256563104639356290982349294477380709218952585423373629)^{2}.

We now show that, if N(M_{p,α}) is a prime then, N(M_{p,α}) can be written as x^{2} + 7y^{2}. Since N(M_{p,α}) = 2^{\frac{p+3}{2}} w_{p} − 2^{p} − 1, representing a prime in the form x^{2} + 7y^{2} depends on

w_{p}. Now, we find the values of v_{p} and w_{p} (mod 7). As we know, for any odd n, N(u^{n}) = v_{n}^{2} − 2w_{n}^{2} = −1. If u^{n} = v_{n} + w_{n}\sqrt{2}, then v_{n} and w_{n} satisfy the following recursions: v_{n+1} = v_{n} + 2w_{n} and w_{n+1} = v_{n} + w_{n}, with initial conditions v_{1} = 1, w_{1} = 1. The above recursions can be used to show that v_{n} and w_{n} satisfy the following:

v_{n+2} = 3v_{n} + 4w_{n} , w_{n+2} = 2v_{n} + 3w_{n};
v_{n+3} = 7v_{n} + 10w_{n} , w_{n+3} = 5v_{n} + 10w_{n};
v_{n+4} = 17v_{n} + 24w_{n} , w_{n+4} = 12v_{n} + 17w_{n};
v_{n+5} = 41v_{n} + 58w_{n} , w_{n+5} = 29v_{n} + 41w_{n};
v_{n+6} = 99v_{n} + 140w_{n} , w_{n+6} = 70v_{n} + 99w_{n};

From the above one may also easily obtain the following congruences:

{v_{6k+1}} ≡ 1 (mod 7) , {w_{6k+1}} ≡ 1 (mod 7);

{v_{6k+5}} ≡ 6 (mod 7) , {w_{6k+5}} ≡ 1 (mod 7).

Since only odd prime powers greater than 3 are considered, we have listed only the congruences for indices congruent to ±1 (mod 6).

Hence

N(M_{p,α}) = 2^{\frac{p+3}{2}} w_{p} − 2^{p} − 1 ≡ 2^{\frac{p+3}{2}} − 2^{p} − 1 (mod 7).  (1)

Let us solve equation (1) for p > 3.

If p = 3k + 1 then, 2^{p} ≡ 2 (mod 7) and 2^{\frac{p+3}{2}} ≡ 4 (mod 7), so

N(M_{p,α}) ≡ 1 (mod 7).

If p = 3k + 2 then, 2^{p} ≡ 4 (mod 7) and 2^{\frac{p+3}{2}} ≡ 2 (mod 7), so

N(M_{p,α}) ≡ 4 (mod 7).

Thus in both cases N(M_{p,α}) can always be represented as x^{2} + 7y^{2}. To prove theorem 8 we need the following lemma.

Lemma 9. If N(M_{p,α}) is a rational prime and N(M_{p,α}) = x^{2} + 7y^{2}, then x ≡ 0 (mod 4), and y ≡ ±3 (mod 8).

Proof. From the previous discussion, we know

N(M_{p,α}) = x^{2} + 7y^{2}.  (2)

But N(M_{p,α}) = 2^{\frac{p+3}{2}} w_{p} − 2^{p} − 1. Clearly we may take p > 6. So either p = 6k + 1 or p = 6k + 5.

If p = 6k + 1, then

N(M_{p,α}) = 2^{\frac{6k+4}{2}} w_{p} − 2^{6k+1} − 1 ≡ −1 ≡ 7 (mod 8).  (3)

If p = 6k + 5, then also,

N(M_{p,α}) = 2^{\frac{6k+5}{2}} w_{p} − 2^{6k+5} − 1 ≡ 7 (mod 8).  (4)

But right hand side of equation (2) is x^{2} + 7y^{2}. We show that x must be even and y odd.

For, if x is odd and y is even, then x^{2} ≡ 1 (mod 8) and either y^{2} ≡ 0 (mod 8) or y^{2} ≡ 4 (mod 8). If y^{2} ≡ 0 (mod 8), then x^{2} + 7y^{2} ≡ 1 (mod 8) contradicting equations (3) and (4); and if y^{2} ≡ 4 (mod 8), then

x^{2} + 7y^{2} ≡ 1 + 7.4 ≡ 5 (mod 8),

again contradicting equations (3) and (4). Thus x is even and y is odd.

Hence by equation (2)

7 ≡ x^{2} + 7y^{2} ≡ x^{2} + 7 (mod 8),

since y^{2} ≡ 1 (mod 8) and so, x^{2} ≡ 0 (mod 8) implying x ≡ 0 (mod 4).

We now prove that y ≡ ±3 (mod 8)

Let p ≡ 1 (mod 6). From equation (3)

N(M_{p,α}) = x^{2} + 7y^{2} = 2^{\frac{6k+4}{2}} w_{p} − 2^{6k+1} − 1.

Reducing modulo 16, we get N(M_{p,α}) ≡ −1 (mod 16). But N(M_{p,α}) = x^{2} + 7y^{2} and x ≡ 0 (mod 4). Hence 7y^{2} ≡ −1 (mod 16), yielding y^{2} ≡ 9 (mod 16). This proves that y ≡ ±3 (mod 8). The same result follows from equation(4) when p ≡ 5 (mod 6).

Outline of the proof of Theorem 8. We now show that x ≡ 0 (mod 8). Virtually, the proof given in Lenstra and Stevenhagen [5] carries over word-for-word, and so, we merely give an outline. All details and notation are as in Lenstra and Stevenhagen [5]. By definition, N(M_{p,α}) = \frac{(2+\sqrt{2})^{p}−1}{1+\sqrt{2}}.\frac{(2−\sqrt{2})^{p}−1}{1−\sqrt{2}}. Denote the two factors on the right by v_{p} and v̄_{p}. It is easy to see that v_{p} and v̄_{p} are both totally positive. We compute the Artin symbols of v_{p}ℤ_{E} and v̄_{p}ℤ_{E}, and show that they are both trivial. We need to consider only two cases: p ≡ 1 (mod 6) and p ≡ 5 (mod 6).

Since \sqrt{2} ≡ 3, 4 (mod 7), by taking \sqrt{2} = 4 in v_{p} and \sqrt{2} = 3 in v̄_{p}, a straightforward computation shows that, v_{p} ≡ 1 (mod 7) and v̄_{p} ≡ 1 (mod 7). This completes the proof.

5 Acknowledgments

The authors gratefully acknowledge the kind help and encouragement given by Prof. Chandan Singh Dalawat during their visit to Harish-Chandra Research Institute, Allahabad, India, in December 2011. His lucid explanation of Artin reciprocity and short introduction to Class field theory was of great help.

References

[1] Pedro Berrizbeitia and Boris Iskra, Gaussian and Eisenstein Mersenne primes, Math. Comp. 79 (2010), 1779–1791.

[2] Wieb Bosma, Explicit primality criteria for h.2^{k} ± 1, Math. Comp. 61 (1993), 97–109.

[3] Henri Cohen, A Course in Computational Algebraic Number Theory, Springer-Verlag, 1993.

[4] David A. Cox, Primes of the form x^{2} + ny^{2}, Wiley -Interscience, 1989.

[5] Hendrik W. Lenstra and Peter Stevenhagen, Artin reciprocity and Mersenne primes, Nieuw Arch. Wiskd. (5) 1 (2000), 44–54.

[6] Wayne L. McDaniel, Perfect Gaussian integers, Acta Arith. 25 (1974), 137–144.

[7] Wayne L. McDaniel, An analogue in certain unique factorization domains of the Euclid-Euler theorem on perfect numbers, Int. J. Math. Math. Sci. 13 (1990), 13–24.

[8] Sushma Palimar, Computations in p-adic discrete dynamics and real quadratic fields, Ph.D Thesis, National Institute of Technology Karnataka, Surathkal, India, 2012.

[9] Robert Spira, The complex sum of divisors, Amer. Math. Monthly 68 (1961), 120–124.

[10] William Stallings, Cryptography and Network Security: Principles and Practices, Prentice-Hall, Inc., 2006.

2010 Mathematics Subject Classification: Primary 11R04. Keywords: Mersenne primes, Artin’s reciprocity law.

(Concerned with sequence \underline{A033207}.)

Received May 2 2012; revised version received May 21 2012. Published in Journal of Integer Sequences, June 11 2012.

Return to Journal of Integer Sequences home page.