Does every Sierpinski number have a finite congruence covering?

The k$k$ below 78557$78557$ are expected to be non-Sierpiński.

We can think of the set of all k$k$ as divided into three sets. 1: The provable or known Sierpiński numbers. 2: The non-Sierpiński numbers where we have actually found a prime of form k2n+1$k{2}^n+1$. And 3: The rest.

All the numbers in class 3 are conjectured to be non-Sierpiński, i.e. it is expected that one will eventually find a prime in {k2n+1∣n∈N}$\{k{2}^n+1\mid n\in \mathbb{N}\}$. That conjecture could be wrong, of course.

You:

Hence the question: Could one expect a congruence covering of the set of integers represented by a Sierpinski number to be finite?

For each class-3 or class-2 k$k$, it is expected that an infinitude of primes k2n+1$k{2}^n+1$ exists, so it is expected that the question is irrelevant there. Or if you define a covering as any set of primes such that at least one of them divides every member of {k2n+1∣n∈N}$\{k{2}^n+1\mid n\in \mathbb{N}\}$, then every covering is infinite in these cases. We think.

For class 1, the "classical" way of proving that a particular k$k$ is Sierpiński, is by exhibiting a finite set of primes that covers every exponent n$n$. This is how k=78557$k=78557$ was proved Sierpiński. Each 78557⋅2n+1$78557\cdot 2^n+1$ is divisible by one of the primes {3,5,7,13,19,37,73}$\{3,5,7,13,19,37,73\}$, depending only on n$n$ modulo 36$36$.

But for class 1, be aware that some proofs that a number is Sierpiński use a combination of algebraic factorizations and a finite set of primes. A class of examples was described in:

Anatoly S. Izotov, A Note on Sierpinski Numbers, Fibonacci Quarterly A 33.3(1995), 206.

Izotov's paper gives infinitely many k$k$ that are (provably) Sierpiński, without a prime set that covers all exponents. The remaining exponents are accounted for by an algebraic factorization. The smallest number from Izotov's example is a perfect fourth power

I will describe here a smaller example, also a fourth power

Whenever the exponent n$n$ is singly even, i.e. is 2$2$ mod 4$4$, we have the aurifeuillean factorization:

For the rest of the exponents n$n$, i.e. the odd ones and those divisible by four, the prime set {3,17,97,241,257,673}$\{3,17,97,241,257,673\}$ accounts for all cases. Check all values of n$n$ modulo 48$48$ to see.

So k=447457554$k={44745755}^4$ is proven Sierpiński, but it is not expected that it has a finite covering. In particular, the numbers 447457554⋅24m+2+1${44745755}^4\cdot 2^{4m+2}+1$ (all of which are composite because of the factorization above) are not expected to be coverable by any finite set of primes.

---

I found another reference:

Michael Filaseta, Carrie Finch, and Mark Kozek: On powers associated with Sierpiński numbers, Riesel numbers and Polignac's conjecture, Journal of Number Theory, Volume 128, Issue 7, July 2008

In it, they mention a conjecture by Erdős:

(conjecture by Erdős, almost certainly false) If k$k$ is a Sierpiński number, then the smallest prime divisor of k⋅2n+1$k\cdot 2^n+1$ is bounded as n$n$ tends to infinity.

This is really equivalent to your question. If the Erdős's claim was correct, we could just take the finite set of all primes below the bound mentioned, and that would be a finite covering.

Of course Filaseta, Finch and Kozek refer to Izotov's example and conclude that this conjecture is "highly likely wrong".

They present a modification of the conjecture where they restrict themselves to k$k$ that are not perfect powers, and keep the same conclusion. That is, they suggest if k$k$ is Sierpiński and not of the form ℓr${\ell }^r$ for some integers ℓ≥1$\ell \ge 1$ and r>1$r>1$, then a finite covering set should exist.

---

Much later addition:

