On Pairwise Intersections of the Fibonacci, Sierpiński, and Riesel Sequences

Dan Ismailescu Department of Mathematics Hofstra University 103 Hofstra University Hempstead, NY 11549 USA

             dan.p.ismailescu@hofstra.edu

Peter Seho Park Korea International School 373-6 Baekhyeon-dong, Budang-gu Seongnam-si, Gyonggi-do Korea

                  peterseho@yahoo.ca

Abstract

A Sierpiński number is an odd integer k with the property that k·2^{n}+1 is composite for all positive integer values of n. A Riesel number is defined similarly; the only difference is that k · 2^{n} − 1 is composite for all positive integer values of n.

In this paper we find Sierpiński and Riesel numbers among the terms of the wellknown Fibonacci sequence. These numbers are smaller than all previously constructed examples. We also find a 23-digit number which is simultaneously a Sierpiński and a Riesel number. This improves on the current record established by Filaseta, Finch and Kozek in 2008. Finally, we prove that there are infinitely many values of n such that the Fibonacci numbers F_{n} and F_{n+1} are both Sierpiński numbers.

1 Constructing Sierpiński and Riesel numbers

In 1960, Sierpiński [11] proved that there are infinitely many odd numbers k such that k·2^{n}+1 is composite for all positive integers n. A few years earlier, Riesel [9] showed that there are infinitely many odd integers k such that k · 2^{n} − 1 is composite for all positive integers n.

The standard way to construct Sierpiński or Riesel numbers is due to Erdős [3]: one seeks a finite collection of triples {(a_{i}, b_{i}, p_{i})}_{i=1}^{i=t} that satisfy the following properties:

(i) The set {(a_{i}, b_{i})}_{i=1}^{i=t} forms a covering system, that is, for every 1 ≤ i ≤ t, a_{i} and b_{i} are integers, b_{i} > 1 and, for all integers n there exists i ∈ {1, …, t} such that n ≡ a_{i} (mod b_{i}).

(ii) The numbers p_{1}, …, p_{t} are distinct primes that satisfy p_{i} | 2^{b_{i}} −1 for all i ∈ {1, …, t}.

To obtain Sierpiński numbers, one imposes the system of congruences k·2^{a_{i}} ≡ mod −1p_{i} for i ∈ {1, …, t}. Since all primes p_{i} are odd, each of the above congruences has a solution for k in the form of an arithmetic progression modulo p_{i}. Then, as p_{1}, …, p_{t} are distinct primes, by the Chinese remainder theorem all odd positive k that satisfy the system of congruences form an arithmetic sequence modulo 2p_{1} ⋯ p_{t} (the fact that k must be odd property translates into an additional congruence k ≡ 1 (mod 2)). All such k have the property that k · 2^{n} + 1 is always divisible by at least one p_{i} for i ∈ {1, …, t}. Thus, if k > max {p_{i} | i = 1, …, t}, then k · 2^{n} + 1 is composite for all n, and therefore, k is a Sierpiński number.

In 1962 Selfridge showed that k = 78557 is a Sierpiński number by using the triples {(0, 2, 3), (1, 3, 7), (1, 4, 5), (11, 12, 13), (15, 36, 19), (27, 36, 37), (3, 36, 73)}. It is widely believed this is the smallest Sierpiński number; there are six smaller candidates which have not been eliminated as potential Sierpiński numbers, the smallest of which is 10223. Seventeen or Bust [6] is a distributed computing project which is testing these remaining numbers.

Similarly, to construct a Riesel number, we impose the system of congruences k · 2^{a_{i}} ≡ 1 (mod p_{i}) for all i ∈ {1, …, t}. Additionally, consider the congruence k ≡ 1 (mod 2) to ensure k is odd. Then, as above, by the Chinese remainder theorem, all odd positive k that satisfy the system of congruences form an arithmetic progression with common difference 2p_{1} ⋯ p_{t}. All such k have the property that k ·2^{n} −1 is always divisible by at least one p_{i} for i ∈ {1, …, t}. Thus, if k > max {p_{i} | i = 1, …, t}, then k · 2^{n} − 1 is composite for all n, and therefore, k has the desired property. Riesel [9] proved that k = 509203 is a Riesel number by using the triples {(0, 2, 3), (2, 3, 7), (1, 4, 5), (7, 8, 17), (7, 12, 13), (3, 24, 241)}. As in the Sierpiński scenario, it is conjectured that 509203 is the smallest Riesel number. There are fifty five smaller numbers which are still being tested as possible candidates — for more information see [7].

