소수생성다항식

1. 개요

---

prime generating polynomial · 素數生成多項式
소수생성다항식이란 말 그대로 소수를 생성해내는 다항식이다. 이는 함수(초등함수)로 간주할 수도 있다.

2. 예시

---

1772년, 스위스의 수학자 레온하르트 오일러가 고안한 소수생성다항식이 유명하다. 그 식은 $$f(x)=x^2+x+41$$인데, $$0\leq{x}\leq{39}$$인 정수 $$x$$에 대하여 $$f(x)$$의 값은 소수가 된다.

$$f(0)=41, f(1)=43, f(2)=47, f(3)=53, f(4)=61, f(5)=71$$ $$f(6)=83, f(7)=97, f(8)=113, f(9)=131, f(10)=151$$ $$f(11)=173, f(12)=197, f(13)=223, f(14)=251, f(15)=281$$ $$f(16)=313, f(17)=347, f(18)=383, f(19)=421, f(20)=461$$ $$f(21)=503, f(22)=547, f(23)=593, f(24)=641, f(25)=691$$ $$f(26)=743, f(27)=797, f(28)=853, f(29)=911, f(30)=971$$ $$f(31)=1033, f(32)=1097, f(33)=1163, f(34)=1231, f(35)=1301$$ $$f(36)=1373, f(37)=1447, f(38)=1523, f(39)=1601$$

나아가, $$f(x)=x^2+x+41$$에서 $$x$$ 대신 $$x-40$$을 대입하면 $$f(x-40)=x^2-79x+1601$$이 되는데, $$g(t)=t^2-79t+1601$$이라는 소수생성다항식에서는 $$0\leq{t}\leq{79}$$인 정수 $$t$$에 대하여 $$g(t)$$의 값은 소수가 된다.

3. 유의미한 소수생성다항식이 되기 위한 조건

---

유의미한 소수생성다항식을 만들기란 어렵다. 위에서 소개한 대로 40개, 80개의 연속된 정수에 대한 함숫값이 모두 소수가 되도록 하는 다항식을 고안하는 것은 더더욱 어렵다. 그러나 '다소 유의미한' 소수생성다항식의 조건을 이야기할 수는 있다. 여기에서는 소수생성다항식을 $$y=f(x)$$($$x$$는 '''음이 아닌 정수''')의 꼴로 놓고 설명한다.

3.1. 함숫값이 항상 홀수일 것

---

2를 제외한 모든 소수는 홀수인 이상, '여러 개의 소수'를 생성해내는, 제법 쓸모 있는 소수생성다항식은 일단 함숫값이 항상 홀수이고 봐야 한다. 자꾸 짝수가 나오면 곤란하다.
위에서 소개한 $$f(x)=x^2+x+41$$이나 $$g(t)=t^2-79t+1601$$은 함숫값이 항상 홀수가 된다. 각각 $$x(x+1)+41$$ 그리고 $$t(t-79)+1601$$로 나타낼 수 있는데, 1과 79가 홀수인 이상 $$x$$와 $$x+1$$ 중 하나는 홀수, 또 다른 하나는 짝수가 되고, $$t$$와 $$t-79$$도 마찬가지다. 그러므로 $$x(x+1)$$과 $$t(t-79)$$는 무조건 홀수와 짝수의 곱이므로 짝수가 되며, 여기에 각각 41과 1601이라는 홀수를 더하면 홀수가 될 수밖에 없다.

3.2. 함숫값의 일의 자리가 5가 되지 않을 것

---

함숫값의 일의 자리가 5라는 것은 그 값이 5의 배수임을 의미하며, 소수생성다항식의 성능은 그에 발맞춰 떨어지는 셈이다. 따라서 함숫값의 일의 자리가 5가 나오지 않도록 하는 것도 훌륭한 소수생성다항식의 조건이다.
위에서 소개한 $$f(x)=x^2+x+41$$이나 $$g(t)=t^2-79t+1601$$은 함숫값의 일의 자리가 절대로 5가 되지 않는다.
우선, $$f(x)$$의 일의 자리가 5가 되려면 $$x^2+x=x(x+1)$$의 일의 자리는 4가 되어야 한다. 그러나

$$x$$의 일의 자리	$$x^2+x$$의 일의 자리
$$0, 4, 5, 9$$	[math(0)]
$$1, 3, 6, 8$$	$$2$$
$$2, 7$$	$$6$$

