메르센 소수

 


1. 개요
2. 역사
3. 메르센 소수의 예
3.1. 작은 메르센 소수
3.2. 큰 메르센 소수


1. 개요

메르센 수 M(n)은 2n -1 형태의 수를 말한다.[1] 메르센 소수는 메르센 수 중 소수인 것들을 가리킨다. M(n)이 메르센 소수이면 n도 소수이다. 하지만 역으로 n이 소수라고 해서 항상 M(n)도 소수인 것은 아니다. 처음 네 개, 즉 n=2, 3, 5, 7일 때는 성립하지만 211 -1=2047=23×89이고, 223 -1=8388607=47×178481인 것이 함정.
참고로 n이 합성수인 경우, n=mk(m, k는 각각 2 이상의 자연수)라 하면 2n-1=(2m-1)(2(k-1)m+2(k-2)m+...+2m+1)이고 여기서 m, k는 2 이상의 자연수라고 했으므로 (2m-1), (2(k-1)m+2(k-2)m+...+2m+1)은 각각 2 이상의 자연수이다. 따라서 2n-1은 합성수이다. n=1일 경우에도 21-1=1이니 소수가 아니다.
2진법으로 나타낼 경우 1이 늘어선 형태를 하게 되며, 늘어선 1의 개수는 언제나 소수다.
메르센 소수는 짝수인 완전수와 일대일 대응한다.[2] 그 수가 유한인지 무한인지는 알려지지 않았지만, 2018년 12월 현재 메르센 소수는 51개가 알려졌다.
M(3), M(7), M(31), M(127)의 경우처럼 2에 메르센 소수를 제곱한 뒤에 1을 빼서 나온 소수는 “이중 메르센 소수”라 하며, 총 4개가 발견되었다. M(7)은 삼중 메르센 소수이기도 하고, M(127)은 사중 메르센 소수이기도 하다.

2. 역사

프랑스의 수도자이자 수학자인 마랭 메르센(1588~1648)은 M(n)이 소수가 되도록 하는 258 미만의 수는 n=2, 3, 5, 7, 13, 17, 19, 31, '''67''', 127, '''257'''이 전부라고 생각하였다. 하지만 그가 이 수들이 소수인지를 전부 확인해 본 것은 아니었고, 틀린 것과 빠진 것이 있었다. 후에 M(67)과 M(257)은 소수가 아닌 것으로 판명되었고, 대신 M(61), M(89), M(107)이 추가되어 1947년에 n=2, 3, 5, 7, 13, 17, 19, 31, '''61, 89, 107''', 127인 경우가 소수임을 확인했다.
M(31) = 2147483647[3]이 소수임을 1772년 레온하르트 오일러가 증명했다. 1876년 루카스가 M(127)이 소수라고 확인하기 전까지는, M(31)은 알려진 소수들 중 가장 큰 수였다. 1883년 페르보차인이 M(61)이 소수임을 증명했는데, 이것이 메르센이 빠뜨린 것이었다. 이후 파우어스가 M(89), M(107)이 소수라는 사실도 확인했다.
1903년, 미국 수학자 학회에서 넬슨 콜이라는 교수가 "큰 수의 소인수분해"라는 강연을 했다. 그는 아무 말 없이 267-1을 칠판에 쓴 후 계산해서 147,573,952,589,676,412,927을 얻었다. 그리고 다른 쪽 칠판에 193,707,721 x 761,838,257,287을 계산해서 똑같은 값인 147,573,952,589,676,412,927을 얻었다. 그는 강의 도중 한 마디도 하지 않았지만 계산이 끝나자 온 강의실이 박수 갈채로 매워졌다. 당시에 컴퓨터는커녕 그럴 듯한 계산기도 없었다는 사실을 생각하면...
그래도 메르센의 방법을 응용하면 큰 소수를 찾는 데 유용하게 쓸 수 있다. 예를 들어 현대적인 암호체계는 크고 아름다운 소수를 사용하는데, 여기서 소수를 찾는 데 사용하는 페르마의 소정리는 메르센의 식에서 -1을 이항한 것이라 보면 된다.
컴퓨터가 발전한 덕에 메르센 소수를 찾기가 급격히 진행되었다. 1952년 컴퓨터의 도움을 받아 M(521), M(607), M(1279), M(2203), M(2281) 등이 우수수 발견되었고, 1992년 32번째 메르센 소수인 M(756,839)이 발견되어 10만 자리(정확히는 227,832자리)를 돌파하였다. 그리고, 1999년에는 M(6,972,593)이 발견되면서 백만 자리(정확히는 2,098,960자리)를 돌파하였다.
2008년 8월 23일 UCLA 수학과의 Edson Smith가 M(43,112,609)을 발견하여 1천만 자리를 돌파하였다. 발견 당시는 45번째였으나, 이후에 이보다 작은 수가 2개나 더 발견되어 크기순으로 47번째(추정)으로 순서가 조정되었다. 참고로 2017년 기준 45번째 메르센 소수인 M(37,156,667)까지는 모두 검증이 끝났다. 이보다 큰 소수에 대해서는 미발견된 메르센 소수가 있는지는 아직 확인되지 않았기에, 순서가 확정되지 않았다. 2018년 4월 47번째로 확정되었다.
2013년 1월 25일 Curtis Cooper 교수가 이끄는 연구팀이 M(57885161)을 발견하였고, 48번째(추정) 메르센 소수로 기록되었다. 17,425,170자리의 수이며, 당시에는 그때까지 알려진 가장 큰 소수였다. #
2016년 1월 7일 역시 Cooper교수의 연구팀이 M(74207281)를 발견했다. 22,338,618자리 수이며, 3003으로 시작해서 6351로 끝난다.
2017년 12월 M(77232917) 가 발견되었다. 23,249,425자리 이며, 50번째 메르센 소수로 추정중이다.
2018년 12월 M(82589933) 이 발견되었다. 24,862,048자리 이며, 51번째 메르센 소수로 추정중이다.
참고로 GIMPS에서는 메르센 소수 발견자에게 포상금을 지급하는데, 최초로 1천만 자리를 넘는 소수를 발견한 Edson Smith가 속한 UCLA 수학과에 5만 달러를 지급했다. 1억 자리를 넘는 소수에 대해서도 새롭게 5만 달러 포상금을 걸었다. 또한, 새로운 메르센 소수를 발견할 때마다 포상금 3천 달러를 지급한다.

