1960년 시어핀스키(Waclaw Sierpinski)는 모든 양의 정수 $n$에 대하여, $k 2^n +1$가 합성수가 되게 하는 홀수 양의 정수 $k$의 갯수는 무한함을 증명하였다. 그의 업적을 기리기 위해, 위 성질을 만족하는 홀수 양의 정수 $k$를 시어핀스키 수_{(Sierpinski number)}라고 한다. 시어핀스키의 증명에는 구체적인 $k$의 값은 제시되지 않았었는데, 2년 후에 셀프리지(John Selfridge)는 $k=78557$이 시어핀스키 수임을 증명하는데 성공하였다. 그의 증명 과정을 조금 더 자세히 알아보자.

증명. 아래의 계산 결과에 의해서 위 정리가 성립함을 알 수 있다.

\[ \begin{align*} n \equiv 0 \pmod{2} \quad &\Longrightarrow \quad 78557 \cdot 2^n + 1 \equiv 0 \pmod{3} \\[5px] n \equiv 1 \pmod{4} \quad &\Longrightarrow \quad 78557 \cdot 2^n + 1 \equiv 0 \pmod{5} \\[5px] n \equiv 7 \pmod{12} \quad &\Longrightarrow \quad 78557 \cdot 2^n + 1 \equiv 0 \pmod{7} \\[5px] n \equiv 11 \pmod{12} \quad &\Longrightarrow \quad 78557 \cdot 2^n + 1 \equiv 0 \pmod{13} \\[5px] n \equiv 3 \pmod{36} \quad &\Longrightarrow \quad 78557 \cdot 2^n + 1 \equiv 0 \pmod{73} \\[5px] n \equiv 15 \pmod{36} \quad &\Longrightarrow \quad 78557 \cdot 2^n + 1 \equiv 0 \pmod{19} \\[5px] n \equiv 27 \pmod{36} \quad &\Longrightarrow \quad 78557 \cdot 2^n + 1 \equiv 0 \pmod{37} \end{align*} \]

위 계산 결과 중 하나만 살펴보도록 하자. 만약 $n \equiv 7 \pmod{12}$라면 적당한 $k \geq 0$에 대하여 $n = 12k+7$로 나타낼 수 있다. 따라서

\[ 78557 \cdot 2^{12k+7} + 1 = 78557 \cdot 8^{4k} \cdot 128 + 1 \equiv 3 \cdot 1 \cdot 2 + 1 \equiv 0 \pmod{7} \]

이 성립한다. 나머지 경우도 마찬가지로 증명할 수 있다..

위 증명을 살펴보면 $78557 \cdot 2^n + 1$은 언제나 다음 집합

\[ P = \{ 3,\, 5,\, 7,\, 13,\, 19,\, 37,\, 74 \} \]

의 원소 중 하나로 반드시 나누어 떨어짐을 알 수 있다. 이와 같은 성질을 갖는 집합 $P$를 덮개집합_{(covering set)}이라 한다. 즉, 덮개집합은 소수들의 부분집합으로써, 모든 양의 정수 $n$에 대하여 $k 2^n +1$이 언제나 집합 $P$의 원소로 나누어 떨어지게 하는 성질을 갖는다. 현재까지 알려진 모든 시어핀스키 수는 모두 덮개집합을 가지는 것으로 알려져 있다.

이제 양의 정수 $n$에 대하여

\[ k 2^{-n} + 1 = \frac{k + 2^n}{2^n} \]

으로 나타낼 수 있으므로, 모든 양의 정수 $n$에 대하여 $k + 2^n$이 언제나 합성수가 되게 하는 홀수 정수 $k$에 대해서 생각해 볼 수 있다. 이러한 성질을 갖는 $k$를 쌍대 시어핀스키 수_{(dual Sierpinski number)}라 부른다. 그러면 정리 1과 유사하게 $k=78557$은 쌍대 시어핀스키 수 임을 증명할 수 있다.

증명. 아래의 계산 결과에 의해서 위 정리가 성립함을 알 수 있다.

\[ \begin{align*} n \equiv 0 \pmod{2} \quad &\Longrightarrow \quad 78557 + 2^n \equiv 0 \pmod{3} \\[5px] n \equiv 3 \pmod{4} \quad &\Longrightarrow \quad 78557 + 2^n \equiv 0 \pmod{5} \\[5px] n \equiv 5 \pmod{12} \quad &\Longrightarrow \quad 78557 + 2^n \equiv 0 \pmod{7} \\[5px] n \equiv 1 \pmod{12} \quad &\Longrightarrow \quad 78557 + 2^n \equiv 0 \pmod{13} \\[5px] n \equiv 33 \pmod{36} \quad &\Longrightarrow \quad 78557 + 2^n \equiv 0 \pmod{73} \\[5px] n \equiv 21 \pmod{36} \quad &\Longrightarrow \quad 78557 + 2^n \equiv 0 \pmod{19} \\[5px] n \equiv 9 \pmod{36} \quad &\Longrightarrow \quad 78557 + 2^n \equiv 0 \pmod{37} \tag*{$\myblue{\blacksquare}$} \end{align*} \]

시어핀스키의 증명에 의해서 무한히 많은 시어핀스키 수가 존재한다는 사실을 알고 있으므로, 가장 작은 시어핀스키 수에 대하여 생각해 볼 수 있다. 하지만 놀랍게도 가장 작은 시어핀스키 수를 찾는 문제는 아직까지도 미해결로 남아 있다. 즉, 현재까지 알려진 최소의 시어핀스키 수는 $k=78557$인데, 이 수가 가장 작은 시어핀스키 수임을 보이는 것은 아직까지 미해결 상태이다. 현재까지 $k=78557$보다 작은 홀수 정수 중 5개를 제외한 모든 수가 시어핀스키 수가 아닌 것으로 판정이 되었는데 이 5개의 수는 다음과 같다.

\[ 21181,\; 22699,\; 24737,\; 55459,\; 67607 \]

주어진 홀수 정수 $k$가 시어핀스키 수가 아님을 보이기 위해서는 $k2^n + 1$이 소수가 되게 하는 $n$이 존재해야만 한다. 하지만 대부분 $k$ 값의 경우 상대적으로 작은 $n$에 대하여 $k2^n + 1$이 소수임을 확인할 수 있었지만, 2002년 까지 17개의 홀수 정수의 시어핀스키 수인지 여부가 알려져 있지 않았었다. 이후 "Seventeen or bust"라는 프로젝트명으로, 분산 컴퓨팅(distributed computing)을 이용한 이 17개의 홀수 정수의 시어핀스키 여부를 확인하려는 프로젝트가 실행되었고, 그 이후로 2018년 1월 현재까지 위에 언급한 5개의 수를 제외한 12개의 수는 모두 시어핀스키 수가 아님이 확인되었다.

위 "Seventeen or bust" 프로젝트의 자세한 설명 및 현황은 이곳에서 확인해 볼 수 있다.