메르센은 소수를 찾는 유용한 방법을 찾는다. 먼저 소수는 아래와 같은 꼴일 것으로 추측했다.
$$M(n)=2^n-1$$
이 수를 메르센 수(Mersenne numbers)라고 한다. 메르센 수 $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년, 미국 수학자 학회에서 넬슨 콜이라는 교수가 "큰 수의 소인수분해"라는 강연을 했다. 그는 아무 말 없이 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
www.mersenne.org
