오일러의 소수생성다항식 x²+x+41

개요

$x^2+x+41$는 정수 $-40\leq x\leq 39$ 에 대하여, 모두 소수가 된다
이 성질은 이차수체의 class number 개념을 사용하여 설명할 수 있다.
이와 비슷한 성질을 갖는 다항식으로 $x^2+x+2$, $x^2+x+3$, $x^2+x+5$, $x^2+x+11$, $x^2+x+17$가 있으며, 이 다항식의 근으로 생성되는, 이차수체는 모두 class number가 1이 된다.

증명

증명의 아이디어

자연수 n이 주어져 있을 때, n 이 소수인지 아닌지를 알려면 $\sqrt{n}$ 보다 작은 모든 소수로 나눠보아 나누어지지 않음을 확인하면 된다.
$0\leq x\leq 39$일 때, $x^2+x+41$가 소수가 아니라면, 반드시 41보다 작은 소수를 약수로 가져야 한다
41보다 작은 소수 p 에 대하여, 합동식 $x^2+x+41\equiv 0 \pmod p$ 가 해를 갖지 않음을 보이면 된다
- p는 {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37} 는 중의 하나
다음을 보이는 것으로 충분하다

(정리) 소수 $2\leq p \leq 37$에 대하여, $x^2+x+41$를 $p$로 나눈 나머지는 0이 될 수 없다

증명

$p=2$인 경우는 쉽게 증명된다.

소수 $2<p\leq 37$ 를 하나 고정시키자. $(\mathbb{Z}/p\mathbb{Z})^\times=\{1,2,\cdots, ,p-1\}$는 기약잉여계이므로, $2b\equiv 1 \pmod p$ 를 만족시키는 $b\in (\mathbb{Z}/p\mathbb{Z})^\times$는 반드시 존재한다. $$x^2+x+41\equiv (x+b)^2-b^2+41 \pmod p$$ 이므로, $x^2+x+41\neq 0 \pmod p$임을 보이기 위해서는, $b^2-41$이 소수 $p$에 대한 비이차잉여임을 보이는 것으로 충분하다. 르장드르 부호를 계산해보자. $$ \left(\frac{b^2-41}{p}\right)=\left(\frac{2^2}{p}\right)\left(\frac{b^2-41}{p}\right)=\left(\frac{(2b)^2-164}{p}\right)=\left(\frac{-163}{p}\right) $$ 이제 $2<p\leq 37$에 대하여, $$\left(\frac{-163}{p}\right)=-1$$ 만 확인하면 된다. $$ \begin{array}{c|c} p & \left(\frac{-163}{p}\right) \\ \hline 3 & -1 \\ 5 & -1 \\ 7 & -1 \\ 11 & -1 \\ 13 & -1 \\ 17 & -1 \\ 19 & -1 \\ 23 & -1 \\ 29 & -1 \\ 31 & -1 \\ 37 & -1 \\ \end{array} $$

자세한 사항은 파일:1989728-소수생성다항식.pdf 파일을 참조

UFD와의 관계

비슷한 예로, 아래는 정수 $0\le x\le q-2$ 일 때, $x^2+x+q$가 모두 소수인 경우
$x^2+x+2$, $x^2+x+3$, $x^2+x+5$, $x^2+x+11$, $x^2+x+17$

$\mathbb{Z}[\frac{-1+\sqrt{-7}}{2}]$

$\mathbb{Z}[\frac{-1+\sqrt{-11}}{2}]$

$\mathbb{Z}[\frac{-1+\sqrt{-19}}{2}]$

$\mathbb{Z}[\frac{-1+\sqrt{-43}}{2}]$

$\mathbb{Z}[\frac{-1+\sqrt{-67}}{2}]$

$\mathbb{Z}[\frac{-1+\sqrt{-163}}{2}]$

가 모두 UFD 라는 사실과 동치이다.

