On the Exponents of Non-Trivial Divisors of Odd Numbers and a Generalization of Proth’s Primality Theorem

Tom Müller Institut für Cusanus-Forschung University and Theological Faculty of Trier Domfreihof 3 54290 Trier Germany

                    mueller2887@t-online.de

Abstract We present a family of integer sequences characterizing the behavior of the quotients σ/s for a given odd natural number H, where N = H · 2^{σ} + 1 is a composite number and h · 2^{s} + 1 (h ≥ 1 odd, s, σ ∈ ℕ) is a non-trivial divisor of N. As an application we prove a generalization of the primality theorem of Proth.

1 Introduction

For every odd natural number N > 1 there exists an unique pair (H, σ) with H an odd natural number, σ ∈ ℕ and N = H · 2^{σ} + 1. In this parametric notation, we call H the multiplier of N and σ the exponent of N. Here and subsequently, the notation A · 2^{α} + 1 always means that A is the multiplier and α the exponent of the represented odd natural number. For a given natural number N > 1 we let D(N) denote the set of the non-trivial divisors of N, i.e., the set of all natural numbers d fulfilling 1 < d < N and d|N. Obviously, N is a prime number if and only if D(N) = ∅.

The aim of this paper is to introduce and study a family of integer sequences characterizing the behavior of the quotient \frac{σ}{s} for a given H, where N = H · 2^{σ} + 1 is a composite number and h · 2^{s} + 1 ∈ D(N). These sequences can be used to give a generalization of the well-known primality theorem of Proth.

If the exponent s is large compared to σ, then there must exist a rather small real number m > 0 with m ≥ \frac{σ}{s}. All the values of σ fulfilling this inequality for a given odd natural number H are elements of the following set:

S_{m}(H) := \{σ ∈ ℕ | ∃d = h · 2^{s} + 1 ∈ D(H · 2^{σ} + 1) : m ≥ \frac{σ}{s} \} .  (1)

With this we define the integer sequence

σ_{m}(H) := sup (S_{m}(H)) .

As usual, we adopt the conventions that sup(∅) = 0 and sup(A) = ∞ if |A| = |ℕ|. The aforementioned definitions immediately imply S_{k}(H) ⊂ S_{l}(H) and hence σ_{k}(H) ≤ σ_{l}(H) if k < l.

2 The σ_{m}-sequences

2.1 Diophantine equations

Definition (1) leads to a general Diophantine equation, which allows to determine the elements of S_{m}(H) for a given m ≥ 1. Suppose N = H · 2^{σ} + 1 = AB to be composite with two non-trivial divisors A = h · 2^{r} + 1 and B = k · 2^{s} + 1. Without loss of generality we can denote A and B such that 1 ≤ r ≤ s. It follows that

AB = 2^{r} (2^{s}hk + 2^{s−r}k + h) + 1 = 2^{σ}H + 1 = N.

This is equivalent to the Diophantine equation

2^{s}hk + 2^{s−r}k + h = 2^{σ−r}H.  (2)

Note that r ≤ s ∈ ℕ and that h and k are odd natural numbers. To reflect the condition m ≥ \frac{σ}{s} of the definition we may include a supplementary parameter n in order to write ⌊ms⌋−n = σ. In general, n can take any integer value between 0 and ⌊ms⌋−1. For practical purposes it is useful to demand for further restrictions, which render the computations more comfortable.

If m = 1 then we get r = σ < s. Therefore, (2) turns into

2^{s}hk + 2^{s−r}k + h = H.  (3)

It is easy to see that for H ∈ {1, 3} equation (3) has no solution (under the abovementioned assumptions). Hence σ_{1}(1) = σ_{1}(3) = 0. For H > 3 the estimate σ < s ≤ log_{2}(H) obviously holds. This gives σ_{1}(H) ≤ ⌊log_{2}(H)⌋ − 1 for all H ≥ 3. In fact, this estimate is best possible in the sense that there are infinitely many values of H for which we actually have σ_{1}(H) = ⌊log_{2}(H)⌋ − 1. We will establish this in subsection 2.3.

It is immediate that by explicitly giving a solution (r, s, h, k, H) of (3), we get the lower bound σ_{1}(H) ≥ r.

Example 1. Because 8 · \frac{10^{n}−1}{9} + 2 · \frac{10^{n}−1}{9} + 1 = \frac{10^{n+1}−1}{9}, we have σ_{1} (\frac{10^{n+1}−1}{9}) ≥ 2 for all natural numbers n.

Remark 2. Since σ_{1}(H) < ∞ for every odd natural number H it is obvious that σ_{m}(H) < ∞ for every 0 < m < 1. Because of S_{m}(H) ⊂ S_{1}(H), the value of σ_{m}(H) can thus explicitly be calculated by examining the elements of S_{1}(H).

Note that for m > 1 we already get r = s < σ in the Diophantine equation (2). Therefore, the Diophantine equation to consider concerning σ_{2}(H) reads

2^{s}hk + h + k = 2^{σ−s} · H  (4)

with the supplementary condition 2s ≥ σ, i.e., s ≥ σ − s. For computational reasons we will deal with another Diophantine equation in this context:

2^{s}hk + h + k = 2^{s−n} · H  (5)

