메르센 소수

메르센 수 $M_n$은 $2^n-1$ 꼴의 수를 의미하고, 메르센 소수는 $2^2-1=3$과 같이 메르센 수 중 소수인 수들을 뜻한다. 메르센 소수는 주로 큰 소수를 찾기 위해 탐색하는 유형의 수들이고, 그런 만큼 현재까지 발견된 가장 큰 5개의 소수까지는 모두 메르센 소수이다.

메르센 소수라는 이름은 17세기의 수학자 겸 철학자 마랭 메르센에서 유래하였다. 메르센은 1644년 한 가지 가설을 냈는데, 그 내용은 $n$이 257 이하일 때 $2^n-1$이 소수가 되는 경우는 $n$이 2, 3, 5, 7, 13, 19, 31, 67, 127, 257인 경우뿐이라는 것이다. 지수가 19인 메르센 수까지는 이미 알려져 있는 소수들이였고, $M_{31}$[1]이 소수라는 것까지는 사실이었지만 그 이후로는 정확성이 매우 떨어졌다. 애초에 메르센도 이것을 어떻게 알아냈는지에 대해 자세히 설명하지 않았고, 17세기 당시에는 컴퓨터 등 검증할 수단이 없었거나 발달하지 않았던 시대였으니 정확히 확인하기는 어려웠다. 지수가 61, 89, 107인 경우가 목록에서 빠져 있었고, 67, 257의 경우는 소수가 아님에도 포함되어 있다는 부분이 있었다.

1772년에 레온하르트 오일러에 의해 $M_{31}$이 소수임이 증명되었고, 100년이 넘는 기간 동안 가장 큰 메르센 소수의 자리를 지키다 에두아르 뤼카(Édouard Lucas)가 1876년에 $M_{127}$가 소수임을 증명했다. 그는 $M_{67}$이 소수가 아니라는 사실 또한 밝혀냈는데, 소인수를 찾아내지는 못했다. 그 뒤 1903년에 프랭크 넬슨 콜이 '큰 수의 소인수분해'라는 강연을 열었다. 미국 수학자 협회 회의실에서 그는 먼저 $M_{67}$(147573952589676412927)을 써 내려갔다. 그 다음 $M_{67}$의 두 소인수(193707721, 761838257287)를 적은 후, 거의 한 시간 동안 아무 말도 하지 않고 두 소인수를 곱해 M67과 같은 수를 얻었고, 그의 청중들은 우레 같은 박수를 보냈다. 이것을 증명하는 데에는 꼬박 3년 간의 일요일이 걸렸다고 한다. 1883년 이반 페르부신(Ivan Pervushin)이 $M_{61}$, 1911년과 1914년에 랄프 어니스트 파워스(Ralph Ernest Powers)가 각각 $M_{89}$와 $M_{107}$를 발견함으로써 메르센의 추측에서 빠졌던 부분들이 모두 채워졌다.

1952년부터는 컴퓨터의 발달로 인해 메르센 소수 탐색에 속도가 붙기 시작했으며, 1952년 한 해에만 $M_{521}$, $M_{607}$, $M_{1279}$, $M_{2203}$, $M_{2281}$이 줄줄이 발견되었다.

1996년에는 GIMPS가 창설되어 더뎌지던 메르센 소수 탐색을 다시 한 번 가속화시켰고, 같은 해 11월 13일에 발견된 $M_{1398269}$를 시작으로 지금까지 발견된 모든 메르센 소수는 GIMPS에 의해 발견되었다.

2008년 8월 23일에 $M_{43112609}$가 발견되었다. 이는 최초로 발견된 천만 자리를 넘는 소수로, 최초로 천만 자리를 넘는 소수의 발견자에게 10만 달러의 상금을 지급하기로 되어 있었다. 그러나 같은 해 9월 6일에 천만 자리를 넘는 또 다른 소수인 $M_{37156667}$이 발견되어 고작 2주 차이로(!) 상금을 놓치게 되었다. 또한 $M_{43112609}$는 발견 당시 45번째 메르센 소수였는데, 더 작은 소수가 발견되어 순서를 조정할지에 대한 의견이 오간 후 46번째로 조정되었다. 그러나 재미있게도 2009년 6월 4일 $M_{42643801}$이 발견되어 $M_{43112609}$는 47번째로 다시 한 번 순서가 조정되었다.

2018년에는 GIMPS에서 여태 사용하던 LL(Lucas-Lehmer) 테스트 대신 PRP(probable prime)테스트를 소수 판별에 사용하기 시작했다. 2024년 10월 12일, 처음으로 PRP 테스트로 메르센 소수가 발견되었는데 $M_{136279841}$으로, PRP를 사용하기 시작한 지 6년 만에 발견되었고, 이후 발견된 메르센 소수는 아직까지 없다.

2026년 4월 11일 기준으로 $M_{80253427}$ 이하인 메르센 수는 모두 소수 판별 검사가 완료되고 승인되었으며 $M_{139760749}$ 이하인 메르센 수는 모두 한 번 이상 소수 판별 검사가 진행되었다. $M_{140000000}$ 이하의 메르센 수가 모두 한 번 이상 소수 판별 검사가 진행된 상태가 되기까지 단 1개[2]만의 검사를 남겨 놓은 상태이기도 하다.