Overpseudoprimes, and Mersenne and Fermat Numbers as Primover Numbers

Vladimir Shevelev Department of Mathematics

Ben-Gurion University of the Negev

Beer-Sheva 84105

Israel

shevelev@bgu.ac.il

Gilberto García-Pulgarín Universidad de Antioquia

Calle 67 No. 53–108 Medellín, Antioquia

Colombia

gigarcia@ciencias.udea.edu.co

Juan Miguel Velásquez-Soto Departamento de Matemáticas

Universidad del Valle Calle 13 No. 100-00 Cali, Valle del Cauca

Colombia

jumiveso@univalle.edu.co

John H. Castillo

Departamento de Matemáticas y Estadística Universidad de Nariño Calle 18 Carrera 50

San Juan de Pasto, Nariño

Colombia

jhcastillo@gmail.com

Abstract

We introduce a new class of pseudoprimes, that we call “overpseudoprimes to base b”, which is a subclass of the strong pseudoprimes to base b. Letting |b|_{n} denote the multiplicative order of b modulo n, we show that a composite number n is an overpseudoprime if and only if |b|_{d} is invariant for all divisors d > 1 of n. In particular, we prove that all composite Mersenne numbers 2^{p} − 1, where p is prime, are overpseudoprimes to base 2 and squares of Wieferich primes are overpseudoprimes to base 2. Finally, we show that some kinds of well-known numbers are “primover to base b”; i.e., they are primes or overpseudoprimes to base b.

1 Introduction

We recall some definitions and fix some notation. Let b an integer greater than 1 and N a positive integer relatively prime to b. Throughout, we denote by |b|_{N} the multiplicative order of b modulo N. For a prime p, ν_{p}(N) means the greatest exponent of p in the prime factorization of N.

Fermat’s little theorem implies that 2^{p−1} ≡ 1 (mod p), where p is an odd prime p. An odd prime p, is called a Wieferich prime if 2^{p−1} ≡ 1 (mod p^{2}),

We recall that a Poulet number, also known as Fermat pseudoprime to base 2, is a composite number n such that 2^{n−1} ≡ 1 (mod n). A Poulet number n which verifies that d divides 2^{d} − 2 for each divisor d of n, is called a Super-Poulet pseudoprime.

Sometimes the numbers M_{n} = 2^{n} − 1, n = 1, 2, …, are called Mersenne numbers, although this name is usually reserved for numbers of the form

M_{p} = 2^{p} − 1  (1)

where p is prime. In this form numbers M_{p}, at the first time, were studied by Marin Mersenne (1588–1648) around 1644; see Guy [3, §A3] and a large bibliography there.

In the next section, we introduce a new class of pseudoprimes and we prove that it just contains the odd numbers n such that |2|_{d} is invariant for all divisors greater than 1 of n. In particular, we show that it contains all composite Mersenne numbers and, at least, squares of all Wieferich primes. In the fourth section, we give a generalization of this concept to arbitrary bases b > 1 as well. In the final section, we put forward some of its consequences.

We note that, the concept of overpseudoprime to base b was found in two independent ways. The first one in 2008, by Shevelev [7] and the second one, by Castillo et al. [1], using consequences of Midy’s property, where overpseudoprimes numbers are denominated Midy pseudoprimes.

The first sections of the present work is a revised version of Shevelev [7]. In the last section, we present a review of Shevelev [8], using results from Castillo et al. [1].

The sequences \underline{A141232}, \underline{A141350} and \underline{A141390} in [9], are result of the earlier work of Shevelev.

2 A class of pseudoprimes

Let n > 1 be an odd number. When we multiply by 2 the set of integers modulo n, we split it in different sets called cyclotomic cosets. The cyclotomic coset containing s ≠ 0 consists of C_{s} = {s, 2s, 2^{2}s, …, 2^{m_{s}−1}s}, where m_{s} is the smallest positive number such that 2^{m_{s}} · s ≡ s (mod n). Actually, it is easy to see that m_{s} = |2|\frac{n}{gcd(n,s)} . For instance the cyclotomic cosets modulo 15 are