with h ≤ k odd and 0 ≤ n < s. Note that (5) follows from (4) by setting 2s = σ + n. The solutions (n, s, h, k, H) of (5) yield the elements σ = 2s − n ∈ S_{2}(H) \ S_{1}(H). Some simple but very useful results can be derived from this Diophantine equation. First, (5) implies 2^{n}hk < H, showing that σ_{2}(H) < ∞ for every odd H. In subsection 2.4 we will give a best possible upper bound of the values of σ_{2}(H). Again, by explicitly giving a solution (n, s, h, k, H) of (5), we get the lower bound σ_{2}(H) ≥ 2s − n.

Example 3. Since 4(8 · 10^{w} − 1) + 8 · 10^{w} = 4(10^{w+1} − 1), we see that σ_{2}(10^{w+1} − 1) ≥ 4 for all natural numbers w.

For m = 3 there is also a condition for existence, limiting the value of n in the Diophantine equation

2^{s}hk + h + k = 2^{2s−n} · H,  (6)

where h ≤ k are odd natural numbers and 0 ≤ n < s. Note that (n, s, h, k, H) is a solution of equation (6) if and only if the corresponding σ = 3s − n is an element of S_{3}(H) \ S_{2}(H).

Now consider such a solution (n, s, h, k, H). By equation (6) we get h + k ≡ 0 (mod 2^{s}), i.e., h + k = 2^{s} · d for an appropriate natural number d. Moreover, there exists a natural number a with a + n = s, i.e., 2s − n = s + a. Then hk = 2^{a}H − d ≤ 2^{a}H − 1. This implies h + k ≤ hk + 1 ≤ 2^{a}H ≤ 2^{s}H and hence 2^{s} = \frac{h+k}{2^{a}H−hk} ≤ 2^{a}H. Finally, he have 2^{n} = 2^{s−a} ≤ H, yielding n ≤ log_{2}(H). Remark 4. This condition of existence already implies that σ_{m}(H) < ∞ for every odd H and m ∈ (2, 3). To see this, suppose σ ∈ S_{m}(H) \ S_{2}(H) ⊂ S_{3}(H) \ S_{2}(H) for a m ∈ (2, 3). This means that the corresponding s leads to a solution in (6) and hence fulfils the inequality s ≤ \frac{σ+log_{2}(H)}{3}. Consequently, σ satisfies \frac{σ}{m} ≤ \frac{σ+log_{2}(H)}{3} which is equivalent to

σ ≤ \frac{m log_{2}(H)}{3 − m}.  (7)

Since σ_{2}(H) < ∞, we can conclude with inequality (7) that σ_{m}(H) is finite as well.

2.2 Some elementary primality results

Proposition 5. Let m be a natural number and H ≥ 1 be an odd number such that σ_{m}(H) = 0. Then N := H · 2^{m} + 1 is a prime number.

Proof. The number N = H · 2^{m} + 1 is either prime or it has a non-trivial divisor of the form h · 2^{r} + 1 with r ≥ 1 = \frac{σ}{m}. The latter case would imply σ_{m}(H) ≥ m > 0.

Corollary 6. Let H ≥ 1 be an odd number. Let l be a nonnegative integer number and m be a natural number with σ_{m}(H) = l < m. Then N := H · 2^{σ} + 1 is a prime number for every σ ∈ [l + 1, m] ∩ ℕ.

Proof. For m = 1 this is exactly the claim of Proposition 5. For m > 1 we know that r = s < σ if there are non-trivial divisors A := h · 2^{r} + 1 and B := k · 2^{s} + 1 of N such that AB = N. But this leads to m > s ≥ 1 ≥ \frac{σ}{m} and hence σ_{m}(H) ≥ σ > l.

Corollary 7. Let H be an odd natural number and let m ≥ 1 be a real number. If the natural number σ ≤ m is not an element of S_{m}(H) then N = H · 2^{σ} + 1 is a prime number.

Proof. Let N = H · 2^{σ} + 1 = AB be a composite number with σ ≤ m. As usual, write A = h · 2^{r} + 1 and B = k · 2^{s} + 1 with r ≤ s. Now suppose that σ is not an element of S_{m}(H). Then we have s < \frac{σ}{m} ≤ 1, contradicting the condition 1 ≤ s.

2.3 Special values of σ_{1}

Theorem 8. Let l and m ≥ l + 1 be natural numbers. Then σ_{1}(2^{m} + 2^{l} + 1) ≥ m − l.

Proof. Under the conditions of the theorem, (r, s, h, k, H) = (m − l, m, 1, 1, 2^{m} + 2^{l} + 1) is a solution of (3).

Theorem 9. Let m ≥ 2 be a natural number. Then σ_{1}(2^{m} + 3) = m − 1.

Proof. For every H > 1 we know that σ_{1}(H) ≤ ⌊log_{2}(H)⌋−1. Therefore, σ_{1}(2^{m} +3) ≤ m−1 for all m ≥ 2. The claim follows with Theorem 8.

On the one hand, Theorem 9 shows that for every H = 2^{m} + 3 (m ≥ 2) the best possible value σ_{1}(H) = ⌊log_{2}(H)⌋ − 1 is actually reached. On the other hand, we can conclude that the arithmetical function σ_{1} : ℕ \ 2ℕ → ℕ_{0} is surjective.

Theorem 10. Let m ≥ 3 be a natural number. Then σ_{1}(2^{m} + 5) = m − 2.

