메르센 소수

**메르센 수**(Mersenne number)는 2의 거듭제곱에서 1이 모자란 숫자를 가리킨다. 지수 n에 대한 메르센 수는 M_n = 2^n - 1로 나타내고 목록은 아래와 같다. : 1, 3, 7, 15, 31, 63, 127, 255, 511, 1023, 2047, 4095, 8191, 16383, 32767... A000225 **메르센 소수**(Mersenne prime)는 **메르센 수** 중에서 소수인 수이다. 예를 들면 3과 7은 둘 다 소수이고 3 = 2^2 - 1, \mbox{ } 7 = 2^3 - 1이므로 3과 7은 둘 다 메르센 소수이다. 반대로 15 = 2^4 - 1은 합성수이다. 현대에 알려진 매우 큰 소수들 중에는 메르센 소수가 상당히 많다. : 3, 7, 31, 127, 8191, 131071, 524287, 2147483647, 2305843009213693951... A000668 메르센 소수가 무한히 많이 존재하는지 아니면 그 개수가 정해져 있는지는 아직 알려져 있지 않다. 즉 이 말은 메르센 소수가 유한한지 무한한지에 대한 여부가 알려져있지 않았다는 것인데, n이 소수라고 해서 항상 해당 메르센 수가 소수가 되지는 않기 때문이다. 예를 들어 n=2, 3, 5, 7, 13, 17, 19 일 땐 소수가 된다. 그러나 11은 소수긴 하나 n=11일 땐 2의 11제곱에서 1을 뺀 수인 2047은 23×89로 소인수분해 가능하다. 비슷한 이유로 23도 소수이나 n=23일 땐 2의 23제곱에서 1을 뺀 수인 8388607도 47×178481로 소인수분해 할 수 있기 때문이다. 마찬가지로 n=29일 때, 37일 때, 41일 때, 그리고 43, 47일 때 등등도 2의 거듭제곱 횟수는 소수이지만, 해당 메르센 수가 소수가 아닌 경우는 무수히 많다.
# 메르센 수의 속성
메르센 수는 다음의 몇 가지 속성을 지닌다. : * *Mn*은 이항계수의 합에서 1을 뺀 값이다. : M_n = \sum_{i=0}^{n} {n \choose i} - 1 * 메르센 수의 지수가 홀수소수=p 이면 소인수의 형태는 다음과 같음을 페르마가 증명하였다. '2pk+1' (k는 음이 아닌 정수) 이것은 메르센 수가 소수, 즉 메르센 소수일때도 성립한다. 또한 n이 홀수 소수인 메르센 수들의 약수들은 모두 8k\pm1 꼴이다.
# 메르센 소수에 관한 정리
* 1) 만일 *n*이 하나의 양의 정수이면, 이항정리에 의해 다음과 같이 쓸 수 있다: :c^n-d^n=(c-d)\sum_{k=0}^{n-1} c^kd^{n-1-k}, 또는 :(2^a-1)\cdot \left(1+2^a+2^{2a}+2^{3a}+\cdots+2^{(b-1)a}\right)=2^{ab}-1 이다(*c* = 2*a*, *d* = 1로, *n* = *b*로 놓았을 때). 증명 :(a-b)\sum_{k=0}^{n-1}a^kb^{n-1-k} :=\sum_{k=0}^{n-1}a^{k+1}b^{n-1-k}-\sum_{k=0}^{n-1}a^kb^{n-k} :=a^n+\sum_{k=1}^{n-1}a^kb^{n-k}-\sum_{k=1}^{n-1}a^kb^{n-k}-b^n :=a^n-b^n
# 역사
1644년 마랭 메르센은 2^n - 1 형태가 소수가 되는 것은, n \le 257 일 때 n = 2, 3, 5, 7, 13, 17, 19, 31, 67, 127, 257 뿐이라고 발표하였다. 그러나 그 주장의 일부는 잘못임이 밝혀졌다. 목록에 포함되지 않은 M_{61}, M_{89}, M_{107}는 소수이며, 목록에 포함되어 있는 M_{67}, M_{257}는 합성수이다. 리젤 수의 발견자이기도 한 스웨덴의 수학자인 한스 리젤이 1956년에 컴퓨터를 이용하여 18번째의 메르센 소수를 발견한 이래, 이후 컴퓨터를 활용하여 새로운 메르센 소수를 찾고 있다.
# 메르센 소수 찾기
n=ab; 다음 등식은 M_n이 메르센 소수가 되기 위해서는 n 자신이 소수여야 한다는 것을 알려준다. :(2^a - 1) (1 + 2^a + 2^{2a} + 2^{3a} + \cdots + 2^{(b-1)a}) = 2^{ab} - 1 따라서, 메르센 소수를 찾기 위해서는 지수가 소수인 경우만 조사하면 되지만, 일반적으로 그 역은 참이 아니다. 즉 n이 소수라고 하여 M_n 또한 소수인 것은 아니다. 예를 들어, 11은 소수지만 2047 = 2^{11} - 1 = 23 \cdot 89로 소인수분해된다.
## 메르센 소수 목록
메르센 소수는 무한한가? 지금까지 발견한 메르센 소수 표 A000668: {| class="wikitable" |- ! # ! n ! M_n ! M_n의 자리수 ! 발견일 !n번째 확정일 ! 발견자 |- | align="right" |1 | align="right" |1 | align="right" |1 | align="right" |1 |기원전 732년 | - |고대 그리스 수학자 |- | align="right" | 2 | align="right" | 2 | align="right" | 3 | align="right" | 1 | 기원전 730년 | - | 고대 그리스 수학자 |- | align="right" | 3 | align="right" | 3 | align="right" | 7 | align="right" | 1 | 기원전 729년 | - | 고대 그리스 수학자 |- | align="right" | 4 | align="right" | 5 | align="right" | 31 | align="right" | 2 | 기원전 276년 | - | 고대 그리스 수학자 |- | align="right" | 5 | align="right" | 7 | align="right" | 127 | align="right" | 3 | 기원전 273년 | - | 고대 그리스 수학자 |- | align="right" | 6 | align="right" | 13 | align="right" | 8191 | align="right" | 4 | 1459년 |1460년 | 익명 |- | align="right" | 7 | align="right" | 17 | align="right" | 131071 | align="right" | 6 | 1606년 |1606년 | 피에트로 카탈디 |- | align="right" | 8 | align="right" | 19 | align="right" | 524287 | align="right" | 6 | 1606년 | - | 피에트로 카탈디 |- | align="right" | 9 | align="right" | 31 | align="right" | 2147483647 | align="right" | 10 | 1772년 |1775년 | 레온하르트 오일러 |- | align="right" | 10 | align="right" | 61 | align="right" | 2305843009213693951 | align="right" | 19 | 1883년 |1887년 | 이반 미흐비치 페르부쉰 |- | align="right" | 11 | align="right" | 89 | align="right" | 61897001 9642690137449562111 | align="right" | 27 | 1911년 |1918년 | R. E. Powers |- | align="right" | 12 | align="right" | 107 | align="right" | 16225927682921 3363391578010288127 | align="right" | 33 | 1914년 |1922년 | R. E. Powers |- | align="right" | 13 | align="right" | 127 | align="right" | 17014118346046923173 1687303715884105727 | align="right" | 39 | 1877년 |1923년 | 에두아르 뤼카 |- | align="right" | 14 | align="right" | 521 | align="right" | 6864797660130609714 9819007990813932172 6943530014330540939 4463459185543183397 6560521225596406614 5455497729631139148 0858037121987999716 6438125740282911150 57151 | align="right" | 157 | 1952년 1월 30일 |1956년 6월 17일 | 라파헬 로빈슨 |- | align="right" | 15 | align="right" | 607 | align="right" | 531137992…031728127 | align="right" | 183 | 1952년 1월 30일 |1956년 7월 4일 | 라파헬 로빈슨 |- | align="right" | 16 | align="right" | 1,279 | align="right" | 104079321…168729087 | align="right" | 386 | 1952년 6월 25일 |1956년 12월 13일 | 라파헬 로빈슨 |- | align="right" | 17 | align="right" | 2,203 | align="right" | 147597991…697771007 | align="right" | 664 | 1952년 10월 7일 |1957년 3월 12일 | 라파헬 로빈슨 |- | align="right" | 18 | align="right" | 2,281 | align="right" | 446087557…132836351 | align="right" | 687 | 1952년 10월 8일 |1957년 3월 14일 | 라파헬 로빈슨 |- | align="right" | 19 | align="right" | 3,217 | align="right" | 259117086…909315071 | align="right" | 969 | 1956년 9월 1일 |1961년 10월 5일 | 한스 리젤 |- | align="right" | 20 | align="right" | 4,253 | align="right" | 190797007…350484991 | align="right" | 1,281 | 1961년 11월 3일 |1965년 4월 13일 | 알렉산더 허비츠 |- | align="right" | 21 | align="right" | 4,423 | align="right" | 285542542…608580607 | align="right" | 1,332 | 1961년 11월 3일 |1965년 4월 13일 | 알렉산더 허비츠 |- | align="right" | 22 | align="right" | 9,689 | align="right" | 478220278…225754111 | align="right" | 2,917 | 1963년 5월 11일 |1967년 11월 20일 | 도널드 길리스 |- | align="right" | 23 | align="right" | 9,941 | align="right" | 346088282…789463551 | align="right" | 2,993 | 1963년 5월 16일 |1967년 11월 21일 | 도널드 길리스 |- | align="right" | 24 | align="right" | 11,213 | align="right" | 281411201…696392191 | align="right" | 3,376 | 1963년 6월 2일 |1968년 1월 12일 | 도널드 길리스 |- | align="right" | 25 | align="right" | 19,937 | align="right" | 431542479…968041471 | align="right" | 6,002 | 1971년 3월 4일 |1978년 9월 19일 | 브리언트 터커맨 |- | align="right" | 26 | align="right" | 21,701 | align="right" | 448679166…511882751 | align="right" | 6,533 | 1978년 10월 30일 |1986년 5월 13일 | 랜돈 커트 놀과 로라 니켈 |- | align="right" | 27 | align="right" | 23,209 | align="right" | 402874115…779264511 | align="right" | 6,987 | 1979년 2월 9일 |1986년 10월 3일 | 랜돈 커트 놀 |- | align="right" | 28 | align="right" | 44,497 | align="right" | 854509824…011228671 | align="right" | 13,395 | 1979년 4월 8일 |1987년 1월 2일 | 해리 넬슨과 데이빗 슬로빈스키 |- | align="right" | 29 | align="right" | 86,243 | align="right" | 536927995…433438207 | align="right" | 25,962 | 1982년 9월 25일 |1990년 7월 20일 | 데이빗 슬로빈스키 |- | align="right" | 30 | align="right" | 110,503 | align="right" | 521928313…465515007 | align="right" | 33,265 | 1988년 1월 28일 |1997년 5월 15일 | 월크 콜킷과 루크 웰시 |- | align="right" | 31 | align="right" | 132,049 | align="right" | 512740276…730061311 | align="right" | 39,751 | 1983년 9월 19일Landon Curt Noll, Mersenne Prime Digits and Names. |1997년 12월 3일 | 데이빗 슬로빈스키 |- | align="right" | 32 | align="right" | 216,091 | align="right" | 746093103…815528447 | align="right" | 65,050 | 1984년 9월 10일 |1999년 3월 23일 | 데이빗 슬로빈스키 |- | align="right" | 33 | align="right" | 756,839 | align="right" | 174135906…544677887 | align="right" | 227,832 | 1992년 2월 19일 |2001년 10월 21일 | 데이빗 슬로빈스키와 폴 게이지 |- | align="right" | 34 | align="right" | 859,433 | align="right" | 129498125…500142591 | align="right" | 258,716 | 1994년 1월 4일 |2002년 11월 16일 | 데이빗 슬로빈스키와 폴 게이지 |- | align="right" | 35 | align="right" | 1,257,787 | align="right" | 412245773…089366527 | align="right" | 378,632 | 1996년 9월 3일 |2003년 10월 24일 | 데이빗 슬로빈스키와 폴 게이지 |- | align="right" | 36 | align="right" | 1,398,269 | align="right" | 814717564…451315711 | align="right" | 420,921 | 1996년 11월 13일 |2003년 12월 9일 | GIMPS / 조엘 아르멩고 |- | align="right" | 51* | align="right" | 77,232,917 | align="right" | 467333183…762179071 | align="right" | 23,249,425 | 2017년 12월 26일 | 2025년 9월 8일 | GIMPS / Jon Pace |- | align="right" | 52* | align="right" | 82,589,933 | align="right" | 110847779…217902591 | align="right" | 24,862,048 | 2018년 12월 7일 | 2025년 10월 24일 | GIMPS / Patrick Laroche |- | align="right" | 53* | align="right" | 136,279,841 | align="right" | 881694327…486871551 | align="right" | 41,024,320 | 2024년 10월 12일 |확정 되지 않음. | GIMPS / Luke Durant |- | align="right" | 54* | align="right" | ? | align="right" | ? | align="right" | ? | ? |확정 되지 않음. | ? |} 45번째 알려진 메르센 소수를 시각적으로 보여 주기 위해서는 1페이지 당, 10진수 75개 자리수의 숫자를 50줄씩 쓴 2,616페이지가 필요하다. *표의 49번째 수인 M_{57,885,161}과 50번째 수인 M_{74,207,281} 사이에 아직 발견되지 않은 다른 메르센 소수가 있는지 2025년 6월 25일에 알려졌다. 없었다. 하지만 중간에 알려지지 않은 메르센 소수가 있을 수 있다. 따라서 이 번호들은 바뀔 수도 있다. 소수가 작은 소수부터 순차적으로 발견되는 것은 아니다. 예를 들어, 30번째 메르센 소수는 31번째와 32번째 소수의 발견 **이후**에 발견되었다. ***M*42,643,801는 2009년 4월 12일 컴퓨터에 의해 처음 발견되었다. 그러나 6월 3일까지 이 사실을 인지한 사람은 아무도 없었다. 그래서, 발견일을 4월 12일 또는 6월 3일로 간주한다. 발견자 스트린드모(Strindmo)는 alias Stig M. Valstad를 사용한 것으로 보인다. ****M*74,207,281는 2015년 9월 17일 컴퓨터에 의해 처음 발견되었다. 그러나 2016년 1월 7일까지 이 사실을 인지한 사람은 아무도 없었다. 그래서, 발견일을 2015년 9월 17일 또는 2016년 1월 7일로 간주한다.
# 완전수
완전수 메르센 소수는 완전수와 여러 관련성이 있어 흥미롭다. 기원전 4세기에 유클리드는 M_n이 메르센 소수이면 다음과 같이 짝수 완전수임을 보였다. : 2^{n-1} \cdot (2^n - 1) = \frac {M_n (M_n + 1)} 2 18세기에 오일러는 모든 짝수 완전수는 이와 같은 형태를 갖는다는 것을 증명했다. 홀수 완전수는 존재하지 않는다. 왜냐하면 완전수로 홀수를 만드려면 무조건 4로 나누었을때 나머지가 무조건 1이나 2여야 한다. 하지만 모든 2의 제곱은 4로 나누어떨어지고 그렇게 되면 4-1=3 나머지가 3이 되기 때문에 홀수 완전수는 존재하지 않는다.
# 일반화
2^n - 1의 2진법 표현은 숫자 1이 n번 반복된다. 예를 들면, 25 \- 1 = 111112와 같이 표기된다. 그러므로 메르센 소수는 2를 밑으로 하는 단위 반복 소수이다.