C_{1} = {1, 2, 4, 8},
C_{3} = {3, 6, 12, 9},
C_{5} = {5, 10}, and
C_{7} = {7, 14, 13, 11}.

Denote by r = r(n), the number of distinct cyclotomic cosets of 2 modulo n. From the above example, r(15) = 4.

Note that, if C_{1}, …, C_{r} are the different cyclotomic cosets of 2 modulo n, then

⋃_{j=1}^{r} C_{j} = {1, 2, …, n − 1} and C_{j_{1}} ∩ C_{j_{2}} = ∅, j_{1} ≠ j_{2}.  (2)

We can demonstrate that

|2|_{n} = lcm(|C_{1}|, …, |C_{r}|).  (3)

If p is an odd prime the cyclotomic cosets have the same number of elements, because for each s ≠ 0 we have m_{s} = |C_{s}| = |2|_{\frac{p}{gcd(p,s)}} = |2|_{p}. So

|C_{1}| = ⋯ = |C_{r}|.  (4)

Therefore, when p is an odd prime, we obtain

p = r(p)|2|_{p} + 1.  (5)

This leave us to study composite numbers such that the equation (5) holds.

Definition 1. We say that an odd composite number n is an overpseudoprime to base 2 if

n = r(n)|2|_{n} + 1.  (6)

Note that if n is an overpseudoprime to base 2, then 2^{n−1} = 2^{r(n)|2|_{n}} ≡ 1 (mod n). Thus, the set of overpseudoprimes to base 2 is a subset of the set of Poulet pseudoprimes to base 2.

Theorem 2. Let n = p_{1}^{l_{1}} ⋯ p_{k}^{l_{k}} be an odd composite number. Then n is an overpseudoprime to base 2 if and only if

|2|_{n} = |2|_{d},  (7)

for each divisor d > 1 of n.

Proof. Let s, different from zero, be an arbitrary element of ℤ_{n}. Take u_{s} = gcd(n, s) and v_{s} = \frac{n}{u_{s}}. Then s = au_{s}, for some integer a relatively prime with n. As we said before,

|C_{s}| = |2|_{v_{s}}.

Note that when s runs through a set of coset representatives modulo n, v_{s} runs through the set of divisors of n. So the value of |C_{s}| is constant if and only if |2|_{d} is invariant for each divisor d > 1 of n, which proves the theorem.

A direct consequence of the last theorem is the following.

Corollary 3. Two overpseudoprimes to base 2, N_{1} and N_{2} such that |2|_{N_{1}} ≠ |2|_{N_{2}}, are relatively primes.

Corollary 4. For a prime p, M_{p} = 2^{p} − 1 is either a prime or an overpseudoprime to base 2.

Proof. Assume that M_{p} is not prime. Let d > 1 be any divisor of M_{p}. Then |2|_{d} divides p and thus |2|_{d} = p.

Corollary 5. Every overpseudoprime to base 2 is a Super-Poulet pseudoprime.

Proof. Let n be an overpseudoprime to base 2 and take d an arbitrary divisor of n. By Theorem 2, d is either prime or overpseudoprime to base 2. In any case, we have 2^{d−1} ≡ 1 (mod d).

Example 6. Consider the super-Poulet pseudoprime, see \underline{A178997} in [9], 96916279 = 167 · 499 · 1163. We know that, cf. \underline{A002326} in [9], |2|_{167} = 83, |2|_{499} = 166 and |2|_{1163} = 166. Thus the reciprocal of the above corollary is not true.

Assume that p_{1} and p_{2} are primes such that |2|_{p_{1}} = |2|_{p_{2}}. Then |2|_{p_{1}p_{2}} = lcm(|2|_{p_{1}}, |2|_{p_{2}}). In consequence, n = p_{1}p_{2} is an overpseudoprime to base 2. With the same objective, we get the following.