Proof. Theorem 8 gives σ_{1}(2^{m} + 5) ≥ m − 2 for all m ≥ 3. Moreover, σ_{1}(2^{m} + 5) ≤ ⌊log_{2}(H)⌋ − 1 = m − 1 for all m ≥ 3. Suppose that there were a solution of (3) yielding σ = m − 1. This solution would have to be of the form 2^{m}hk + 2k + h = 2^{m} + 5, since s ≤ log_{2}(H). But for h = k = 1 we have 2^{m} + 2 + 1 < 2^{m} + 5, whereas for max{h, k} > 1 there is 2^{m} + 5 < 2^{m}hk + 2k + h. Thus, such a solution does not exist.

Remark 11. The sequence (a(n))_{n≥0} with a(n) = σ_{1}(2n + 1) is sequence \underline{A272894} of the OEIS.

2.4 Special values of σ_{2}

Theorem 12. Let m be a natural number and let H be an odd natural number with H < 2^{m}. Then σ_{2}(H) ≤ 2m − 1.

Proof. We already know that σ_{1}(H) ≤ log_{2}(H) < m, so we do not have to consider the solutions of (3) here. Given the Diophantine equation (5), we see that h + k ≡ 0 (mod 2^{s−n}), i.e., there is a natural number d with h + k = d · 2^{s−n}. This implies 2^{n}hk = H − d ≤ 2^{m} − 2 or

hk ≤ \frac{2^{m} − 2}{2^{n}}.  (8)

First, if n = 0 then (8) gives

h + k ≤ hk + 1 ≤ 2^{m} − 1 < 2^{m}.

Consequently, a transformation of the Diophantine equation (5) leads to

2^{s} = \frac{h + k}{H − hk} < 2^{m},

since H − hk is a natural number. So, here we have s < m, i.e., s ≤ m − 1 and hence σ ≤ 2m − 2.

Secondly, for n ≥ 1, again with (8), we get

h + k ≤ hk + 1 ≤ 2^{m−n} + 1 − \frac{1}{2^{n−1}} .

This means that the even natural number h + k always fulfils h + k ≤ 2^{m−n}. In the present case, the Diophantine equation (5) can be changed into

2^{s−n} = \frac{h + k}{H − 2^{n}hk} ≤ 2^{m−n}

with a natural denominator H − 2^{n}hk, giving the estimations s ≤ m and σ ≤ 2m − n. The maximal value of the latter expression obviously is 2m − 1. Therefore, σ_{2}(H) ≤ 2m − 1 for every H < 2^{m}.

Moreover, the arguments H leading to maximal values of σ_{2}(H) can be specified.

Theorem 13. Let m ≥ 2 be a natural number and let H be an odd natural number with H < 2^{m}. Then σ_{2}(H) = 2m − 1 if and only if H = 2^{m} − 1.

Proof.

(1) If H = 2^{m}−1 with m ≥ 2 then the Diophantine equation (5) has the solution (n, s, h, k) = (1, m, 1, 2^{m−1} − 1) and consequently σ_{2}(H) = 2m − 1.

(2) Suppose that σ_{2}(H) = 2m − 1 for a H < 2^{m}. The Diophantine equation h + k = hk + 1 (under the assumption that 1 ≤ h ≤ k) implies h = 1. So, if 3 ≤ h ≤ k, then we have h + k < hk. Note that h + k = hk is impossible for every odd k. Applying (8) we can assert that

h + k < hk ≤ \frac{2^{m} − 2}{2^{n}} < 2^{m−n}

for 3 ≤ h ≤ k and H < 2^{m}. Hence 2^{s−n} < 2^{m−n}. This leads to s ≤ m − 1 and σ ≤ 2m − 2 − n ≤ 2m − 2.

It follows that σ = 2m − 1 requires h = 1, n = 1 and s = m. Then (5) can be rewritten as

2^{m}k + k + 1 = 2^{m−1}H,

or

k + 1 = 2^{m−1}(H − 2k).  (9)

As seen above, we have k + 1 = k + h ≤ 2^{m−n} = 2^{m−1} and hence H − 2k = 1, or

k = \frac{H − 1}{2}.  (10)

Substituting (10) in (9) yields H = 2^{m} − 1.

Remark 14. Combining the Theorems 12 and 13 yields the inequality σ_{2}(H) ≤ 2 log_{2}(H) for every odd natural number H.

Some other subsequences can be given in parametric form.

Theorem 15. Let m ≥ 3 be a natural number and let H be an odd natural number with H < 2^{m}. Then σ_{2}(H) = 2m − 2 if and only if H = 2^{m} − 3.

Proof.

(1) For H = 2^{m} − 3 with m ≥ 3 there is the solution

(n, s, h, k) = (2, m, 1, 2^{m−2} − 1)

to the Diophantine equation (5), i.e., σ = 2m−2. Theorem 13 states that σ_{2}(2^{m}−3) ≠ 2m−1, which is why σ_{2}(2^{m} − 3) = 2m − 2.

(2) Suppose that for a H < 2^{m} we have σ_{2}(H) = 2m − 2. The only pairs (n, s) leading to σ = 2s − n = 2m − 2 are (0, m − 1) or (2, m). Moreover, we know that 3 ≤ h ≤ k implies s < m. Therefore, the second pair requires h = 1 and transforms (5) into 2^{m}k+k+1 = 2^{m−2}H or

k + 1 = 2^{m−2}(H − 4k).  (11)

Because k + 1 ≤ 2^{m−2}, we get H − 4k = 1, i.e., k = \frac{H−1}{4}. Substituting k in (11) yields H = 2^{m} − 3.