2 Sierpiński and Riesel numbers in the Fibonacci sequence

Let F_{n} be the Fibonacci sequence defined by the recurrence relation F_{n} = F_{n−1} + F_{n−2} for n ≥ 2, with F_{0} = 0 and F_{1} = 1. The Lucas sequence is defined analogously: L_{0} = 2, L_{1} = 1 and L_{n} = L_{n−1} + L_{n−2} for n ≥ 2.

Luca and Mejía-Huguet proved in [8] that there are infinitely many Fibonacci numbers which are Sierpiński numbers and infinitely many Fibonacci numbers which are Riesel numbers. Baczkowski, Fasoranti and Finch [1] proved similar results for the Lucas sequence. We use the same technique to improve the results for the Fibonacci numbers.

We construct {(a_{i}, b_{i}, p_{i})}_{i=1}^{i=t} that satisfies conditions (i) and (ii) as described in the previous section. Let k be a Sierpiński or Riesel number in the arithmetic sequence constructed from the above system. Then, k ≡ ϵ2^{−a_{i}} (mod p_{i}) for all i = 1, …, t, where ϵ = −1 for the Sierpiński case, and ϵ = 1 for the Riesel case. For a positive integer m, let h(m) be the m-th Pisano period, the period with which the Fibonacci sequence repeats modulo m. The existence of h(m) is easy to establish, see, e. g., [12]. For every integer x, let

A(x, m) = {0 ≤ y ≤ h(m) − 1 | F_{y} ≡ x (mod m)} + h(m)ℤ.  (1)

In other words, A(x, m) denotes the set of all y modulo h(m) such that F_{y} ≡ x (mod m). For k to be a Fibonacci number, the congruence k ≡ F_{y_{i}} (mod p_{i}) must have a solution y_{i} for each i = 1, …, t. Here, the set of possible solutions y_{i} is A(ϵ2^{−a_{i}}, p_{i}), where ϵ = −1 for the Sierpiński case, and ϵ = 1 for the Riesel case. So, in order for k to be a Fibonacci number, it is necessary and sufficient that

⋂_{i=1}^{t} A(ϵ2^{−a_{i}}, p_{i}) ≠ ∅.

Finally, since Sierpiński and Riesel numbers are odd, it is necessary that if k = F_{n} (for k that is either a Sierpiński or Riesel number), then n cannot be divisible by 3.

Luca and Mejía-Huguet [8] proved the following:

Theorem 1. For every n ≡ 1807873 (mod 3543120), F_{n} is a Riesel number.

We managed to find two arithmetic sequences with the same property but smaller first terms. The first such sequence has a smaller common difference as well.

Theorem 2.

(a) For every n ≡ 820438 (mod 1517040), F_{n} is a Riesel number.

(b) For every n ≡ 385297 (mod 3543120), F_{n} is a Riesel number.

Proof. (a) Let t = 7 and

{(a_{i}, b_{i}, p_{i})}_{i=1}^{i=7} = {(1, 2, 3), (2, 4, 5), (4, 8, 17), (8, 16, 257), (0, 48, 7), (32, 48, 13), (16, 48, 97)}.

It is easy to check that conditions (i) and (ii) are satisfied. For these choices of the primes p_{i} we have (h(p_{1}), …, h(p_{7})) = (8, 20, 36, 516, 16, 28, 196). It follows that

