A Simple Proof of Skula’s Theorem on Prime Power Divisors of Mersenne Numbers

Jiří Klaška Institute of Mathematics Faculty of Mechanical Engineering Brno University of Technology Technická 2 CZ – 616 69 Brno Czech Republic

                            klaska@fme.vutbr.cz

Abstract

Recently, Skula proved an interesting result concerning the equivalence between higher order Wieferich primes and prime power divisors of Mersenne numbers. In the present paper, we provide a simple proof of Skula’s result.

1 Introduction

The Mersenne numbers M_{n} = 2^{n} − 1, n ∈ ℕ have been studied by many authors over past centuries, with a number of remarkable statements discovered and proved since the time of Marin Mersenne (1588–1648). See sequences \underline{A000225} and \underline{A001348} in the On-Line Encyclopedia of Integer Sequences [6].

The present paper is concerned with the connection between higher-order Wieferich primes and prime power divisors of Mersenne numbers. First, however, we recall certain definitions and facts relating to this topic. In 1997, Agoh, Dilcher, and Skula published the well-known paper [1] in which the concepts of Fermat quotient and Wieferich prime were extended substantially.

Let a, m ∈ ℤ, m ≥ 2 and let gcd(a, m) = 1. By [1, Definition 1.2],

q(a, m) = \frac{a^{φ(m)} − 1}{m}

is called the Euler quotient of m with base a. From Euler’s theorem it is clear (see for example [2, p. 33] or [4, p. 42]) that q(a, m) ∈ ℤ. By [1, Definition 1.2], m is called a Wieferich number with base a if q(a, m) ≡ 0 (mod m). See also [6, \underline{A077816}]. Specifically, if p is a prime satisfying q(2, p) ≡ 0 (mod p), we obtain the well-known definition of a Wieferich prime: p is a Wieferich prime if 2^{p−1} ≡ 1 (mod p^{2}). See [6, \underline{A001220}]. By [5, Definition 1.4] a Wieferich prime p is called a Wieferich prime of order n ∈ ℕ if

q(2, p^{n}) ≡ 0 (mod p^{n}) or, equivalently, 2^{p^{n−1}(p−1)} ≡ 1 (mod p^{2n}).

Hence, a prime p is a Wieferich one if and only if p is Wieferich prime of order 1 and, p is a Wieferich prime of order n if and only if p^{n} is a Wieferich number with base 2.

Finally, let us recall that the smallest positive integer h for which a^{h} ≡ 1 (mod m) is called the multiplicative order of a modulo m, which we write as h = ord_{m}(a). Now we can formulate the main result presented in [5].

Theorem 1 (Skula, 2019). Let n ∈ ℕ and let p, q be odd primes. If p^{n}|M_{q}, then the following statements are equivalent:

(A) p^{n+1}|M_{q}.

(B) p is a Wieferich prime of order n.

(C) ord_{p^{n+1}}(2) = q.

The proof of Theorem 1 given in [5] is mainly based on some special properties of Euler quotient, such as the logarithm property presented in [5, Proposition 1.1] or the proposition on the Euler quotient for two bases [5, Proposition 2.1]. Furthermore, the proof in [5] uses the results [1, Lemma 5.1] and [1, Corollary 5.2] on the order of the number q(2, p) modulo p within the meaning of definition [2, p. 3]. Hence, the proof of Theorem 1 in [5] is the result of resourcefully applying a series of findings.

The main purpose of this paper is to show that Theorem 1 can be proved in a way simpler than the one in [5], that is, without using special propositions on the Euler quotient.

2 Proof of Theorem 1

We begin by recalling some of the known properties of ord_{m}(a), which are needed in our proof of Theorem 1.

Lemma 2. Let a, m ∈ ℤ, m ≥ 2 and let gcd(a, m) = 1. Then (i)–(vii) holds.

(i) Let k ∈ ℕ. Then a^{k} ≡ 1 (mod m) if and only if ord_{m}(a)|k.

(ii) ord_{m}(a)|φ(m). Consequently, if p is an odd prime, then ord_{p}(2)|p − 1.