Let us now turn our attention to the pair (0, m − 1). Suppose that there is a solution to the Diophantine equation 2^{m−1}hk + h + k = 2^{m−1}H with H < 2^{m}. A simple transformation gives h + k = 2^{m−1}(H − hk), yielding H − hk = 2 since h + k ≤ 2^{m} and H − hk even. So, h = 2^{m} − k and h = \frac{H−2}{k}. Combining these two equalities gives k^{2} − 2^{m}k + H − 2 = 0, or

H = −k^{2} + 2^{m}k + 2.

Note that the inequality −k^{2} + 2^{m}k < 2^{m} − 2 is fulfilled for no 1 ≤ k < 2^{m}. This can be verified, e.g., by basic analytic considerations of the polynomial function f(x) = −x^{2} + 2^{m}x − 2^{m}. Consequently, we obtain H > 2^{m}. This contradiction proves the theorem.

Theorem 16. Let m > 3 be a natural number. Then σ_{2}(2^{m} + 1) = 2m − 2.

Proof. Note that for all m > 3 there is σ_{1}(2^{m} + 1) ≤ ⌊log_{2}(2^{m} + 1)⌋ − 1 = m − 1 ≤ 2m − 2. Consider the equality 2^{m−1}(2^{m} − 1) + 2^{m} = 2^{m−1}(2^{m} + 1) showing that (n, s, h, k) = (0, m − 1, 1, 2^{m} − 1) is a solution of the Diophantine equation (5). Therefore, we have σ_{2}(2^{m} + 1) ≥ 2m − 2 > σ_{1}(2^{m} + 1). According to the Theorems 12, 13 and 15, the only larger value that σ_{2}(2^{m} + 1) could equal to for m ≥ 3 is 2m − 1. The latter value requires (n, s) ∈ {(1, m), (3, m + 1)}. The first of these pairs gives 2^{m}hk + h + k = 2^{m−1}(2^{m} + 1) or

h + k = 2^{m−1}(2^{m} + 1 − 2hk) ≤ 2^{m}.

Since 2^{m} + 1 − 2hk is odd, this implies 2^{m} + 1 − 2hk = 1 which is impossible for odd h and k when m > 3. The second pair yields 2^{m+1}hk + h + k = 2^{m−2}(2^{m} + 1) or

h + k = 2^{m−2}(2^{m} + 1 − 8hk) ≤ 2^{m−2}.

This gives 2^{m} + 1 − 8hk = 1, an equality that also cannot hold for odd h and k when m > 3. Hence, σ_{2}(2^{m} + 1) = 2m − 2 for all m > 3.

Theorem 17. Let m ≥ 3 be a natural number. Then σ_{2}(2^{m} + 3) = 2m − 4.

Proof. Note that for all m ≥ 3 there is σ_{1}(2^{m} + 3) ≤ ⌊log_{2}(2^{m} + 3)⌋ − 1 = m − 1 ≤ 2m − 4. Consider the equality 2^{m−2}(2^{m}−1)+2^{m} = 2^{m−2}(2^{m}+3). Thus (n, s, h, k) = (0, m−2, 1, 2^{m}−1) is a solution of the Diophantine equation (5) for all m ≥ 3 and hence σ_{2}(2^{m} + 3) ≥ 2m − 4 ≥ σ_{1}(2^{m} + 3). Because 2^{m} + 3 < 2^{m+1} − 3 for all m ≥ 3, we know by the Theorems 12, 13 and 15 that σ_{2}(2^{m} + 3) < 2(m + 1) − 2 = 2m. Therefore, other potential values for σ_{2}(2^{m} + 3) are 2m − 3, 2m − 2 or 2m − 1.

To obtain σ = 2m − 3 we need (n, s) ∈ {(1, m − 1), (3, m), (5, m + 1)}.

The first pair gives 2^{m−1}hk + h + k = 2^{m−2}(2^{m} + 3) or

h + k = 2^{m−2}(2^{m} + 3 − 2hk).  (12)

Since h + k ≤ 2^{m}, the odd natural number 2^{m} + 3 − 2hk can take the values 1 or 3.

(a) 2^{m} + 3 − 2hk = 1 is equivalent to h = \frac{2^{m−1}+1}{k}. Substituting h in (12) gives k^{2} − 2^{m−2}k + 2^{m−1} + 1 = 0. The latter quadratic equation has integer solutions k only if Δ = 2^{2m−2} − 4(2^{m−1} + 1) = 4(2^{2m−4} − 2^{m−1} − 1) is a perfect square. It is easy to see that Δ is a perfect square if and only if \frac{Δ}{4} is one as well. But for m ≥ 3 we have \frac{Δ}{4} ≡ 3 (mod 4), which is impossible for a perfect square.

(b) 2^{m} + 3 − 2hk = 3 is equivalent to h = \frac{2^{m−1}}{k} which is impossible for odd h and k.

The pair (3, m) yields 2^{m}hk + h + k = 2^{m−3}(2^{m} + 3) or

h + k = 2^{m−3}(2^{m} + 3 − 8hk).

Here, we have h + k ≤ 2^{m−2} and so, the odd natural number 2^{m} + 3 − 8hk can only take the value 1. This gives h = \frac{2^{m−1}+1}{4k} which is impossible.

With the pair (5, m + 1) we get 2^{m+1}hk + h + k = 2^{m−4}(2^{m} + 3) or