Theorem 7. Let p_{1}, …, p_{k} be different primes such that |2|_{p_{i}} = |2|_{p_{j}}, when i ≠ j. Assume that p_{i}^{l_{i}} is an overpseudoprime to base 2, where l_{i} are positive integers, for each i = 1, …, k. Then n = p_{1}^{l_{1}} ⋯ p_{k}^{l_{k}} is an overpseudoprime to base 2.

3 The (w + 1)-th power of Wieferich prime of order w is overpseudoprime to base 2

Knauer and Richstein [4], proved that 1093 and 3511 are the only Wieferich primes less than 1.25 × 10^{15}. More recently, Dorais and Klyve [2] extend this interval to 6.7 × 10^{15}.

We say that a prime p is a Wieferich prime of order w ≥ 1, if ν_{p}(2^{p−1} − 1) = w + 1. The following result, from Nathanson [6, Thm. 3.6], give us a method to calculate |b|_{p^{t}}

from |b|_{p}.

Theorem 8. Let p be an odd prime not divisor of b, m = ν_{p}(b^{|b|^{p}} −1) and t a positive integer, then

|b|_{p^{t}} = \begin{cases}|b|_{p} , & if t ≤ m; \\ p^{t−m} |b|_{p} , & if t > m. \end{cases}

Theorem 9. A prime p is a Wieferich prime of order greater than or equal to w if and only if p^{w+1} is an overpseudoprime to base 2.

Proof. Suppose that p is a Wieferich prime of order greater than or equal to w. Then p^{w+1} | 2^{p−1} − 1 and thus |2|_{p^{w+1}} is a divisor of p − 1.

By Theorem 8, |2|_{p^{w+1}} = p^{r} |2|_{p} for some non-negative integer r. So, r = 0. Therefore, p^{w+1} is an overpseudoprime to base 2. The reciprocal is clear.

Theorem 10. Let n be an overpseudoprime to base 2. If n is not the multiple of the square of a Wieferich prime, then n is squarefree.

Proof. Let n = p_{1}^{l_{1}} … p_{k}^{l_{k}} and, say, l_{1} ≥ 2. If p_{1} is not a Wieferich prime, then |2|_{p_{1}^{2}} divides p_{1}(p_{1} − 1) but does not divide p_{1} − 1. Thus, |2|_{p_{1}^{2}} ≥ p_{1}. Since |2|_{p_{1}} ≤ p_{1} − 1, then |2|_{p_{1}^{2}} > |2|_{p_{1}} and by Theorem 2, n is not an overpseudoprime to base 2.

4 Overpseudoprime to base b

Take b a positive integer greater than 1. Denote by r = r_{b}(n) the number of cyclotomic cosets of b modulo n. If C_{1}, …, C_{r} are the different cyclotomic cosets of b modulo n, then C_{j_{1}} ∩ C_{j_{2}} = ∅, j_{1} ≠ j_{2} and ⋃_{j=1}^{r} C_{j} = {1, 2, …, n − 1}.

Let p be a prime which does not divide b(b − 1). Once again, we get r_{b}(p)|b|_{p} = p − 1.

Definition 11. We say that a composite number n, relatively prime to b, is an overpseudoprime to base b if it satisfies

n = r_{b}(n)|b|_{n} + 1.  (8)

The proof of the next theorem follows similarly as in Theorem 2.

Theorem 12. Let n be a composite number such that gcd(n, b) = 1. Then n is an overpseudoprime to base b if and only if |b|_{n} = |b|_{d}, for each divisor d > 1 of n.

Definition 13. A prime p is called a Wieferich prime in base b if b^{p−1} ≡ 1 (mod p^{2}). A Wieferich prime to base b is of order w ≥ 1, if ν_{p}(b^{p−1} − 1) = w + 1.

With this definition in our hands, we can generalize Theorems 9 and 10. The respective proofs, are similar to that ones.

Theorem 14. A prime p is a Wieferich prime in base b of order greater than or equal to w if and only if p^{w+1} is an overpseudoprime to base b.

Theorem 15. If n is overpseudoprime to base b and is not a multiple of a square of a Wieferich prime to base b, then n is squarefree.