A(2^{−a_{1}}, p_{1}) = A(2, 3) = {3, 5, 6} (mod 8)
A(2^{−a_{2}}, p_{2}) = A(4, 5) = {9, 11, 12, 18} (mod 20)
A(2^{−a_{3}}, p_{3}) = A(16, 17) = {17, 19, 20, 34} (mod 36)
A(2^{−a_{4}}, p_{4}) = A(256, 257) = {257, 259, 260, 514} (mod 516)
A(2^{−a_{5}}, p_{5}) = A(1, 7) = {1, 2, 6, 15} (mod 16)
A(2^{−a_{6}}, p_{6}) = A(3, 13) = {4, 10} (mod 28)
A(2^{−a_{7}}, p_{7}) = A(35, 97) = {116, 178} (mod 196)

It can be checked that if n ≡ 820438 (mod 1517040), then n belongs to all A(2^{−a_{i}}, p_{i}) for i = 1, …, 7. The numbers in boldface in the above sets represent the remainders of n modulo h(p_{i}). Furthermore, since 820438 ≡ 1 (mod 3) and 1517040 ≡ 0 (mod 3), no n in the above arithmetic sequence is divisible by 3. Thus, for all such n, F_{n} is a Riesel number.

(b) Let t = 7 and

{(a_{i}, b_{i}, p_{i})}_{i=1}^{i=7} = {(0, 2, 3), (0, 3, 7), (3, 4, 5), (5, 12, 13), (13, 36, 19), (1, 36, 37), (25, 36, 73)}.

As in part (a), it is easy to verify that conditions (i) and (ii) are satisfied. For these choices of the primes p_{i} we have (h(p_{1}), …, h(p_{7})) = (8, 16, 20, 28, 18, 76, 148). Straightforward computations show that

A(2^{−a_{1}}, p_{1}) = A(1, 3) = {1, 2, 7} (mod 8)
A(2^{−a_{2}}, p_{2}) = A(1, 7) = {1, 2, 6, 15} (mod 16)
A(2^{−a_{3}}, p_{3}) = A(2, 5) = {3, 14, 16, 17} (mod 20)
A(2^{−a_{4}}, p_{4}) = A(11, 13) = {11, 17} (mod 28)
A(2^{−a_{5}}, p_{5}) = A(13, 19) = {7, 11} (mod 18)
A(2^{−a_{6}}, p_{6}) = A(19, 37) = {23, 48, 53, 66} (mod 76)
A(2^{−a_{7}}, p_{7}) = A(4, 73) = {53, 95} (mod 148)

It is easy to check that if n ≡ 385297 (mod 3543120), then n belongs to all A(2^{−a_{i}}, p_{i}) for i = 1, …, 7. The numbers in boldface in the above sets represent the remainders of n modulo h(p_{i}). Furthermore, since 385297 ≡ 1 (mod 3) and 3543120 ≡ 0 (mod 3), no n in the above arithmetic sequence is divisible by 3. Thus, for all such n, F_{n} is a Riesel number.

In the same paper, Luca and Mejía-Huguet proved the following:

Theorem 3. For every n ≡ 20808199653121 (mod 206353240410240), F_{n} is a Sierpiński number.

Notice that the first term of the above arithmetic sequence is a 14-digit number while the common difference is a 15-digit number. We manage to improve this result by finding an arithmetic sequence with the same property, but with only a 6-digit initial term and a 7-digit common difference.

Theorem 4. For every n ≡ 696602 (mod 1517040), F_{n} is a Sierpiński number.

Proof. Let t = 7 and

{(a_{i}, b_{i}, p_{i})}_{i=1}^{i=7} = {(1, 2, 3), (0, 3, 7), (2, 4, 5), (4, 8, 17,), (8, 12, 13), (16, 48, 97), (40, 48, 257)}.

It is easy to verify that conditions (i) and (ii) are satisfied. For this selection of the primes p_{i} it is then straightforward to find the corresponding Pisano periods: (h(p_{1}), …, h(p_{7})) = (8, 16, 20, 36, 28, 196, 516). It follows that