h + k = 2^{m−4}(2^{m} + 3 − 32hk).

Here, we have h + k ≤ 2^{m−4} and hence 2^{m} + 3 − 32hk = 1 or h = \frac{2^{m−1}+1}{16k} which again is impossible. We can conclude that σ_{2}(2^{m} + 3) ≠ 2m − 3.

The case σ = 2m−2 requires (n, s) ∈ {(0, m−1), (2, m), (4, m+1)}, while for σ = 2m−1 there ought to be (n, s) ∈ {(1, m), (3, m + 1)}. In total analogy to the case σ = 2m − 3, one can establish that none of these five pairs leads to a solution of the Diophantine equation (5). The details of these computations are left to the reader. Consequently, σ_{2}(2^{m} + 3) = 2m − 4 for all m ≥ 3.

Remark 18.

(1) We know that σ_{2}(1) = 0. Moreover, the Theorems 17 and 13 state that for every natural number N ≥ 2 there exists an odd number H with σ_{2}(H) = N. A question arising from these observations is, whether the sequence σ_{2} is surjective on ℕ_{0}? The answer is “yes”, since a straightforward computation yields σ_{2}(27) = 1.

(2) The sequence (a(n))_{n≥0} with a(n) = σ_{2}(2n + 1) is sequence \underline{A272895} of the OEIS.

2.5 Some further observations about σ_{3}

The Diophantine equation (6) is equivalent to

h + k = 2^{s}(2^{s−n}H − hk).  (13)

From the observations made at the end of subsection 2.1 we know that h + k ≤ 2^{s} · H. So, there is an odd natural number α ≤ H with 2^{s−n}H −hk = α, i.e., h = \frac{2^{s−n}H−α}{k}. Substituting h in (13) gives

k^{2} − 2^{s}αk + 2^{s−n}H − α = 0.  (14)

The latter quadratic equation in the variable k is solvable in integers if and only if the number τ := 2^{2s−2}α^{2} + α − 2^{s−n}H is a perfect square.

We study two different cases. First, if α ≡ 3 (mod 4) then we have to consider the following subcases. If s − n = 1 then τ has the form 2^{2n}α^{2} + α − 2H. So, for n = 0 we get τ = α^{2} + α − 2H ≡ 2 (mod 4), which cannot be a perfect square. In the case n ≥ 1 this yields τ ≡ 1 (mod 4) and hence a potential perfect square leading to a solution of (14) of the form k = 2^{n}α ± \sqrt{2^{n}α^{2} + α − 2H}. The corresponding value of σ would be σ = 3(n + 1) − n = 2n + 3. Note, that the condition 1 ≤ n ≤ log_{2}(H) has to be fulfilled, which is why only a finite number of solutions of the latter form can exist. If s − n ≥ 2 then τ ≡ 3 (mod 4) and hence τ never is a perfect square.

Secondly, let α ≡ 1 (mod 4). Again consider the case s − n = 1, i.e., τ = 2^{2n}α^{2} + α − 2H. For n = 0 we get τ ≡ 0 (mod 4) and therefore the potential solution k = α ± \sqrt{α^{2} + α − 2H} with a corresponding σ = 3. If n ≥ 1 then τ ≡ 3 (mod 4) cannot be a perfect square. The case s − n ≥ 2 always gives τ ≡ 1 (mod p) and hence potential solutions of the form k = 2^{s−1}α ± \sqrt{2^{2s−2}α^{2} + α − 2^{s−n}H} with corresponding σ = 3s − n.

Note that the latter subcase is the only one that could possibly lead to an infinity of solutions. More precisely, we can have σ_{3}(H) = ∞ only if τ = 2^{2s−2}α^{2} + α − 2^{s−n}H is a perfect square for an infinity of tuples (s, n, α) fulfilling 0 ≤ n < s − 1, n ≤ log_{2}(H) and 1 ≤ α ≤ H with α ≡ 1 (mod 4).

Proposition 19. Let H be an odd natural number. Then

1) σ = 3 ∈ S_{3}(H) \ S_{2}(H) if k = α ± \sqrt{α^{2} + α − 2H} and h = \frac{2^{s−n}H−α}{k} are odd natural numbers for a given α ≡ 1 (mod 4) with α ≤ H.

2) σ = 3s − n ∈ S_{3}(H) \ S_{2}(H) if k = 2^{s−1}α ± \sqrt{2^{2s−2}α^{2} + α − 2^{s−n}H} and h = \frac{2^{s−n}H−α}{k} are odd natural numbers for 0 ≤ n < s − 1, n ≤ log_{2}(H) and 1 ≤ α ≤ H with α ≡ 1 (mod 4).

3) σ = 2n + 3 ∈ S_{3}(H) \ S_{2}(H) if k = 2^{n}α ± \sqrt{2^{n}α^{2} + α − 2H} and h = \frac{2^{s−n}H−α}{k} are odd natural numbers for 1 ≤ n ≤ log_{2}(H) and α ≤ H with α ≡ 3 (mod 4). These three cases give all possible elements of the set S_{3}(H) \ S_{2}(H).

Example 20.

(1) For a given odd natural number t the tuples (s, 0, t^{2}) yield the perfect squares 2^{2s−2}t^{4} + t^{2} − 2^{s}t^{3} = (2^{s−1}t^{2} − t)^{2} for all s ∈ ℕ, leading to k = 2^{s}t^{2} − t and h = t. This means that σ_{3}(t^{3}) = ∞ for every odd natural number t.

