메르센 소수

1 개요

메르센 수 M(n)은 2n -1의 형태를 가지는 수를 말한다. 메르센 소수는 메르센 수 중 소수인 수를 가리킨다. M(n)이 메르센 소수이면 n도 소수이다. 하지만 역으로 n이 소수라고 해서 항상 M(n)도 소수가 되는 것은 아니다. 처음 네 개, 즉 n=2, 3, 5, 7일 때는 성립하지만 211 -1=2047=23×89이고, 223 -1=8388607=47×178481인 것이 함정.

메르센 소수는 짝수인 완전수와 일대일 대응한다[1]. 그 수가 유한인지 무한인지는 알려져 있지 않으며, 2015년까지도 50개가 채 되지 않는 메르센 소수가 알려져 있었다.

2 역사

프랑스의 수도사이자 수학자인 마랭 메르센(1588~1648)은 M(n)이 소수가 되도록 하는 258 미만의 수는 n=2, 3, 5, 7, 13, 17, 19, 31, 67, 127, 257이 전부라고 생각하였다. 하지만 그가 이 수들이 소수인지를 전부 확인해 본 것은 아니었고, 틀린 수와 빠진 수가 존재한다. 1947년이 되어서야 n=2, 3, 5, 7, 13, 17, 19, 31, 61, 89, 107, 127 이 전부임이 밝혀졌다.

M(31) = 2147483647[2] 이 소수라는 것은 1772년 레온하르트 오일러에 의해 증명되었다. 이 수는 1876년 루카스에 의해 M(127)이 소수임이 확인될 때까지 알려진 소수중 가장 큰 수가 되었다. 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을 이항한거라 보면 된다.

2008년 8월 23일 UCLA 수학과의 Edson Smith가 M(43112609)을 발견하였다. 크기 순서로는 47번째이나, 41번째인 M(24036583) 이후로 발견된 수들 사이에 메르센 소수가 존재하는지 아닌지는 확인되지 않았다.

2013년 1월 25일 Curtis Cooper가 M(57885161)을 발견하였고, 48번째(추정)로 기록될 예정이다. 17425170 자리의 수이며, 현재가지 알려진 가장 큰 소수이기도 하다. 현재 추가된 모양이다.

2016년 1월 7일 Curtis Cooper가 이끄는 연구팀이 M(74207281)를 발견하여 가장 큰 소수 기록을 갈아치웠다. 22,338,618 자리 수이며, 3003으로 시작해서 6351로 끝난다.

참고로 GIMPS 에서는 메르센 소수 발견자에게 포상금을 지급하는데, 최초로 1000만 자리를 넘는 소수를 발견한 Edson Smith가 속한 UCLA 수학과에 50000$가 지급되었다. 그리고, 1억 자리를 넘는 소수에 대해서도 새롭게 50000$의 포상금이 걸려 있다. 또한, 새로운 메르센 소수를 발견할 때마다도 3000$의 포상금을 지급한다.

3 메르센 소수의 예

3.1 작은 메르센 소수

  • M(2) = 3
  • M(3) = 7
  • M(5) = 31
  • M(7) = 127
  • M(13) = 8191
  • M(17) = 131071
  • M(19) = 524287
  • M(31) = 2147483647
  • M(61) = 2305843009213693951

3.2 큰 메르센 소수

순서에 (추정)이 붙은 이유는 이보다 작은 수들에 대해서 완전히 검증이 끝난게 아니기 때문이다. 실제로 M(43112609)가 발견되었을때는 46번째로 추정되었지만, 다음해 이보다 작은 M(42643801)가 발견되면서 순서가 재조정되었다.

  • M(37156667) - 약 1118만 자리. 45번째 (추정)
  • M(42643801) - 약 1283만 자리. 46번째 (추정)
  • M(43112609) - 약 1297만 자리. 47번째 (추정)
  • M(57885161) - 약 1754만 자리. 48번째 (추정)
  • M(74207281) - 약 2200만 자리. 49번째 (추정) 이다. 2016년 기준 발견된 가장 큰 소수이기도 하다.
  1. 2p -1 이 소수일 때 2p-1 ×(2p -1)은 짝수 완전수가 되며, 역도 성립한다.
  2. 프로그래밍을 할 줄 알면 익숙한 그 수. 변수 타입 중 자주 쓰는 정수형의 표현 가능 범위가 –2,147,483,648에서 2,147,483,647이다. 크기가 32비트이고 부호 표시를 제외하면 31비트이므로 2의 31승까지 표현이 가능하다. 오버플로 문제와 관련이 있기 때문에 익숙한 것.