시에르핀스키 수 (Sierpinski Number) 의 정의는 다음과 같습니다.
모든 자연수 n에 대하여, k×2n+1가 합성수가 되도록 하는 홀수 k을 시에르핀스키 수라고 한다.현재까지 알려진 시에르핀스키 수 중 가장 작은 것은 78557입니다.
정리 1.
모든 자연수 n에 대하여, 78557×2n+1은 합성수이다.
따라서, 78557은 시에르핀스키 수 이다.
1. 2^{n} \pmod{p}의 주기성 (모든 자연수 n에 대해 2^{n} \equiv 2^{n + (p - 1)} \pmod{p}이다.)
2^{0} \equiv 1 \pmod{p}은 자명하고, 페르마의 소정리 에 의해 2^{p - 1} \equiv 1 \pmod{p} 이다.
따라서 2^{1} \equiv 2^{p - 1 + 1} \pmod{p}, 2^{2} \equiv 2^{p - 1 + 2} \pmod{p}, ... 2^{k} \equiv 2^{p - 1 + k} \pmod{p} 이고, 2^{n} \pmod{p}은 p - 1의 주기를 가진다.
(최소 주기가 아닐 수도 있다. 2^{3} \equiv 1 \pmod{7})
2. X \equiv Y \pmod{n} 이면 aX + c \equiv aY + c \pmod{n} (자명함)
A. 78557 \times 2^{0} + 1 \equiv 0 \pmod{3}에서 n \equiv 0 \pmod{2}이면 78557 \times 2^{n} + 1 \equiv 0 \pmod{3} (1, 2번 성질에 의해 78557 \times 2^{n} + 1 \equiv 0 \pmod{3}의 주기가 2)
B. 78557 \times 2^{1} + 1 \equiv 0 \pmod{5}에서 n \equiv 1 \pmod{4}이면 78557 \times 2^{n} + 1 \equiv 0 \pmod{5}
C. 78557 \times 2^{1} + 1 \equiv 0 \pmod{7}에서 n \equiv 1 \pmod{6}이면 78557 \times 2^{n} + 1 \equiv 0 \pmod{7}
D. 78557 \times 2^{11} + 1 \equiv 0 \pmod{13}에서 n \equiv 11 \pmod{12}이면 78557 \times 2^{n} + 1 \equiv 0 \pmod{13}
E. 78557 \times 2^{15} + 1 \equiv 0 \pmod{19}에서 n \equiv 15 \pmod{18}이면 78557 \times 2^{n} + 1 \equiv 0 \pmod{19}
F. 78557 \times 2^{27} + 1 \equiv 0 \pmod{37}에서 n \equiv 27 \pmod{36}이면 78557 \times 2^{n} + 1 \equiv 0 \pmod{37}
G - 1. 78557 \times 2^{3} + 1 \equiv 0 \pmod{73}에서 n \equiv 3 \pmod{72}이면 78557 \times 2^{n} + 1 \equiv 0 \pmod{73}
G - 2. 78557 \times 2^{39} + 1 \equiv 0 \pmod{73}에서 n \equiv 39 \pmod{72}이면 78557 \times 2^{n} + 1 \equiv 0 \pmod{73}
G. n \equiv 3 \pmod{72}, n \equiv 39 \pmod{72}이면 n \equiv 3 \pmod{36}이다. n \equiv 3 \pmod{36}이면 78557 \times 2^{n} + 1 \equiv 0 \pmod{73}
다음은 n = 36m + k (0 \leq k < 36)이라 할 때, k의 값에 따른 표이다. (k = 3일 때 G이므로, "G"의 n \equiv 3 \pmod{36} 의 경우에 해당된다는 뜻)
0 A |
1 B C |
2 A |
3 G |
4 A |
5 B |
6 A |
7 C |
8 A |
9 B |
10 A |
11 D |
12 A |
13 B C |
14 A |
15 E |
16 A |
17 B |
18 A |
19 C |
20 A |
21 B |
22 A |
23 D |
24 A |
25 B C |
26 A |
27 F |
28 A |
29 B |
30 A |
31 C |
32 A |
33 B E |
34 A |
35 D |