Hypothetical Elite Primes for Mersenne Numbers and Repunits

Amin Witno Department of Basic Sciences Philadelphia University 19392 Jordan

                       awitno@gmail.com

Abstract

We study prime numbers p that have the property that the numbers (b^{q} −1)/(b−1) are quadratic residues modulo p for all sufficiently large primes q. We give a practical criterion for testing for such primes with respect to the base b and, for certain values of b, we find a connection between these primes and anti-elite primes, i.e., where b^{2^{n}} + 1 are quadratic residues modulo p for all large n.

1 Introduction

Aigner [1] called a prime number p elite if the Fermat numbers F_{n} := 2^{2^{n}} + 1 are quadratic non-residues modulo p for all sufficiently large values of n. Such primes p play a role in Pepin’s primality criterion for Fermat numbers, i.e., that F_{n} is prime if and only if p^{\frac{Fn−1}{2}} ≡ −1 (mod F_{n}).

Müller [5] defined a prime p to be anti-elite if the numbers F_{n} are quadratic residues modulo p for all large n. Despite their name, anti-elite primes are still elite in the sense of being rare, as their elite counterparts are, but without the privilege of having a role in primality testing.

Meanwhile, the counterparts to the Fermat numbers are the Mersenne numbers M_{q} := 2^{q} − 1, where q is a prime. Both Fermat and Mersenne numbers belong to the simplest class of the Cunningham numbers b^{N} ± 1, in this case with b = 2, which are of great interest as far as primality and factorization are concerned.

We explored the analogous idea of elite primes with respect to Mersenne numbers in place of the Fermat numbers and noted immediately that if a prime q = (p − 1)k + 1 (with infinitely many choices for k, says Dirichlet’s theorem), then clearly M_{q} ≡ 1 (mod p) by Fermat’s theorem, hence a quadratic residue. Therefore, a prime p cannot be “elite” with respect to Mersenne numbers, but perhaps p can be “anti-elite,” i.e., where M_{q} is a quadratic residue modulo p for all large primes q.

With this definition, and after establishing a practical computational criterion for finding such primes (Theorem 5), we looked through the primes p < 10^{9} and found no result except p = 2 and 3. So we extended the domain of M_{q} to include a generalization of Mersenne numbers in the form M_{b,q} := \frac{b^{q}−1}{b−1}, where b ≥ 2 and q is prime. This time the numerical results, collected in Table 1, were encouraging enough for us to continue with the investigation.

Thus, in this article we study the primes p modulo which M_{b,q} are quadratic residues for all large primes q. Some results relate back to Fermat numbers, presumably not surprising, and with respect to certain bases these primes can also be anti-elite with respect to the generalized Fermat numbers b^{2^{n}} + 1.

We should mention that the numbers M_{b,n} in general are also known as repunits, since their base-b representations consist of a string of ones.

2 First observations

Definition 1. For all b ≥ 2 and m ≥ 1, we fix the notation

M_{b,m} = \frac{b^{m} − 1}{b − 1}.

We reserve the variables p, q for prime numbers only, and we use the notation (\frac{a}{p}) for the Legendre/Jacobi symbol. Now let P stand for the set of all prime numbers, and define

P_{b} = \{p ∈ P : (\frac{M_{b,q}}{p} ) = +1 for all sufficiently large primes q\} .

(Since the property p ∈ P_{b} is hypothetical, perhaps we should call such primes hypo-elite to the base b.)

Table 1 displays the elements of P_{b} up to five billion with b ≤ 10. They can be obtained using an algorithm based on a criterion for p ∈ P_{b} explained in Theorem 5 later in this section, after some preliminary observations.

Theorem 2. If p | b(b + 1), then p ∈ P_{b}. If 2 < p | (b − 1), then p ∉ P_{b}. In particular, 2 ∈ P_{b} for all b ≥ 2, and 3 ∈ P_{b} if and only if b ≢ 1 (mod 3).

b p ∈ P_{b}
2 2, 3
3 2, 3, 7, 13, 61, 73, 547, 757, 1093, 4561, 6481, 368089,

398581, 530713, 797161, 42521761, 47763361, 2413941289

