Jakóbczyk’s Hypothesis on Mersenne Numbers and Generalizations of Skula’s Theorem

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 published an interesting article on the divisibility of Mersenne numbers 2^{n} − 1 by powers of primes. His main result is closely related to Jakóbczyk’s hypothesis. We generalize Skula’s result for the numbers a^{n} ± 1 where a ∈ ℕ, a ≥ 2.

1 Introduction

In 1951, Polish priest and mathematician Franciszek Jakóbczyk [9, p. 127] published two remarkable hypotheses concerning Mersenne [23, \underline{A000225}] and Fermat [23, \underline{A000215}] numbers. These hypotheses can be formulated as follows.

Hypothesis 1. Every Mersenne number M_{n} = 2^{n} − 1 with a prime exponent n is of the form M_{n} = p_{1} ⋯ p_{k} where p_{1}, …, p_{k} are distinct odd primes and k ≥ 1.

Hypothesis 2. Every Fermat number F_{n} = 2^{2^{n}} + 1 with n ∈ ℕ ∪ {0} is of the form F_{n} = p_{1} ⋯ p_{k} where p_{1}, …, p_{k} are distinct odd primes and k ≥ 1.

Hypotheses 1 and 2 are currently among the well-known unresolved number theory problems. See, for example, [21, p. 92], [5, pp. 14–16] and, [13, p. 160]. A more detailed examination of the divisibility of Mersenne and Fermat numbers led to the discovery of a link between Jakóbczyk’s hypotheses and the Wieferich primes [23, \underline{A001220}]. Recall that a prime p is called Wieferich if 2^{p−1} ≡ 1 (mod p^{2}). Wieferich primes were first introduced in 1909 in relation to the first case of Fermat’s last theorem. In the paper [27] Wieferich proved that, if p is an odd prime and x^{p} + y^{p} + z^{p} = 0 has a solution in integers x, y, z with p ∤ xyz, then 2^{p−1} ≡ 1 (mod p^{2}). Only two Wieferich primes have been discovered so far. The first Wieferich prime, 1093, was found by Meissner [17] in 1913 and the second Wieferich prime, 3511, was found by Beeger [2] in 1922. Whether the set W of all Wieferich primes is a finite or infinite set is another unanswered question. Recent calculations (March 2021) made under the PrimeGrid project [19] have shown that, if a third Wieferich prime exists, then its value must be greater than 3.15 × 10^{18}. In the following section, we give a summary of all known results related to Wieferich primes and Jakóbczyk’s hypotheses. Details of the life and work of Franciszek Jakóbczyk (1905–1992) can be found in [18].

2 Jakóbczyk’s hypotheses and Wieferich primes

In 1964, Schinzel [21, p. 102] posed the following problem: Do there exist infinitely many natural numbers n for which the number M_{n} = 2^{n} −1 is not divisible by any square of natural number > 1? A partial answer to Schinzel’s question is a result proved by Rotkiewicz [20, p. 79].

Theorem 3. (Rotkiewicz, 1965) If there are infinitely many square-free Mersenne numbers, then there are infinitely many primes p satisfying 2^{p−1} ≢ 1 (mod p^{2}).

In 1967, Warren and Bray [24, p. 563] proved the following implications:

Theorem 4. (Warren and Bray, 1967) Let n ∈ ℕ, n ≠ 1 and let p, q be odd primes. Then

(i) If p | M_{q}, then 2^{(p−1)/2} ≡ 1 (mod M_{q}).

(ii) If p | F_{n}, then 2^{(p−1)/2} ≡ 1 (mod F_{n}).

The below corollary can be obtained easily from Theorem 4.

Corollary 5. Let n ∈ ℕ and let p, q be odd primes. Then (i) and (ii) hold.

(i) If p^{2} | M_{q}, then 2^{p−1} ≡ 1 (mod p^{2}).

(ii) If p^{2} | F_{n}, then 2^{p−1} ≡ 1 (mod p^{2}).

The results presented by Warren and Bray can be extended as follows.

Theorem 6. Let n ∈ ℕ and let p, q be odd primes. Then (i) and (ii) hold.

(i) If p | M_{q}, then p^{2} | M_{q} if and only if 2^{p−1} ≡ 1 (mod p^{2}).

(ii) If p | F_{n}, then p^{2} | F_{n} if and only if 2^{p−1} ≡ 1 (mod p^{2}).

See [13, p. 68] and, [13, p. 217]. Theorem 6 provides the basic link between Jakóbczyk’s hypotheses and Wieferich primes. Finally, part (i) of Theorem 6 was generalized by Skula [22] in 2019. Before formulating Skula’s result, it may be appropriate to recall some concepts and definitions. Let k ∈ ℕ and let p be a Wieferich prime. By Definition 1.4 in the paper [22], p is called a Wieferich prime of order k if q(2, p^{k}) ≡ 0 (mod p^{k}) or, equivalently, 2^{p^{k−1}(p−1)} ≡ 1 (mod p^{2k}). Here, q(2, p^{k}) means the Euler quotient of p^{k} with base 2. See [1, Definition 1.2]. Hence, a prime p is Wieferich if and only if p is a Wieferich prime of order 1. Furthermore, note that, by [1, Definition 1.3], p is a Wieferich prime of order k if and only if p^{k} is a Wieferich number with base 2. See also [23, \underline{A077816}]. Finally, let a, m ∈ ℕ, m ≥ 2 and let gcd(a, m) = 1. 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). See [15, p. 55] or [13, p. 17]. It is clear from Euler’s theorem [1, p. 55] that ord_{p^{k}}(2) exists for every odd prime p and k ∈ ℕ.

Now we can formulate the main result proved in [22].

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

(i) p^{k+1} | M_{q}.

(ii) p is a Wieferich prime of order k.

(iii) ord_{p^{k+1}}(2) = q.

For an alternative proof of Theorem 7 see [12]. We conclude this section by recalling some known properties of ord_{m}(a) needed for proving our results.

Proposition 8. Let a, m ∈ ℕ, m ≥ 2 and let gcd(a, m) = 1. Then (i) – (vii) hold.