Let us remember that an odd composite N such that N − 1 = 2^{r}s with s an odd integer and (b, N) = 1, is a strong pseudoprime to base b if either b^{s} ≡ 1 (mod N) or b^{2^{i}s} ≡ −1 (mod N), for some 0 ≤ i < r. The following result shows us, that the overpseudoprimes do not appear more frequently than the strong pseudoprimes.

Theorem 16. If n is an overpseudoprime to base b, then n is a strong pseudoprime to the same base.

Proof. Let n be an overpseudoprime to base b. Suppose that n − 1 = 2^{r}s and |b|_{n} = 2^{t}s_{1}, for some odd integer s, s_{1} and nonnegative integers r, t. Since n is an overpseudoprime, then |b|_{n}|n − 1. Thus t ≤ r and s_{1} divides s. Assume t = 0. So |b|_{n} is a divisor of s and thus

b^{s} ≡ 1 (mod n).

Then n is a strong pseudoprime to base b.

On the other hand, assume that t ≥ 1 and write A = b^{s_{1}} = b^{\frac{|b|n}{2^{t}}}. Note that

(A − 1)(A + 1)(A^{2} + 1)(A^{2^{2}} + 1) ⋯ (A^{2^{t−1}} + 1) = A^{2^{t}} − 1 ≡ 0 (mod n).

We claim that for any i < t−1 the greatest common divisor gcd(n, A^{2^{i}} +1) is 1 . Indeed, assume that d > 1 divides both n and A^{2^{i}} + 1. Since n is an overpseudoprime to base b, we have |b|_{d} = |b|_{n} and the congruence A^{2^{i}} = b^{2^{i}s_{1}} ≡ −1 (mod d), leave us to a contradiction with the definition of |b|_{d}. Thus, gcd(A^{2^{i}} + 1, n) = 1. Similarly gcd (A − 1, n) = 1 and we obtain

A^{2^{t−1}} + 1 ≡ 0 (mod n).

Consequently, b^{2^{t−1}s} ≡ −1 (mod n). Therefore, n is a strong pseudoprime to base b.

Note that there are strong pseudoprimes to base b such that |b|_{n} = 2^{t}s_{1} and b^{2^{i}s_{1}} ≢ −1 (mod n) for i < t − 1, but n is not an overpseudoprime to base b. For example n = 74415361 and b = 13.

As before, where we have proved that every overpseudoprime to base 2 is super-Poulet pseudoprime, using Theorem 12 we can prove the following statement.

Theorem 17. Every overpseudoprime n to base b is a superpseudoprime, that is

b^{d−1} ≡ 1 (mod d),  (9)

for each divisor d > 1 of n.

Theorem 18. If n is an overpseudoprime to base b, then for every two divisors d_{1} < d_{2} of n, including 1 and n, we have

|b|_{n}|d_{2} − d_{1}.  (10)

Proof. By the equation (9), we have |b|_{d_{i}} = |b|_{n} divides d_{i} − 1, for i = 1, 2, and thus (10) follows.

5 Primoverization Process

Note that, if n is an overpseudoprime to base b, a divisor of n is either prime or overpseudoprime to base b. In this section we study some kinds of numbers which satisfy this property.

In the sequel, we denote by Φ_{n} (x) the n-th cyclotomic polynomial. We recall the following theorems from Castillo et al. [1].

Theorem 19. A composite number N with gcd (N, |b|_{N}) = 1, is an overpseudoprime to base b if and only if Φ_{|b|_{N}} (b) ≡ 0 (mod N) and |b|_{N} > 1.

Theorem 20. Let N > 2 and P_{N} (b) = \frac{Φ_{N} (b)}{gcd (N, Φ_{N} (b))}. If P_{N} (b) is composite, then P_{N} (b)

is an overpseudoprime to base b.

The last theorem leads us to the next definition.

Definition 21. A positive integer is called primover to base b if it is either prime or an overpseudoprime to base b.

By Theorem 12, we know that each divisor greater than 1, of a overpseudoprime to base b is primover to the same base b. By Corollary 2, M_{p} is primover to base 2.