4 2, 5, 13, 17, 41, 241, 257, 61681, 65537, 15790321,

4278255361, 4562284561

5 2, 3, 5, 7, 521, 601, 5167, 390001, 234750601
6 2, 3, 7, 31, 97, 101
7 2, 7, 43, 1201, 2801, 117307, 6568801
8 2, 3, 19, 73, 87211, 262657, 18837001
9 2, 3, 5, 13, 41, 73, 757, 1093, 1181, 4561, 6481, 368089,

530713, 797161, 21523361, 42521761, 47763361, 2413941289

10 2, 5, 7, 11, 13, 37, 52579, 459691, 2906161

Table 1: The primes p ∈ P_{b} up to p < 5 · 10^{9} and 2 ≤ b ≤ 10.

Proof. Since M_{b,q} = 1 + b + b^{2} + ⋯ + b^{q−1}, then p | b(b + 1) implies that M_{b,q} ≡ 1 (mod p) for all primes q > 2. In that case M_{b,q} is a quadratic residue modulo p and p ∈ P_{b}. Now if p > 2 and p | (b − 1), then M_{b,q} ≡ q (mod p). By Dirichlet’s theorem, we know there are infinitely many primes q in an arbitrary reduced residue class modulo p, in particular the class of a quadratic non-residue; hence p ∉ M_{b} in this case. The second part of the claim follows as 2 | b(b + 1) and that {b − 1, b, b + 1} is a complete residue system modulo 3.

Remark 3. In particular, P_{b} contains all the prime factors of b. Hence, given an arbitrarily large number L, we can find a base b such that |P_{b}| ≥ L, e.g., by considering b which is the product of L distinct primes. Remark 4. It is clear from the definition that we have p ∈ P_{b} if and only if p ∈ P_{B} for all B ≡ b (mod p). Hence, for a fixed prime p, we can identify all the bases b for which p ∈ P_{b} once they have been determined up to b < p, such as what we have in Table 1. For convenience, based on Theorem 2, we may set P_{1} = {2} and P_{0} = P. Then, for instance, we observe from Table 1 that 11 ∈ P_{b} only for b = 0 and 10, so we may conclude that 11 ∈ P_{b} if and only if b ≡ 0, 10 (mod 11).

In what follows, the notation |b|_{p} stands for the multiplicative order of b modulo p.

Theorem 5. Let p ∤ b(b − 1), and let R = R_{b,p} be a reduced residue system modulo |b|_{p}. Then the prime p ∈ P_{b} if and only if M_{b,n} is a quadratic residue modulo p for every n ∈ R.

Proof. The condition p ∤ b(b − 1) ensures that k := |b|_{p} ≥ 2. If q is a large prime, then q belongs to a residue class modulo k represented by one of the elements in R, say n, so that M_{b,q} ≡ M_{b,n} (mod p) since q ≡ n (mod k). Conversely by Dirichlet’s theorem, for every n ∈ R, we have an infinite class of primes congruent to n modulo k. Thus the condition that M_{b,n} be quadratic residue for all n ∈ R is sufficient as well as necessary for having p ∈ P_{b}.

Furthermore, we can reduce computation by observing that only half the elements of R in the preceding theorem need to be tested:

Theorem 6. Let k = |b|_{p}, where p ∤ b(b − 1), and let H = \{x : 1 < x < \frac{k}{2}, gcd(x, k) = 1\}. Then the prime p ∈ P_{b} if and only if −b and M_{b,n} are quadratic residues modulo p for all n ∈ H.

For example, every Mersenne prime M_{q} ∉ P_{2}, except M_{2} = 3, because (\frac{−2}{2^{q}−1}) = (\frac{−1}{2^{q}−1})(\frac{2}{2^{q}−1}) = (−1)(+1) = −1. As for primes M_{b,q} in general bases, we do have some positive results stated in the next theorem.

Proof. Let R = {x : 1 ≤ x ≤ k, gcd(x, k) = 1}. By Theorem 5, we have p ∈ P_{b} if and only if (\frac{M_{b,n}}{p} ) = +1 for all n ∈ R. Note that as n ranges through elements of R, so does k − n, only in reverse order. Moreover,

