| 정수론 Number Theory | |||
| {{{#!wiki style="margin: 0 -10px -5px; min-height: calc(1.5em + 5px)" {{{#!folding [ 펼치기 · 접기 ] {{{#!wiki style="margin: -5px -1px -11px" | 공리 | ||
| 페아노 공리계 · 정렬 원리 · 수학적 귀납법 · 아르키메데스 성질 | |||
| 산술 | |||
| 나눗셈 | 약수·배수 | 배수 · 약수(소인수) · 소인수분해(목록 · 알고리즘) · 공배수 · 공약수 · 최소공배수 · 최대공약수 | |
| 약수들의 합에 따른 수의 분류 | 완전수 · 부족수 · 과잉수 · 친화수 · 사교수 · 혼약수 · 반완전수 · 불가촉 수 · 괴짜수 | ||
| 정리 | 베주 항등식 · 산술의 기본정리 · 나눗셈 정리 | ||
| 기타 | 유클리드 호제법 · 서로소 | ||
| 디오판토스 방정식 | 페르마의 마지막 정리 · 피타고라스 세 쌍 · 버치-스위너턴다이어 추측(미해결) | ||
| 모듈러 연산 | |||
| 잉여역수 · 2차 잉여 · 기약잉여계 · 완전잉여계 · 중국인의 나머지 정리 · 합동식 · 페르마의 소정리 · 오일러 정리 · 윌슨의 정리 | |||
| 소수론 | |||
| 수의 분류 | 소수 · 합성수 · 메르센 소수 · 쌍둥이 소수(사촌 소수 · 섹시 소수) · 페르마 소수 · 레퓨닛 수 | ||
| 분야 | 대수적 정수론(대수적 정수론/심화) · 해석적 정수론 | ||
| 산술함수 | 뫼비우스 함수 · 소수 계량 함수 · 소인수 계량 함수 · 약수 함수 · 오일러 파이 함수 · 폰 망골트 함수 · 체비쇼프 함수 · 소수생성다항식 | ||
| 정리 | 그린 타오 정리 · 페르마의 두 제곱수 정리 · 디리클레 정리 · 소피 제르맹의 정리 · 리만 가설(미해결) · 골드바흐 추측(미해결)(천의 정리) · 폴리냑 추측(미해결) · 소수 정리 | ||
| 기타 | 에라토스테네스의 체 · 윌런스의 공식 | ||
| 초등함수 Elementary Functions | ||
| {{{#!wiki style="margin: 0 -10px -5px; min-height: calc(1.5em + 5px)" {{{#!folding [ 펼치기 · 접기 ] {{{#!wiki style="margin: -5px -1px -11px; word-break: keep-all" | <colbgcolor=#567843> 대수함수 | 다항함수 (상수 · 1차 · 2차 · 3차 · 4차 · 추론 · 공식 ( 길이 · 넓이 ) · 소수생성) · 유리함수 · 무리함수 |
| 초월함수 | 지수함수( 확률밀도함수 · 허수지수함수 ) · 로그함수 ( 복소로그함수 ) · 삼각함수 · 역삼각함수 · 쌍곡선 함수 · 역쌍곡선 함수 | }}}}}}}}} |
1. 개요
素數生成多項式 / prime generating polynomial말 그대로 소수를 생성해내는 다항식이다. 이는 함수(초등함수)로 간주할 수도 있다.
2. 예시
1772년, 스위스의 수학자 레온하르트 오일러가 고안한 소수생성다항식이 유명하다. 그 식은 [math(f(x)=x^2+x+41)]인데, [math(0\leq{x}\leq{39})]인 정수 [math(x)]에 대하여 [math(f(x))]의 값은 소수가 된다.| [math(f(0)=41, f(1)=43, f(2)=47, f(3)=53, f(4)=61, f(5)=71)] [math(f(6)=83, f(7)=97, f(8)=113, f(9)=131, f(10)=151)] [math(f(11)=173, f(12)=197, f(13)=223, f(14)=251, f(15)=281)] [math(f(16)=313, f(17)=347, f(18)=383, f(19)=421, f(20)=461)] [math(f(21)=503, f(22)=547, f(23)=593, f(24)=641, f(25)=691)] [math(f(26)=743, f(27)=797, f(28)=853, f(29)=911, f(30)=971)] [math(f(31)=1033, f(32)=1097, f(33)=1163, f(34)=1231, f(35)=1301)] [math(f(36)=1373, f(37)=1447, f(38)=1523, f(39)=1601)] |
3. 유의미한 소수생성다항식이 되기 위한 조건
유의미한 소수생성다항식을 만들기란 어렵다. 위에서 소개한 대로 40개, 80개의 연속된 정수에 대한 함숫값이 모두 소수가 되도록 하는 다항식을 고안하는 것은 더더욱 어렵다. 그러나 '다소 유의미한' 소수생성다항식의 조건을 이야기할 수는 있다. 여기에서는 소수생성다항식을 [math(y=f(x))]([math(x)]는 음이 아닌 정수)의 꼴로 놓고 설명한다.3.1. 함숫값이 항상 홀수일 것
2를 제외한 모든 소수는 홀수인 이상, '여러 개의 소수'를 생성해내는, 제법 쓸모 있는 소수생성다항식은 일단 함숫값이 항상 홀수이고 봐야 한다. 자꾸 짝수가 나오면 곤란하다.위에서 소개한 [math(f(x)=x^2+x+41)]이나 [math(g(t)=t^2-79t+1601)]은 함숫값이 항상 홀수가 된다. 각각 [math(x(x+1)+41)] 그리고 [math(t(t-79)+1601)]로 나타낼 수 있는데, 1과 79가 홀수인 이상 [math(x)]와 [math(x+1)] 중 하나는 홀수, 또 다른 하나는 짝수가 되고, [math(t)]와 [math(t-79)]도 마찬가지다. 그러므로 [math(x(x+1))]과 [math(t(t-79))]는 무조건 홀수와 짝수의 곱이므로 짝수가 되며, 여기에 각각 41과 1601이라는 홀수를 더하면 홀수가 될 수밖에 없다.
3.2. 함숫값의 일의 자리가 5가 되지 않을 것
함숫값의 일의 자리가 5라는 것은 그 값이 5의 배수임을 의미하며, 소수생성다항식의 성능은 그에 발맞춰 떨어지는 셈이다. 따라서 함숫값의 일의 자리가 5가 나오지 않도록 하는 것도 훌륭한 소수생성다항식의 조건이다.위에서 소개한 [math(f(x)=x^2+x+41)]이나 [math(g(t)=t^2-79t+1601)]은 함숫값의 일의 자리가 절대로 5가 되지 않는다.
우선, [math(f(x))]의 일의 자리가 5가 되려면 [math(x^2+x=x(x+1))]의 일의 자리는 4가 되어야 한다. 그러나
| [math(x)]의 일의 자리 | [math(x^2+x)]의 일의 자리 |
| [math(0, 4, 5, 9)] | [math(0)] |
| [math(1, 3, 6, 8)] | [math(2)] |
| [math(2, 7)] | [math(6)] |
마찬가지로, [math(g(t))]의 일의 자리가 5가 되려면 [math(t^2-79t=t(t-79))]의 일의 자리는 [math(t^2-79t\geq0)]일 경우 4, [math(t^2-79t<0)]일 경우 6이 되어야 한다. 그러나
| [math(t^2-79t>0)] | [math(t^2-79t<0)] | [math(t^2-79t=0)] | |||
| [math(t)]의 일의 자리 | [math(t^2-79t)]의 일의 자리 | [math(t)]의 일의 자리 | [math(t^2-79t)]의 일의 자리 | [math(t)]의 일의 자리 | [math(t^2-79t)]의 일의 자리 |
| [math(0, 4, 5, 9)] | [math(0)] | [math(0, 4, 5, 9)] | [math(0)] | [math(0, 9)][1] | [math(0)][2] |
| [math(1, 3, 6, 8)] | [math(2)] | [math(1, 3, 6, 8)] | [math(8)] | ||
| [math(2, 7)] | [math(6)] | [math(2, 7)] | [math(4)] | ||
4. 소수생성다항식은 만능인가
결론부터 말하자면 그렇지 않다(...). 위에서 소개한 소수생성다항식들도 결국 특정 값을 대입할 경우에만 소수가 생성될 뿐이다. 소수만을 찍어내는 만능제조기란 없다. 위에서 소개한 식을 고안한 오일러의 제자였던 아드리앵마리 르장드르는 소수 함숫값만을 갖는 유리식이 존재하지 않음을 증명했고, 골드바흐는 소수 함숫값만을 갖는 정수계수 다항식이 존재하지 않음을 증명했다.5. 차선책: 소수를 무한히 생성
눈을 낮추어 함숫값이 양수일 때만 소수가 된다든가, 더 낮추어 비율은 적지만 아무튼 무한히 많은 소수 함숫값을 갖는 다항식을 생각해볼 수 있다.5.1. 디리클레 정리
우선 일차식([math(ax+b)], [math(a \not= 0)]의 꼴)의 경우, [math( \gcd (a,b)>1)]이면 많아야 두 함숫값([math( \pm\gcd (a,b))])만 소수이다. 반면, [math( \gcd (a,b)=1)]이면 무한히 많은 [math(x \in \mathbb{Z})]에 대해 [math(ax+b)]가 소수임이 알려져 있는데 이를 디리클레 정리라 한다.5.2. 부냐콥스키 추측
디리클레 정리를 2차 이상으로 확장하여 정수를 정의역으로 하는 정수계수 다항함수의 치역의 최대공약수가 1이면 소수를 무한히 생성할 것이라는 것이 부냐콥스키 추측이다.6. 차차선: 다항식이 아닌 소수생성식
이젠 다항식조차 아니게된다.6.1. 윌런스의 공식
n번째 소수를 내놓는 이론적으로는 완벽한 소수생성 함수인데, 결과적으로는 에라토스테네스의 체보다도 비효율적인 노가다이다.6.2. Prime-Representing Constant
[math(\displaystyle f_1=\sum_{n=1}^\infty \frac{p_n-1}{\displaystyle \prod_{m=1}^{n-1}p_m}\approx 2.920050977316)]를 Prime-Representing Constant라고 한다.x보다 크지 않은 최대의 정수를 [math(leftlfloor x rightrfloor)]라 할 때, 다음과 같은 점화식
[math(f_{n+1}=\left\lfloor f_{n} \right\rfloor(\left\lfloor f_{n} \right\rfloor-f_{n}+1))]에 의해
[math(\displaystyle f_k=\sum_{n=k}^\infty \frac{p_n-1}{\displaystyle \prod_{m=k}^{n-1}p_m}=p_k-1+\frac{p_{k+1}-1}{p_{k}}+\frac{p_{k+2}-1}{p_{k}p_{k+1}}...)]이 되므로
[math(\left\lfloor f_k \right\rfloor=p_k)]
초항을 구할 때 소수가 들어갔으니 윌런스의 공식보다도 실용적인 의미는 없으나, 이걸로 증명되는 데 5년이나 걸렸던 베르트랑-체비쇼프 정리[3]를 단번에 증명가능하다.
7. 목록
- [math(x^2-x+41)][4]
- [math(x^2+x+17)][5]
- [math(2x^2+29)][6]
- [math(2x^2+2x+19)][7]
- [math(4x^2+4x+59)][8]
- [math(4x^2+170x+1847)]
[1] 각각 [math(t=0)]일 때와 [math(t=79)]일 때. 이는 이차방정식 [math(t^2-79t=0)]의 두 근이다.[2] 처음부터 [math(t^2-79t=0)]으로 전제했으므로 이는 당연한 결과이다.[3] 2 이상의 정수 [math(n)]에 대하여, [math(n<p<2n)]을 만족하는 소수 [math(p)]가 존재한다는 정리. '1보다 큰 임의의 실수 [math(r)]에 대하여, [math(n<p<rn)]을 만족하는 소수 [math(p)]와 충분히 큰 정수 [math(n)]이 존재한다'는 변주도 있다.[4] [math(x)]에 [math(1)]부터 [math(40)]까지 대입했을 때 모두 다른 소수가 나온다.[5] [math(x)]에 [math(0)]부터 [math(15)]까지 대입했을 때 모두 다른 소수가 나온다.[6] [math(x)]에 [math(0)]부터 [math(28)]까지 대입했을 때 모두 다른 소수가 나온다.[7] [math(x)]에 [math(0)]부터 [math(17)]까지 대입했을 때 모두 다른 소수가 나온다.[8] [math(x)]에 [math(0)]부터 [math(13)]까지 대입했을 때 모두 다른 소수가 나온다.