Theorem 20 suggests that we need to know the value of gcd (N, Φ_{N} (b)). To that objective, we recall a result from Motose [5, Th. 2].

Theorem 22. We set n ≥ 2, a ≥ 2. Then p is a prime divisor of Φ_{n}(b) if and only if gcd(b, p) = 1 and n = p^{γ}|b|_{p} where γ ≥ 0. A prime divisor p of Φ_{n}(b) for n ≥ 3 has the property such that n = |a|_{p} or ν_{p}(Φ_{n}(b)) = 1 as γ = 0 or not.

Let p be the greatest prime divisor of N. We claim that either gcd(N, Φ_{N}(b)) = 1 or p. Indeed, assume that there is a prime q < p divisor of N and Φ_{N}(b). Thus, Theorem 22 implies that N = q^{γ}|b|_{q}. But as p divides N, we obtain a contradiction. So gcd(N, Φ_{N}(b)), is either 1 or a power of p. If gcd(N, Φ_{N}(b)) > 1, then N = p^{l}|b|_{p}. Since l > 0, Theorem 22 implies that p^{2} does not divide Φ_{N}(b). Therefore, we get the following corollary.

Corollary 23. Let N > 1 and p the greatest prime divisor of N. Then gcd(N, Φ_{N}(b)) = 1 or p.

In the sequel, we prove that some known kinds of numbers are primovers to some base b.

Theorem 24. A generalized Fermat number, F_{n}(b) = b^{2^{n}} + 1, with n a positive integer and b even; is primover to base b.

Proof. It is well known that if p is prime, then Φ_{p^{r}} (x) = \frac{x^{p^{r}} − 1}{x^{p^{r−1}} − 1}. Since gcd (2^{n+1}, Φ_{2^{n+1}} (b)) =

1, we have P_{2^{n+1}}(b) = F_{n} (b) and the result follows from Theorem 20.

Theorem 25. A generalized Mersenne number, M_{p} (b) = \frac{b^{p} − 1}{b − 1}, with p a prime such that

gcd(p, b − 1) = 1, is primover to base b.

Proof. Note that Φ_{p}(b) = M_{p} (b) and gcd(p, Φ_{p}(b)) = 1. So P_{p}(b) = M_{p}(b) and the result follows from Theorem 20.

By Theorems 18 and 25, once again, we can prove that the numbers M_{p}(b) satisfy a similar property of the Mersenne numbers M_{p}.

Corollary 26. If gcd(p, b − 1) = 1, then for every pair of divisors d_{1} < d_{2} of M_{p}(b), including trivial divisors 1 and M_{p}(b), we have

p|d_{2} − d_{1}.  (11)

The following corollary give us an interesting property of M_{r}(b).

Corollary 27. Let r be a prime with gcd(r, b − 1) = 1. Then M_{r}(b) is prime if and only if the progression (1 + rx)_{x≥0} contains just one prime p such that |b|_{p} = r.

Proof. Assume that M_{r}(b) is prime. If there exists a prime p, such that |b|_{p} = r, then p = M_{r}(b). Since r|p − 1, i.e., p is the unique prime in the progression (1 + rx)_{x≥0}.

Conversely, assume that there exists only one prime of the form p = 1 + rx, with x ≥ 0, such that |b|_{p} = r. So p divides M_{r}(b). If M_{r}(b) is composite, then it is overpseudoprime to base b and thus to other prime divisor q of M_{r}(b) we obtain |b|_{q} = r. This contradicts our assumption.

The next result shows that Fermat numbers to base 2 are the only ones, of the form 2^{m} + 1, which are primover to base 2.

Theorem 28. The following properties hold.

1. Assume that b is even. Then P_{m}(b) = b^{m} + 1 is primover to base b if and only if m is a power of 2.

2. Suppose that gcd(n, b − 1) = 1. Then M_{n}(b) = \frac{b^{n} − 1}{b − 1} is primover to base b if and only if n is prime.

Proof. Sufficient conditions were proved in Theorems 24 and 25.

