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

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라고 둔다. 그러면 pp_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{)}을 얻는다.

역으로 pn^{n^n}-1의 최소의 소인수라 하면 pn의 소인수가 될 수 없다. 따라서 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)

References

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

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

답글 남기기

아래 항목을 채우거나 오른쪽 아이콘 중 하나를 클릭하여 로그 인 하세요:

WordPress.com 로고

WordPress.com의 계정을 사용하여 댓글을 남깁니다. 로그아웃 /  변경 )

Google photo

Google의 계정을 사용하여 댓글을 남깁니다. 로그아웃 /  변경 )

Twitter 사진

Twitter의 계정을 사용하여 댓글을 남깁니다. 로그아웃 /  변경 )

Facebook 사진

Facebook의 계정을 사용하여 댓글을 남깁니다. 로그아웃 /  변경 )

%s에 연결하는 중