(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. Here, φ means the Euler function.

(iii) Let m = p_{1}^{k_{1}} ⋯ p_{s}^{k_{s}} be a prime factorization of m. Then

ord_{m}(a) = lcm(ord_{p_{1}^{k_{1}}}(a), …, ord_{p_{s}^{ks}}(a)).

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

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

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

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

(vi) Let k ∈ ℕ, p be an odd prime and let p ∤ a. Then ord_{p^{k+1}}(a) = p^{s} ord_{p}(a) for some s ∈ {0, …, k}.

(vii) Let k, s ∈ ℕ, p be an odd prime and let p ∤ a. If ord_{p}(a) = ⋯ = ord_{p^{k}}(a) ≠ ord_{p^{k+1}}(a), then ord_{p^{k+s}}(a) = p^{s} ord_{p}(a).

The proof of (i) and (ii) can be found in [16, p. 43]. For (iii) see [4, p. 30]. Part (iv) is Theorem 4.4 proved by LeVeque in [15, pp. 80–81]. See also [16, pp. 52–53]. Finally, (v), (vi) and (vii) immediately follow from (iv).

3 Some arithmetic properties of the numbers a^{n} ± 1

In this section, we will study in more detail the arithmetic properties of the numbers M_{n}(a) = a^{n} − 1 and L_{n}(a) = a^{n} + 1 where a ∈ ℕ, a ≥ 2, n ∈ ℕ ∪ {0}. First, we can observe that the sequences (M_{n}(a))_{n=0}^{∞} and (L_{n}(a))_{n=0}^{∞} are determined by the same linear second-order recurrence formula

H_{n+2} = (a + 1)H_{n+1} − aH_{n},  (1)

with suitable initial conditions H_{0}, H_{1} ∈ ℕ ∪ {0}. To see this, consider the characteristic equation (1). We have x^{2} − (a + 1)x + a = (x − 1)(x − a) = 0. Hence, it follows that Binet’s formula for H_{n} has the form H_{n} = c_{1} + c_{2}a^{n} where H_{0} = c_{1} + c_{2} and H_{1} = c_{1} + ac_{2}. After short calculation, we obtain

H_{n} = \frac{aH_{0} − H_{1}}{a − 1} + \frac{H_{1} − H_{0}}{a − 1} a^{n}.  (2)

If [H_{0}, H_{1}] = [0, a − 1], then H_{n} = M_{n}(a) by (2). If [H_{0}, H_{1}] = [2, a + 1], then H_{n} = L_{n}(a). Let m ∈ ℕ, m ≥ 2 and let gcd(a, m) = 1. We define

M(a, m) = min{n ∈ ℕ : [M_{n}(a), M_{n+1}(a)] ≡ [0, a − 1] (mod m)},
L(a, m) = min{n ∈ ℕ : [L_{n}(a), L_{n+1}(a)] ≡ [2, a + 1] (mod m)},
μ(a, m) = min{n ∈ ℕ : M_{n}(a) ≡ 0 (mod m)},
λ(a, m) = min{n ∈ ℕ : L_{n}(a) ≡ 0 (mod m)}.

Following the customary notation of the theory of linear recurrences, we call the numbers M(a, m) and L(a, m) primitive periods of the sequences

(M_{n}(a) mod m)_{n=0}^{∞} and (L_{n}(a) mod m)_{n=0}^{∞}.

The numbers μ(a, m) and λ(a, m) will then be called the rank of appearance of m in (M_{n}(a))_{n=0}^{∞} and (L_{n}(a))_{n=0}^{∞} respectively. In the following Theorem 9, the basic properties of the numbers M(a, m), L(a, m), μ(a, m) and λ(a, m) will be given.

Theorem 9. Let a, m ∈ ℕ, a, m ≥ 2 and let gcd(a, m) = 1. Then

(A) The numbers M(a, m), L(a, m) and μ(a, m) exist and we have

M(a, m) = L(a, m) = μ(a, m) = ord_{m}(a).  (3)

(B) Let m ≠ 2 and let ord_{m}(a) be odd. Then λ(a, m) does not exist. Let m = 2. Then λ(a, 2) = 1.

(C) Let m ≠ 2 and let ord_{m}(a) = 2t for some t ∈ ℕ. If λ(a, m) exists, then

λ(a, m) = \frac{ord_{m}(a)}{2} = t.  (4)

(D) Let k, t ∈ ℕ, p be an odd prime and let p ∤ a. Then

ord_{p^{k}}(a) = 2t if and only if λ(a, p^{k}) = t.

Proof. We prove (A). First, observe that ord_{m}(a) exists. Next, it is clear that μ(a, m) = min{n ∈ ℕ : a^{n} ≡ 1 (mod m)} = ord_{m}(a), which means that μ(a, m) exists. Let r = μ(a, m). Applying gcd(a, m) = 1, we obtain a^{r} − 1 ≡ 0 (mod m) if and only if a^{r+1} − 1 ≡ a − 1 (mod m). Hence, M(a, m) = r and, thus, M(a, m) = μ(a, m) = ord_{m}(a). Finally, [a^{r} − 1, a^{r+1} − 1] ≡ [0, a − 1] (mod m) if and only if [a^{r} + 1, a^{r+1} + 1] ≡ [2, a + 1] (mod m). Hence, M(a, m) = L(a, m). This proves (3).

We prove (B). Let m ≠ 2 and suppose that λ(a, m) = s for some s ∈ ℕ. Then a^{s} ≡ −1 (mod m) and, a^{2s} ≡ 1 (mod m) follows. Hence, ord_{m}(a) | 2s. Since ord_{m}(a) is odd, there exists a t ∈ ℕ ∪ {0} satisfying ord_{m}(a) = 2t + 1. This means that 2t + 1 | 2s. Thus, there exists an u ∈ ℕ, u ≠ 1 such that 2s = u(2t + 1). Hence, we see that u = 2v for some v ∈ ℕ and, thus, s = v(2t + 1). Therefore, a^{s} = (a^{2t+1})^{v} ≡ 1^{v} ≡ 1 (mod m). Since a^{s} ≡ −1 (mod m), we have 2 ≡ 0 (mod m). Hence, m = 2, a contradiction.

Let m = 2. Then, it follows from gcd(a, 2) = 1 that a is odd and, thus, 2 | a^{n} + 1 for every n ∈ ℕ ∪ {0}. Hence, λ(a, m) = 1. This proves (B).

We prove (C). Assume that λ(a, m) exists and that λ(a, m) = s for some s ∈ ℕ. Then a^{s} ≡ −1 (mod m) and a^{2s} ≡ 1 (mod m) follows. Hence, ord_{m}(a) | 2s. Since, ord_{m}(a) = 2t we get t | s. Suppose that t < s. Then there is a u ∈ ℕ, u ≠ 1 such that s = tu. First, suppose that u be even. Then we have u = 2v for some v ∈ ℕ. Hence, a^{s} = (a^{2t})^{v} ≡ 1^{v} ≡ 1 (mod m). On the other hand, a^{s} ≡ −1 (mod m). Hence, 2 ≡ 0 (mod m). Since m ≠ 2, we have a contradiction. Next, suppose that u be odd. Then u = 2v + 1 for some v ∈ ℕ ∪ {0}. Hence, a^{s} = a^{t(2v+1)} = (a^{2t})^{v}a^{t} ≡ a^{t} (mod m). This, together with a^{s} ≡ −1 (mod m), yields a^{t} ≡ −1 (mod m). Since s = min{n ∈ ℕ : a^{n} ≡ −1 (mod m)}, we get t ≥ s, which is a contradiction with t < s. Hence, s = t and (4) follows.

We prove (D). (i) First, assume that ord_{p^{k}}(a) = 2t. Therefore,

a^{2t} − 1 = (a^{t} − 1)(a^{t} + 1) ≡ 0 (mod p^{k}).  (5)

Let k > 1. Suppose that a^{t} − 1 ≡ 0 (mod p) and a^{t} + 1 ≡ 0 (mod p). Then 2 ≡ 0 (mod p). As p ≠ 2, we get a contradiction. Consequently, we have either a^{t} − 1 ≡ 0 (mod p^{k}) or a^{t} + 1 ≡ 0 (mod p^{k}). Since the case a^{t} − 1 ≡ 0 (mod p^{k}) leads to a contradiction with ord_{p^{k}}(a) = 2t, we have a^{t} + 1 ≡ 0 (mod p^{k}). Similarly, if k = 1, then (5) together with ord_{p}(a) = 2t yields a^{t} + 1 ≡ 0 (mod p). Hence, t ∈ {n ∈ ℕ : a^{n} + 1 ≡ 0 (mod p^{k})} for every k ∈ ℕ. This means that λ(a, p^{k}) exists. Applying part (C) of Theorem 9, we now obtain λ(a, p^{k}) = t.

(ii) Conversely, assume that λ(a, p^{k}) exists and that λ(a, p^{k}) = t. Then it follows from part (B) of Theorem 9 that ord_{p^{k}}(a) is even. Therefore, there is an s ∈ ℕ such that ord_{p^{k}}(a) = 2s. Hence, a^{2s} ≡ 1 (mod p^{k}), which yields (a^{s}−1)(a^{s}+1) ≡ 0 (mod p^{k}). Using the same reasoning as in (i), we conclude that a^{s} ≡ −1 (mod p^{k}). Suppose that s ≠ t. Since λ(a, p^{k}) = t, we have s > t. On the other hand, from a^{t} ≡ −1 (mod p^{k}), we get a^{2t} ≡ 1 (mod p^{k}), which means that ord_{p^{k}}(a) | 2t. Since ord_{p^{k}}(a) = 2s, we have s | t, which is a contradiction with s > t. Hence, s = t. This proves (D).

In the remaining part of this section, we will study the properties of the numbers λ(a, m) in more detail.

Theorem 10. Let a, m ∈ ℕ, a, m ≥ 2, 2 ∤ m and let gcd(a, m) = 1. Further, let ord_{m}(a) = 2t for some t ∈ ℕ and let m = p_{1}^{k_{1}} ⋯ p_{s}^{k_{s}} be a prime factorization of m. Then λ(a, m) exists if and only if (i) and (ii) hold.

(i) λ(a, p_{i}^{k_{i}}) exists for i ∈ {1, …, s}.

(ii) For i ∈ {1, …, s}, there is an odd w_{i} ∈ ℕ satisfying t = λ(a, p_{i}^{k_{i}})w_{i}.

In addition, if λ(a, m) exists, then

λ(a, m) = lcm(λ(a, p_{1}^{k_{1}}), …, λ(a, p_{s}^{k_{s}})) = t.  (6)

Proof. First, assume that λ(a, m) exists. Then it follows that λ(a, p_{i}^{k_{i}}) exists for every i ∈ {1, …, s}. Let t_{i} = λ(a, p_{i}^{k_{i}}). Applying part (D) of Theorem 9, we obtain ord_{p_{i}^{k_{i}}}(a) = 2t_{i}. Next, using part (iii) of Proposition 8 , we get

2t = ord_{m}(a) = lcm(ord_{p_{1}^{k_{1}}}(a), …, ord_{p_{s}^{ks}}(a)) = 2 lcm(t_{1}, …, t_{s}).  (7)

Hence, t_{i} | t for i ∈ {1, …, s}. This means that t = t_{i}w_{i} for some w_{i} ∈ ℕ.

Suppose that there is an j ∈ {1, …, s} such that 2 | w_{j}. Using a^{t_{j}} ≡ −1 (mod p_{j}^{k_{j}}), we find a^{t} = (a^{t_{j}})^{w_{j}} ≡ (−1)^{w_{j}} ≡ 1 (mod p_{j}^{k_{j}}). Suppose now that p_{j}^{k_{j}} | a^{t} + 1. Then a^{t} ≡ −1 (mod p_{j}^{k_{j}}). This, together with a^{t} ≡ 1 (mod p_{j}^{k_{j}}), yields 2 ≡ 0 (mod p_{j}^{k_{j}}). Since p_{j} is an odd prime, we have a contradiction. Hence p_{j}^{k_{j}} ∤ a^{t} + 1, which implies m ∤ a^{t} + 1. Therefore, λ(a, m) ≠ t. Since ord_{m}(a) = 2t, by part (C) of Theorem 9, we conclude that λ(a, m) does not exist, which is a contradiction.

For i ∈ {1, …, s}, let w_{i} be odd. Then a^{t} = (a^{t_{i}})^{w_{i}} ≡ (−1)^{w_{i}} ≡ −1 (mod p_{i}^{k_{i}}). Hence, p_{i}^{k_{i}} | a^{t} + 1. If w_{i} is odd for i ∈ {1, …, s}, then m = p_{1}^{k_{1}} ⋯ p_{s}^{k_{s}} | a^{t} + 1 and t ∈ {n ∈ ℕ : a^{n} + 1 ≡ 0 (mod m)}. This means that λ(a, m) exists, and, using part (C) of Theorem 9, we get λ(a, m) = t. This, together with (7), yields (6).

Conversely, assume that (i) and (ii) hold. If t_{i} = λ(a, p_{i}^{k_{i}}), we have a^{t_{i}} ≡ −1 (mod p_{i}^{k_{i}}). Now we can find a^{t} = (a^{t_{i}})^{w_{i}} ≡ (−1)^{w_{i}} ≡ −1 (mod p_{i}^{k_{i}}). We now see that p_{i}^{k_{i}} | a^{t} +1 for every i ∈ {1, …, s} and, thus, m = p_{1}^{k_{1}} ⋯ p_{s}^{k_{s}} | a^{t} + 1. Hence, t ∈ {n ∈ ℕ : a^{n} + 1 ≡ 0 (mod m)}, which means that λ(a, m) exists. By part (C) of Theorem 9, we obtain λ(a, m) = t. The proof is complete.

Remark 11. In [15, p. 57], LeVeque published the following Problem 19.

Show that, if m > 1 is odd and ord_{m}(a) = 2t, then a^{t} ≡ −1 (mod m).  (8)

We now prove, using a counterexample, that LeVeque’s implication is not true. Let m = 91 = 7 · 13 and let a = 5. Then ord_{91}(5) = 12, which means, by (8), that t = 6. Hence, 5^{6} ≡ 64 ≢ −1 (mod 91). It is evident that LeVeque’s erroneous claim is closely related to the existence of the numbers λ(a, m). By part (iii) of Proposition 8, we have

ord_{91}(5) = lcm(ord_{7}(5), ord_{13}(5)) = lcm(6, 4) = 12.

Hence, using part (D) of Theorem 9, we obtain λ(5, 7) = ord_{7}(5)/2 = 3 and λ(5, 13) = ord_{13}(5)/2 = 2. Next, applying Theorem 10, we get w_{1} = 6/λ(5, 7) = 2 and w_{2} = 6/λ(5, 13) = 3. Because w_{1} is not odd, λ(5, 91) does not exist. In other words, 91 ∤ L_{6}(5) = 5^{6} + 1 = 2 · 13 · 601.

Let a ∈ ℕ, a > 1 and let a be odd. Then 2 | a + 1 and thus {k ∈ ℕ : 2^{k} | a + 1} ≠ ∅. Put ν(a) = max{k ∈ ℕ : 2^{k} | a + 1}. In the following Lemma 12, we show that there is a close connection between the numbers ν(a) and λ(a, 2^{k}).

Lemma 12. Let a, k, n ∈ ℕ, a > 1 and let a be odd. Then

(A) If 2 | n, then 2 ∥ a^{n} + 1.

(B) If 2 ∤ n, then 2^{ν(a)} ∥ a^{n} + 1.

(C) λ(a, 2^{k}) exist if and only if k ≤ ν(a). In this case, λ(a, 2^{k}) = 1.

Proof. We prove (A). Let 2 | n. Since a > 1 is odd, there is an α ∈ ℕ such that a = 2α + 1. Hence, using the assumption 2 | n and the binomial theorem, we get

a^{n} + 1 = (2α + 1)^{n} + 1 ≡ 2 (mod 4).  (9)

By (9), 2 ∥ a^{n} + 1 for an even n.

We prove (B). Let 2 ∤ n . Then a^{n} + 1 = (a + 1)(a^{n−1} − a^{n−2} + ⋯ − a + 1). Since a is odd, we have 2 ∤ (a^{n−1} − a^{n−2} + ⋯ − a + 1). Hence, 2^{s} | a^{n} + 1 if and only if 2^{s} | a + 1 for every s ∈ ℕ. This means that 2^{ν(a)} ∥ a^{n} + 1 for any odd n.

Combining (A) and (B), (C) follows immediately.

Lemma 12 will be useful in proving Theorem 13.

Theorem 13. Let a, M ∈ ℕ, a, M ≥ 2, gcd(a, M) = 1 and let 2 ∤ a, 2 | M. Further, let M = 2^{α}p_{1}^{α_{1}} ⋯ p_{s}^{α_{s}} be a prime factorization of M and let m = p_{1}^{α_{1}} ⋯ p_{s}^{α_{s}}. Then (A) and (B) hold.

(A) Let α = 1. Then λ(a, M) exists if and only if λ(a, m) exists. Moreover, if λ(a, M) exists, then λ(a, M) = λ(a, m).

(B) Let α > 1. Then λ(a, M) exists if and only if λ(a, 2^{α}) and λ(a, m) exist and, 2 ∤ λ(a, m). Moreover, if λ(a, M) exists, then λ(a, M) = λ(a, m).

Proof. We prove (A). Assume that λ(a, M) exists and that λ(a, M) = U. Then M | a^{U} + 1. Since M = 2m and gcd(2, m) = 1, we get m | a^{U} + 1, which implies that λ(a, m) exists and that λ(a, m) ≤ U = λ(a, M).

Conversely, assume that λ(a, m) exists and that λ(a, m) = u. Then m | a^{u} + 1. Since a is odd, we have 2 | a^{n} + 1 for every n ∈ ℕ. Hence and from gcd(2, m) = 1, we obtain M = 2m | a^{u} + 1. This means that λ(a, M) exists and that λ(a, M) ≤ u = λ(a, m). This proves (A).

We prove (B). Let α > 1. First, assume that λ(a, M) exists and that λ(a, M) = U. Then M = 2^{α}m | a^{U} + 1. Hence and from gcd(2^{α}, m) = 1, we obtain 2^{α} | a^{U} + 1 and m | a^{U} + 1. This means that λ(a, 2^{α}) and λ(a, m) exist. Next, by part (C) of Lemma 12, we have α ≤ ν(a) and, from m | a^{U} + 1, we get λ(a, m) ≤ U = λ(a, M).

Let λ(a, m) = u. Suppose that 2 | u. Then, by part (A) of Lemma 12, we have 2 ∥ a^{u} +1. This means that 2^{α} ∤ a^{u} + 1. Hence, M = 2^{α}m ∤ a^{u} + 1 and, thus, λ(a, M) ≠ u = λ(a, m). This, together with u = λ(a, m) ≤ U, yields u < U. Hence, U = u + k for some k ∈ ℕ. From 2^{α}m | a^{u+k} + 1 and gcd(2^{α}, m) = 1, we can deduce that m | a^{u+k} + 1, or equivalently, a^{u}a^{k} ≡ −1 (mod m). Using a^{u} ≡ −1 (mod m), we now obtain a^{k} ≡ 1 (mod m). Hence, ord_{m}(a) | k. Suppose that ord_{m}(a) is odd. Then, by part (B) of Theorem 9, λ(a, m) does not exist, which is a contradiction. Hence, 2 | ord_{m}(a) and, 2 | k follows. Therefore, 2 | u + k = U. By part (A) of Lemma 12, we now obtain 2 ∥ a^{U} + 1. Hence and from α > 1, we get 2^{α} ∤ a^{U} + 1, which means 2^{α}m = M ∤ a^{U} + 1, a contradiction.

Let 2 ∤ u. Then, by part (B) of Lemma 12, we have 2^{ν(a)} | a^{u} + 1. As α ≤ ν(a), we also have 2^{α} | a^{u} + 1. Hence and from m | a^{u} + 1, we obtain 2^{α}m = M | a^{u} + 1, and U = λ(a, M) ≤ u follows. This, together with u = λ(a, m) ≤ U, yields λ(a, M) = λ(a, m).

Conversely, assume that λ(a, 2^{α}) and λ(a, m) exist and that λ(a, m) is odd. First, observe that, if α > 1 and λ(a, 2^{α}) exists, then, by part (C) of Lemma 12, we have α ≤ ν(a) and, by part (B) of Lemma 12, we have 2^{α} | a^{n} + 1 for any odd n ∈ ℕ. Let λ(a, m) = u. Then m | a^{u} +1. Since u is odd, we get 2^{α} | a^{u} +1. Hence and from gcd(2^{α}, m) = 1, we now obtain M = 2^{α}m | a^{u}+1, which means that λ(a, M) exists and that λ(a, M) ≤ u. Put λ(a, M) = U. Then we can write M = 2^{α}m | a^{U} + 1. Since gcd(2^{α}, m) = 1, we get m | a^{U} + 1, which yields λ(a, m) ≤ U. Finally, combining U = λ(a, M) ≤ u with u = λ(a, m) ≤ U, we get λ(a, M) = λ(a, m). This proves (B).

Remark 14. Let us note for completeness sake that the case of λ(a, m), where 2 | a and 2 | m, is trivial. Since a^{n} + 1 is odd for all n ∈ ℕ, λ(a, m) does not exist.

Let us conclude this section with an illustrative example.

Example 15. Let a = 11, m = 1769 = 29 · 61 and let M = 7076 = 2^{2}m. First, observe that ord_{29}(11) = 28, ord_{61}(11) = 4 and, ord_{1769}(11) = 28. Applying part (D) of Theorem 9, we obtain λ(11, 29) = ord_{29}(11)/2 = 14 and, λ(11, 61) = ord_{61}(11)/2 = 2. Next, using Theorem 10, we get t = ord_{1769}(11)/2 = 14, w_{1} = 14/λ(11, 29) = 1 and, w_{2} = 14/λ(11, 61) = 7. Since w_{1} and w_{2} are odd numbers, λ(11, 1769) exists and, by (6), we have λ(11, 1769) = 14. Further, observe that 2^{2} | a+1 = 12. Hence, by Lemma 12, λ(11, 2^{2}) exists and λ(11, 2^{2}) = 1. Because λ(11, 1769) is an even number, by Theorem 13, we conclude that λ(11, 7076) does not exist.

4 Mersenne numbers with base a

In this section, we generalize Skula’s result presented in Theorem 7. Let a, k ∈ ℕ, a ≥ 2 and let p be a prime satisfying p ∤ a. We will call p a Wieferich prime of order k with base a if p^{k} is a Wieferich number with base a. That is, p is a Wieferich prime of order k with base a if and only if

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

See [1, Definition 1.3].

Proposition 16. Let a, k ∈ ℕ, a ≥ 2, p be a prime and let p ∤ a. Then

(A) a^{p^{k−1}(p−1)} ≡ 1 (mod p^{2k}) if and only if a^{p−1} ≡ 1 (mod p^{k+1}).
(B) a^{p−1} ≡ 1 (mod p^{k+1}) if and only if ord_{p^{k+1}}(a) = ord_{p}(a).

(C) p is a Wieferich prime of order k with base a if and only if ord_{p^{k+1}}(a) = ord_{p}(a).

Proof. First, we prove (A). Assume that a^{p^{k−1}(p−1)} ≡ 1 (mod p^{2k}). Then, by part (i) of Proposition 8,

ord_{p^{2k}}(a) | p^{k−1}(p − 1).  (10)

Suppose that a^{p−1} ≢ 1 (mod p^{k+1}). Then ord_{p^{k+1}}(a) ≠ ord_{p}(a) and, by part (vi) of Proposition 8, there exists an r ∈ {1, …, k} such that ord_{p^{k+1}}(a) = p^{r} ord_{p}(a). Hence, by part (vii) of Proposition 8, we have

ord_{p^{2k}}(a) = p^{k} ord_{p^{k+1}}(a) = p^{k+r} ord_{p}(a).  (11)

Since r ∈ {1, …, k} and ord_{p}(a) | p − 1, we get a contradiction by relations (10) and (11).

Conversely, assume that a^{p−1} ≡ 1 (mod p^{k+1}). Then ord_{p^{k+1}}(a) | p − 1, which yields ord_{p}(a) = ord_{p^{k+1}}(a). Hence, by part (vi) of Proposition 8, there exists an s ∈ {0, …, k − 1} such that ord_{p^{2k}}(a) = p^{s} ord_{p^{k+1}}(a) = p^{s} ord_{p}(a). Since s ≤ k − 1, we get ord_{p^{2k}}(a) | p^{k−1} ord_{p}(a), which, together with ord_{p}(a) | p − 1, yields ord_{p^{2k}}(a) | p^{k−1}(p − 1). Hence, a^{p^{k−1}(p−1)} ≡ 1 (mod p^{2k}). This proves (A).

We prove (B). Let a^{p−1} ≡ 1 (mod p^{k+1}). Then ord_{p^{k+1}}(a) | p − 1. Using part (vi) of Proposition 8, we obtain ord_{p^{k+1}}(a) = p^{t} ord_{p}(a) for some t ∈ {0, …, k}. If t ≠ 0, then p^{t} ord_{p}(a) | p − 1, which is a contradiction. Hence, ord_{p^{k+1}}(a) = ord_{p}(a).

Conversely, let ord_{p^{k+1}}(a) = ord_{p}(a) = u. Then u | p − 1, which means that there exists a v ∈ ℕ such that p − 1 = uv. Since a^{u} ≡ 1 (mod p^{k+1}), we have a^{p−1} = a^{uv} = (a^{u})^{v} ≡ 1 (mod p^{k+1}) as required.

Finally, combining (A) and (B), we obtain (C). The proof is complete.

Remark 17. The conclusion (A) in Proposition 16 also holds if p | a. In this case, of course, we have a^{p^{k−1}(p−1)} ≢ 1 (mod p^{2k}), a^{p−1} ≢ 1 (mod p^{k+1}) for every a, k ∈ ℕ, a ≥ 2. The conclusion (B) in Proposition 16 also holds for k = 0.

Now we can to prove Theorem 18.

Theorem 18. Let a, k ∈ ℕ, a ≥ 2, p, q be odd primes and let p ∤ a, p ∤ a − 1. If p^{k} | M_{q}(a), then the following statements are equivalent:

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

(B) p is a Wieferich prime with base a of order k.

(C) ord_{p^{k+1}}(a) = q.

Proof. First, we show that (A) implies (B). Let p^{k+1} | M_{q}(a). Then a^{q} ≡ 1 (mod p^{k+1}), which yields ord_{p^{k+1}}(a) | q. Since q is a prime, we have ord_{p^{k+1}}(a) ∈ {1, q}. If ord_{p^{k+1}}(a) = 1, then ord_{p}(a) = 1, which means p | a − 1, a contradiction. Hence, ord_{p^{k+1}}(a) = q. Suppose that p = q. Then ord_{p^{k+1}}(a) = p and, using part (vi) of Proposition 8, we get ord_{p}(a) = 1. Hence, p | a−1, a contradiction. Let p ≠ q. Then, by part(vi) of Proposition 8, ord_{p^{k+1}}(a) = p^{s} ord_{p}(a) for some s ∈ {0, …, k}. Since p ≠ q, we get s = 0 and ord_{p^{k+1}}(a) = ord_{p}(a) = q. This means, by Proposition 16, that p is a Wieferich prime of order k with base a.

Next, we show that (B) implies (C). Assume that p is a Wieferich prime of order k with base a. Then, by Proposition 16, we have 2^{p−1} ≡ 1 (mod p^{k+1}) and, using part (i) of Proposition 8, we get ord_{p^{k+1}}(a) | p − 1. Next, from the basic assumption p^{k} | M_{q}(a), we obtain a^{q} ≡ 1 (mod p^{k}) and ord_{p^{k}}(a) | q follows. Hence, ord_{p^{k}}(a) ∈ {1, q}. Suppose that ord_{p^{k}}(a) = 1. Then p^{k} | a − 1, which yields p | a − 1, a contradiction. Hence, ord_{p^{k}}(a) = q. Now, by part (v) of Proposition 8, we have ord_{p^{k+1}}(a) = pq or ord_{p^{k+1}}(a) = q. Suppose that ord_{p^{k+1}}(a) = pq. Since ord_{p^{k+1}}(a) | p − 1, we get pq | p − 1, a contradiction. Hence, (C).

Finally, we show that (C) implies (A). If ord_{p^{k+1}}(a) = q, then a^{q} ≡ 1 (mod p^{k+1}), which yields p^{k+1} | M_{q}(a). The proof is complete.

Another generalization of Theorem 7 provide Theorem 19.

Theorem 19. Let a, k ∈ ℕ, a ≥ 2, p, q be primes and let p ∤ a. Then we have p^{k+1} | M_{q}(a) if and only if at least one of the below conditions (A), (B), (C) holds.

(A) ord_{p}(a) = 1, ord_{p^{k+1}}(a) = p, p = q.

(B) ord_{p}(a) = ord_{p^{k+1}}(a) = 1.

(C) ord_{p}(a) = ord_{p^{k+1}}(a) = q.

Proof. (i) If p^{k+1} | M_{q}(a), then a^{q} ≡ 1 (mod p^{k+1}), which yields ord_{p^{k+1}}(a) | q. Since q is a prime, we have ord_{p^{k+1}}(a) ∈ {1, q}. If ord_{p^{k+1}}(a) = 1, then ord_{p}(a) = 1 and (B) follows. If ord_{p^{k+1}}(a) = q, then, by part (vi) of Proposition 8, we have ord_{p^{k+1}}(a) = p^{s} ord_{p}(a) for some s ∈ {0, …, k}. Hence, p^{s} ord_{p}(a) = q. Since ord_{p}(a) ∈ ℕ and p, q are primes, only two following cases can occur.

Case 1: s = 1, ord_{p}(a) = 1, p = q. Hence, (A).

Case 2: s = 0, ord_{p}(a) = q. Hence, (C).

(ii) The proof of a converse implication consists of three simple parts. Assume (A). Then ord_{p^{k+1}}(a) = p implies a^{p} ≡ 1 (mod p^{k+1}), which means p^{k+1} | a^{p} − 1. Since p = q, we have p^{k+1} | a^{q} − 1 = M_{q}(a). Assume (B). Then ord_{p^{k+1}}(a) = 1 implies a ≡ 1 (mod p^{k+1}), thus, p^{k+1} | a − 1. Hence, p^{k+1} | (a − 1)(a^{q−1} + ⋯ + a + 1) = a^{q} − 1 = M_{q}(a). Assume (C). Then ord_{p^{k+1}}(a) = q implies a^{q} ≡ 1 (mod p^{k+1}). Hence, p^{k+1} | a^{q} − 1 = M_{q}(a).

Applying Theorem 19 for a = 2, we obtain Corollary 20.

Corollary 20. Let k ∈ ℕ, p, q be primes and let p ≠ 2. Then p^{k+1} | M_{q} if and only if ord_{p^{k+1}}(2) = ord_{p}(2) = q. Consequently,

p^{2} | M_{q} if and only if p ∈ W and ord_{p}(2) = q.  (12)

Proof. If p is a prime satisfying ord_{p}(2) = 1, then 2 ≡ 1 (mod p), which is a contradiction. Hence, the cases (A) and (B) in Theorem 19 never occur. Part (C) in Theorem 19 yields ord_{p^{k+1}}(2) = ord_{p}(2) = q. If k = 1, (12) follows immediately.

We now show some examples demonstrating part (C) of Theorem 19.

Example 21. (i) Let k = 1, a = 53, p = 47. Then

ord_{47}(53) = ord_{47^{2}}(53) = 23 and, 47^{2} | M_{23}(53) = 53^{23} − 1.

(ii) Let k = 2, a = 6619, p = 383. Then

ord_{383}(6619) = ord_{383^{3}}(6619) = 191 and, 383^{3} | M_{191}(6619) = 6619^{191} − 1.

(iii) Let k = 3, a = 2819, p = 19. Then

ord_{19}(2819) = ord_{19^{4}}(2819) = 3 and, 19^{4} | M_{3}(2819) = 2819^{3} − 1.

(iv) Let k = 3, a = 15384, p = 71. Then

ord_{71}(15384) = ord_{71^{4}}(15384) = 7 and, 71^{4} | M_{7}(15384) = 15384^{7} − 1.

5 Landry numbers with base a

In this section we will refer to Landry numbers with base a as the numbers

L_{n}(a) = a^{n} + 1 where a ∈ ℕ, a ≥ 2, n ∈ ℕ ∪ {0}.

In particular, to numbers L_{n} = L_{n}(2) = 2^{n} + 1, we will refer as Landry numbers. The term of Landry numbers we will introduce in honor of the French mathematician Fortuné Landry (1799–1895), who successfully dealt with prime factorizations of the numbers 2^{n} ± 1. This designation has been inspired by a note presented by Williams [26, p. 463]. Here, Williams mentions that some of Landry’s results have not received due attention being largely ignored. For details see [26].

The main aim of this section is to show that results analogous to Theorem 7 can also be proved for Landry numbers. The following Lemma 22 will be useful in proving Theorem 23.

Lemma 22. Let k ∈ ℕ, p, q be primes and let p ≠ 2. Then (i) – (iv) hold.

(i) ord_{p^{k}}(2) ≠ 1.

(ii) ord_{p^{k}}(2) = 2 if and only if p = 3 and k = 1.

(iii) ord_{p^{k+1}}(2) ≠ 2.

(iv) If ord_{p^{k+1}}(2) = 2q then, ord_{p}(2) ≠ q.

The proof of Lemma 22 can be left to the reader.

Theorem 23. Let k ∈ ℕ, p, q be odd primes and let p > 3. If p^{k} | L_{q}, then the following statements are equivalent:

(A) p^{k+1} | L_{q}.

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

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

Proof. First, we prove that (A) implies (B). Let p^{k+1} | L_{q}. Then we have 2^{q} ≡ −1 (mod p^{k+1}), which yields 2^{2q} ≡ 1 (mod p^{k+1}). Hence, ord_{p^{k+1}}(2) | 2q. By Lemma 22, we now obtain ord_{p^{k+1}}(2) = 2q. Since ord_{p}(2) | ord_{p^{k+1}}(2), we have ord_{p}(2) ∈ {1, 2, q, 2q} and, by Lemma 22, we get ord_{p}(2) = 2q. Hence, ord_{p^{k+1}}(2) = ord_{p}(2). This means, by Proposition 16, that p is a Wieferich prime of order k.

Next, we prove that (B) implies (C). Assume that p is a Wieferich prime of order k. Then, by Proposition 16, we have 2^{p−1} ≡ 1 (mod p^{k+1}) and, by part (i) of Proposition 8, we get ord_{p^{k+1}}(2) | p − 1. Next, from the basic assumption p^{k} | L_{q}, we obtain 2^{q} ≡ −1 (mod p^{k}), which yields 2^{2q} ≡ 1 (mod p^{k}). Hence, ord_{p^{k}}(2) | 2q and, by Lemma 22, we obtain ord_{p^{k}}(2) = 2q. Further, by part (v) of Proposition 8, we get ord_{p^{k+1}}(2) ∈ {2q, 2pq}.

Suppose that ord_{p^{k+1}}(2) = 2pq. Since ord_{p^{k+1}}(2) | p − 1, we get 2pq | p − 1, a contradiction. Hence, ord_{p^{k+1}}(2) = 2q.

Finally, we prove that (C) implies (A). Assume, that ord_{p^{k+1}}(2) = 2q. Then 2^{2q} ≡ 1 (mod p^{k+1}) yielding p^{k+1} | (2^{q} − 1)(2^{q} + 1). Suppose that p | 2^{q} − 1. Then we have ord_{p}(2) | q, which means that ord_{p}(2) ∈ {1, q}. Hence, by Lemma 22, a contradiction follows. Therefore, p^{k+1} | 2^{q} + 1 = L_{q}. The proof is complete.

For Landry numbers with a base a ∈ ℕ, a ≥ 2, we can prove the following theorem.

Theorem 24. Let a, k ∈ ℕ, a ≥ 2, let p, q be odd primes, and let p ∤ a. Then p^{k+1} | L_{q}(a) if and only if at least one of the below conditions (A), (B), (C) holds.

(A) ord_{p}(a) = 2, ord_{p^{k+1}}(a) = 2p, p = q.

(B) ord_{p}(a) = ord_{p^{k+1}}(a) = 2.

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

Proof. (i) Let p^{k+1} | L_{q}(a). Then a^{q} ≡ −1 (mod p^{k+1}), which yields ord_{p^{k+1}}(a) ≠ q. On the other hand, the congruence a^{q} ≡ −1 (mod p^{k+1}) implies a^{2q} ≡ 1 (mod p^{k+1}). Hence, ord_{p^{k+1}}(a) | 2q. Since q is an odd prime, we have ord_{p^{k+1}}(a) ∈ {1, 2, 2q}. Next, by part (vi) of Proposition 8, there exists an s ∈ {0, …, k} such that ord_{p^{k+1}}(a) = p^{s} ord_{p}(a). Hence, p^{s} ord_{p}(a) | 2q.

Let s ≠ 0. Since p, q are odd primes, the relation p^{s} ord_{p}(a) | 2q implies s = 1, p = q and ord_{p}(a) | 2. Hence, ord_{p}(a) ∈ {1, 2}. Suppose that ord_{p}(a) = 1. Then ord_{p^{k+1}}(a) = p, which means that a^{p} ≡ 1 (mod p^{k+1}). Since we have p = q, it follows from p^{k+1} | L_{q}(a) that a^{p} ≡ −1 (mod p^{k+1}). Combining a^{p} ≡ 1 (mod p^{k+1}) and a^{p} ≡ −1 (mod p^{k+1}), we obtain 2 ≡ 0 (mod p^{k+1}), a contradiction. If ord_{p}(a) = 2, then ord_{p^{k+1}}(a) = 2p = 2q. Hence, (A).

Let s = 0. Then we have ord_{p^{k+1}}(a) = ord_{p}(a). Suppose that ord_{p^{k+1}}(a) = 1. Then p^{k+1} | a−1. Hence, p^{k+1} | (a−1)(a^{q−1}+⋯+a+1) = a^{q}−1, which yields a^{q} ≡ 1 (mod p^{k+1}). On the other hand, from p^{k+1} | L_{q}(a), it follows a^{q} ≡ −1 (mod p^{k+1}). Along with a^{q} ≡ 1 (mod p^{k+1}), this yields 2 ≡ 0 (mod p^{k+1}), a contradiction. Finally, if ord_{p^{k+1}}(a) = 2, we get (B) and, if ord_{p^{k+1}}(a) = 2q, we get (C).

(ii) The proof of the converse implication consists of the three following parts.

Assume (A). From ord_{p^{k+1}}(a) = 2p, it follows that p^{k+1} | a^{2p} − 1 = (a^{p} − 1)(a^{p} + 1). Suppose that p | a^{p} − 1. Then ord_{p}(a) ∈ {1, p}, which is a contradiction with ord_{p}(a) = 2. Hence, p^{k+1} | a^{p} + 1. Since p = q, we have p^{k+1} | a^{q} + 1 = L_{q}(a).

Assume (B). From ord_{p^{k+1}}(a) = 2, it follows that p^{k+1} | a^{2} − 1 = (a − 1)(a + 1). Suppose that p | a − 1. Then we have ord_{p}(a) = 1, which is a contradiction with ord_{p}(a) = 2. Hence, p^{k+1} | a + 1, which yields p^{k+1} | (a + 1)(a^{q−1} − a^{q−2} + ⋯ − a + 1) = a^{q} + 1 = L_{q}(a).

Assume (C). From ord_{p^{k+1}}(a) = 2q, it follows that p^{k+1} | a^{2q} − 1 = (a^{q} − 1)(a^{q} + 1). Suppose that p | a^{q} − 1. Then ord_{p}(a) ∈ {1, q}, which is a contradiction with ord_{p}(a) = 2q. Hence, p^{k+1} | a^{q} + 1 = L_{q}(a).

Applying Theorem 24 for a = 2 and k = 1, we obtain Corollary 25.

Corollary 25. Let p, q be an odd primes. Then p^{2} | L_{q} if and only if

[p, q] = [3, 3] or ord_{p}(2) = ord_{p^{2}}(2) = 2q.  (13)

Consequently, if p > 3, then

p^{2} | L_{q} if and only if p ∈ W and ord_{p}(2) = 2q.  (14)

Proof. Let p be an odd prime satisfying ord_{p}(2) = 2. Then 2^{2} ≡ 1 (mod p), which yields p = 3. Since ord_{9}(2) = 6, part (A) in Theorem 24 is equivalent to [p, q] = [3, 3] and part (B) will never occur. Next, part (C) of Theorem 24 yields ord_{p}(2) = ord_{p^{2}}(2) = 2q. Hence, (13). Finally, (14) immediately follows from (13) and Proposition 16.

We now demonstrate part (C) of Theorem 24 by some examples.

Example 26. (i) Let k = 1, a = 79, p = 263. Then

ord_{263}(79) = ord_{263^{2}}(79) = 2 · 131 and, 263^{2} | L_{131}(79) = 79^{131} + 1.

(ii) Let k = 2, a = 42, p = 23. Then

ord_{23}(42) = ord_{23^{3}}(42) = 2 · 11 and, 23^{3} | L_{11}(42) = 42^{11} + 1.

(iii) Let k = 3, a = 119551, p = 107. Then

ord_{107}(119551) = ord_{107^{4}}(119551) = 2 · 53 and, 107^{4} | L_{53}(119551) = 119551^{53} + 1.

(iv) Let k = 1, a = 26, p = 6695256707. Then

ord_{p}(26) = ord_{p^{2}}(26) = 2q, q = 3347628353 and, 6695256707^{2} | L_{q}(26) = 26^{q} + 1.

Note, that the number 26^{q} + 1 has 4736804899 digits. This can be verified using the formula N = ⌊log_{10}(n) + 1⌋. Here, N stands for the number of digits of n and ⌊·⌋ denotes the floor function.

Remark 27. After a brief inspection of the proof of Theorem 24, we see that its conclusion cannot be true for q having a value of 2. Namely, if q = 2, then (B) does not imply p^{k+1} | L_{q}(a). To see this, assume (B). Then ord_{p^{k+1}}(a) = 2, which means a^{2} ≡ 1 (mod p^{k+1}). Suppose that p^{k+1} | L_{2}(a). Then a^{2} ≡ −1 (mod p^{k+1}). This, together with a^{2} ≡ 1 (mod p^{k+1}), yields 2 ≡ 0 (mod p^{k+1}), a contradiction. It is worth noting that all the remaining implications in Theorem 24 are also true for q = 2.

Theorem 28. Let a, k ∈ ℕ, a > 2, 2 ∤ a and let q be a prime. Then (A) and (B) hold.

(A) Let q ≠ 2. Then 2^{k+1} | L_{q}(a) if and only if 2^{k+1} | L_{1}(a).

(B) Let q = 2. Then 2^{k+1} ∤ L_{2}(a).

Proof. We prove (A). First, using the assumption q ≠ 2, we obtain

L_{q}(a) = L_{1}(a)(a^{q−1} − a^{q−2} + ⋯ − a + 1).  (15)

Next, applying 2 ∤ a and 2 ∤ q, we get 2 ∤ (a^{q−1} − a^{q−2} + ⋯ − a + 1). This, together with (15), yields (A).

We prove (B). Since a > 2 and 2 ∤ a, there exists an α ∈ ℕ such that a = 2α + 1. Hence, a^{2} + 1 = 2(2α^{2} + 2α + 1). This means that 4 ∤ a^{2} + 1 and, 2^{k+1} ∤ L_{2}(a) follows.

We conclude this section by Hypothesis 29.

Hypothesis 29. Every Landry number L_{n} = 2^{n} + 1 with a prime exponent n > 3 is of the form L_{n} = p_{1} ⋯ p_{k} where p_{1}, …, p_{k} are distinct odd primes and k ≥ 1.

6 Some problems related to ord_{p}(2)

We start this section by recalling some known properties of the quadratic character of 2.

Theorem 30. Let p be a prime, p ≠ 2. Then

(\frac{2}{p}) ≡ 2^{\frac{p−1}{2}} (mod p)  (16)

and,

(\frac{2}{p}) = (−1)^{\frac{p^{2}−1}{8}} = \begin{cases}1, & if p ≡ 1, 7 (mod 8); \\ −1, & if p ≡ 3, 5 (mod 8). \end{cases}  (17)

For a proof of (16) see, for example, [6, p. 86] or [8, p. 51]. An elementary proof of (17), based on Gauss’s lemma, can be found in books [8, p. 53] and [15, p. 102]. For some alternative proofs of (17), consult articles [10] and [25].

Proposition 31. Let p be a prime, p ≠ 2 and let ord_{p}(2) = q, where q is a prime. Then

p = 3 or p ≡ 1, 7 (mod 8).  (18)

Proof. If q = 2, then ord_{p}(2) = 2. Hence, 3 ≡ 0 (mod p) and p = 3 follows. Let q ≠ 2. Since q | p−1, there exists a u ∈ ℕ such that p−1 = 2qu. Hence, 2^{(p−1)/2} = (2^{q})^{u} ≡ 1^{u} ≡ 1 (mod p). Applying (16) and (17), we now obtain p ≡ 1, 7 (mod 8).

The below example illustrates that, in (18), both cases p ≡ 1, 7 (mod 8) can occur.

Example 32. (i) Let p = 89. Then p ≡ 1 (mod 8) and we have ord_{89}(2) = 11. (ii) Let p = 7. Then p ≡ 7 (mod 8) and we have ord_{7}(2) = 3. The values of the primes p presented are the least values for which the corresponding cases occur.

Proposition 33. Let p be a prime, p ≠ 2 and let ord_{p}(2) = 2q, where q is a prime. Then (i) and (ii) hold:

(i) p ≠ 8k + 5 for any k ∈ ℕ.

(ii) p ≠ 8k + 7 for any k ∈ ℕ.

Proof. First observe that, if q = 2, then ord_{p}(2) = 4 and, thus, 15 ≡ 0 (mod p). Hence, p = 3 or p = 5, which yields a contradiction in both cases (i) and (ii).

To prove (i), let q ≠ 2. Suppose that p = 8k + 5 for some k ∈ ℕ. Then, by Theorem 30, (2/p) ≡ 2^{(p−1)/2} ≡ −1 (mod p). Since 2q | p − 1, there exists a u ∈ ℕ such that p − 1 = 2qu. Hence,

2^{qu} = 2^{(p−1)/2} ≡ −1 (mod p).  (19)

Next, it is clear from ord_{p}(2) = 2q that 2^{2q} ≡ 1 (mod p). Hence, 2^{q} ≡ −1 (mod p). Suppose that u is even. Then

2^{qu} = (2^{q})^{u} ≡ (−1)^{u} ≡ 1 (mod p).  (20)

Combining (19) and (20) we obtain 2 ≡ 0 (mod p). Hence, p = 2, a contradiction.

Suppose that u is odd. Then u = 2v + 1 for some v ∈ ℕ ∪ {0}. From p − 1 = 2qu, it follows that p = 4qv + 2q + 1, which yields p ≡ 2q + 1 (mod 4). On the other hand, using the assumption p = 8k + 5, we get p ≡ 1 (mod 4). This, together with p ≡ 2q + 1 (mod 4), yields q ≡ 0 (mod 2). Hence, q = 2, a contradiction. This proves (i).

The proof of (ii) is similar.

From Proposition 33, we immediately obtain Corollary 34.

Corollary 34. Let p be a prime, p ≠ 2 and let ord_{p}(2) = 2q, where q is a prime. Then

p = 5 or p ≡ 1, 3 (mod 8).  (21)

The below example illustrates that, in (21), both cases p ≡ 1, 3 (mod 8) can occur.

Example 35. (i) Let p = 1049. Then p ≡ 1 (mod 8) and we have ord_{1049}(2) = 2 · 131. (ii) Let p = 11. Then p ≡ 3 (mod 8) and we have ord_{11}(2) = 2 · 5. The values of the primes p presented are the least values for which the corresponding cases occur.

In the remaining part of this section, the following notation will be adopted. If A is a finite set, #A denotes the number of elements of A. Next, P denotes the set of all odd primes. Finally, for an n ∈ ℕ, we define

π(n) = #{p ∈ P ∪ {2} : p ≤ n},
E(n) = #{p ∈ P : p ≤ n, ord_{p}(2) is even},
O(n) = #{p ∈ P : p ≤ n, ord_{p}(2) is odd},
Q(n) = #{p ∈ P : p ≤ n, ord_{p}(2) = q, q ∈ P ∪ {2}},
T (n) = #{p ∈ P : p ≤ n, ord_{p}(2) = 2q, q ∈ P ∪ {2}}.

Computer investigation of the values E(n), O(n), Q(n), T (n) and π(π(n)) for n ≤ 10^{10} yields the data in Table 1:

\begin{matrix}n & E(n) & O(n) & Q(n) & T (n) & π(n) & π(π(n)) \\ 10^{2} & 16 & 8 & 6 & 5 & 25 & 9 \\ 10^{3} & 117 & 50 & 22 & 17 & 168 & 39 \\ 10^{4} & 878 & 350 & 106 & 96 & 1229 & 201 \\ 10^{5} & 6794 & 2797 & 586 & 590 & 9592 & 1184 \\ 10^{6} & 55550 & 22947 & 3846 & 3745 & 78498 & 7702 \\ 10^{7} & 470633 & 193945 & 26561 & 26596 & 664579 & 53911 \\ 10^{8} & 4081095 & 1680359 & 196652 & 196695 & 5761455 & 397557 \\ 10^{9} & 36016626 & 14830907 & 1511508 & 1509239 & 50847534 & 3048955 \\ 10^{10} & 322328955 & 132723555 & 11982381 & 11981476 & 455052511 & 24106415 \end{matrix}

Table 1: Some values of E(n), O(n), Q(n), T (n) and π(π(n)).

From Table 1, we immediately obtain

\frac{E(10^{10})}{π(10^{10})} ≐ 0.708333, \frac{O(10^{10})}{π(10^{10})} ≐ 0.291666 and \frac{O(10^{10})}{E(10^{10})} ≐ 0.411764.  (22)

The relations given in (22) reveal a significant difference between the numbers E(n) and O(n) in the investigated range. In fact, in 1966, Hasse, [7, p. 23] proved that

lim_{n→∞} \frac{E(n)}{π(n)} = \frac{17}{24}, lim_{n→∞} \frac{O(n)}{π(n)} = \frac{7}{24} and lim_{n→∞} \frac{O(n)}{E(n)} = \frac{7}{17}.  (23)

See also Lagarias [14, p. 449]. Furthermore, from Table 1, we obtain

\frac{Q(10^{10})}{T (10^{10})} ≐ 1.000075 and \frac{π(π(10^{10}))}{Q(10^{10})} ≐ 2.011821.  (24)

This leads to a natural question, which can be formulated as Problem 36.

Problem 36. Prove or disprove

lim_{n→∞} \frac{Q(n)}{T (n)} = 1 and lim_{n→∞} \frac{π(π(n))}{Q(n)} = 2.  (25)

Next, for an n ∈ ℕ, let us define

R(n) = #{p ∈ P : p ≤ n, ord_{p}(2) = q, q ∈ P ∪ {2}, p ≡ 1 (mod 8)},
S(n) = #{p ∈ P : p ≤ n, ord_{p}(2) = q, q ∈ P ∪ {2}, p ≡ 7 (mod 8)},
U(n) = #{p ∈ P : p ≤ n, ord_{p}(2) = 2q, q ∈ P ∪ {2}, p ≡ 1 (mod 8)},
V (n) = #{p ∈ P : p ≤ n, ord_{p}(2) = 2q, q ∈ P ∪ {2}, p ≡ 3 (mod 8)}.

Computer investigation of the values R(n), S(n), U(n), and V (n) for n ≤ 10^{10}, yields the data in Table 2.

\begin{matrix}n & R(n) & S(n) & U(n) & V (n) \\ 10^{2} & 1 & 4 & 0 & 4 \\ 10^{3} & 2 & 19 & 0 & 16 \\ 10^{4} & 13 & 92 & 18 & 77 \\ 10^{5} & 92 & 493 & 95 & 494 \\ 10^{6} & 629 & 3216 & 594 & 3150 \\ 10^{7} & 4182 & 22378 & 4320 & 22275 \\ 10^{8} & 30556 & 166095 & 30961 & 165733 \\ 10^{9} & 233384 & 1278123 & 233357 & 1275881 \\ 10^{10} & 1834805 & 10147575 & 1835943 & 10145532 \end{matrix}

Table 2: Some values of R(n), S(n), U(n), and V (n).

From Tables 1 and 2, we get

\frac{R(10^{10})}{Q(10^{10})} ≐ 0.153125, \frac{S(10^{10})}{Q(10^{10})} ≐ 0.846874 and \frac{R(10^{10})}{S(10^{10})} ≐ 0.180812.

\frac{U(10^{10})}{T (10^{10})} ≐ 0.153231, \frac{V (10^{10})}{T (10^{10})} ≐ 0.846768 and \frac{U(10^{10})}{V (10^{10})} ≐ 0.180960.

Hence, we can propose the following problem. Problem 37. Find the limits (26) and (27) and prove that α_{i} = β_{i} for i ∈ {1, 2, 3}.

α_{1} = lim_{n→∞} \frac{R(n)}{Q(n)}, α_{2} = lim_{n→∞} \frac{S(n)}{Q(n)} and α_{3} = lim_{n→∞} \frac{R(n)}{S(n)}.  (26)

β_{1} = lim_{n→∞} \frac{U(n)}{T (n)}, β_{2} = lim_{n→∞} \frac{V (n)}{T (n)} and β_{3} = lim_{n→∞} \frac{U(n)}{V (n)}.  (27)

7 Concluding remarks

The following questions play an important role in further investigating the problem of the existence of primes p, q satisfying p^{2} | 2^{q} ± 1. Is there a third Wieferich prime? Is the set W of all Wieferich primes finite or infinite? Opinions vary as to what are the correct answers to such questions. See, for example, Beeger [3, p. 52] and Guy [5, p. 14]. If Beeger’s point of view is right, that is, W = {1093, 3511}, then both Hypothesis 1 and Hypothesis 29 hold. This follows immediately from (28) and (29).

ord_{1093}(2) = ord_{1093^{2}}(2) = 364 = 2^{2} · 7 · 13,  (28)
ord_{3511}(2) = ord_{3511^{2}}(2) = 1755 = 3^{3} · 5 · 13.  (29)

On the other hand, by (12) and (14), both hypotheses may hold true even if the set W is infinite. This fact makes both problems even more interesting.

It is worth noting that a similar disunity of opinion can also be seen in the analogous problem concerning the existence of Wall-Sun-Sun primes. A detailed historical study of this problem can be found in the article [11].

In conclusion, let us note that a statement similar to (12) and (14) can also be proved for Fermat numbers as shown below.

Theorem 38. Let n ∈ ℕ ∪ {0} and let p be a prime. Then

p^{2} | F_{n} if and only if p ∈ W and ord_{p}(2) = 2^{n+1}.  (30)

Using a computer, it can be verified that, for p ≤ 10^{10}, there exist only 20 primes satisfying ord_{p}(2) = 2^{k} for some k ∈ ℕ:

3, 5, 17, 257, 641, 65537, 114689, 274177, 319489, 974849, 2424833, 6700417, 13631489,
26017793, 45592577, 63766529, 167772161, 825753601, 1214251009, 6487031809.

8 Acknowledgment

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] N. Beeger, On a new case of the congruence 2^{p−1} ≡ 1 (mod p^{2}), Messenger of Mathematics 51 (1922), 149–150.

