메르센 소수

덤프버전 :



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



1. 개요[편집]


메르센 수 [math(M(n))]은 [math(2^n-1)] 형태의 수를 말한다.[1] 메르센 소수는 메르센 수 중 소수인 것들을 가리킨다. [math(M(n))]이 메르센 소수이면 [math(n)]도 소수이다. 하지만 역으로 [math(n)]이 소수라고 해서 항상 [math(M(n))]도 소수가 되는 것은 아니다. 처음 네 개, 즉 [math(n=2,\,3,\,5,\,7)]일 때는 성립하지만 [math(2^{11}-1=2047=23\times89)]이고, [math(2^{23}-1=8388607=47\times178481)]인 것이 함정.

참고로 [math(n=mk)]이 합성수인 경우, [math(m)]과 [math(k)]는 각각 2 이상의 자연수라 하면 [math(2^n-1=(2^m-1)(2^{(k-1)m}+2^{(k-2)m}+\dots+2^m+1))]이고 여기서 [math(m)], [math(k)]는 2 이상의 자연수라고 했으므로 [math(2^m-1)]과 [math(2^{(k-1)m}+2^{(k-2)m}+\dots+2^m+1)] 은 각각 2 이상의 자연수이다. 따라서 [math(2^n-1)]은 [math(2^m-1)]과 [math(2^k-1)]을 약수로 가지므로 합성수이다. [math(n=1)]일 경우에도 [math(2^1-1=1)]이니 소수가 아니다.


2. 역사[편집]


프랑스수도자이자 수학자인 마랭 메르센(1588~1648)은 [math(M(n))]이 소수가 되도록 하는 258보다 작은 수는 [math(n=2,\,3,\,5,\,7,\,13,\,17,\,19,\,31,\,\boldsymbol{67},\,127,\,\boldsymbol{257})] 이 전부라고 생각하였다. 하지만 그가 이 수들이 소수인지를 전부 확인해본 것은 아니었고, 틀린 것과 빠진 것이 있었다. 후에 [math(M(67))]과 [math(M(257))]은 소수가 아닌 것으로 판명되었고, 대신 [math(M(61))], [math(M(89))], [math(M(107))]이 추가되어 1947년에 [math(n\lt258)]일 때 [math(n=2,\,3,\,5,\,7,\,13,\,17,\,19,\,31,\,\boldsymbol{61},\,\boldsymbol{89},\,\boldsymbol{107},\,127)] 인 경우가 소수임을 확인했다.

[math(M(31))] = 2147483647[2]이 소수임을 1772년 레온하르트 오일러가 증명했다. 1876년 루카스가 [math(M(127))]이 소수라고 확인하기 전까지는, [math(M(31))]은 알려진 소수들 중 가장 큰 수였다. 1883년 페르보차인이 [math(M(61))]이 소수임을 증명했는데, 이것이 메르센이 빠뜨린 것이었다. 이후 파우어스가 [math(M(89))], [math(M(107))]이 소수라는 사실도 확인했다.

1903년, 미국 수학자 학회에서 넬슨 콜이라는 교수가 "큰 수소인수분해"라는 강연을 했다. 그는 아무 말 없이 [math(2^{67}-1)]을 칠판에 쓴 후 계산해서 [math(147,573,952,589,676,412,927)]을 얻었다. 그리고 다른 쪽 칠판에 [math(193,707,721\times761,838,257,287)]을 계산해서 똑같은 값인 [math(147,573,952,589,676,412,927)]을 얻었다. 그는 강의 도중 한 마디도 하지 않았지만 계산이 끝나자 온 강의실이 박수갈채로 메워졌다. 당시에 컴퓨터는커녕 제대로 된 계산기도 없었다는 사실을 생각하면... 일요일에만 연구해서 이 사실을 밝히는 데 3년이 걸렸다고 한다. 이로써 넬슨 콜은 기록된 역사상 단 한 마디도 하지 않은 강연을 했다고 한다. 또한 이로써 [math(2^{67}-1)]은 소수가 아님이 밝혀졌다.

그래도 메르센의 방법을 응용하면 큰 소수를 찾는 데 유용하게 쓸 수 있다. 예를 들어 현대적인 암호체계는 큰 소수를 사용하는데, 여기서 소수를 찾을 때 사용하는 페르마의 소정리는 메르센의 식에서 -1을 이항한 것이라 보면 된다.

