메르센 소수

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

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

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

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

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

$$M(n)=\sum _{k=0}^n\left(\begin{array}{c}n\\ k\end{array}\right)-1$$

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

$$\begin{array}{rl}{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{array}$$

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

$$\begin{array}{rl}{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{array}$$

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

$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년, 미국 수학자 학회에서 넬슨 콜이라는 교수가 "큰 수의 소인수분해"라는 강연을 했다. 그는 아무 말 없이 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