(iii) Let a, k, n ∈ ℕ and let p be an odd prime satisfying p ∤ a. Further, let ord_{p}(a) = h and let p^{k}∥a^{h} − 1. Then

ord_{p^{n}}(a) = \begin{cases}h, & for n ≤ k; \\ p^{n−k}h, & for n > k. \end{cases}

Here, p^{k}∥a^{h} − 1 means that p^{k}|a^{h} − 1 but p^{k+1} ∤ a^{h} − 1.

(iv) Let a, n ∈ ℕ and let p be an odd prime satisfying p ∤ a. If ord_{p^{n}}(a) = h, then ord_{p^{n+1}}(a) ∈ {h, ph}. Consequently, ord_{p^{n}}(a)| ord_{p^{n+1}}(a).

(v) Let k, n ∈ ℕ and let p be an odd prime. If ord_{p}(2) = ⋯ = ord_{p^{n}}(2) ≠ ord_{p^{n+1}}(2), then ord_{p^{n+k}}(2) = p^{k} ord_{p}(2).

(vi) Let n ∈ ℕ and let p be an odd prime. If ord_{p^{n}}(2)|p − 1, then ord_{p^{k}}(2) = ord_{p^{n}}(2) for any k ∈ {1, …, n}.

(vii) Let n ∈ ℕ and let p, q be odd primes. If ord_{p^{n}}(2)|q, then ord_{p^{k}}(2) = q for any k ∈ {1, …, n}.

The proofs of (i) and (ii) can be found in [4, p. 43]. Part (iii) is Theorem 4.4 proved by LeVeque in [3, pp. 80–81]. See also Theorem 4–6 in [4, pp. 52–53]. Part (iv) immediately follows from (iii). Part (v) is a direct consequence of (iii) for p = 2. Finally, (vi) and (vii) follow from (iv).

Proposition 3. Let n ∈ ℕ and let p be a prime. Then,

2^{p^{n−1}(p−1)} ≡ 1 (mod p^{2n}) if and only if 2^{p−1} ≡ 1 (mod p^{n+1}).  (1)

Proof. Let us first assume that p is an odd prime.

Let 2^{p^{n−1}(p−1)} ≡ 1 (mod p^{2n}). Applying (i), we obtain

ord_{p^{2n}}(2)|p^{n−1}(p − 1).  (2)

Suppose that 2^{p−1} ≢ 1 (mod p^{n+1}). From (i), it now follows that ord_{p^{n+1}}(2) ∤ p − 1 and, by (ii), ord_{p}(2)|p − 1. This means that ord_{p^{n+1}}(2) ≠ ord_{p}(2). From (v), it follows that there exists an s ∈ {1, …, n} such that ord_{p^{n+1}}(2) = p^{s} ord_{p}(2). Hence,

ord_{p^{2n}}(2) = p^{n} ord_{p^{n+1}}(2) = p^{n+s} ord_{p}(2).  (3)

Combining (3) and (2), we obtain p^{n+s} ord_{p}(2)|p^{n−1}(p − 1). Since s ∈ {1, …, n} and ord_{p}(2)|p − 1, we have a contradiction.

Conversely, let 2^{p−1} ≡ 1 (mod p^{n+1}). Then, by (i), we have ord_{p^{n+1}}(2)|p − 1 and, using (vi), we obtain ord_{p^{n+1}}(2) = ord_{p}(2). Further, by (v), there exist a t ∈ {0, …, n − 1} such that

ord_{p^{2n}}(2) = p^{t} ord_{p^{n+1}}(2) = p^{t} ord_{p}(2).  (4)

Since t ≤ n − 1, (4) implies ord_{p^{2n}}(2)|p^{n−1} ord_{p}(2), which, together with ord_{p}(2)|p − 1, yields ord_{p^{2n}}(2)|p^{n−1}(p − 1). Hence, 2^{p^{n−1}(p−1)} ≡ 1 (mod p^{2n}).

Finally, let p = 2. Then, for any n ∈ ℕ, 2^{2^{n−1}} ≢ 1 (mod 2^{2n}) and 2 ≢ 1 (mod 2^{n+1}). This means that, (1) holds for p = 2 as well. The proof is now complete.