\frac{b^{n} − 1}{b − 1} (−b^{k−n}) = \frac{−b^{k} + b^{k−n}}{b − 1} ≡ \frac{b^{k−n} − 1}{b − 1} (mod p).

Therefore,

(\frac{M_{b,n}}{p} ) (\frac{M_{b,k−n}}{p} ) = (\frac{−b^{k−n}}{p} ) = (\frac{−b^{k+n}}{p} ) = (\frac{−b^{n}}{p} ) .

Now if n is odd, then (\frac{−b^{n}}{p} ) = (\frac{−b}{p}). But if n is even, then k is odd, in which case k | \frac{p−1}{2} since k | (p − 1) by Fermat’s theorem. It would follow that (\frac{b}{p}) ≡ b^{\frac{p−1}{2}} ≡ +1 (mod p), so again (\frac{−b^{n}}{p} ) = (\frac{−b}{p}). We have shown that for all n ∈ R,

(\frac{M_{b,n}}{p} ) (\frac{M_{b,k−n}}{p} ) = (\frac{−b}{p}) .

In particular, if (\frac{−b}{p}) = −1, then M_{b,k−1} is a non-residue modulo p and p ∉ P_{b}. But if (\frac{−b}{p}) = +1, then (\frac{M_{b,k−n}}{p} ) = (\frac{M_{b,n}}{p} ), in which case the set R may be replaced by R ∩ \{1, 2, …, ⌊\frac{k}{2}⌋\}. The case n = 1 is trivially redundant, as is the case \frac{k}{2} ∈ R, which can occur only when k = 2 and n = 1.

Remark 7. The necessary condition (\frac{−b}{p}) = +1 translates into a congruence class criterion on the prime p which, for small b, is not hard to formulate. For b ≤ 10, these criteria are displayed in Table 2, with the purpose of checking against the primes we have obtained in the first table.

b Criteria for p such that (\frac{−b}{p}) = +1
2 p ≡ 1, 3 (mod 8)
3 p ≡ 1 (mod 6)
4 p ≡ 1 (mod 4)
5 p ≡ 1, 3, 7, 9 (mod 20)
6 p ≡ 1, 5, 7, 11 (mod 24)
7 p ≡ 1, 9, 11 (mod 14)
8 p ≡ 1, 3 (mod 8)
9 p ≡ 1 (mod 4)
10 p ≡ 1, 7, 9, 11, 13, 19, 23, 37 (mod 40)

Table 2: Congruence condition necessary for the prime p ∈ P_{b}.

Theorem 8. Suppose that b mod 4 ∈ {0, 3}. If M_{b,q} is a prime number, then M_{b,q} ∈ P_{b^{k}} for all k ≥ 1 such that q ∤ k.

Dubner [2] provides us with a table of primes M_{b,q} up to b = 99, e.g., for b = 3, we can take q = 3, 7, 13, 71, 103, 541. The first three of these, corresponding to p = 13, 1093, 797161, appear in our Table 1, belonging to both P_{3} and P_{9}.

Proof. We shall show first that for arbitrary m and n with gcd(m, n) = 1,

(\frac{M_{b,n}}{M_{b,m}} ) = +1.

Note that M_{b,m} ≡ 1 (mod 4) when b mod 4 = 0, as well as when b mod 4 = 3 provided that m is odd. So let us assume now that m is odd. (For m even, we reverse the roles of m and n.) Moreover, similar to what we have seen in the proof of Theorem 6, we have that

(\frac{M_{b,n}}{M_{b,m}} ) (\frac{M_{b,m−n}}{M_{b,m}} ) = (\frac{−b^{n}}{M_{b,m}} ) .

And since M_{b,m} ≡ 1 (mod 4), we have

(\frac{−b^{n}}{M_{b,m}} ) = (\frac{b}{M_{b,m}} )^{n} = (\frac{1}{b})^{n} = +1,

when b is odd, i.e., when b ≡ 3 (mod 4), as well as when b ≡ 0 (mod 4) by involving the Kronecker symbol. (In the case b ≡ 4 (mod 8), the claim holds without further justification, whereas if b ≡ 0 (mod 8), the same result holds as M_{b,m} ≡ 1 (mod 8).) It follows that