Now assume that m has an odd prime divisor. So b + 1 is a divisor of P_{m}(b) and thereby it is not a prime. Since, |b|_{b+1} = 2 and |b|_{b^{m}+1} = 2m; also it is not an overpseudoprime to base b.

To prove the necessity of the second part, suppose that n is not prime. Thus for a prime p divisor of n, we have M_{n}(b) is composite and b^{p} − 1 is one of its proper divisors. As |b|_{b^{p}−1} = p and |b|_{M_{n}(b)} = n, we get that M_{n}(b) is not an overpseudoprime to base b.

We note that, for p and q primes with q < p, |b|_{Φ_{pq}(b)} = pq.

Theorem 29. If q < p are primes, then

N = \frac{(b − 1)(b^{pq} − 1)}{(b^{p} − 1)(b^{q} − 1)}

is primover to base b if and only if N is not multiple of p.

Proof. It is clear that, N = Φ_{pq} (b). Assume that N is not a multiple of p. Corollary 23 implies that gcd (pq, Φ_{pq} (b)) = 1 and the result follows from Theorem 20.

Conversely assume that N is primover to base b and p divides N. Thereby, |b|_{p} divides q and as |b|_{N} = pq, we get a contradiction.

Corollary 30. With the above notation, if p divides N, then \frac{N}{p} is primover to base b.

Once again, using Corollary 23 and Theorem 20 we can prove the following theorems.

Theorem 31. If p is prime, then

N = \frac{b^{p^{n}} − 1}{b^{p^{n−1}} − 1}

is primover to base b if and only if N is not multiple of p.

Theorem 32. Let n = p_{1}p_{2} ⋯ p_{t}, where p_{1} < p_{2} < ⋯ < p_{t} are primes and let

N = ∏_{e|n} (b^{e} − 1)^{μ(e)μ(n)} .

If gcd(N, p_{t}) = 1, then N is primover to base b. In other case, \frac{N}{p_{t}} is primover to base b.

References

[1] J. H. Castillo, G. García-Pulgarín, and J. M. Velásquez-Soto, Pseudoprimes stronger than strong pseudoprimes, 2012, submitted. Available at

http://arxiv.org/abs/1202.3428.

[2] F. G. Dorais and D. Klyve, A Wieferich prime search up to 6.7 × 10^{15}, J. Integer Seq. 14 (2011), Article 11.9.2.

[3] R. K. Guy, Unsolved Problems in Number Theory, third ed., Problem Books in Mathematics, Springer-Verlag, 2004.

[4] J. Knauer and J. Richstein, The continuing search for Wieferich primes, Math. Comp. 74 (2005), no. 251, 1559–1563 (electronic).

[5] K. Motose, On values of cyclotomic polynomials. II, Math. J. Okayama Univ. 37 (1995), 27–36 (1996).

[6] M. B. Nathanson, Elementary Methods in Number Theory, Graduate Texts in Mathematics, Vol. 195, Springer-Verlag, 2000.

[7] V. Shevelev, Overpseudoprimes, Mersenne numbers and Wieferich primes, preprint.

Available at http://arxiv.org/abs/0806.3412.

[8] V. Shevelev, Process of “primoverization” of numbers of the form a^{n} − 1, preprint.

Available at http://arxiv.org/abs/0807.2332.

[9] N. J. A. Sloane, The On-Line Encyclopedia of Integer Sequences, published electroni-

    cally at http://oeis.org.

2010 Mathematics Subject Classification: Primary 11A51; Secondary 11A41, 11A07. Keywords: Mersenne numbers, cyclotomic cosets of 2 modulo n, order of 2 modulo n, Poulet pseudoprime, super-Poulet pseudoprime, overpseudoprime, Wieferich prime.

(Concerned with sequences \underline{A002326}, \underline{A141232}, \underline{A141350}, \underline{A141390} and \underline{A178997}.)

Received June 4 2012; revised version received September 6 2012. Published in Journal of Integer Sequences, September 8 2012.

Return to Journal of Integer Sequences home page.