[3] N. Beeger, On the congruence 2^{p−1} ≡ 1 (mod p^{2}) and Fermat’s last theorem, Nieuw Arch. Wiskunde 20 (1939), 51–54.

[4] E. Deza, Mersenne Numbers and Fermat Numbers, Selected Chapters of Number Theory: Special Numbers, World Scientific, 2021.

[5] R. K. Guy, Unsolved Problems in Number Theory, 3rd edition, Springer, 2004.

[6] G. H. Hardy and E. M. Wright, An Introduction to the Theory of Numbers, 6th edition, Oxford University Press, 2008.

[7] H. Hasse, Über die Dichte der Primzahlen p, für die eine vorgegebene ganzrationale Zahl a ≠ 0 von gerader bzw. ungerader Ordnung mod.p ist, Math. Ann. 166 (1966), 19–23.

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

[9] F. Jakóbczyk, Les applications de la fonction λ_{g}(n) à l’étude des fractions périodiques et de la congruence chinoise 2^{n} − 2 ≡ 0 (mod n), Ann. Univ. Mariae Curie-Skłodowska 5 (1951), 97–138.

[10] R. Jakimczuk, The quadratic character of 2, Math. Mag. 84 (2011), 126–127.

[11] J. Klaška, Donald Dines Wall’s conjecture, Fibonacci Quart. 56 (2018), 43–51.