이렇게 되므로 $$x^2+x$$의 일의 자리는 4가 될 수 없고, $$f(x)$$의 일의 자리는 5가 될 수 없다.
마찬가지로, $$g(t)$$의 일의 자리가 5가 되려면 $$t^2-79t=t(t-79)$$의 일의 자리는 $$t^2-79t\geq0$$일 경우 4, $$t^2-79t<0$$일 경우 6이 되어야 한다. 그러나

$$t^2-79t>0$$		$$t^2-79t<0$$		$$t^2-79t=0$$
$$t$$의 일의 자리	$$t^2-79t$$의 일의 자리	$$t$$의 일의 자리	$$t^2-79t$$의 일의 자리	$$t$$의 일의 자리	$$t^2-79t$$의 일의 자리
$$0, 4, 5, 9$$	[math(0)]	$$0, 4, 5, 9$$	[math(0)]	$$0, 9$$[1]	[math(0)][2]
$$1, 3, 6, 8$$	$$2$$	$$1, 3, 6, 8$$	$$8$$
$$2, 7$$	$$6$$	$$2, 7$$	$$4$$

이렇게 된다. 다시 말해, $$t^2-79t>0$$이면 일의 자리가 0, 2, 6 중 하나이므로 4가 될 수 없다. $$t^2-79t<0$$이면 일의 자리가 0, 4, 8 중 하나이므로 6이 될 수 없다. $$t^2-79t=0$$이면 일의 자리가 무조건 0이므로 4가 될 수 없다. 따라서, $$g(t)$$의 일의 자리는 5가 될 수 없다.

4. 소수생성다항식은 만능인가

---

'''결론부터 말하자면 그렇지 않다.''' 위에서 소개한 소수생성다항식들도 결국 특정 값을 대입할 경우에만 소수가 생성될 뿐이다. 소수만을 찍어내는 만능제조기란 없다. 위에서 소개한 식을 고안한 오일러의 제자였던 아드리앵 마리 르장드르는 소수 함숫값만을 갖는 유리식이 존재하지 않음을 증명했고, 골드바흐는 소수 함숫값만을 갖는 정수계수 다항식이 존재하지 않음을 증명했다.

5. 차선책: 소수를 무한히 생성

---

눈을 낮추어 함숫값이 양수일 때만 소수가 된다든가, 더 낮추어 비율은 적지만 아무튼 무한히 많은 소수 함숫값을 갖는 다항식을 생각해볼 수 있다.

5.1. 디리클레 정리

---

우선 일차식($$ax+b$$, $$a \not= 0$$의 꼴)의 경우, $$ \gcd (a,b)>1$$이면 많아야 두 함숫값($$ \pm\gcd (a,b)$$)만 소수이다. 반면, $$ \gcd (a,b)=1$$이면 무한히 많은 $$x \in \mathbb{Z}$$에 대해 $$ax+b$$가 소수임이 알려져 있는데 이를 디리클레 정리라 한다.

5.2. 부냐콥스키 추측

---

소수를 무한히 생성하는 이차 이상의 다항식은 알려져 있지 않은데, 이에 착안하여 소수를 무한히 생성하는 이차 이상의 다항식이 없을 것이라는 것이 부냐콥스키 추측이다.

5.3. 윌런스의 공식

---

n번째 소수를 내놓는 이론적으로는 완벽한 소수생성 함수인데, 결과적으로는 에라토스테네스의 체보다도 비효율적이다.

6. 목록

---

• $$\displaystyle x^2-x+41$$ [3]
• $$\displaystyle 4x^2+4x+59$$ [4]
• $$\displaystyle 4x^2+170x+1847$$
• $$\displaystyle x^2+x+17$$ [5]
• $$\displaystyle 2x^2+29$$ [6]
• $$\displaystyle 2x^2+2x+19$$ [7]

[1] 각각 $$t=0$$일 때와 $$t=79$$일 때. 이는 $$t^2-79t=0$$이라는 이차방정식의 두 근이다.

[2] 처음부터 $$t^2-79t=0$$으로 전제했으므로 이는 당연한 결과이다.

[3] x에 1부터 40까지 대입했을 때 모두 다른 소수가 나온다.

[4] x에 0부터 13까지 대입했을 때 모두 다른 소수가 나온다.

[5] x에 0부터 15까지 대입했을 때 모두 다른 소수가 나온다.

[6] x에 0부터 28까지 대입했을 때 모두 다른 소수가 나온다.

[7] x에 0부터 17까지 대입했을 때 모두 다른 소수가 나온다.