A(−2^{−a_{1}}, p_{1}) = A(1, 3) = {1, 2, 7} (mod 8)
A(−2^{−a_{2}}, p_{2}) = A(6, 7) = {7, 9, 10, 14} (mod 16)
A(−2^{−a_{3}}, p_{3}) = A(1, 5) = {1, 2, 8, 19} (mod 20)
A(−2^{−a_{4}}, p_{4}) = A(1, 17) = {1, 2, 16, 35} (mod 36)
A(−2^{−a_{5}}, p_{5}) = A(10, 13) = {18, 24} (mod 28)
A(−2^{−a_{6}}, p_{6}) = A(62, 97) = {18, 80} (mod 196)
A(−2^{−a_{7}}, p_{7}) = A(1, 257) = {1, 2, 256, 515} (mod 516)

If n ≡ 696602 (mod 1517040), then n belongs to all A(−2^{−a_{i}}, p_{i}) for i = 1, …, 7. As before, the boldface numbers in the above sets represent the remainders of n modulo h(p_{i}). Furthermore, since 696602 ≡ 2 (mod 3) and 1517040 ≡ 0 (mod 3), no n in the above arithmetic progression is divisible by 3. Thus, for all such n, F_{n} is a Sierpiński number.

3 Consecutive Fibonacci-Sierpiński numbers

Despite their relative scarcity, we were able to find infinitely many values of n such that both F_{n} and F_{n+1} are Fibonacci-Sierpiński numbers.

Theorem 5. For every n ≡ 1510614062400961 (mod 3021228124801920), both F_{n} and F_{n+1} are Fibonacci-Sierpiński numbers.

Proof. Take t = 7 and

{(a_{i}, b_{i}, p_{i})}_{i=1}^{i=7} = {(1, 2, 3), (2, 4, 5), (4, 8, 17), (8, 16, 257), (16, 32, 65537),
(0, 64, 641), (32, 64, 6700417)}.

We see that conditions (i) and (ii) are fulfilled. The Pisano periods sequence in this case is (h(p_{1}), …, h(p_{7})) = (8, 20, 36, 516, 14564, 640, 13400836). Then,

A(−2^{−a_{1}}, p_{1}) = A(1, 3) = {1, 2, 7} (mod 8)
A(−2^{−a_{2}}, p_{2}) = A(1, 5) = {1, 2, 8, 19} (mod 20)
A(−2^{−a_{3}}, p_{3}) = A(1, 17) = {1, 2, 16, 35} (mod 36)
A(−2^{−a_{4}}, p_{4}) = A(1, 257) = {1, 2, 256, 515} (mod 516)
A(−2^{−a_{5}}, p_{5}) = A(1, 65537) = {1, 2, 7280, 14563} (mod 14564)
A(−2^{−a_{6}}, p_{6}) = A(640, 641) = {319, 321, 322, 638} (mod 640)
A(−2^{−a_{7}}, p_{7}) = A(1, 6700417) = {1, 2, 6700416, 13400835} (mod 13400836)

One sees that if n ≡ 1510614062400961 (mod 3021228124801920) then both n and n + 1 belongs to all sets A(−2^{−a_{i}}, p_{i}) for i = 1, …, 7. The boldface numbers in the sets above are the remainders of n and n + 1 modulo h(p_{i}). Checking that 1510614062400961 ≡ 1 (mod 3), 1510614062400962 ≡ 2 (mod 3), and 3021228124801920 ≡ 0 (mod 3), it follows that that no number in either of the two arithmetic sequences above is divisible by 3. Thus, for all such n, both F_{n} and F_{n+1} are Sierpiński numbers, thus proving the assertion in the theorem.

It would be interesting to decide if there exist consecutive Fibonacci numbers both of which are Riesel numbers. We were unsuccessful in constructing such an example.

4 Riesel-Sierpiński numbers

Cohen and Selfridge [2] were the first to prove that there exist infinitely many integers that are simultaneously Sierpiński numbers and Riesel numbers. Their discovery came in connection to the question whether there exist integers that cannot be written as the sum or difference of two prime powers. Apparently unaware of this result, Brier, Gallot and Vantieghem constructed other Riesel-Siepiński numbers, but none smaller than Cohen and Selfridge’s record, which is 26-digits long. For an interesting account of their efforts the reader is referred to [10, 5].