(\frac{M_{b,n}}{M_{b,m}} ) = (\frac{M_{b,m−n}}{M_{b,m}} ) .

Using the fact that M_{b,n} mod M_{b,m} = M_{b,n mod m}, we then apply the reciprocity law and remainder mod operations to get

(\frac{M_{b,n}}{M_{b,m}} ) = (\frac{M_{b,n_{1}}}{M_{b,m}} ) = (\frac{M_{b,m}}{M_{b,n_{1}}} ) = (\frac{M_{b,n_{2}}}{M_{b,n_{1}}} ) = ⋯

where n_{1} = n mod m or m − (n mod m), whichever is odd, and n_{2} = m mod n_{1} or n_{1} − (m mod n_{1}), whichever is odd, etc., in order to maintain M_{b,n_{j}} ≡ 1 (mod 4), thereby each reciprocal remains free of minus sign. Hence with gcd(m, n) = 1, this process will terminate with (\frac{M_{b,n}}{M_{b,m}} ) = ⋯ = (\frac{M_{b,1}}{M_{b,n_{t}}} ) = +1.

Now letting m = q, a fixed odd prime, and n be any larger prime, we have proved that if M_{b,q} is prime, then M_{b,q} ∈ P_{b}. (The case q = 2 deals with the prime p = b + 1, to which Theorem 2 applies.) As for the base b^{k}, note the identity M_{b,kn} = M_{b^{k},n}M_{b,k}. So if q ∤ k, then the same arguments as before yield

(\frac{M_{b^{k},n}}{M_{b,q}} ) = (\frac{M_{b,kn}}{M_{b,q}} ) (\frac{M_{b,k}}{M_{b,q}} ) = (+1)(+1) = +1,

establishing the claim.

Remark 9. We can also show that M_{b,q} ∉ P_{b} in the case b ≡ 2 (mod 4). Note, for instance, when q and q′ ≡ 2 (mod q) are primes,

(\frac{M_{b,q′}}{M_{b,q}} ) = (\frac{M_{b,2}}{M_{b,q}} ) = (\frac{b + 1}{M_{b,q}}) = − (\frac{M_{b,q}}{b + 1}) = − (\frac{1}{3}) = −1.

This observation agrees with the known fact that the Mersenne numbers M_{q} cannot be a perfect square, for otherwise the Jacobi symbol would equal +1. (An old result by Lebesgue [4] states that x^{m} − 1 = y^{2} is not solvable.)

3 Results involving Fermat numbers

Table 1 shows that the Fermat primes F_{m} ∈ P_{4} for m = 1, 2, 3, 4. Although it is unknown if there exists another Fermat prime after F_{4}, we will prove in Corollary 14 that all Fermat primes belong in P_{4}. Other results in this section concern the idea of a prime being anti-elite with respect to Fermat numbers in general bases:

Definition 10. Recall the generalized Fermat numbers F_{b,n} = b^{2^{n}} + 1. Let a prime p be considered anti-elite to the base b if F_{b,n}, when sufficiently large, are all quadratic residues modulo p.

Theorem 11. Fix an even base b, and let m = 2^{s}r, with 0 ≤ s ≤ n and 2 ∤ r. The following results apply to the Jacobi symbol (\frac{M_{b,m}}{F_{b,n}} ) with n ≥ 1.

1. For s = 0, we have (\frac{M_{b,m}}{F_{b,n}} ) = +1 if b ≡ 0 (mod 4), and indeterminate if b ≡ 2 (mod 4).

2. For s = 1, we have (\frac{M_{b,m}}{F_{b,n}} ) = +1 if b ≡ 0, 6 (mod 8), and (\frac{M_{b,m}}{F_{b,n}} ) = −1 if b ≡ 2, 4 (mod 8).

3. For s ≥ 2, we have (\frac{M_{b,m}}{F_{b,n}} ) = +1 if b ≡ 0, 2 (mod 8), and (\frac{M_{b,m}}{F_{b,n}} ) = −1 if b ≡ 4, 6 (mod 8).