I have wanted to supplement the above example of a fourth-power Sierpiński number without a covering set, with a cube number, for a while.

For cubes, we do not need the aurifeuillean factorization but can use the high-school factorization x3+1=(x+1)(x2−x+1)$x^3+1=(x+1)(x^2-x+1)$ to cover all exponents divisible by three.

If we just wanted any cube Sierpiński number, we could use the full covering set {3,5,17,257,65537,641,6700417}$\{3,5,17,257,65537,641,6700417\}$ to find one. The smallest one is k=2014465031451651773$k={201446503145165177}^3$. But the covering set {3,5,17,257,65537,641,6700417}$\{3,5,17,257,65537,641,6700417\}$ has "modulus" 64$64$, meaning that the least common multiple of all the exponents (orders of 2 in the multiplicative groups modulo the primes in the covering) is 64$64$. Since three obviously does not divide 64$64$, the fact that every exponent divisible by three will be handled by the factorization of x3+1$x^3+1$, is incompatible with this covering set.

(Whenever I speak of the exponent of a prime in the following, I mean the multiplicative order of two modulo that prime.)

Therefore we need a set where some of the primes have exponent three (or a multiple of three). This implies that the prime is of the form 3j+1$3j+1$. For such primes, not all elements have cube roots modulo the prime. We run into the problem that often the exponents we can cover with such primes, are exponents that are already taken care of by the algebraic factorization. For example, consider the prime 13$13$ for which the exponent of two is 12$12$. Modulo 13$13$, the only residues that are cubes, are k=1,5,8,12$k=1,5,8,12$. But for each of these k$k$, the only time k⋅2n+1≡0(mod13)$k\cdot 2^n+1\equiv 0(\mathrm{mod}13)$, is when n$n$ is a multiple of three. But they are already removed by the factorization, so a prime like 13$13$ is not useful for this purpose.

It turns out we need some primes where the exponent is a multiple of three (as before) and additionally the "co-order" or "co-exponent", that is p−1$p-1$ divided by the exponent, is also a multiple of three.

After much searching, inspired by this page by J. McLean, I figured out a suitable set would be:

Its modulus (LCM of exponents) is 336$336$, and the primes with both exponents and co-exponents divisible by three, are 5419$5419$ and 2017$2017$. The smallest cube Sierpiński number with this set for which there appears to be no full covering set, is (if I did all my searching correctly):

k=1912811221450688053578833$$k={191281122145068805357883}^3$$

To prove it is Sierpiński, run through n=0…335$n=0\dots 335$ and note that when n≢0(mod3)$n\not\equiv 0(\mathrm{mod}3)$, one of the primes in the set covers, and apply to the factorization when n≡0(mod3)$n\equiv 0(\mathrm{mod}3)$.

The reason why it is almost certain that 1912811221450688053578833${191281122145068805357883}^3$ does not have a full covering set, is that for exponents n≡183(mod336)$n\equiv 183(\mathrm{mod}336)$ there do not seem to be small factors. Only the (x3+1)$(x^3+1)$-thing saves these. For example:

and none of these primes seems to have an exponent that is particularly small or compatible with 336$336$, and:

1912811221450688053578833⋅2183+336+1=(48457519167352386533552756221⋅47260703772109141310697209830783748054722899797)⋅(139⋅C149)$$\begin{gathered} {191281122145068805357883}^3\cdot 2^{183+336}+1= \\ (48457519167352386533552756221 \\ \cdot 47260703772109141310697209830783748054722899797)\cdot (139\cdot \text{C149}) \end{gathered}$$

where "C149" is a composite number with 149 figures and no small factors, and so on.

Therefore, 1912811221450688053578833${191281122145068805357883}^3$ is a proven Sierpiński very unlikely to possess a covering set.

---

Summary: Perfect powers such as 1912811221450688053578833${191281122145068805357883}^3$ and 447457554${44745755}^4$ are proved to be Sierpiński and seem to have no covering sets.