다음 소수를 찾는 또 다른 방법

$p_1=2$ 로 두고, $n=p_1p_2 \cdots p_k$ 에 대해 $n^{n^n}-1$ 의 최소의 소인수를 $p_{k+1}$ 로 정의하면 $p_k$ 는 크기 순으로 $k$ 번째 소수가 된다는 내용. [1] 이는 양의 정수 $n$ 에 대해 $n^{n^n}-1$ 의 최소의 소인수는 $n$ 의 소인수가 아닌 최소의 소수임을 보임으로써 증명할 수 있다.

$n=1$ 인 경우는 자명하므로 $n \geq 2$ 라 가정하고 $n$ 을 나누지 않는 최소의 소수를 $p$ 라고 하고 $n$ 의 소인수를 $p_1, \ldots,p_k$ 라고 둔다. 그러면 $p$ 는 $p_1 p_2 \cdots p_k$ 를 나누지 못하는 최소의 소수인데 $p_1 p_2 \cdots p_k+1$ 의 임의의 소인수 또한 $p_1 p_2 \cdots p_k$ 를 나누지 못하므로 $p$ 는 그보다도 작거나 같아야 해 $p \leq p_1 p_2 \cdots p_k+1 \leq n+1$ 을 얻는다. 또한 $p-1$ 의 모든 소인수들은 ( $p$ 보다 작으므로 $p$ 의 최소성에 의해) $p_1, \ldots ,p_k$ 의 일부여야 하며, $p_i^n \geq 2^n \geq n+1 \geq p$ 이므로, $p-1$ 을 소인수분해한 결과 소인수는 $p_i$ 꼴이며 그 지수가 $n$ 이하가 되어 $p-1 | (p_1 \cdots p_k)^n$ , 즉 $p-1 | n^n$ 을 얻는다. 따라서 페르마의 소정리에 의해 $n^{n^n} \equiv 1\text{ (mod }p\text{)}$ 을 얻는다.

역으로 $p$ 가 $n^{n^n}-1$ 의 최소의 소인수라 하면 $p$ 는 $n$ 의 소인수가 될 수 없다. 따라서 $n^{n^n}-1$ 의 소인수의 집합을 $A$ , $n$ 의 소인수가 아닌 소수의 집합을 $B$ 라 하면 $\min(A) \in B, \min(B) \in A$ 로부터 $\min(A) \geq \min(B) \geq \min(A)$ , 즉 $\min(A)=\min(B)$ 가 되어 증명이 끝난다.

부가적으로 위 보조정리에서 양의 정수 $N$ 에 대해 $n=N!$ 로 두면, $N$ 보다 큰 최소의 소수는 $N!^{N!^{N!}}-1$ 의 최소의 약수(1을 제외)가 됨을 알 수 있다.

$p_1=2$ 이고 $p_{k+1}$ 을 $p_1 p_2 \cdots p_k+1$ 의 최소의 소인수로 정의하는 수열 $\{ p_i \}$ 는 Euclid-Mullin 수열로 알려져있는데, 이게 모든 소수를 커버한다는 conjecture는 아직도 오픈.

트윗 타래를 정리. (2018/11/24)

https://t.co/jZNn2CAony p_1=2로 놓고, p_1에서 p_k까지의 곱을 n이라 할 때 n^(n^n)-1의 최소의 소인수를 p_{k+1}로 정의하면 p_k는 크기 순으로 k번째 소수가 됨 (Wooley, 2016)
— 유닼 (@udaqueness) November 24, 2018

References

[1] T. D. Wooley, “A Superpowered Euclidean Prime Generator” American Mathematical Monthly, 124(4), 351-352. DOI: 10.4169

월	화	수	목	금	토	일
	1	2	3	4	5	6
7	8	9	10	11	12	13
14	15	16	17	18	19	20
21	22	23	24	25	26	27
28	29	30	31

다음 소수를 찾는 또 다른 방법

References

“다음 소수를 찾는 또 다른 방법”의 1개의 생각

댓글 남기기 응답 취소

References

이 글 공유하기:

관련

“다음 소수를 찾는 또 다른 방법”의 1개의 생각

댓글 남기기 응답 취소