[퍼온글] 소수(Prime number) 이야기

※ 출처 - http://kevin0960.tistory.com/

수학에서 소수란, $1$보다 큰 자연수 들 중에서 $1$과 자기 자신으로만 나누어 떨어지는 수를 가리키는 말이다. 무수히 많은 소수들이 있다는 것은 기원전 $300$년 경 위대한 그리스 수학자 유클리드에 의해 증명되었다. 처음 몇 개의 소수들을 나열해 보자면

\[ 2,\, 3,\, 5,\, 7,\, 11,\, 13,\, 17,\, 19,\, 23,\, 29,\, 31,\, 37,\, 41,\, 43,\, 47,\, 53,\, \ldots \]

와 같다.  

소수에 대한 연구는 정수론에 많은 부분을 차지 하고 있다. 소수에 대해 많은 수학자들이 연구를 하였고, 아직도 몇 가지 기본적인 질문들을 해결하지 못한 것 들이 있다. 예를 들어 리만 가설(Riemann hypothesis)이나 골드바흐 추측(Goldbach conjecture)등은 아직도 몇 세기 동안 해결되지 못한 것들이다. 소수의 빈도수 또한 정수론 학자들에게는 매우 인기있는 주제이기도 하다. 

소수의 역사

<< 유클리드 (Euclid) >>

이집트인들의 기록을 살펴보자면 그들이 소수에 대한 약간에 지식이 있었던 것으로 보인다. 예를들어 Rhind papyrus에는 여러가지 소수들과 합성수 들이 쓰여져 있었다. 그러나 실질적으로 소수에 대한 연구가 시작된 것은 고대 그리스 부터였다. 유클리드(Euclid)가 저술한 원론(기원전 300년)에서는 몇 가지 기본적이고 중요한 증명들이 있는데 예를들면 소수의 무한성도 그 중 하나였다. 또한 유클리드는 Mersenne 소수로 부터 어떻게 완전수를 만들 수 있는지도 보였다. 

에라토스테네스(Eratosthenes)가 고안한 에라토스테네스 체(Sieve of Eratosthenes)는 소수를 찾기에는 가장 간단한 방법이지만 현재 큰 소수를 찾는 컴퓨터는 이 알고리즘은 택하지 않았다. 그리스 이후 17세기까지 소수에 대한 연구는 큰 진보를 하지 않았으나 다음과 같은 사실이 발견되었다. 

 

<< 페르마 (Pierre de Feramt) >>