It was not until 2008 when Filaseta, Finch and Kozek [4] found a Riesel-Sierpiński number with only 24 digits: 143665583045350793098657. We were able to slightly refine their approach and construct a Riesel-Sierpiński number with only 23 digits. We present the details below.

To find a Riesel-Sierpiński number, one constructs a set of triples {(a_{i}, b_{i}, p_{i})}_{i=1}^{i=t} to obtain an arithmetic sequence of Sierpiński numbers and a set of triples {(a′_{i}, b′_{i}, p′_{i})}_{i=1}^{i=t′} which generates an arithmetic sequence of Riesel numbers, with both sets of triples satisfying (i), (ii). If additionally we impose the condition that

{k | 2^{a_{i}}k ≡ −1 (mod p_{i}) ∀i ∈ {1, …, t}} ∩ {k′ | 2^{a′_{i}}k′ ≡ 1 (mod p′_{i}) ∀i ∈ {1, …, t′}} ≠ ∅,

then the Sierpiński numbers k and the Riesel numbers k′ are each in an arithmetic sequence modulo p_{1} ⋯ p_{t} and modulo p′_{1} ⋯ p′_{t′}, respectively. Taking into account the additional congruences k ≡ 1 (mod 2) and k′ ≡ 1 (mod 2), the Chinese remainder theorem guarantees that {p_{1}, …, p_{t}} ∩ {p′_{1}, …, p′_{t′}} = ∅ is sufficient to prove that there are infinitely many integers belonging to both arithmetic sequences.

However, this condition would require that p = 3 and the corresponding b = 2 can only be used once: either for the Sierpiński part or for the Riesel part.

Fortunately, p = 3 and b = 2 can be used for both Sierpiński and Riesel cases. As shown by Cohen and Selfridge in [2], if {p_{1}, …, p_{t}} ∩ {p′_{1}, …, p′_{t′}} = {3}, and (a_{i}, b_{i}, p_{i})_{i=1}^{i=t} and (a′_{i}, b′_{i}, p′_{i})_{i=1}^{i=t′} have distinct a values (0 or 1) corresponding to b = 2 and p = 3, then there exist integers belonging to both arithmetic sequences.

Theorem 6. Every n ≡ 10439679896374780276373 (mod 66483084961588510124010691590) is a Sierpiński-Riesel number.

Proof. Let t = 7 and

{(a_{i}, b_{i}, p_{i})}_{i=1}^{i=7} = {(0, 2, 3), (3, 4, 5), (5, 8, 17), (9, 16, 257), (9, 48, 13), (17, 48, 97), (1, 48, 241)}.

Let us notice that in this step we use the same set of primes as Filaseta, Finch and Kozek. It is straightforward to verify that the triples (a_{i}, b_{i}, p_{i})_{i=1}^{i=t} satisfy conditions (i) and (ii). With these choices the congruences k · 2^{a_{i}} ≡ −1 (mod p_{i}) imply that k ≡ 2 (mod 3), k ≡ 3 (mod 5), k ≡ 9 (mod 17), k ≡ 129 (mod 257), k ≡ 5 (mod 13), k ≡ 31 (mod 97) and k ≡ 120 (mod 241). Using the Chinese remainder theorem, we obtain that

k ≡ 18354878963 (mod 19916152035).  (2)

Every odd number satisfying (2) is a Sierpiński number. Let us now work the Riesel part. Let t = 12 and

{(a′_{i}, b′_{i}, p′_{i})}_{i=1}^{i=12} = {(1, 2, 3), (0, 3, 7), (8, 9, 73), (2, 18, 19), (32, 36, 37), (14, 36, 109), (4, 5, 31),
(6, 10, 11), (10, 15, 151), (28, 30, 331), (12, 20, 41), (22, 60, 61)}.

