# Does every Sierpinski number have a finite congruence covering?

The following link notes that $k = 78557$ is a Sierpinski number and the answer provides a congruence covering to prove that no integer of the form $k2^n + 1$ is prime:

pew (https://math.stackexchange.com/users/139000/pew), How was 78557 originally suspected to be a Sierpinski number?, URL (version: 2014-12-30): How was 78557 originally suspected to be a Sierpinski number?

There are six values of $k$ remaining less than $78557$ that PrimeGrid is trying to show are not Sierpinski numbers by finding a prime of each form.

Maybe an alternate way of approaching the problem would be to attempt to find a congruence covering for those six values of $k$ implying that no prime can be found. However, that would be a feasible approach only if one could expect the number of congruences involved in the covering to be finite.

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

• Jeppe Stig Nielsen posted a new answer which is better than mine. If you have an opportunity, please un-accept my answer and accept his. – Charles Apr 22 '18 at 19:11
• @Charles I have accepted Jeppe Stig Nielsen's answer. Thank you to both of you. – Frank Hubeny Apr 23 '18 at 0:56

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

We can think of the set of all $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 $k2^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 $\{k2^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$, it is expected that an infinitude of primes $k2^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 $\{k2^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$ is Sierpiński, is by exhibiting a finite set of primes that covers every exponent $n$. This is how $k=78557$ was proved Sierpiński. Each $78557\cdot 2^n+1$ is divisible by one of the primes $\{3, 5, 7, 13, 19, 37, 73\}$, depending only on $n$ modulo $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$ 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: $$k=166528519813771386496141126495646000631459761803173801006187890625$$ It is a perfect fourth power.

I will describe here a smaller example, namely $k=4008735125781478102999926000625$, also a fourth power. Whenever the exponent $n$ is singly even, i.e. is $2$ mod $4$, we have the aurifeuillean factorization:

$$4008735125781478102999926000625\cdot 2^{4m+2}+1= \\ (2002182590520025\cdot 2^{2m+1}+44745755\cdot 2^{m+1}+1) \\ (2002182590520025\cdot 2^{2m+1}-44745755\cdot 2^{m+1}+1)$$

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

So $k=4008735125781478102999926000625$ is proven Sierpiński, but it is not expected that it has a finite covering. In particular, the numbers $4008735125781478102999926000625\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$ is a Sierpiński number, then the smallest prime divisor of $k\cdot 2^n + 1$ is bounded as $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$ that are not perfect powers, and keep the same conclusion. That is, they suggest if $k$ is Sierpiński and not of the form $\ell^r$ for some integers $\ell\ge 1$ and $r>1$, then a finite covering set should exist.