Proof. The condition s ≤ n implies that gcd(b^{m} − 1, b^{2^{n}} + 1) = 1. Let us perform Bezout’s algorithm for evaluating gcd(2^{n−s}, r) = 1, and where in each iteration we multiply the equation by 2^{s}:

2^{n} = (2^{s}r)u + 2^{s}r_{1}
2^{s}r = (2^{s}r_{1})u_{1} + 2^{s}r_{2}
2^{s}r_{1} = (2^{s}r_{2})u_{2} + 2^{s}r_{3}
⋮
2^{s}r_{t−1} = (2^{s}r_{t})u_{t} + 2^{s}.

Note that r > r_{1} > r_{2} > ⋯ > r_{t} > 1. With these, we apply the reciprocal law to the Jacobi symbol (\frac{b^{m}−1}{b^{2^{n}}+1}) repeatedly,

(\frac{b^{2^{s}r} − 1}{b^{2^{n}} + 1}) = (\frac{b^{2^{n}} + 1}{b^{2^{s}r} − 1}) = (\frac{b^{2^{s}r_{1}} + 1}{b^{2^{s}r} − 1}) = (\frac{b^{2^{s}r} − 1}{b^{2^{s}r_{1}} + 1}) = (\frac{(−1)^{u_{1}}b^{2^{s}r_{2}} − 1}{b^{2^{s}r_{1}} + 1})

Note that (\frac{−1}{b^{2^{s}r_{1}}+1}) = +1. Depending on the parity of u_{1}, we continue,

(\frac{(−1)^{u_{1}}b^{2^{s}r_{2}} − 1}{b^{2^{s}r_{1}} + 1}) = (\frac{±b^{2^{s}r_{2}} − 1}{b^{2^{s}r_{1}} + 1}) = (\frac{b^{2^{s}r_{2}} ∓ 1}{b^{2^{s}r_{1}} + 1}) = (\frac{b^{2^{s}r_{1}} + 1}{b^{2^{s}r_{2}} ∓ 1}) .

At this point, there are three ways to go with the +/− sign:

(\frac{b^{2^{s}r_{1}} + 1}{b^{2^{s}r_{2}} ∓ 1}) = (\frac{b^{2^{s}r_{3}} + 1}{b^{2^{s}r_{2}} − 1}) or (\frac{b^{2^{s}r_{3}} + 1}{b^{2^{s}r_{2}} + 1}) or (\frac{b^{2^{s}r_{3}} − 1}{b^{2^{s}r_{2}} + 1}) .

In fact, these three are the only possible forms until we reach the t-th iteration, i.e.,

(\frac{b^{2^{s}r} − 1}{b^{2^{n}} + 1}) = (\frac{b^{2^{s}} + 1}{b^{2^{s}r_{t}} − 1}) or (\frac{b^{2^{s}} + 1}{b^{2^{s}r_{t}} + 1}) or (\frac{b^{2^{s}} − 1}{b^{2^{s}r_{t}} + 1}) .

We proceed case by case, respectively:

Case 1. Note that here r_{t} must be odd since we start off with the Jacobi symbol (\frac{b^{m}−1}{b^{2^{n}}+1}) having gcd(b^{m} − 1, b^{2^{n}} + 1) = 1. Hence,

(\frac{b^{2^{s}} + 1}{b^{2^{s}r_{t}} − 1}) = (\frac{b^{2^{s}r_{t}} − 1}{b^{2^{s}} + 1}) = (\frac{(−1)^{r_{t}} − 1}{b^{2^{s}} + 1}) = (\frac{−2}{b^{2^{s}} + 1}) .

Case 2. This time, r_{t} is even:

(\frac{b^{2^{s}} + 1}{b^{2^{s}r_{t}} + 1}) = (\frac{b^{2^{s}r_{t}} + 1}{b^{2^{s}} + 1}) = (\frac{(−1)^{r_{t}} + 1}{b^{2^{s}} + 1}) = (\frac{2}{b^{2^{s}} + 1}) .

Case 3. Similarly,