(2) It is easy to verify that the expressions 2^{2s−2} + 1 − 2^{s−n} · 3 are never perfect squares for n ∈ {0, 1} and s ≥ n + 2. Thus, we obtain σ_{3}(3) < ∞. A straightforward computation actually yields σ_{3}(3) = σ_{2}(3) = 3.

3 Primality testing and generalized Fermat numbers

In 1877, Pépin [21] showed that for n > 1 the Fermat number F_{n} = 2^{2^{n}}+1 is prime if and only if 5^{\frac{Fn−1}{2}} ≡ −1 (mod F_{n}). The so-called Pépin test has since been a popular method to check Fermat numbers for primality. A structural equivalence of Pépin’s test for Fermat numbers and the Lucas-Lehmer test for Mersenne numbers has been brought to light recently [11].

Some further results were inspired by Pépin’s theorem. First, Proth [22] found the following generalization: Let N = H · 2^{σ} + 1 be an odd number with 2^{σ} > H. Let b be a quadratic nonresidue modulo N. Then N is a prime number if and only if b^{\frac{N−1}{2}} ≡ −1 (mod N). So called Proth primes, i.e., numbers that can be shown being prime using Proth’s theorem, play an important role in finding factors of Fermat numbers.

Another question, arising from an observation by Lucas [16, p. 313], was brought up by Aigner [1] in 1986: Are there other prime numbers suitable to be used as bases in Pépin’s test? Aigner identified the basic property of any suitable prime number p to be that almost all Fermat numbers are quadratic nonresidues modulo p. He found 14 such primes less than 35·10^{6} and, because of their rareness, called them elite prime numbers. In recent years, elite primes have been the subject of a number of research papers [5, 6, 14, 15, 17, 18, 19, 23, 24].

In this context, Reinhart and the author [18, 20] studied some fundamental properties of the behavior of the so called Fermat periods of natural numbers. For a natural number b consider the generalized Fermat numbers F_{b,n} = b^{2^{n}} + 1. Because of the recurrence relation F_{b,n+1} = (F_{b,n} − 1)^{2} + 1 it is obvious that the congruence F_{b,n} (mod N) becomes periodic for every natural number N, i.e., there exist minimal nonnegative integer numbers s and L ≥ 1 such that F_{b,s} ≡ F_{b,s+Lk} (mod N) for all natural numbers k. We call the parameter s =: s_{b}(N) the start index and L =: L_{b}(N) the period length of the b-Fermat period of N. Some applications of generalized Fermat numbers have been studied [4, 7, 9, 12]. For a survey on Fermat numbers we refer the reader to the book of Křížek, Luca, and Somer [13]. Some generalizations of Proth’s theorem dealing with other parametric forms of N = Ka^{n} +b have been discussed by several authors [2, 8, 10]. In this section, we give another generalization of Proth’s primality theorem lowering the requirements that the base b has to fulfil.

Theorem 21. Let H be an odd natural number and let m ≥ 1 be a real number such that σ_{m}(H) < ∞. Let N = H · 2^{σ} + 1 be an odd natural number with σ > σ_{m}(H). Then N is a prime number if and only if there are two natural numbers b and k with gcd(N, b) = 1, k ≥ \frac{σ}{m} and b^{2^{k−1}H} ≡ −1 (mod N).

Remark 22.

(1) Taking into account the inequality σ_{1}(H) ≤ log_{2}(H), Proth’s theorem follows from Theorem 21 when we use m = 1.

(2) In many cases, the condition σ > σ_{m}(H) is actually weaker than that demanded by Proth. E.g., σ_{1}(3) = 0, σ_{2}(165) = 0, σ_{2}(27) = σ_{2}(45) = σ_{2}(267) = 1, σ_{2}(H) = 2 for H ∈ {11, 51, 85, 195, 201, 231, …}, σ_{2}(H) = 3 for H ∈ {21, 37, 55, 87, 93, 123, 153, 181, 243, 245, …}, etc.

(3) Proth’s theorem needs the base b to be a quadratic nonresidue modulo N. In our result this requirement falls aside for m > 1. E.g., because of σ_{2}(1) = 0, the first four Fermat Numbers F_{n} := 2^{2^{n}} + 1 (n ∈ {0, 1, 2, 3}) can be proved being prime numbers using Theorem 21 with b = 2, k := n + 1 ≥ 2^{n−1} and 2^{2^{k−1}} ≡ −1 (mod F_{n}). Unfortunately, for all n ≥ 4 the base b = 2 is not suitable anymore and b = 3, i.e., Pépin’s Test, has to be applied for larger Fermat Numbers.

The proof of Theorem 21 is based on elementary properties of b-Fermat periods and thus points out another application of generalized Fermat numbers.

3.1 Fermat periods

Using the parametric form N = H · 2^{σ} + 1 allows a characterization of the start index and the length of the Fermat periods of N [20].

Theorem 23. Let N = H · 2^{σ} + 1 and b be natural numbers with gcd(N, b) = 1. We let t · 2^{s} (t odd) denote the multiplicative order of b modulo N. Then we have s_{b}(N) = s and L_{b}(N) = ord_{t}(2). If N is a prime number, then s ≤ σ and t divides H.

A result linking the period length of a composite N to the period lengths of coprime factors is also known [20].

Theorem 24. Let A and B be two coprime natural numbers and b ∈ ℕ. Then L_{b}(AB) = lcm(L_{b}(A), L_{b}(B)).

