시어핀스키 수(Sierpinski number)

      Comments Off on 시어핀스키 수(Sierpinski number)

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

 

정리 1.

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

 

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

\[ \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$은 쌍대 시어핀스키 수 임을 증명할 수 있다.

 

정리 2.

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

 

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

\[ \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개의 수는 모두 시어핀스키 수가 아님이 확인되었다.

 

$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" 프로젝트의 자세한 설명 및 현황은 이곳에서 확인해 볼 수 있다.