(\frac{b^{2^{s}} − 1}{b^{2^{s}r_{t}} + 1}) = (\frac{b^{2^{s}r_{t}} + 1}{b^{2^{s}} − 1}) = (\frac{2}{b^{2^{s}} − 1}) .

From all these we collect the following results.

1. For s = 0, we have (\frac{b^{m}−1}{b^{2^{n}}+1}) = +1 if b ≡ 0 (mod 8), and (\frac{b^{m}−1}{b^{2^{n}}+1}) = −1 if b ≡ 4 (mod 8), and indeterminate if b ≡ 2 (mod 4).

2. For s = 1, we have (\frac{b^{m}−1}{b^{2^{n}}+1}) = +1 if b ≡ 0 (mod 4), and (\frac{b^{m}−1}{b^{2^{n}}+1}) = −1 if b ≡ 2 (mod 4).

3. For s ≥ 2, we have (\frac{b^{m}−1}{b^{2^{n}}+1}) = +1 in all cases.

We also verify easily that (\frac{b−1}{b^{2^{n}}+1}) = +1 if b ≡ 0, 2 (mod 8), and (\frac{b−1}{b^{2^{n}}+1}) = −1 if b ≡ 2, 4 (mod 8). Lastly, we use the relation (\frac{M_{b,m}}{F_{b,n}} ) = (\frac{b^{m}−1}{b^{2^{n}}+1})(\frac{b−1}{b^{2^{n}}+1}) to put together the desired claim.

Corollary 12. Suppose that b ≡ 0 (mod 4). Then (\frac{M_{b,q}}{F_{b,n}} ) = +1 for any odd number q. Hence, if F_{b,n} is prime, then F_{b,n} ∈ P_{b}. In reciprocal, if M_{b,q} is prime, then M_{b,q} is anti-elite to the base b.

Remark 13. This corollary is the case s = 0 in Theorem 11. Primes M_{b,q}, being scarce, are typically discovered having large values of q. Now, since Fermat numbers are recursive, they are periodic modulo p. In the case of p = M_{b,q}, the period length is given by |2|_{q}, hence expectedly large too. For instance, the fourteenth repunit prime base 12, according to \underline{A004064} in OEIS [6], is M_{12,769543}. Since 12 is a multiple of 4, this prime is anti-elite to this base with period |2|_{769543} = 384771.

Corollary 14. Suppose that F_{b,n} is a prime number for some n ≥ 1. If b ≡ 0 (mod 4), then F_{b,n} ∈ P_{b^{k}} for all k ≥ 1 such that 2^{n+1} ∤ k. If b ≡ 2 (mod 4), then F_{b,n} ∈ P_{b^{2k}} for all k ≥ 1 such that 2^{n} ∤ k. In particular, all Fermat primes F_{n} ∈ P_{4^{k}} for all such k.

Proof. The identity M_{b,km} = M_{b^{k},m}M_{b,k} gives (\frac{M_{b^{k},m}}{F_{b,n}} ) = (\frac{M_{b,km}}{F_{b,n}} )(\frac{M_{b,k}}{F_{b,n}} ). Note that if m is odd,

the factor of 2 dividing k and km are of the same multiplicity. In that case (\frac{M_{b,km}}{F_{b,n}} ) = (\frac{M_{b,k}}{F_{b,n}} ) by Theorem 11, provided that we require k to be even when b ≡ 2 (mod 4) in order to avoid the indeterminate case. Hence, (\frac{M_{b^{k},q}}{F_{b,n}} ) = +1 for all odd prime q.

Remark 15. We can extend the proof of Theorem 11 to include (\frac{M_{b^{k},m}}{F_{b,n}} ) = +1 if m is even, provided that k is also even, or a multiple of 4 when b ≡ 2 (mod 4). In particular, with m = 2 and k = 2^{r}, we have M_{b^{2^{r}} , 2} = F_{b,r}. Then (\frac{F_{b,n}}{F_{b,r}} ) = (\frac{F_{b,r}}{F_{b,n}} ) = +1 for all n > r. Hence, we can show that generalized Fermat primes F_{b,r}, for r ≥ 2, are anti-elite to their own base. However, this is a fact already known [5] and easy to obtain due to the relation F_{b,n} ≡ 2 (mod F_{b,r}) for all n > r. And unfortunately, no other anti-elite primes can be identified in this manner as it has been observed that M_{b,q} is always composite when b is a perfect power, except possibly for q = 2, i.e., the Fermat primes already considered.

