시어핀스키 수(Sierpinski number)

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

정리 1.

$k=78557$일 때, 모든 양의 정수 $n$에 대하여 $k{2}^n+1$은 언제나 합성수이다.

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

$$\begin{array}{rl}n\equiv 0(\mathrm{mod}2)& ⟹78557\cdot 2^n+1\equiv 0(\mathrm{mod}3)\\ n\equiv 1(\mathrm{mod}4)& ⟹78557\cdot 2^n+1\equiv 0(\mathrm{mod}5)\\ n\equiv 7(\mathrm{mod}12)& ⟹78557\cdot 2^n+1\equiv 0(\mathrm{mod}7)\\ n\equiv 11(\mathrm{mod}12)& ⟹78557\cdot 2^n+1\equiv 0(\mathrm{mod}13)\\ n\equiv 3(\mathrm{mod}36)& ⟹78557\cdot 2^n+1\equiv 0(\mathrm{mod}73)\\ n\equiv 15(\mathrm{mod}36)& ⟹78557\cdot 2^n+1\equiv 0(\mathrm{mod}19)\\ n\equiv 27(\mathrm{mod}36)& ⟹78557\cdot 2^n+1\equiv 0(\mathrm{mod}37)\end{array}$$

위 계산 결과 중 하나만 살펴보도록 하자. 만약 $n\equiv 7(\mathrm{mod}12)$라면 적당한 $k\ge 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(\mathrm{mod}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$은 쌍대 시어핀스키 수 임을 증명할 수 있다.

정리 2.

$k=78557$일 때, 모든 양의 정수 $n$에 대하여 $k+2^n$은 언제나 합성수이다.

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

$$\begin{array}{rl}n\equiv 0(\mathrm{mod}2)& ⟹78557+2^n\equiv 0(\mathrm{mod}3)\\ n\equiv 3(\mathrm{mod}4)& ⟹78557+2^n\equiv 0(\mathrm{mod}5)\\ n\equiv 5(\mathrm{mod}12)& ⟹78557+2^n\equiv 0(\mathrm{mod}7)\\ n\equiv 1(\mathrm{mod}12)& ⟹78557+2^n\equiv 0(\mathrm{mod}13)\\ n\equiv 33(\mathrm{mod}36)& ⟹78557+2^n\equiv 0(\mathrm{mod}73)\\ n\equiv 21(\mathrm{mod}36)& ⟹78557+2^n\equiv 0(\mathrm{mod}19)\\ n\equiv 9(\mathrm{mod}36)& ⟹78557+2^n\equiv 0(\mathrm{mod}37)\end{array}$$

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

$$21181,22699,24737,55459,67607$$

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

$k$	$n$	자릿수	발견날짜	발견자
46,157	698,207	210,186	26 Nov 2002	Stephen Gibson
65,567	1,013,803	305,190	03 Dec 2002	James Burt
44,131	995,972	299,823	06 Dec 2002	deviced (nickname)
69,109	1,157,446	348,431	07 Dec 2002	Sean DiMichele
54,767	1,337,287	402,569	22 Dec 2002	Peter Coels
5,359	5,054,502	1,521,561	06 Dec 2003	Randy Sundquist
28,433	7,830,457	2,357,207	30 Dec 2004	Anonymous
27,653	9,167,433	2,759,677	08 Jun 2005	Derek Gordon
4,847	3,321,063	999,744	15 Oct 2005	Richard Hassler
19,249	13,018,586	3,918,990	26 Mar 2007	Konstantin Agafonov
33,661	7,031,232	2,116,617	13 Oct 2007	Sturle Sunde
10,223	31,172,165	9,383,761	31 Oct 2016	Péter Szabolcs
21,181	> 31,626,428 ?	> 9,520,507 ?	(Double check in progress)
22,699	> 31,625,902 ?	> 9,520,349 ?	(Double check in progress)
24,737	> 31,626,727 ?	> 9,520,597 ?	(Double check in progress)
55,459	> 31,626,694 ?	> 9,520,588 ?	(Double check in progress)
67,607	> 31,625,811 ?	> 9,520,322 ?	(Double check in progress)

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