3. 메르센 소수의 예

이곳에 가면 모든 예시를 확인할 수 있다.

3.1. 작은 메르센 소수

손가락 뒤의 수는 일대일 대응되는 완전수이다
  • M(2) = 3 ☞ 6
  • M(3) = 7 ☞ 28
  • M(5) = 31 ☞ 496
  • M(7) = 127 ☞ 8,128
  • M(13) = 8,191 ☞ 33,550,336
  • M(17) = 131,071 ☞ 8,589,869,056
  • M(19) = 524,287 ☞ 137,438,691,328
  • M(31) = 2,147,483,647 ☞ 2,305,843,008,139,952,128
  • M(61) = 2,305,843,009,213,693,951 ☞ 2,658,455,991,569,831,744,654,692,615,953,842,176 [참고]

3.2. 큰 메르센 소수

순서에 (추정)이 붙은 이유는 이보다 작은 수들에 대해서 완전히 검증이 끝나지 않았기 때문이다. 실제로 M(43112609)가 발견되었을 때는 45번째로 추정되었지만, 바로 한 달 뒤에 M(37156667)가 발견되었고, 그 다음해에도 M(42643801)가 발견되어 순서를 재조정했다.
  • M(32582657) - 약 980만 자리. 44번째 - 1천만 자리에서 2% 모자란 덕분에 1천만 자리 소수 상금 획득에는 실패했다.
  • M(37156667) - 약 1118만 자리. 45번째 - 이보다 작은 모든 메르센 소수 후보는 모두 검증이 끝났기에 공식적으로 45번째로 확정되었다.
  • M(42643801) - 약 1283만 자리. 46번째
  • M(43112609) - 약 1297만 자리. 47번째 - 앞의 소수 2개보다 먼저 발견되었기에, 최초로 발견된 1천만 자리가 넘는 소수로 기록되었다.
  • M(57885161) - 약 1754만 자리. (48번째 추정)
  • M(74207281) - 약 2200만 자리. (49번째 추정) - 최초로 2천만 자리를 넘는 소수. 위에 언급한 대로 2016년 1월에 발견되었다.
  • M(77232917) - 약 2324만 자리. (50번째 추정) - 2017년 12월 26일에 발견되었고 검증 작업은 2018년 1월 3일에 종료.
  • M(82589933) - 약 2486만 자리. (51번째 추정) - 2018년 12월에 발견되었다.

[1] 메르센 수 중에 최초의 과잉수는 m(12)=212-1=4095로 진약수의 합은 4641이다.[2] 2p -1 이 소수일 때 2p-1 ×(2p -1)은 짝수 완전수가 되고, 역도 성립한다.[3] 프로그래밍 을 할 줄 알면 익숙한 그 수. 변수 타입 중 자주 쓰는 정수형의 표현 가능 범위가 –2,147,483,648에서 2,147,483,647이다. 크기가 32비트이고 부호 표시를 제외하면 31비트이므로 2의 31제곱까지 표현이 가능하다. 오버플로 문제와 관련이 있기 때문에 익숙한 것.[참고] 37자리 수라서 일상적인 수까지는 엄청 큰게 맞으나 아래를 보면 코딱지만큼 보일 것 이다

분류