소수를 찾아 떠나는 여행

차례

 

초등학교에서 소수를 배운다. 여기서 소수는 1보다 큰 자연수 중 1과 자기 자신만을 약수로 가지는 수를 일컫는다. 한자로 素數라 쓰고 사잇소리를 넣어 ‘소쑤’라 읽는다. 문화어로는 ‘씨수’, 영어로는 prime number다. 한자인 素는 물들이지 않은 명주실을 뜻하는 글자로 바탕이나 처음을 뜻한다고 한다. prime은 으뜸, 첫째를 뜻하는 라틴어 primus에서 온 말이니 문화어 ‘씨수’가 뜻이 제법 와닿는다. 이제 우리나라에서 한자는 생명을 다하는 느낌이다. 아무튼 말은 달라도 부르는 이름에서 소수가 상당히 중요한 무엇임을 느낄 수 있다.

우리는 대부분 소인수분해를 쉽게 여긴다. 1272와 1271을 소인수분해 해보자. 차이는 1이지만 난이도는 완전 다르다.  소수를 찾는 규칙이 없어서 어떤 수를 소인수 분해 하는 일은 가볍게 인간의 능력을 벗어난다. 소수를 찾는 과정에서 수학자들은 기쁨과 좌절을 반복하였다. 소수를 찾아 떠난 수학자들이 남긴 발자취를 정리해 둔다.

에라토스테네스의 체

에라토스테네스의 체는 소수를 찾는 방법으로 가장 오래된 방법이다. 어쩌면 유일한 방법이다. 방법은 간단하다.

2를 남기고 나머지 2의 배수를 지우다. 3을 남기고 나머지 3의 배수를 지운다.

소수 P를 남기고 나머지 p의 배수를 지운다.

위키백과에서

에라토스테네스가 관장이었던 알렉산드리아 도서관