Filaseta, Finch and Kozek considered an almost identical set of primes: the only difference is that they used the prime 1321 instead of 41. It is not hard to check that the triples (a′_{i}, b′_{i}, p′_{i})_{i=1}^{i=t′} satisfy conditions (i) and (ii). With these choices, the congruences k · 2^{a′_{i}} ≡ 1 (mod p′_{i}) imply that k ≡ 2 (mod 3), k ≡ 1 (mod 7), k ≡ 2 (mod 73), k ≡ 5 (mod 19), k ≡ 16 (mod 37), k ≡ 93 (mod 109), k ≡ 2 (mod 31), k ≡ 5 (mod 11), k ≡ 32 (mod 151), k ≡ 4 (mod 331), k ≡ 10 (mod 41), k ≡ 49 (mod 61).

Using the Chinese remainder theorem, we obtain that

k ≡ 4625814406597377449 (mod 5007223647777439011).  (3)

Every odd number satisfying (3) is a Riesel number. Now let us combine (2) and (3) using the Chinese remainder theorem for one last time. We get that

k ≡ 10439679896374780276373 (mod 33241542480794255062005345795)

Taking into account that k must be odd, the statement in the theorem follows.

5 Conclusions

In this paper we find subsequences of the Fibonacci sequence whose terms have either the Sierpiński property or the Riesel property. We also construct a new arithmetic sequence, all of whose terms are simultaneously Sierpiński and Riesel numbers. While the existence of such numbers was known before, our main contribution is that our results are smaller than any of the previous ones.

The interesting question is whether there is a number which has all three properties simultaneously. Obtaining this would require the construction of two sets of triples (one for the Sierpiński case and one for the Riesel case) sharing no b value other than 2, and satisfying (i), (ii), and the condition that each set of triples generates a Fibonacci-Sierpiński or Fibonacci-Riesel arithmetic progression. If the two arithmetic progressions have nonempty intersection, then that intersection would be an arithmetic sequence of Fibonacci indices n for which F_{n} would be both Sierpiński and Riesel numbers. Unfortunately, so far we were unable to find such an example.

6 Acknowledgements

The authors would like to thank the anonymous referee whose thorough and competent suggestions greatly improved the exposition and the content of this paper.

References

[1] D. Baczkowski, O. Fasoranti, and C. E. Finch, Lucas-Sierpiński and Lucas-Riesel numbers, Fibonacci Quart. 49 (2011), 334–339.

[2] F. Cohen and J. L. Selfridge, Not every number is the sum or difference of two prime powers. Math. Comp. 29 (1975), 79–81.

[3] P. Erdős, On integers of the form 2^{k} + p and some related problems. Summa Brasil. Math. 2 (1950), 113–123.

[4] M. Filaseta, C. Finch, and M. Kozek, On powers associated with Sierpiński Numbers, Riesel numbers and Polignac’s conjecture, J. Number Theory 128 (2008), 1916–1940.

[5] Y. Gallot, A search for some small Brier numbers, 2000, manuscript,

    http://yves.gallot.pagesperso-orange.fr/papers/smallbrier.pdf.

[6] L. Helm and D. Norris, Seventeen or bust: a distributed atack on the Sierpiński problem,

    http://www.seventeenorbust.com/.

[7] W. Keller, The Riesel problem: definition and status,

    http://www.prothsearch.net/rieselprob.html.

[8] F. Luca and V. J. Mejía-Huguet, Fibonacci-Riesel and Fibonacci-Sierpiński numbers, Fibonacci Quart. 46/47 (2008/2009), 216–219.

[9] H. Riesel, Nǎgra stora primtal, Elementa 39 (1956), 258–260.

[10] C. Rivera, The prime puzzles & problem connection,

    http://www.primepuzzles.net/problems/prob_029.htm.

[11] W. Sierpiński, Sur un problème concernant les nombres k·2^{n}+1, Elem. Math. 15 (1960), 73–74.

[12] D. D. Wall, Fibonacci series modulo m, Amer. Math. Monthly, 67 (1960), 525–532.

2010 Mathematics Subject Classification: Primary 11B25; Secondary 11B50. Keywords: Fibonacci number, Riesel number, Sierpiński number, covering congruence.

(Concerned with sequences \underline{A000045}, \underline{A076336}, and \underline{A076337}.)

Received June 1 2013; revised version received December 4 2013. Published in Journal of Integer Sequences, December 5 2013.

Return to Journal of Integer Sequences home page.