A similar result can be shown for the start indices of composite numbers.

Proposition 25. Let A, B and b be natural numbers with gcd(A, B) = gcd(AB, b) = 1. Then s_{b}(AB) = max{s_{b}(A), s_{b}(B)}.

Proof. It is well-known that for natural numbers A, B and b with gcd(A, B) = gcd(AB, b) = 1 we have ord_{AB}(b) = lcm(ord_{A}(b), ord_{B}(b)). With Theorem 23 this implies s_{b}(AB) = max{s_{b}(A), s_{b}(B)}.

The following proposition settles the problem of the start indices of non-squarefree numbers.

Proposition 26. Let p be an odd prime number. Let m and b be natural numbers with gcd(p, b) = 1. Then s_{b}(p^{m}) = s_{b}(p).

Proof. We let α denote the multiplicative order of b modulo p, i.e., b^{α} = pk + 1 for a suitable k ∈ ℤ. This leads to

b^{αp^{m−1}} = (pk + 1)^{p^{m−1}}

= ∑_{ν=0}^{p^{m−1}} \binom{p^{m−1}}{ν}p^{ν}k^{ν}

≡ 1 (mod p^{m}).

It follows that the multiplicative order of b modulo p^{m} is a divisor of αp^{m−1}. Now suppose that there is a β < α fulfilling b^{βp^{m−1}} ≡ 1 (mod p^{m}). Then Fermat’s little theorem implies b^{β} ≡ 1 (mod p), contradicting the fact that α is the multiplicative order of b modulo p.

So, the multiplicative order of b modulo p^{m} has to be of the form αp^{d} with d ∈ {0, 1, …, m− 1}. By writing p = h · 2^{r} + 1, Theorem 23 states that α = 2^{s}t with s ≤ r, t a divisor of h and s_{b}(p) = s. Again with Theorem 23, this time applied to p^{m}, we obtain the start index s_{b}(p^{m}) = s since ord_{p^{m}}(b) = 2^{s}tp^{d} and tp^{d} is odd.

Corollary 27. Let N = ∏_{ν=1}^{n} p_{ν}^{α_{ν}} be the canonical prime factorization of an odd natural number N. Then s_{b}(N) = max_{1≤ν≤n}{s_{b}(p_{ν})} for every base b ∈ ℕ with gcd(N, b) = 1.

Proof. By induction over the number of prime factors, Proposition 25 can be generalized to s_{b}(N) = max_{1≤k≤n}{s_{b}(p_{k}^{α_{k}})}. With Proposition 26 we then get s_{b}(N) = max_{1≤k≤n}{s_{b}(p_{k})}.

Remark 28. All the results formulated so far for Fermat numbers remain correct if we consider power sequences instead. So, for practical use, it does not matter whether we investigate the congruential behavior of the numbers F_{b,n} or that of the numbers b^{2^{n}}.

3.2 A primality theorem using Fermat periods

Theorem 29. Let H be an odd natural number and let m ≥ 1 be a real number such that σ_{m}(H) < ∞. Let N = H · 2^{σ} + 1 be an odd natural number with σ > σ_{m}(H). Then N is a prime number if and only if there is a natural number b with gcd(N, b) = 1 and s_{b}(N) ≥ \frac{σ}{m}.

Proof.

(1) Suppose N = H·2^{σ}+1 to be a prime number. Then there exists a primitive root b modulo N, i.e., gcd(N, b) = 1 and ord_{N}(b) = 2^{σ} · H. With Theorem 23, this implies s_{b}(N) = σ ≥ \frac{σ}{m}.

(2) Let b be a natural number with gcd(N, b) = 1 and s_{b}(N) ≥ \frac{σ}{m}. Suppose that N = H · 2^{σ} + 1 = AB is a composite number with the two factors A = h · 2^{r} + 1 and B = k · 2^{s} + 1. Note that by definition there is 1 < A, B. Therefore, the numbers A and B represent every possible combination of two nontrivial divisors of N that multiply to N.

Since σ > σ_{m}(H), we know that r = s < \frac{σ}{m}. It follows that every prime factor p = q·2^{w}+1 of N must fulfil w < \frac{σ}{m}. Corollary 27 then implies s_{b}(N) < \frac{σ}{m} for every base b with gcd(N, b) = 1. This contradiction proves the theorem.

3.3 Proof of Theorem 21

(1) Let N be a prime number. Then there is a primitive root b modulo N fulfilling gcd(N, b) = 1 and, by Euler’s criterion, b^{2^{σ−1}H} ≡ −1 (mod N).

(2) Let b and k be natural numbers with gcd(N, b) = 1, k ≥ \frac{σ}{m} and

b^{2^{k−1}H} ≡ −1 (mod N).

Therefore, 2^{k}H is a multiple of the multiplicative order of b modulo N, while 2^{k−1}H is not. Hence, there must be a divisor d of H such that ord_{N}(b) = 2^{k}d. Theorem 23 now gives s_{b}(N) = k ≥ \frac{σ}{m}. Since σ > σ_{m}(H), we can apply Theorem 29 and we immediately obtain the primality of N. □

4 Discussion and open problems

(1) Are there more elegant criteria than those of Proposition 19 to decide whether σ_{3}(H) < ∞? Are the multipliers H = t^{3} the only values giving σ_{3}(H) = ∞?

(2) Are there conditions of existence for values m > 3 allowing to evaluate σ_{m}(H)?