1640년 피에르 데 페르마 (Pierre de Fermat) 는 그의 페르마 소정리 (Fermat's little theorem)를 발견하였고, 이는 후에 라이프니츠(Leibnitz)와 오일러(Euler)에 의해 증명되었다. 참고적으로 페르마 소정리의 특정 부분은 훨씬 전부터 중국에서도 알려져 있었다. 페르마는 $n=4$일때 까지를 검토해 본 후 모든 $2^{2^n} + 1$ 꼴의 수는 소수일 것이라고 추측하였으나 (이들을 페르마 수 라 부른다) 그 $54$번 째 페르마 수인 $2^{32}+1$은, 오일러의 노력에 의해 $641$의 배수임을 밝혀졌다.

<< 마린 메르센느(Marin Mersenne) >>

프랑스의 수도사 마린 메르센느(Marin Mersenne)는 $2^p - 1$ 꼴의 소수 ($p$는 소수)에 대한 연구를 하였고, 이 공로를 인정받아 $2^p - 1$ 꼴의 소수는 나중에 메르센느 소수라는 이름이 붙는다. 

 

<<오일러(Leonhard Euler) >>

오일러의 정수에 대한 연구는 소수에 대해 많은 결과를 낳았는데, 그는 다음과 같은 형태의 무한 급수 

\[ \frac{1}{2} + \frac{1}{3} + \frac{1}{5} + \frac{1}{7} + \frac{1}{11} + \cdots \]

가 발산함을 보여, 소수가 무한함을 유클리드와는 다른 방식으로 증명하였다. 또한 오일러는 $2^{p-1}(2^p - 1)$ 꼴의 수 (이 때, 두번째 항은 메르센느 소수) 들이 모두 유일한 짝수 완전수 꼴 임을 보였다. 하지만 현재까지도 홀수 완전수가 존재하는지 존재하지 않는지에 대한 어떠한 증명도 발견되지 않고 있다.

 

<< 르장드르(Adrien-Marie Legendre) >>

그 후 19세기 초에, 르장드르(Legendre)와 가우스(Gauss)는 독립적으로 $x$가 무한대로 발산할 때, $x$ 보다 작은 소수의 개수는 $x / \log(x)$ 와 같다는 사실을 발견하였다. 1859년에 리만은 그의 논문에서 제타 함수(zeta-function)에 대한 아이디어를 선보였다. 리만의 아이디어를 이용하여 1896년 아다마르(Hadamard)와 발레푸생(Vallée-Poussin)은 독립적으로 소수 정리를 증명하였다. 

이 후 수학자들은 매우 큰 수에 대하여, 이 수가 소수인지 아닌지 (짧은 시간에) 판단할 수 있는 방법을 모색했다. 이에 따라 1877년에는 페르마 소수들을 위한 Pépin's 테스트가, 1878년엔 Proth의 정리, 1856년엔 메르센느 소수들을 위한 Lucas–Lehmer 테스트 등이 발견되었다. 현대에 가장 많이 쓰이는 알고리즘으로는 APRT-CL, ECPP, AKS 등이 있지만 여전히 더 나은 알고리즘을 찾기 위해 많은 수학자들이 노력하고 있다.

오랜 시간동안 소수는 순수 수학 외에는 아무 쓸모가 없다고 판단되었으나, 1970년 발명된 RSA 암호 방식 (소인수 분해가 오랜 시간이 걸린다는 사실을 이용한 암호화 방식)을 통해 소수에 대한 생각이 완전히 바뀌게 되었다.

1 에대한 논란

19세기 까지 많은 수학자들은 $1$을 소수로 취급 했었다. Derrick Norman Lehmer의 소수리스트에도 1956년 까지 $1$을 소수로 취급해 소수가 $1$ 부터 나와있었다. 게다가  Stern과 Zeisel의 업적처럼 $1$을 소수로 간주하고 쌓은 많은 정리들이 있다. Henri Lebesgue은 $1$을 소수로 간주했던 마지막 수학자 였다. 

소수에 대한 여러가지 정리

다음은 소수에 대한 여러가지 정리 중 일부이다.

1. $10$ 이상의 모든 소수들은 일의 자리수가 $1$, $3$, $7$, $9$ 중 하나이다.
2. 만약 소수 $p$가 두 정수 $a$, $b$의 곱 $ab$를 나누면, $p \mid a$ 거나, $p \mid b$이다. 이는 유클리드의 보조정리에 나와 있으며 주어진 수의 소인수분해가 유일하다는 사실을 증명하는데 쓰인다.
3. $p$가 소수이고 $a$가 임의의 정수일때, $p \mid a^p − a$이다. (페르마 소정리)
4. $p$가 소수일때, $p \mid (p-1)! + 1$이다. (윌슨 정리)
5. $n$이 $1$ 보다 큰 정수일때, $n < p < 2n$ 을 만족하는 소수 $p$가 적어도 한 개 이상 존재한다. (베르트랑 공준, 쳬비셰프 정리)
6. 등차수열 $a,\, a + d,\, a + 2d,\, a + 3d,\, \ldots$ 에서 만약 $a$와 $q$가 서로소 이면 이 수열에는 무수히 많은 소수가 존재한다. (등차수열에 대한 디리클레 정리)
7. $x$가 충분히 큰 실수일 때, $x$ 이하의 소수의 수는 $x/\ln x$에 접근한다. (소수 정리)

소수를 찾는 공식 ? 

현재까지 소수를 효과적으로 찾는 공식은 존재하지 않는다. 예를들어 $f(n) = n^2 − n + 41$ 라는 함수는 $n$ 이 $0$ 부터 $40$ 까지의 결과값이 모두 소수이지만 $41$이나 $42$일 때 합성수이다. 참고로 아래의 26개의 변수를 갖는 14개의 디오판토스 방정식 또한 소수를 찾는데 사용될 수 있다. 1976년에 Jones, Sato, Wada, Wiens는 주어진 수 $k$가 아래 14개의 방정식을 모두 만족한다면 $k+2$는 소수임을 증명하였다. 그 방정식들은 다음과 같다.

\[ \begin{aligned} \alpha _{0} &= wz+h+j-q=0 \\ \alpha _{1} &= (gk+2g+k+1)(h+j)+h-z=0 \\ \alpha _{2} &= 16(k+1)^{3}(k+2)(n+1)^{2}+1-f^{2}=0 \\ \alpha _{3} &= 2n+p+q+z-e=0 \\ \alpha _{4} &= e^{3}(e+2)(a+1)^{2}+1-o^{2}=0 \\ \alpha _{5} &= (a^{2}-1)y^{2}+1-x^{2}=0 \\ \alpha _{6} &= 16r^{2}y^{4}(a^{2}-1)+1-u^{2}=0 \\ \alpha _{7} &= n+l+v-y=0 \\ \alpha _{8} &= (a^{2}-1)l^{2}+1-m^{2}=0 \\ \alpha _{9} &= ai+k+1-l-i=0 \\ \alpha _{{10}} &= ((a+u^{2}(u^{2}-a))^{2}-1)(n+4dy)^{2}+1-(x+cu)^{2}=0 \\ \alpha _{{11}} &= p+l(a-n-1)+b(2an+2a-n^{2}-2n-2)-m=0 \\ \alpha _{{12}} &= q+y(a-p-1)+s(2ap+2a-p^{2}-2p-2)-x=0 \\ \alpha _{{13}} &= z+pl(a-p)+t(2ap-p^{2}-1)-pm=0 \end{aligned}\]

큰 소수들

2007년 8월 현재 발견된 소수 중 가장 큰 소수로는 $2^{74,207,281} − 1$ 로 $22,338,618$ 자리나 된다. 2016년 1월 GIMPS (Great Internet Mersenne Prime Search) 프로그램을 통해 발견되었다. 특별히 메르센느 소수들만 찾는 이유는, Lucas–Lehmer 테스트가 메르센느 소수에 비교적 빠르게 적용되기 때문이다. 메르센느소수가 아닌 가장 큰 소수는 $19,249 \times 2^{13,018,586} + 1$로 $3,918,990$ 자리 이다. 

풀리지 않은 소수에 관련한 문제들

소수에 관련한 문제들은 무수히 많다. 먼저 그 유명한 리만 가설(Riemann hypothesis)이 있으며 이는 19세기 중반에 발표된 이래 이는 수학사의 주요 미해결 난제의 하나로 남아 있다. 또한 리만 가설은 힐베르트가 언급한 23개의 난제들 중 최고봉에 위치한 난제 중에 하나이다. 대개 유명한 추측들( 예를들어 골드바흐의 추측) 은 비록 증명되지는 않았지만 맞을 확률이 매우 높다. 

리만 가설외에도 다음과 같은 추측들이 있다.

1. 유클리드 소수(Euclid prime)의 무한성. 여기서 유클리드 수 $E_n$은 $E_n = p_n\sharp + 1$로 정의되는 수이다. (단, $p_n\sharp$ 은 $n$번째까지 모든 소수 들의 곱이다.)
2. 강한 골드바흐 추측 (Strong Goldbach conjecture). $2$보다 큰 모든 짝수는 $2$개의 소수의 합으로 표현할 수 있다. "$5$보다 큰 모든 홀수는 $3$개의 소수의 합으로 표현할 수 있다"는 정리인 약한 골드바흐 추측(Weak Goldbach conjecture)은 2013년 Harald Helfgott에 의해 참임이 증명되었다.
3. 쌍둥이 소수의 무한성. 쌍둥이 소수란 $p$, $p+2$가 모두 소수인 수를 말한다.
4. Polignac의 추측(Polignac's conjecture). 임의의 정수 $n$에 대하여 차이가 $2n$이 나는 소수들의 쌍이 무수히 많이 존재한다. $n=1$이면 쌍둥이 소수의 무한성에 대한 문제가 된다.
5. 메르센느 소수의 무한성. 이것이 증명되면 완전수의 무한성도 같이 증명된다.
6. $n^2 + 1$ 꼴의 소수의 무한성.
7. 르장드르의 추측 (Legendre's conjecture). $n^2$ 와 $(n + 1)^2$ 사이엔 소수가 적어도 한 개 이상 존재한다.