Proposition 4. Let n ∈ ℕ ∪ {0} and let p be an odd prime. Then,

2^{p−1} ≡ 1 (mod p^{n+1}) if and only if ord_{p^{n+1}}(2) = ord_{p}(2).

Proof. Let 2^{p−1} ≡ 1 (mod p^{n+1}). Then, by (i), ord_{p^{n+1}}(2)|p−1. Next, applying (iii), we obtain ord_{p^{n+1}}(2) = p^{s} ord_{p}(2) for some s ∈ {0, …, n}. Suppose that s ≠ 0. Then, p^{s} ord_{p}(2)|p − 1, which is a contradiction. Hence, ord_{p^{n+1}}(2) = ord_{p}(2).

Conversely, let ord_{p^{n+1}}(2) = ord_{p}(2) = h. Then, by (ii), h|p − 1. This means that there exists a k ∈ ℕ such that p−1 = hk. Since 2^{h} ≡ 1 (mod p^{n+1}), we have 2^{p−1} = 2^{hk} = (2^{h})^{k} ≡ 1 (mod p^{n+1}), as required.

Now we are ready to prove Theorem 1.

Proof. First, we show that (A) implies (B). Let p^{n+1}|M_{q}. Then, 2^{q} ≡ 1 (mod p^{n+1}) which yields ord_{p^{n+1}}(2)|q. Applying (vii), we obtain ord_{p^{n+1}}(2) = ord_{p}(2) = q. This means, by Proposition 4, that 2^{p−1} ≡ 1 (mod p^{n+1}) and, using Proposition 3, we conclude that p is a Wieferich prime of order n.

Next, we show that (B) implies (C). Assume that p is a Wieferich prime of order n. Then, by Proposition 3, 2^{p−1} ≡ 1 (mod p^{n+1}) and, using (i), we get ord_{p^{n+1}}(2)|p − 1. Next, from the basic assumption p^{n}|M_{q}, we obtain 2^{q} ≡ 1 (mod p^{n}) and, by (i), we get ord_{p^{n}}(2)|q. Since q is an odd prime and ord_{p^{n}}(2) ≠ 1, we have ord_{p^{n}}(2) = q. Hence, by (iv), ord_{p^{n+1}}(2) = pq or ord_{p^{n+1}}(2) = q. Suppose that ord_{p^{n+1}}(2) = pq. Since ord_{p^{n+1}}(2)|p − 1, we get pq|p − 1, a contradiction.

Finally, we show that (C) implies (A). Let ord_{p^{n+1}}(2) = q. Then, 2^{q} ≡ 1 (mod p^{n+1}), which yields p^{n+1}|M_{q}. The proof is complete.

3 Acknowledgments

The author thanks the anonymous referee for carefully reading the manuscript.

References

[1] T. Agoh, K. Dilcher, and L. Skula, Fermat quotients for composite moduli, J. Number Theory 66 (1997), 29–50.

[2] K. Ireland and M. Rosen, A Classical Introduction to Modern Number Theory, 2nd edition, Springer-Verlag, 1992.

[3] W. J. LeVeque, Fundamentals of Number Theory, Addison-Wesley, 1977.

[4] W. J. LeVeque, Topics in Number Theory, Volume I, Dover Publications, 2002.

[5] L. Skula, Prime power divisors of Mersenne numbers and Wieferich primes of higher order, Integers 19 (2019), #A19.

[6] N. J. A. Sloane et al., The On-Line Encyclopedia of Integer Sequences, available at

   https://oeis.org, 2022.

2020 Mathematics Subject Classification: Primary 11A41; Secondary 11A07. Keywords: Mersenne number, Wieferich number, Wieferich prime.

(Concerned with sequences \underline{A000225}, \underline{A001220}, \underline{A001348}, and \underline{A077816}.)

Received January 27 2022; revised version received March 29 2022. Published in Journal of Integer Sequences, March 31 2022.

Return to Journal of Integer Sequences home page.