컴퓨터가 발전한 덕에 메르센 소수의 발견이 급격히 진행되었다. 1952년 컴퓨터의 도움을 받아 [math(M(521))], [math(M(607))], [math(M(1279))], [math(M(2203))], [math(M(2281))] 등이 줄줄이 발견되었고, 1992년 32번째 메르센 소수인 M(756,839)이 발견되어 10만 자리(정확히는 227,832자리)를 돌파하였다. 그리고, 1999년에는 M(6,972,593)이 발견되면서 백만 자리(정확히는 2,098,960자리)를 돌파하였다.

2008년 8월 23일, UCLA 수학과의 에드슨 스미스가 [math(M(43,112,609))]을 발견하여 1천만 자리를 돌파하였다. 발견 당시는 45번째였으나, 이후에 2주 뒤에 이 수보다 작은 메르센 소수가 하나 발견되었고, 그 후로 10달 뒤에 또 하나가 더 발견되면서 이보다 작은 2개가 더 발견되어 크기순으로 47번째(추정)으로 순서가 재조정, 2018년 4월에 47번째로 확정되었다. 2017년 기준 45번째 메르센 소수인 [math(M(37,156,667))]까지는 모두 검증이 끝났으므로 순서를 확정지었다.

2013년 1월 25일 커티스 쿠퍼 교수가 이끄는 연구팀이 [math(M(57,885,161))]을 발견하였고, 48번째 메르센 소수로 기록되었다. 17,425,170자리의 수이며, 당시에는 그때까지 알려진 가장 큰 소수였다. 8년이 넘게 48번째 메르센 소수로 추정되다가 2021년 10월 6일 48번째 메르센 소수로 확정되었다. 이보다 큰 소수에 대해서는 미발견된 메르센 소수가 있는지는 아직 정확히 확인되지 않았기에 순서가 확정되지 않았으며, 중간에 다른 메르센 소수가 존재할 가능성도 있기 때문에 이후 메르센 소수의 순서에는 (추정)이 붙는다.

2016년 1월 7일 역시 쿠퍼 교수의 연구팀이 [math(M(74,207,281))]를 발견했다. 22,338,618자리 수이며, 3003으로 시작해서 6351로 끝난다. 참고로, 여기서부터는 메르센 소수에 대한 검증이 완전히 끝나지 않은 상태라서 중간에 발견되지 않은 다른 메르센 소수가 있을 가능성도 있기에 순서에 추정이 붙는다. 현재 49번째 메르센 소수로 추정되고 있다.

2017년 12월 [math(M(77,232,917))]가 발견되었다. 23,249,425자리이며, 50번째 메르센 소수로 추정되고 있다.

2018년 12월 [math(M(82,589,933))]가 발견되었다. 24,862,048자리이며, 51번째 메르센 소수로 추정되고 있다.

참고로 GIMPS에서는 메르센 소수 발견자에게 포상금을 지급하는데, 최초로 1천만 자리를 넘는 소수를 발견한 에드슨 스미스가 속한 UCLA 수학과에 5만 달러를 지급했다. 1억 자리를 넘는 소수에 대해서도 새롭게 5만 달러 포상금을 걸었다. 또한, 새로운 메르센 소수를 발견할 때마다 포상금 3천 달러를 지급한다.

현재 GIMPS에서는 지속적으로 메르센 소수의 발견과 검증을 진행하고 있는데, 2020년 12월 4일, 1억 이하의 소수들이 메르센 소수인지 최초 검사가 끝났으며, 이 수들의 자세한 검증, 또 그 위의 수들의 발견을 계속 시도하고 있다.

3. 메르센 소수의 예[편집]


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


3.1. 작은 메르센 소수[편집]


순서
표기

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

3.2. 큰 메르센 소수[편집]


순서에 (추정)이 붙은 이유는 이보다 작은 수들에 대해서 완전히 검증이 끝나지 않았기 때문이다. 실제로 [math(M(43,112,609))]가 발견되었을 때는 45번째로 추정되었지만, 바로 한 달 뒤에 [math(M(37,156,667))]가 발견되었고, 그 다음 해에도 [math(M(42,643,801))]가 발견되어 순서를 재조정했다.