정수의 집합 $\mathbb{Z}=\{\dots, -3, -2, -1, 0, 1, 2, 3, \dots\}$으로 다시 돌아갑시다. 정수의 성질에 대해 연구하는(?) 수학의 분야인 정수론의 유명한 고전인 G.H.Hardy와 E.M.Wright의 “An Introduction to the Theory of Numbers“ 의 첫번째 정리는 “모든 1이 아닌 양의 정수는 소수들의 곱으로 쓰여진다” 입니다. 그리고 두번째 정리는 바로 “정수를 그렇게 소수들의 곱으로 표현하는 방법은 유일하다”입니다. 너무나도 자명하여, 이게 정리인지 아닌지조차 헷갈릴 정도입니다. 그러나 이 두번째 정리에는 “The Fundamental Theorem of Arithmetic”이라고 하는 멋진 이름이 붙어 있습니다. “산술의 기본 정리”라고 하면 될까요. 이렇게 그 안의 수들이 소수들로 유일하게 분해될 때, 수학자들은 그 녀석을 UFD(Unique Factorization Domain) 라고 부릅니다. “산술의 기본 정리”를 다른 말로 표현하면 “$\mathbb{Z}$는 UFD 이다” 가 되겠습니다. 그럼 이제 이 당연해 보이는 사실이 왜 자명하지 않은지에 대해 한번 이해를 해 볼 차례입니다.

이제 $\mathbb{Z}$가 아닌 $\mathbb{Z}[\sqrt{-5}]=\{a+b\sqrt{-5} \: : \: a,b \in \mathbb{Z}\}$라는 집합을 생각해 봅시다. 이 녀석 역시 정수처럼 더하기 곱하기가 그 안에서 잘 성립합니다. 가령,$1+\sqrt{-5}$과 $2-\sqrt{-5}$ 를 곱한다고 해 봅시다.

$(1+\sqrt{-5})(2-\sqrt{-5})=2+(2-1)\sqrt{-5}-(-5)=7+\sqrt{-5}$

한 집합에서 두 녀석을 뽑아서 곱했더니, 여전히 같은 집합에 있다는 것이 제가 곱하기가 잘 성립한다고 말하는 것입니다. 이제 $1+\sqrt{-5}$과 $1-\sqrt{-5}$ 를 곱해봅시다. 계산을 해 보면, 6을 얻게 됩니다. 2와 3을 곱해도 6을 얻게 됩니다.
그런데 사실, $\mathbb{Z}[\sqrt{-5}]$ 안에서, $1+\sqrt{-5}$ ,$1-\sqrt{-5}$,2,3 은 모두 소수 역할을 하는 녀석들입니다. 즉, 저 녀석들을 다른 수들의 곱으로 표현할 수 있는 방법이 없습니다. 6은 적어도 두가지 이상의 방식으로 소수들로 쪼개진다! 이 결과가 말하는 것은 바로 “$\mathbb{Z}[\sqrt{-5}]$ 는 UFD 가 아니다” 라는 것입니다.

자 이제 매우 중요한 결과를 하나 언급 해야겠습니다.\[x=0,1,2,\cdots, 39\] 일때, $f(x)=x^2+x+41$ 는 소수라는 사실은, $\mathbb{Z}[\frac {-1+\sqrt{-163}} {2}]=\{a+b\cdot \frac {-1+\sqrt{-163}} {2} \: : \: a,b \in \mathbb{Z}\}$이 UFD 라는 사실과 동치입니다.

매스매티카 파일 및 계산 리소스

사전형태의 참고자료

링크

피타고라스의 창

오일러의 소수생성다항식 x²+x+41

목차

개요

증명

증명의 아이디어

증명

UFD와의 관계

관련된 학부 과목과 미리 알고 있으면 좋은 것들

관련된 대학원 과목

관련된 항목들

매스매티카 파일 및 계산 리소스

사전형태의 참고자료

관련도서

관련논문

링크

둘러보기 메뉴

검색