유클리드 원론에 소수는 무한함을 보이는 증명이 있다. 귀류법을 쓴 이 증명은 수학사에서 아름다운 증명으로 꼽힌다.(a가 n의 약수일 때 기호로 $a\mid n$으로 적고 약수가 아닐 때는 $a \nmid n$으로 적는다.

정리 소수는 무한하다.

증명 소수가 유한하다고 하고 $p_n$이 마지막 소수라고 하자.

아래와 같은 합성수를 생각하자.

$$P=p_1 p_2 p_3 \cdots p_n +1$$

$P>1$이므로 소인수 $p$를 가진다고 하면 $p=p_k \;(1\leq k \leq n)$이다.

$p|P$이고 $p|p_1 p_2 p_3 \cdots p_n$이므로 $p|P-p_1 p_2 p_3 \cdots p_n$이다.

$p|1$이므로 모순이다.

따라서 소수는 무한하다.

유클리드 수

이제 $p^\#$을 소수 $p$와 같거나 작은 모든 소수를 곱한 수라고 정의하자.

증명 과정에 나오는 $p^\# + 1$을 '유클리드 수(Euclidean numbers)로 부른다.

$\displaystyle{p^\# =\prod_{p\in S}p=\prod_{i=1}^{n}p_i}$라고 표현하기도 한다.

$$\begin{split}2^\# +1&=3\\3^\# +1&=2\cdot 3 +1=7\\5^\# +1 &=2\cdot 3\cdot 5 +1=31\\7^\# +1&=2\cdot 3\cdot 5\cdot 7 +1=211\\11^\# +1&=2\cdot 3\cdot 5\cdot 7 \cdot 11+1=2311\end{split}$$

은 소수이지만 아래는 소수가 아니다.

$$\begin{split}13^\# +1&=59\cdot 509\\17^\# +1&=19\cdot 97\cdot 277\\19^\# +1&=347\cdot 27953\end{split}$$

여기에 아직 답이 알려지지 않은 한 가지 물음이 있다.

$p^\# + 1$이 소수가 되는 소수 $p$는 무한한가? 합성수가 되는 소수는 무한한가?

$p^\# +1$이 소수임이 밝혀진 소수 18개가 있다. 

$$p=2,3,5,7,11,31,379,1019,1021,2657,3229,4547,11549,13649,18523,23081,204049$$

마지막 수는 1995년에 찾아냈는데 자릿수가 무려 $10387$이나 되는 엄청나게 큰 수이다. $p\leq 35000$일 때 나머지는 모두 합성수임이 알려져 있다.

본즈 부등식

다음과 같은 수열을 생각하자.

 

$$\begin{split}n_1&=2\\n_2&=n_1 +1\\n_3&=n_1 n_2 +1\\n_4 &=n_1 n_2 n_3 +1\\ &\vdots \\ n_k&=n_1 n_2 n_3 \cdots n_{k-1}+1\\ &\vdots\end{split}$$

$n_k >1$이므로 소인수를 가진다. 하지만 둘 이상의 $n_k$가 공통된 소인수를 가지지 않는다.

왜냐하면 $d=gcd(n_i , n_k)\;\;\;(i<k)$라고 하면 $d|n_k ,d|n_1 n_2 \cdots n_{k-1}$이므로 $d|1$이다.

따라서 $n_k$는 모두 서로소이다.

$n$번 째 소수를 $p_n$으로 나타낸다면 유클리드 증명에서 $p_1 p_2 p_3 \cdots p_n +1$이 소인수를 가진다면 새로운 소수 $p_{n+1}$이 있다는 것이다. 또 $p_{n+1}$는 $p_1 p_2 p_3 \cdots p_n +1$을 초과할 수 없다.

$$p_{n+1}\leq p_1 p_2 p_3 \cdots p_n +1\quad \quad \quad n\geq 1$$

다시 적으면

$$p_{n}\leq p_1 p_2 p_3 \cdots p_{n-1} +1\quad \quad \quad n\geq 2$$

이고

$$p_{n}\leq p_1 p_2 p_3 \cdots p_{n-1} -1\quad \quad \quad n\geq 3$$

$n=5$라면 아래와 같다.

$$11=p_5 \leq 2\cdot 3\cdot 5\cdot 7 -1=209$$

본즈 부등식(Bonse's inequality)에 의하여

$${p_{n} }^2 <p_1 p_2 p_3 \cdots p_{n-1}\quad \quad \quad n\geq 5$$

${p_{5}}^2 <210$이므로 $p_5 \leq 14$이다. 소수를 찾는 더 좋은 부등식은 아래와 같다.

$$p_{2n}=p_2 p_3 \cdots p_n -2\quad\quad n\geq 3$$

$$p_5 <p_6 \leq p_2 p_3 -2 =3\cdot5 -2=13$$

참고

http://en.wikipedia.org/wiki/Bonse's_inequality

Bonse's inequality - Wikipedia

http://en.wikipedia.org/wiki/Prime_number

Prime number - Wikipedia

 

 

메르센의 소수

메르센은  소수를 찾는 유용한 방법을 찾는다. 먼저 소수는 아래와 같은 꼴일 것으로 추측했다.

$$M(n)=2^n-1$$

이 수를 메르센 수라고 한다.  메르센 수 $M(n)$이 소수이면 $n$은 소수이다. 하지만 역은 성립하지 않는다. $n$이 소수라고 해도 $M(n)$이 소수인 것은 아니다.

$n=pq$이면 $M(ab)$는 합성수임을 보이자.

메르센 수는 이항정리로 나타낼 수 있다.

$$M(n)=\sum_{k=0}^n \pmatrix{n\\k}-1$$

이항정리를 이용하여 인수분해를 하면 아래와 같다.

$$\begin{split}a^n-b^n &=a^n+\sum_{k=1}^{n-1}a^{k} b^{n-k}-\sum_{k=1}^{n-1} a^k b^{n-k} - b^n\\&=\sum_{k=0}^{n-1} a^{k+1} b^{n-1-k}-\sum_{k=0}^{n-1}a^k b^{n-k}\\&=(a-b)\sum_{k=0}^{n}a^k b^{n-1-k}\end{split}$$

$a=2^p, b=1, n=q$라고 하면

$$\begin{split}2^{pq}-1&=(2^p -1)\sum_{k=0}^{q-1}2^{kp} \\&=(2^p -1)(1+2^p+2^{2p}+2^{3p}+\cdots+2^{(q-1)p})\end{split}$$

메르센은 메르센 수에서 차례대로 소수인 것을 찾아 나갔다.

$n<258$일 때, $M(n)$이 소수가 되는 것은 $n=2, 3, 5, 7, 13, 17, 19, 31, 67, 127, 257$이 전부라고 생각하였다. 하지만 훗날 $M(67)$과 $M(257)$은 소수가 아닌 것으로 판명되었고, 대신 $M(61), M(89), M(107)$이 추가되었다. 

1903년, 미국 수학자 학회에서 넬슨 콜이라는 교수가 "큰 수의 소인수분해"라는 강연을 했다.
그는 아무 말 없이 $2^{267}-1$을 칠판에 쓴 후 계산해서 147,573,952,589,676,412,927을 얻었다.
그리고 다른 쪽 칠판에 193,707,721×761,838,257,287을 계산해서 똑같은 값인 147,573,952,589,676,412,927을 얻었다. 그는 강의 도중 한 마디도 하지 않았지만 계산이 끝나자 온 강의실이 박수갈채로 메워졌다. 나무위키

1947년에 $n< 258$일 때, $n=2, 3, 5, 7, 13, 17, 19, 31, 61, 89, 107, 127$인 경우가 소수임을 확인했다. 

1957년 스웨덴 수학자 한스 리젤(Hans Ivar Riesel: 1929.5.28.–2014.12.21.)은 컴퓨터(BESK)를 사용하여 18번째 메르센 소수를 찾았다. $2^{3217}-1$는 969자리 수이다.

컴퓨터가 발전하면서 이제 메르센 소수를 찾는 일은 컴퓨터 공학이 되었다. 상금 10만 달러가 걸려 있으니 도전해 보시라. 

아래 링크를 따라가면 기록이 나온다. 가장 큰 소수는 2018년 12월 7일에 발견된 $2^{82589933}-1$인데 자릿수가 무려 2486만 2048자리다. 저 정도면 다 인쇄된 걸 본 사람도 몇 명 되지 않을 듯하다.

https://www.mersenne.org/primes/

List of known Mersenne prime numbers - PrimeNet

소수를 찾는 규칙이 있는가?

소수가 나타나는 규칙을 알기 위한 여러 가지 시도가 있다.

소수 나선

수 나선은 가느다란 띠에 음이 아닌 정수를 차례로 쓰고 0을 중심으로 말아서 만든다. 아래 그림과 같이 완전 제곱수($1,4,9,16,\cdots$)가 일렬로 놓이도록 놓을 수 있다.

조금 더 떨어져서 넓게 들여다본다면 아래와 같다.

숫자가 있는 자리에 점을 찍은 그림으로 나타내고 더 넓게 들여다보면 아래 그림과 같다. 아래 그림에 있는 점은 2026개이다.

이 그림에서 소수인 점을 소수가 아닌 점보다 진하게 표시해 보자.

소수가 어떤 곡선에 가까이 붙어 있는 것처럼 보인다. 더 잘 보이도록 점을 46,656개를 찍어서 그린 그림은 아래와 같다.

북서 쪽이나 남서 쪽으로 휘는 파란색 곡선을 따라 소수가 있는 것처럼 보인다. 이 패턴에 대한 연구는 아래 링크를 통해 보면 된다. 이럴 줄 알았으면 정수론을 열심히 공부할 걸 그랬다. 그다지 재미없는 과목처럼 생각했는데 알면 알수록 재밌는 것이 많다.

1772년 오일러가 발견한 소수를 생성하는 식은 $x^2 +x+41$이다.

 

numberspiral.com/index.html

NumberSpiral.com - Home

울람의 나선

소수 나선으로 더 알려진 것은 울람의 나선이 있다. 수학자 회의에 참석한 울람이 지루함을 달래려고 나선 모양으로 나열한 자연수에서 소수를 찾아 색을 칠했다. 뜻밖에 소수가 나타나는 자리가 대각선과 연관이 있지 않을까 생각했다고 전해진다. 위에서 소개하고 있는 수 나선은 울람의 나선을 배치 조금 다르게 한 것으로 생각할 수 있다.

위키백과에서

 

가우스의 추측

카를 프리드리히 가우스는 수학의 왕자로 불린다. 가우스는 소수와 관련된 분야에서도 큰 발자국을 남긴다. 어린 가우스는 소수를 찾는 취미가 있었다. 1792년부터 1793년 사이에 수를 1000개 씩 끊어서 소수를 찾아 나갔다. 당연하게도 1 가까운 소수는 많지만 1에서 멀어질수록 소수는 적어진다. 하지만 특별한 규칙은 없다. 하지만 가우스는 규칙이 아닌 개수에 주목했다.

소수의 개수를 비율로 나타내면 $10^2$이하는 25개로 25%, $10^4$이하는 1229개로 12.29%, $10^6$이하는 78498개로 7.84%이다. 이렇게 얻은 결과를 바탕으로 정해진 수보다 작은 소수의 개수를 나타내는 함수를 만든다.  $n$보다 작은 소수의 개수는 $\displaystyle{\frac{n}{\ln n}}$에 한없이 가까워진다는 것이다.

겨우 15살이던 가우스는 발표하지 않았고 훗날 르장드르가 소수 정리를 발표하였다. 소수 정리는 $x$보다 작은 소수의 개수를 나타내는 함수를 $\pi(x)$라고 할 때 아래와 같이 표현된다.

$\displaystyle{\pi(x)\sim \frac{x}{\ln x}}$ 또는 $\displaystyle{\lim_{x\rightarrow \infty}\frac{\pi(x)\ln x}{x}=1}$

 

$n$	$n$보다 작은 소수의 개수	$$\frac{n}{\ln n}$$	오차(%)
500000	41556	41606.4	0.010
1000000	78501	78627.5	0.012
1500000	114112	114263.1	0.010
2000000	148883	149054.8	0.008
2500000	183016	183245.0	0.009
3000000	216745	216970.6	0.007

 

리만 가설

리만은 가우스의 제자이다. 리만은 천재 가우스도 인정한 엄청난 천재다. 그가 젊은 나이에 죽지 않았다면 가정부가 그가 남긴 자료를 불태우지 않았다면 수학자들은 훨씬 더 빨리 성취를 이룰 수 있었을 것이다. 그의 논문 <주어진 수보다 작은 소수의 개수에 대하여>에 아래와 같은 식이 등장한다.

$$\prod\frac{1}{1-\frac{1}{p^s}}=\sum\frac{1}{n^s}$$

좌변을 아래와 같이 적으면 그 유명한 제타 함수다. $\mathbb{P}$는 알려진 모든 소수의 집합이라고 하자.

$$\zeta(s)=\prod_{p\in \mathbb{P}}^{\infty}\frac{1}{1-p^{-s}}$$

리만은 논문 마지막에 아래와 같이 적었다. 이 논문은 월간지에 실린 아주 짧은 간단한 논문이다.

제타 함수의 자명한 영점은 실수부가 음의 짝수인 점이고 자명하지 않은 영점은 실수부가 1/2인 점이다. 모든 근이 이러할 것이라는 확신이 있다. 물론 이는 엄밀한 증명을 거쳐야 한다. 다만 본 논문의 주제에는 벗어나므로 헛되이 시간을 허비하는 것을 막고자 이쯤에서 다음으로 넘기기로 한다.

 

리만 가설이다. 페르마의 마지막 정리가 떠오르는 이야기다. 페르마의 마지막 정리는 증명되었지만 리만 가설은 아직 아무도 증명하지 못했다.

신기하게도 제타 함수의 함숫값은 원주율과 이어진다.

$$\zeta(2)=\frac{\pi^2}{6}$$

$$\zeta(4)=\frac{\pi^4}{90}$$

$$\zeta(6)=\frac{\pi^6}{945}$$

$$\zeta(8)=\frac{\pi^8}{9450} $$

소수와 원은 전혀 관계가 없어 보인다. 하지만 소수와 원 사이에 아직 아무도 모르는 연결 고리가 있는 모양이다. 소수를 찾아 떠난 여행은 아직 끝나지 않았다. 현대는 이제 컴퓨터 알고리즘의 시대다. 수학자들은 아직까지 소수를 찾는 완벽한 알고리즘을 찾지 못했다. 하지만 아주 큰 수의 소인수분해를 이용하여 절대로 깨지지 않는 암호체계를 만드는 알고리즘을 만들었다. 

수학자들은 도전을 멈추지 않을 것이다. 어쩌면 인공지능이 해결할 수도 있지 않을까?

참고

https://youtu.be/sD0NjbwqlYw

 

 

https://suhak.tistory.com/858

리만 제타함수로 $\sum_{n=1}^{\infty}\frac{1}{n^2}$ 계산하기