Processing math: 22%

II-eugene-II Note

Home Math Code
시에르핀스키 수

시에르핀스키 수 (Sierpinski Number) 의 정의는 다음과 같습니다.

모든 자연수 n에 대하여, k×2n+1가 합성수가 되도록 하는 홀수 k시에르핀스키 수라고 한다.
현재까지 알려진 시에르핀스키 수 중 가장 작은 것은 78557입니다.
시에르핀스키 수 후보로는 21181, 22699, 24737, 55459, 67607이 있습니다.
원래 78557보다 작은 시에르핀스키 수 후보가 17개 있었는데, Seventeen of Bust 프로젝트로 많이 줄였습니다.
최근에는 10223×231172165+1 소수 임이 밝혀지면서 후보 10223이 사라졌습니다.
발전된 프로트의 정리 로 위 후보들의 소수판정을 해볼 수 있습니다.
이와 닮은 꼴의 수로 리젤 수 가 있는데, 만약 시에르핀스키 수이면서 리젤 수이면 브라이어 수 라고 합니다.
정리 1.
모든 자연수 n에 대하여, 78557×2n+1은 합성수이다.
따라서, 78557시에르핀스키 수 이다.
정리 1 증명

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 

모든 자연수 n에 대하여 78557 \times 2^{n} + 1은 집합 P = \left\{ 3, 5, 7, 13, 19, 37, 73 \right\} 의 원소 중 하나로 나누어떨어진다.
+) 집합 P는 Covering Set 이라 한다.