[12] J. Klaška, A simple proof of Skula’s theorem on prime power divisors of Mersenne numbers, J. Integer Sequences 25 (2022), Article 22.4.3.

[13] M. Křížek, F. Luca, and L. Somer, 17 Lectures on Fermat Numbers, From Number Theory to Geometry, Canadian Mathematical Society, Springer, 2001.

[14] J. C. Lagarias, The set of primes dividing the Lucas numbers has density 2/3, Pacific J. Math. 118 (1985), 449–461.

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

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

[17] W. Meissner, Über die Teilbarkeit von 2^{p} −2 durch das Quadrat der Primzahl p = 1093, Sitzungsberichte der Akademie der Wissenschaften 35 (1913), 663–667.

[18] H. Piersa, Śp. Ksia̧dz dr Franciszek Jakóbczyk (9 X 1905–3 VI 1992), Roczniki Filozoficzne 39–40, (1991–1992), 5–7.

[19] PrimeGrid, https://www.primegrid.com.

[20] A. Rotkiewicz, Sur les nombres de Mersenne dépourvus de diviseurs carrés et sur les nombres naturels n, tels que n^{2} | 2^{n} − 2, Mat. Vestnik 17 (1965), 78–80.

[21] W. Sierpiński, A Selection of Problems in the Theory of Numbers, Pergamon Press, 1964.

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

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

    https://oeis.org, 2023.

[24] L. R. Warren and H. G. Bray, On the square-freeness of Fermat and Mersenne numbers, Pacific J. Math. 22 (1967), 563–564.

[25] K. S. Williams, The quadratic character of 2 mod p, Math. Mag. 49 (1976), 89–90.

[26] K. S. Williams, How was F_{6} factored?, Math. Comp. 61 (1993), 463–474.

[27] A. Wieferich, Zum letzten Fermat’schen Theorem, J. Reine Angew. Math. 136 (1909), 293–302.

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

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

Received February 9 2023; revised versions received March 16 2023; March 17 2023. Published in Journal of Integer Sequences, March 17 2023.

Return to Journal of Integer Sequences home page.