순서
표기
추정 자릿수
비고
44
[math(M(32,582,657))]
약 980만 자리
1천만 자리에서 2% 모자란 덕분에 1천만 자리 소수 상금 획득에는 실패했다.
45
[math(M(37,156,667))]
약 1,118만 자리

46
[math(M(42,643,801))]
약 1,283만 자리

47
[math(M(43,112,609))]
약 1,297만 자리
앞의 소수 2개보다 먼저 발견되었기에, 최초로 발견된 1천만 자리가 넘는 소수로 기록되었다.
48
[math(M(57,885,161))]
약 1,754만 자리
이보다 작은 모든 메르센 소수 후보는 모두 검증이 끝났기에 2021년 10월 6일, 공식적으로 48번째로 확정되었다.
49(추정)
[math(M(74,207,281))]
약 2,200만 자리
최초로 2천만 자리를 넘는 소수. 위에 언급한 대로 2016년 1월에 발견되었다.
50(추정)
[math(M(77,232,917))]
약 2,324만 자리
2017년 12월 26일에 발견되었고 검증 작업은 2018년 1월 3일에 종료.
51(추정)
[math(M(82,589,933))]
약 2,486만 자리
2018년 12월에 발견되었다.
[1] 메르센 수 중에 최초의 과잉수는 [math(M(12)=2^{12}-1=4095)]로 진약수의 합은 4641이다. 여담으로 이 수는 메르센 수이면서 동시에 삼각수인 자연수 중 가장 큰 수이기도 하다.[2] 프로그래밍을 할 줄 알면 혹은 게임 치트를 쓰다보면 익숙한 그 수. 변수 타입 중 자주 쓰는 정수형의 표현 가능 범위가 –2,147,483,648에서 2,147,483,647이다. 크기가 32비트이고 부호 표시를 제외하면 31비트이므로 2의 31제곱까지 표현이 가능하다. 오버플로 문제와 관련이 있기 때문에 익숙한 것.[3] 37자리 수라서 일상적인 수로는 엄청 큰 게 맞으나 아래의 예를 보면 코딱지만 하게 보일 것이다.[4] 37자리 수라 충분히 큰 수로 보이지만 아래의 예시에 비하면 아직 작은 수이다.


4. 기타[편집]


2진법으로 나타낼 경우 1이 늘어선 형태를 하게 되며, 늘어선 1의 개수가 즉 n에 해당하므로 소수다.

메르센 소수는 짝수인 완전수와 일대일 대응한다.[5] 그 수가 유한인지 무한인지는 알려지지 않았지만, 2018년 12월까지 메르센 소수는 51개가 알려졌다.

[math(M(M(2))=M(2^2-1)=M(3)=7)], [math(M(M(3))=M(2^3-1)=M(7)=127)], [math(M(M(5))=M(2^5-1)=M(31)=2 147483647)], [math(M(M(7))=M(2^7-1)=M(127))][전체]의 경우처럼 2에 메르센 소수를 제곱한 뒤에 1을 빼서 나온 소수는 "이중 메르센 소수"([math(M^2)])라 하며, 총 4개가 발견되었다. [math(M(7))]은 삼중 메르센 소수([math(M^3)])이기도 하고, [math(M(127))]은 사중 메르센 소수([math(M^4)])이기도 하다. 다만 그 외의 [math(M(31))] 이상의 메르센 수들은 모두 너무 커서 2의 거듭제곱 횟수(지수)에 들어가면 숫자가 2018년 12월에 발견된 51번째일 것으로 추정되는 메르센 소수보다도 훨씬 더 커지게 되므로 2를 그렇게나 큰 메르센 소수만큼 거듭제곱하고 나서 1을 뺀 수가 소수인지를 알아보기는 매우 힘들다.

6002자리 수인 [math(M(19937))]은 난수생성 중의 한 방법인 메르센 트위스터에 자주 쓰인다.

파일:크리에이티브 커먼즈 라이선스__CC.png 이 문서의 내용 중 전체 또는 일부는 2023-11-27 15:20:11에 나무위키 메르센 소수 문서에서 가져왔습니다.

[5] [math(2^p-1)] 이 소수일 때 [math(2^{p-1}(2^p-1))]은 짝수 완전수가 되고, 역도 성립한다. 반면 [math(2^p-1)]이 소수가 아닐 경우 그 수는 과잉수가 된다.[전체] 170,141,183,460,469,231,731,687,303,715,884,105,727