We do not observe a general pattern for odd bases b. The following theorem deals with an isolated result for b = 3.

Theorem 16. If the number \frac{F_{3,n}}{2} is prime, then \frac{F_{3,n}}{2} ∈ P_{9^{k}} for all k odd.

Primes of the form \frac{F_{3,n}}{2} are currently known with n = 0, 1, 2, 4, 5, 6 [\underline{A275377}]. Four of these are included in Table 1, belonging in P_{9}.

Proof. We exclude n = 0, although it is valid, and introduce the notation E_{r} = \frac{9^{r}+1}{2}. Hence \frac{F_{3,n}}{2} = E_{2^{n−1}}. Note the following facts.

1. We have E_{r} ≡ 1 (mod 4) for all r ≥ 0.

2. The number M_{9,m} is odd only when m is odd.

3. We have gcd(E_{2^{n−1}}, M_{9,m}) = 1 for all n ≥ 1 when m is odd.

We first show that (\frac{M_{9,m}}{E_{2^{n−1}}} ) = +1 for all odd m, then it would follow that (\frac{M_{9^{k},m}}{E_{2^{n−1}}} ) =

(\frac{M_{9,km}}{E_{2^{n−1}}} )(\frac{M_{9,k}}{E_{2^{n−1}}} ) = (+1)(+1) = +1 for all odd k.

Let us fix an odd m, and let r_{1} = 2^{n−1} mod m. By the congruence 9^{m} ≡ 1 (mod M_{9,m}), we get

(\frac{E_{2^{n−1}}}{M_{9,m}} ) = (\frac{2}{M_{9,m}} ) (\frac{9^{2^{n−1}} + 1}{M_{9,m}}) = (\frac{2}{M_{9,m}} ) (\frac{9^{r_{1}} + 1}{M_{9,m}}) = (\frac{E_{r_{1}}}{M_{9,m}} ) .

Now by the congruence 9^{r_{1}} ≡ −1 (mod E_{r_{1}}), this Jacobi symbol equals to

(\frac{M_{9,m}}{E_{r_{1}}} ) = (\frac{8}{E_{r_{1}}} ) (\frac{9^{m} − 1}{E_{r_{1}}}) = (\frac{8}{E_{r_{1}}} ) (\frac{±9^{r_{2}} − 1}{E_{r_{1}}}) ,

where r_{2} = m mod r_{1}. In the plus case, we have

(\frac{E_{2^{n−1}}}{M_{9,m}} ) = (\frac{8}{E_{r_{1}}} ) (\frac{9^{r_{2}} − 1}{E_{r_{1}}}) = (\frac{M_{9,r_{2}}}{E_{r_{1}}} ) = (\frac{E_{r_{1}}}{M_{9,r_{2}}} ) ,

noting that if r_{2} is even, then the Jacobi symbol is temporarily replaced by Kronecker symbol. Similarly, in the minus case,

(\frac{E_{2^{n−1}}}{M_{9,m}} ) = (\frac{8}{E_{r_{1}}} ) (\frac{−9^{r_{2}} − 1}{E_{r_{1}}}) = (\frac{2}{E_{r_{1}}} ) (\frac{9^{r_{2}} + 1}{E_{r_{1}}}) = (\frac{E_{r_{2}}}{E_{r_{1}}} ) = (\frac{E_{r_{1}}}{E_{r_{2}}} ) .

This process terminates, say at the t-th iteration, having produced the remainders r_{1} > r_{2} > ⋯ > r_{t} > 1. Observe that there are only three possible final forms. Case 1. We have (\frac{E_{2^{n−1}}}{M_{9,m}} ) = ⋯ = (\frac{M_{9,1}}{E_{r_{t}}} ) = +1. Case 2. The case where we must have r_{t} odd, since gcd(E_{2^{n−1}}, M_{9,m}) = 1:

(\frac{E_{2^{n−1}}}{M_{9,m}} ) = ⋯ = (\frac{E_{1}}{M_{9,r_{t}}} ) = (\frac{M_{9,r_{t}}}{5} ) = (\frac{8}{5}) (\frac{9^{r_{t}} − 1}{5}) = − (\frac{−2}{5}) = +1.

Case 3. The last case, where we would have r_{t} even:

(\frac{E_{2^{n−1}}}{M_{9,m}} ) = ⋯ = (\frac{E_{1}}{E_{r_{t}}} ) = (\frac{5}{E_{r_{t}}} ) = (\frac{2}{5}) (\frac{9^{r_{t}} + 1}{5}) = (\frac{2}{5}) (\frac{2}{5}) = +1.

And the proof is complete.

Our last observation in connection with anti-elite primes is irrespective of the family to which the prime p belongs, but is given by the multiplicative order of the base b.

Theorem 17. Suppose that |b|_{p} is an odd number. If p ∈ P_{b}, then p is anti-elite to the base b.

Table 1 contains quite a number of occurrences with odd |b|_{p}, thus anti-elite primes, e.g., 2906161 in base 10 and 2413941289 in base 3, as well as the repunit M_{3,13} = 797161 ∈ P_{3}.

Proof. Note that F_{b,n} M_{b,2^{n}} = M_{b,2^{n+1}} and that gcd(2^{n}, |b|_{p}) = 1 for all n. Hence, if p ∈ P_{b}, then by Theorem 5, both M_{b,2^{n}} and M_{b,2^{n+1}} are quadratic residues modulo p, and so is F_{b,n}.

Corollary 18. Every repunit prime M_{b,q} is anti-elite to its base, if b ≡ 0, 3 (mod 4).

Proof. The case b mod 4 = 0 overlaps with Corollary 12. Regardless, for these two classes of b, we have M_{b,q} ∈ P_{b} if prime, by Theorem 8. Such an event comes with |b|_{M_{b,q}} = q, which is necessarily an odd prime.

4 For further research

This has been an initial investigation on primes p elements of P_{b}, i.e., such that (\frac{M_{b,q}}{p} ) = +1 for all large primes q, and motivated by the search for new insight into elite/anti-elite primes. If the subject is proven worthwhile, we would invite the readers to look into the infinitude of P_{b}, for all or specific values of b. The facts that some P_{b} can be large (Remark 3) and that some contain repunit primes naturally suggest that there may indeed be infinitely many such primes for a fixed base. However, our numerical data also suggest that we may have a convergent reciprocal sum ∑_{p∈P_{b}} 1/p, in line with the reciprocal sum of elite primes, which has been proved convergent by Křížek et al. [3].

References

[1] A. Aigner, Über Primzahlen, nach denen (fast) alle Fermatschen Zahlen quadratische Nichtreste sind, Monatsh. Math. 101 (1986), 85–93.

[2] H. Dubner, Generalized repunit primes, Math. Comp. 61 (1993), 927–930.

[3] M. Křížek, F. Luca, and L. Somer, On the convergence of series of reciprocals of primes related to the Fermat numbers, J. Number Theory 97 (2002), 95–112.

[4] M. Lebesgue, Sur l’impossibilité, en nombres entiers, de l’équation x^{m} = y^{2}+1, Nouvelles Annales de Mathématiques 1^{re} série 9 (1850), 178–181.

[5] T. Müller, On anti-elite prime numbers, J. Integer Sequences 10 (2007), Article 07.9.4.

[6] N. J. A. Sloane et al., The On-Line Encyclopedia of Integer Sequences, https://oeis. org, last accessed January 2021.

2020 Mathematics Subject Classification: Primary 11A15; Secondary 11A41. Keywords: Fermat number, Mersenne number, generalized repunit, elite prime.

(Concerned with sequences \underline{A004064}, \underline{A102742}, \underline{A128852}, and \underline{A275377}.)

Received August 4 2020; revised version received January 2 2021. Published in Journal of Integer Sequences, January 3 2021.

Return to Journal of Integer Sequences home page.