|
정수론 Number Theory |
|||
|
{{{#!wiki style="margin: 0 -10px -5px; min-height: calc(1.5em + 5px)" {{{#!folding [ 펼치기 · 접기 ] {{{#!wiki style="margin: -5px -1px -11px" |
공리 | ||
| 페아노 공리계 · 정렬 원리 · 수학적 귀납법 · 아르키메데스 성질 | |||
| 산술 | |||
| 나눗셈 | 약수· 배수 | 배수 · 약수( 소인수) · 소인수분해( 목록 · 알고리즘) · 공배수 · 공약수 · 최소공배수 · 최대공약수 | |
| 약수들의 합에 따른 수의 분류 | 완전수 · 부족수 · 과잉수 · 친화수 · 사교수 · 혼약수 · 반완전수 · 불가촉 수 · 괴짜수 | ||
| 정리 | 베주 항등식 · 산술의 기본정리 · 나눗셈 정리 | ||
| 기타 | 유클리드 호제법 · 서로소 | ||
| 디오판토스 방정식 | 페르마의 마지막 정리 · 피타고라스 세 쌍 · 버치-스위너턴다이어 추측(미해결) | ||
| 모듈러 연산 | |||
| 잉여역수 · 2차 잉여 · 기약잉여계 · 완전잉여계 · 중국인의 나머지 정리 · 합동식 · 페르마의 소정리 · 오일러 정리 · 윌슨의 정리 | |||
| 소수론 | |||
| 수의 분류 | 소수 · 합성수 · 메르센 소수 · 쌍둥이 소수( 사촌 소수 · 섹시 소수) · 페르마 소수 · 레퓨닛 수 | ||
| 분야 | 대수적 정수론( 국소체) · 해석적 정수론 | ||
| 산술함수 | 뫼비우스 함수 · 소수 계량 함수 · 소인수 계량 함수 · 약수 함수 · 오일러 파이 함수 · 폰 망골트 함수 · 체비쇼프 함수 · 소수생성다항식 | ||
| 정리 | 그린 타오 정리 · 페르마의 두 제곱수 정리 · 디리클레 정리 · 소피 제르맹의 정리 · 리만 가설(미해결) · 골드바흐 추측(미해결)( 천의 정리) · 폴리냑 추측(미해결) · 소수 정리 | ||
| 기타 | 에라토스테네스의 체 · 윌런스의 공식 | ||
1. 개요
1964년에 수학자 윌런스(C. P. Willans)가 발표한 공식이다.이 공식에 n을 대입하면 n번째 소수가 되는 공식이다. 공식은 다음과 같다.[math(\displaystyle P_n=1+\sum_{m=1}^{2^n}\left\lfloor\sqrt[n]{n}\left(\sum_{x=1}^{m}\left\lfloor\cos^2\pi\frac{\left(x-1\right)!+1}{x}\right\rfloor \right)^{-\frac{1}{n}}\right\rfloor)]
굉장히 복잡해 보이지만 실제로 공식을 까보면 별 거 없다. 밑의 문단을 보자.2. 유도
윌런스의 공식에서 가장 핵심적인 부분은 윌슨의 정리이다. 윌슨의 정리를 살짝 변형하면 아래와 같은 정리를 얻는다.1보다 큰 자연수 [math(x)]가 소수라는 것과 [math(\left(x-1\right)!+1)]이 [math(x)]의 배수라는 것은 동치이다.
윌슨의 정리에 의해 [math(\dfrac{\left(x-1\right)!+1}{x})]라는 식은 [math(x)]가 1이거나
소수일 때는
정수, 그 외의 경우는 모두 정수가 아니다. 여기서 이 값에 [math(\pi)]를 곱하고
코사인값을 구하면, [math(x)]가 1이거나 소수일 때는 1 또는 -1이 되고, [math(x)]가
합성수인 경우에는
절댓값이 1보다 작은 수가 된다. 결국 [math(\cos\pi\dfrac{\left(x-1\right)!+1}{x})]는 [math(x)]가 1이나 소수일 때만 -1 혹은 1이다.이제 이 값을 제곱한 다음 최대 정수 함수[1]를 붙인 함수를 [math(F(x))]라 하면, [math(x)]가 1이거나 소수일 때 [math(F(x)=1)], [math(x)]가 합성수일 때 [math(F(x)=0)]이 된다. 즉, [math(\left\lfloor\cos^2\pi\dfrac{\left(x-1\right)!+1}{x}\right\rfloor)]는 [math(x)]가 1이거나 소수일 때만 1이 되고, 그렇지 않으면 0이 된다.
여기서 함수 [math(F(x))]의 값을 [math(x=1)]부터 [math(x=m)]까지 차례대로 구해서 더하면, 그 값은 [math(m)]보다 작거나 같은 자연수 가운데 1과 소수의 개수가 된다. 따라서 [math(\displaystyle \sum_{x=1}^{m}F(x)=\pi (m)+1)]이 된다. 여기에서 [math(\pi\left(m\right))]는 [math(m)]보다 작거나 같은 자연수 가운데 소수가 몇 개인지 세는 함수이다.
이제 [math(\pi (m))]을 이용하여 [math(n)]번째 소수를 만드는 방법을 찾아야 한다. [math(m=1,2,3,\cdots)]에 대하여, [math(\pi (m))]값이 [math(n)]이 되기 전까지는 1씩 더하고, [math(\pi (m)=n)]일 때부터 0을 더하면 [math(P_n-1)]값이 된다.
(그러니까 예시로 5번째 소수([math(P_5)])인 11을 구할 때, m이 1~10 일때는 [math(\pi (m))]값이 5 미만이여서 1이 10번 더해진다. 그러면 값이 10이 되는데, 이는 11에서 1을 뺀 값과 같다)
따라서 다음과 같은 함수를 정의한다.
[math(\displaystyle A_n (a)=\left \lfloor\sqrt[n]{\frac{n}{1+a}}\right \rfloor)]
이 함수는 [math(a)]가 [math(n)]보다 작을 때 1이 되고, 그렇지 않을 때는 0이 된다.
따라서 [math(\displaystyle P_n=1+\sum_{m=1}^{\infty}A_n (\pi (m)))]를 계산하면 [math(1+1+1+\cdots+1+0+0+0+\cdots)]이므로 함수값은 [math(n)]번째 소수가 된다. 그런데 여기서 마지막에 0을 무한 번 더할 필요는 없으므로, 적당히 끊어줘야 한다. [math(n)]번째 소수가 [math(2^n)]보다 작거나 같다는 사실은 1852년 증명된 베르트랑 체비쇼프 정리로 쉽게 보일 수 있으므로 식을 최종적으로 정리하면 맨 위의 공식이 나온다. 흔히 베르트랑의 공준이라고 하는 이 정리에 의하면 임의의 2 이상의 정수 [math(N)]에 대해 [math(N < p < 2N)]인 소수 p가 존재한다. 2는 1번째 소수이고, [math(2^{n-1} < p < 2^n)]인 소수 [math(p)]는 [math(n)]번째 이상의 소수임은 귀납적으로 증명된다.
3. 결론
윌런스의 공식은 그 자체만 보면 신기할 수 있지만 공식을 계산하는 과정에서 결국 1부터 [math(2^n)]까지 모든 수를 소수인지 아닌지 따져보는 것과 같아서 에라토스테네스의 체보다도 비효율적이다. 소수를 판별하는 방법도 비효율적인데, 여기서는 윌슨의 정리로 소수를 판별했고, 이 판별법은 상당히 비효율적이다. 게다가 이 공식은 소수에 관한 아주 간단한 성질조차 증명할 수 없을 정도로 무의미하기 때문에,[2] 그냥 재미로 알아두기만 해도 된다. 프로그래밍 쪽에 이용하기도 난감하다[3] 차라리 소수 정리[4]를 활용하는 쪽이 더 효율적일 수 있다.어찌 보면 공식이 만능은 아니다는 것을 보여주는 일종의 수학 유머로 생각할 수 있겠다.[5] 실제로 윌런스가 이 공식을 투고한 학술지 Mathematical Gazette는 수학 교육/학습 목적의 재미난 이야기들을 다루는 저널이다. 말 그대로 '이런 공식도 만들 수 있다'라는 것만을 보여주는 공식인 셈. 애초에 수학은 공식만 외워서는 절대로 잘 할 수 있는 과목이 아니다. 공식뿐만아니라 이해력과 수학적 사고력 등이 모두 필요하다.
4. 관련 문서
[1]
[math(lfloor xrfloor)]는 [math(x)]보다 크지 않은 가장 큰 정수이다. 흔히 가우스 기호로 알려진 것.
[2]
서로 다른 두 소수는 서로소라는 아주 당연한 정리조차 증명하지 못한다!
[3]
입력값이 20정도만 넘어도 [math((x-1)!)]를 계산하기 곤란해진다.
[4]
로그함수로 n 이하의 소수의 개수를 어림한다.
[5]
현대의 수학자들은 단순히 수학 기호로 대상을 나타내는 것만을 공식이라고 생각하지 않는다. 대다수의 대상이 우리가 보통 생각하는 공식 (closed form이라고 한다)으로 나타나지 않는 현실 속에선 단순한 기호로서의 공식은 의미 없다는 사실을 지각하고, 대신에 효율적으로 계산가능한 (effectively computable) 알고리즘으로서의 공식을 더욱 높게 간주하는 것. 수학 공식의 진가는 그 자체가 아니라, 단순한 표현이나 빠른 계산법을 제공해 주는 활용성에 있다.