(3) Another open problem is the question how to efficiently find a suitable base b in order to use Theorem 21 for primality testing. The following heuristic argument suggests that it might suffice to try b = 2 for m ≥ 2, H ≥ 3 with σ_{m}(H) < ∞ and large σ. We know that for every prime number p = H · 2^{σ} + 1 that is not a divisor of 2^{H} − 1, there exists a generalized Fermat number of the form (2^{H})^{2^{k−1}} + 1 being a multiple of p. In such a case, the difference σ − k := t indicates that 2^{H} is a 2^{t}-power residue but not a 2^{t+1}-power residue modulo p [3]. Now suppose that k < \frac{σ}{m}. This would imply t > \frac{(m−1)σ}{m} and thus 2^{H} would have to be at least a 2^{⌊ \frac{(m−1)σ}{m} ⌋+1}-power residue modulo p. The probability that this is true actually equals 2^{−⌊ \frac{(m−1)σ}{m} ⌋−1}. Therefore, for large values of σ it is quite improbable that our test fails with b = 2.

Evidently, if N = H · 2^{σ} + 1 (not being a divisor of 2^{H} − 1) does not divide a generalized Fermat number of the form (2^{H})^{2^{k}} + 1 for 1 ≤ k ≤ σ − 1, then N is composite. Therefore, under the assumption that b = 2 is suitable, an algorithm based on Theorem 21 leads to a primality or compositeness statement for a given N = H · 2^{σ} + 1 with large σ after at most σ − 1 squaring and congruence operations and hence runs in O(log(N)).

(4) Perhaps it is useful to consider restrictions of the sequences σ_{m} for m ≥ 3 in order to get finite subsequences that allow us to use Theorem 21 for selected exponents σ even though σ_{m}(H) = ∞.

References

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

[2] P. Berrizbeitia, T. G. Berry, and J. Tena-Ayuso, A generalization of Proth’s theorem, Acta Arith. 110 (2003), 107–115.

[3] A. Björn and H. Riesel, Factors of generalized Fermat numbers, Math. Comp. 67 (1998), 441–446.

[4] C. K. Caldwell and T. Komatsu, Powers of Sierpinski numbers base B, Integers 10 (2010), A36, 423–436.

[5] A. Chaumont and T. Müller, All elite primes up to 250 billion, J. Integer Sequences 9 (2006), Article 06.3.8.

[6] A. Chaumont, J. Leicht, T. Müller, and A. Reinhart, The continuing search for large elite primes, Int. J. Number Theory 5 (2009), 209–218.

[7] J. B. Cosgrave and K. Dilcher, A role for generalized Fermat numbers, Math. Comp., to appear.

[8] J. M. Grau, A. M. Oller-Marcén, and S. Sadornil, A primality test for Kp^{n} +1 numbers, Math. Comp. 84 (2015), 505–512.

[9] T. A. Gulliver, Self-reciprocal polynomials and generalized Fermat numbers, IEEE Trans. Inform. Theory 38 (1992), 1149–1154.

[10] A. Guthmann, A generalization of Proth’s theorem. Preprint No. 216, Universität Kaiserslautern, Fachbereich Mathematik, 1992.

[11] J. H. Jaroma, Equivalence of Pepin’s and the Lucas-Lehmer tests, Eur. J. Pure Appl. Math. 2 (2009), 352–360.

[12] P. Kurlberg and C. Pomerance, On the periods of the linear congruential and power generators, Acta Arith. 119 (2005), 149–169.

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

[14] 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.

[15] M. Křížek, F. Luca, I. E. Shparlinski, and L. Somer, On the complexity of testing elite primes, J. Integer Sequences 14 (2011), Article 11.1.2.

[16] E. Lucas, Théorie des fonctions numériques simplement périodiques, Amer. J. Math. 1 (1878), 184–240, 289–321.

[17] T. Müller, Searching for large elite primes, Exp. Math. 15 (2005), 183–186.

[18] T. Müller and A. Reinhart, On generalized elite primes, J. Integer Sequences 11 (2008), Article 08.3.1.

[19] T. Müller, A generalization of a theorem by Křížek, Luca and Somer on elite primes, Analysis (Munich) 28 (2008), 375–382.

[20] T. Müller, On the Fermat periods of natural numbers, J. Integer Sequences 13 (2010), Article 10.9.5.

[21] T. Pépin, Sur la formule 2^{2^{n}} + 1, C. R. Acad. Sci. Paris 85 (1877), 329–331.

[22] F. Proth, Théorèmes sur les nombres premiers, C. R. Acad. Sci. Paris 87 (1878), 926.

[23] A. Witno, On elite primes of period four, Int. J. Number Theory 6 (2010), 667–671.

[24] A. Witno, Primes modulo which almost all Fermat numbers are primitive roots, Note Mat. 30 (2010), 133–140.

2010 Mathematics Subject Classification: Primary 11A41; Secondary 11A51, 11B83, 11D61, 11D72, 11Y11. Keywords: exponent, non-trivial divisor, composite number, primality test, prime number, Diophantine equation, generalized Fermat number, Fermat period.

(Concerned with sequences \underline{A000125}, \underline{A102742}, \underline{A128852}, \underline{A272894}, and \underline{A272895}.)

Received May 12 2016; revised version received December 1 2016. Published in Journal of Integer Sequences, December 27 2016.

Return to Journal of Integer Sequences home page.