메르센 소수 문서 원본 보기

{{위키데이터 속성 추적}}
'''메르센 수'''({{lang|en|Mersenne number}})는 [[2의 거듭제곱]]에서 1이 모자란 숫자를 가리킨다. 지수 <math>n</math>에 대한 메르센 수는 <math>M_n = 2^n - 1</math>로 나타내고 목록은 아래와 같다.
: [[1]], [[3]], [[7]], [[15]], [[31]], [[63]], [[127]], [[255]], [[511]], [[1023]], [[2047]], [[4095]], [[8191]], [[16383]], [[32767]]... {{OEIS|A000225}}

'''메르센 소수'''({{lang|en|Mersenne prime}})는 '''메르센 수''' 중에서 [[소수 (수론)|소수]]인 수이다. 예를 들면 3과 7은 둘 다 소수이고 <math>3 = 2^2 - 1, \mbox{ } 7 = 2^3 - 1</math>이므로 3과 7은 둘 다 메르센 소수이다. 반대로 <math>15 = 2^4 - 1</math>은 합성수이다. 현대에 알려진 매우 큰 소수들 중에는 메르센 소수가 상당히 많다.
: [[3]], [[7]], [[31]], [[127]], [[8191]], [[131071]], [[524287]], [[2147483647]], [[2305843009213693951]]... {{OEIS|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의 거듭제곱 횟수는 소수이지만, 해당 메르센 수가 소수가 아닌 경우는 무수히 많다.

== 메르센 수의 속성 ==
메르센 수는 다음의 몇 가지 속성을 지닌다. :

* ''<math>M</math><sub><math>n</math></sub>''은 [[이항계수]]의 [[합]]에서 1을 뺀 값이다.
: <math> M_n = \sum_{i=0}^{n} {n \choose i} - 1 </math>

* 메르센 수의 지수가 홀수소수<math>=p</math> 이면 소인수의 형태는 다음과 같음을 [[피에르 드 페르마|페르마]]가 증명하였다.

<math>'2pk+1'</math> (<math>k</math>는 음이 아닌 정수)

이것은 메르센 수가 소수, 즉 메르센 소수일때도 성립한다.

또한 n이 홀수 소수인 메르센 수들의 약수들은 모두 <math>8k\pm1</math> 꼴이다.

== 메르센 소수에 관한 정리 ==
* 1) 만일 ''<math>n</math>''이 하나의 양의 정수이면, [[이항정리]]에 의해 다음과 같이 쓸 수 있다:

:<math>c^n-d^n=(c-d)\sum_{k=0}^{n-1} c^kd^{n-1-k},</math>

또는
:<math>(2^a-1)\cdot \left(1+2^a+2^{2a}+2^{3a}+\cdots+2^{(b-1)a}\right)=2^{ab}-1</math>

이다(''<math>c</math>''&nbsp;=&nbsp;<math>2</math><sup>''<math>a</math>''</sup>, ''<math>d</math>''&nbsp;=&nbsp;<math>1</math>로, ''<math>n</math>''&nbsp;=&nbsp;''<math>b</math>''로 놓았을 때).

증명

:<math>(a-b)\sum_{k=0}^{n-1}a^kb^{n-1-k}</math>

:<math>=\sum_{k=0}^{n-1}a^{k+1}b^{n-1-k}-\sum_{k=0}^{n-1}a^kb^{n-k}</math>

:<math>=a^n+\sum_{k=1}^{n-1}a^kb^{n-k}-\sum_{k=1}^{n-1}a^kb^{n-k}-b^n</math>

:<math>=a^n-b^n</math>

== 역사 ==
[[1644년]] [[마랭 메르센]]은 <math>2^n - 1</math> 형태가 소수가 되는 것은, <math>n \le 257</math> 일 때 <math>n = 2, 3, 5, 7, 13, 17, 19, 31, 67, 127, 257</math> 뿐이라고 발표하였다. 그러나 그 주장의 일부는 잘못임이 밝혀졌다. 목록에 포함되지 않은 <math>M_{61}</math>, <math>M_{89}</math>, <math>M_{107}</math>는 소수이며, 목록에 포함되어 있는 <math>M_{67}</math>, <math>M_{257}</math>는 [[합성수]]이다.

[[리젤 수]]의 발견자이기도 한 스웨덴의 수학자인 [[한스 리젤]]이 [[1957년]]에 컴퓨터를 이용하여 18번째의 메르센 소수를 발견한 이래, 이후 컴퓨터를 활용하여 새로운 메르센 소수를 찾고 있다.

== 메르센 소수 찾기 ==
<math>n=ab;</math> 다음 등식은 <math>M_n</math>이 메르센 소수가 되기 위해서는 <math>n</math> 자신이 소수여야 한다는 것을 알려준다.

:<math>(2^a - 1) (1 + 2^a + 2^{2a} + 2^{3a} + \cdots + 2^{(b-1)a}) = 2^{ab} - 1</math>

따라서, 메르센 소수를 찾기 위해서는 지수가 소수인 경우만 조사하면 되지만, 일반적으로 그 역은 참이 아니다. 즉 <math>n</math>이 소수라고 하여 <math>M_n</math> 또한 소수인 것은 아니다. 예를 들어, 11은 소수지만 <math> 2047 = 2^{11} - 1 = 23 \cdot 89</math>로 소인수분해된다.

=== 메르센 소수 목록 ===

{{미해결|수학|메르센 소수는 무한한가?}}
현재까지 발견한 메르센 소수 표 {{OEIS|A000668}}:
{| class="wikitable"
|-
! #
! <math>n</math>
! <math>M_n</math>
! <math>M_n</math>의 자리수
! 발견일
! 발견자
|-
| align="right" | 1
| align="right" | 2
| align="right" | [[3]]
| align="right" | 1
| 기원전 430년 경
| 고대 그리스 수학자
|-
| align="right" | 2
| align="right" | 3
| align="right" | [[7]]
| align="right" | 1
| 기원전 430년 경
| 고대 그리스 수학자
|-
| align="right" | 3
| align="right" | 5
| align="right" | [[31]]
| align="right" | 2
| 기원전 300년 경
| 고대 그리스 수학자
|-
| align="right" | 4
| align="right" | 7
| align="right" | [[127]]
| align="right" | 3
| 기원전 300년 경
| 고대 그리스 수학자
|-
| align="right" | 5
| align="right" | 13
| align="right" | 8191
| align="right" | 4
| [[1456년]]
| 익명
|-
| align="right" | 6
| align="right" | 17
| align="right" | 131071
| align="right" | 6
| [[1588년]]
| [[피에트로 카탈디]]
|-
| align="right" | 7
| align="right" | 19
| align="right" | 524287
| align="right" | 6
| [[1588년]]
| 피에트로 카탈디
|-
| align="right" | 8
| align="right" | 31
| align="right" | [[2147483647]]
| align="right" | 10
| [[1772년]]
| [[레온하르트 오일러]]
|-
| align="right" | 9
| align="right" | 61
| align="right" | 2305843009213693951
| align="right" | 19
| [[1883년]]
| [[이반 미흐비치 페르부쉰]]
|-
| align="right" | 10
| align="right" | 89
| align="right" | 61897001
9642690137449562111
| align="right" | 27
| [[1911년]]
| R. E. Powers
|-
| align="right" | 11
| align="right" | 107
| align="right" | 16225927682921
3363391578010288127
| align="right" | 33
| [[1914년]]
| R. E. Powers
|-
| align="right" | 12
| align="right" | 127
| align="right" | 17014118346046923173
1687303715884105727
| align="right" | 39
| [[1876년]]
| [[에두아르 뤼카]]
|-
| align="right" | 13
| align="right" | 521
| align="right" | 6864797660130609714
9819007990813932172
6943530014330540939
4463459185543183397
6560521225596406614
5455497729631139148
0858037121987999716
6438125740282911150
57151
| align="right" | 157
| [[1952년]] [[1월 30일]]
| [[라파헬 로빈슨]]
|-
| align="right" | 14
| align="right" | 607
| align="right" | 531137992…031728127
| align="right" | 183
| 1952년 1월 30일
| 라파헬 로빈슨
|-
| align="right" | 15
| align="right" | 1,279
| align="right" | 104079321…168729087
| align="right" | 386
| 1952년 [[6월 25일]]
| 라파헬 로빈슨
|-
| align="right" | 16
| align="right" | 2,203
| align="right" | 147597991…697771007
| align="right" | 664
| 1952년 [[10월 7일]]
| 라파헬 로빈슨
|-
| align="right" | 17
| align="right" | 2,281
| align="right" | 446087557…132836351
| align="right" | 687
| 1952년 [[10월 9일]]
| 라파헬 로빈슨
|-
| align="right" | 18
| align="right" | 3,217
| align="right" | 259117086…909315071
| align="right" | 969
| [[1957년]] [[9월 8일]]
| [[한스 리젤]]
|-
| align="right" | 19
| align="right" | 4,253
| align="right" | 190797007…350484991
| align="right" | 1,281
| [[1961년]] [[11월 3일]]
| [[알렉산더 허비츠]]
|-
| align="right" | 20
| align="right" | 4,423
| align="right" | 285542542…608580607
| align="right" | 1,332
| 1961년 11월 3일
| 알렉산더 허비츠
|-
| align="right" | 21
| align="right" | 9,689
| align="right" | 478220278…225754111
| align="right" | 2,917
| [[1963년]] [[5월 11일]]
| [[도널드 길리스]]
|-
| align="right" | 22
| align="right" | 9,941
| align="right" | 346088282…789463551
| align="right" | 2,993
| 1963년 [[5월 16일]]
| 도널드 길리스
|-
| align="right" | 23
| align="right" | 11,213
| align="right" | 281411201…696392191
| align="right" | 3,376
| 1963년 [[6월 2일]]
| 도널드 길리스
|-
| align="right" | 24
| align="right" | 19,937
| align="right" | 431542479…968041471
| align="right" | 6,002
| [[1971년]] [[3월 4일]]
| [[브리언트 터커맨]]
|-
| align="right" | 25
| align="right" | 21,701
| align="right" | 448679166…511882751
| align="right" | 6,533
| [[1978년]] [[10월 30일]]
| [[랜돈 커트 놀]]과 [[로라 니켈]]
|-
| align="right" | 26
| align="right" | 23,209
| align="right" | 402874115…779264511
| align="right" | 6,987
| [[1979년]] [[2월 9일]]
| 랜돈 커트 놀
|-
| align="right" | 27
| align="right" | 44,497
| align="right" | 854509824…011228671
| align="right" | 13,395
| 1979년 [[4월 8일]]
| [[해리 넬슨]]과 [[데이빗 슬로빈스키]]
|-
| align="right" | 28
| align="right" | 86,243
| align="right" | 536927995…433438207
| align="right" | 25,962
| [[1982년]] [[9월 25일]]
| 데이빗 슬로빈스키
|-
| align="right" | 29
| align="right" | 110,503
| align="right" | 521928313…465515007
| align="right" | 33,265
| [[1988년]] [[1월 28일]]
| [[월크 콜킷]]과 [[루크 웰시]]
|-
| align="right" | 30
| align="right" | 132,049
| align="right" | 512740276…730061311
| align="right" | 39,751
| [[1983년]] [[9월 19일]]<ref name="isthe">Landon Curt Noll, [http://www.isthe.com/chongo/tech/math/prime/mersenne.html#largest Mersenne Prime Digits and Names].</ref>

| 데이빗 슬로빈스키
|-
| align="right" | 31
| align="right" | 216,091
| align="right" | 746093103…815528447
| align="right" | 65,050
| [[1985년]] [[9월 1일]]<ref name="isthe" />
| 데이빗 슬로빈스키
|-
| align="right" | 32
| align="right" | 756,839
| align="right" | 174135906…544677887
| align="right" | 227,832
| [[1992년]] [[2월 19일]]
| 데이빗 슬로빈스키와 [[폴 게이지]]
|-
| align="right" | 33
| align="right" | 859,433
| align="right" | 129498125…500142591
| align="right" | 258,716
| [[1994년]] [[1월 4일]]
| 데이빗 슬로빈스키와 폴 게이지
|-
| align="right" | 34
| align="right" | 1,257,787
| align="right" | 412245773…089366527
| align="right" | 378,632
| [[1996년]] [[9월 3일]]
| 데이빗 슬로빈스키와 폴 게이지 [http://primes.utm.edu/notes/1257787.html]
|-
| align="right" | 35
| align="right" | 1,398,269
| align="right" | 814717564…451315711
| align="right" | 420,921
| [[1996년]] [[11월 13일]]
| [[GIMPS]] / 조엘 아르멩고 [http://primes.utm.edu/notes/1398269.html]{{깨진 링크|url=http://primes.utm.edu/notes/1398269.html }}
|-
| align="right" | 36
| align="right" | 2,976,221
| align="right" | 623340076…729201151
| align="right" | 895,932
| [[1997년]] [[8월 24일]]
| GIMPS / 고든 스펜스 [http://primes.utm.edu/notes/2976221.html]{{깨진 링크|url=http://primes.utm.edu/notes/2976221.html }}
|-
| align="right" | 37
| align="right" | 3,021,377
| align="right" | 127411683…024694271
| align="right" | 909,526
| [[1998년]] [[1월 27일]]
| GIMPS / 롤랜드 클락슨 [http://primes.utm.edu/notes/3021377.html]{{깨진 링크|url=http://primes.utm.edu/notes/3021377.html }}
|-
| align="right" | 38
| align="right" | 6,972,593
| align="right" | 437075744…924193791
| align="right" | 2,098,960
| [[1999년]] [[6월 11일]]
| GIMPS / 난야 하이라트왈라 [http://www.mersenne.org/various/6972593.htm]
|-
| align="right" | 39
| align="right" | 13,466,917
| align="right" | 924947738…256259071
| align="right" | 4,053,946
| [[2001년]] [[11월 14일]]
| GIMPS / 마이클 카메론 [http://www.mersenne.org/various/13466917.htm]
|-
| align="right" | 40
| align="right" | 20,996,011
| align="right" | 125976895…855682047
| align="right" | 6,320,430
| [[2003년]] [[11월 17일]]
| GIMPS / 마이클 셰이퍼 [http://www.mersenne.org/various/20996011.htm]
|-
| align="right" | 41
| align="right" | 24,036,583
| align="right" | 299410429…733969407
| align="right" | 7,235,733
| [[2004년]] [[5월 15일]]
| GIMPS / 조지 핀들리 [http://www.mersenne.org/various/24036583.htm]
|-
| align="right" | 42
| align="right" | 25,964,951
| align="right" | 122164630…577077247
| align="right" | 7,816,230
| [[2005년]] [[2월 18일]]
| GIMPS / 마르틴 노바크 [http://www.mersenne.org/various/25964951.htm]
|-
| align="right" | 43
| align="right" | 30,402,457
| align="right" | 315416475…652943871
| align="right" | 9,152,052
| [[2005년]] [[9월 15일]]
| GIMPS / [[커티스 쿠퍼]]와 [[스티븐 분]] [http://www.mersenne.org/various/30402457.htm]
|-
| align="right" | 44
| align="right" | 32,582,657
| align="right" | 124575026…053967871
| align="right" | 9,808,358
| [[2006년]] [[9월 4일]]
| GIMPS / 커티스 쿠퍼와 스티븐 분 [http://www.mersenne.org/various/32582657.htm]
|-
| align="right" | 45
| align="right" | 37,156,667
| align="right" | 202254406…308220927
| align="right" | 11,185,272
| [[2008년]] [[9월 6일]]
| GIMPS / Hans-Michael Elvenich [http://www.mersenne.org/primes/m45and46.htm]
|-
| align="right" | 46
| align="right" | 42,643,801
| align="right" | 169873516…562314751
| align="right" | 12,837,064
| [[2009년]] [[4월 12일]]<sup>**</sup>
| GIMPS / Odd Magnar Strindmo
|-
| align="right" | 47
| align="right" | 43,112,609
| align="right" | 316470269…697152511
| align="right" | 12,978,189
| [[2008년]] [[8월 23일]]
| GIMPS / Edson Smith [http://www.mersenne.org/primes/m45and46.htm]
|-
| align="right" | 48
| align="right" | 57,885,161
| align="right" | 581887266…724285951
| align="right" | 17,425,170
| [[2013년]] [[1월 25일]]
| GIMPS / Curtis Cooper [http://mersenne.org/various/57885161.htm]
|-
| align="right"| 49<sup>*</sup>
| align="right"| 74,207,281
| align="right"| 300376418…086436351
| align="right"| 22,338,618
| [[2015년]] [[9월 17일]]<sup>***</sup>
| GIMPS / Curtis Cooper [http://mersenne.org/primes/?press=M74207281]
|-
| align="right"| 50*
| align="right"| 77,232,917
| align="right"| 467333183…762179071
| align="right"| 23,249,425
| [[2017년]] [[12월 26일]]
| GIMPS / Jon Pace
|-
| align="right"| 51*
| align="right"| 82,589,933
| align="right"| 110847779…217902591
| align="right"| 24,862,048
| [[2018년]] [[12월 7일]]
| GIMPS / Patrick Laroche
|-
| align="right"| 52*
| align="right"| 136,279,841
| align="right"| 881694327…486871551
| align="right"| 41,024,320
| [[2024년]] [[10월 12일]]
| GIMPS / Luke Durant
|}

44번째 알려진 메르센 소수를 시각적으로 보여 주기 위해서는 1페이지 당, 10진수 75개 자리수의 숫자를 50줄씩 쓴 2,616페이지가 필요하다.

<sup>*</sup>표의 48번째 수인 <math>M_{57,885,161}</math>과 49번째 수인 <math>M_{74,207,281}</math> 사이에 아직 발견되지 않은 다른 메르센 소수가 있는지는 아직 알려져 있지 않다. 따라서 이 번호들은 바뀔 수도 있다. 소수가 작은 소수부터 순차적으로 발견되는 것은 아니다. 예를 들어, 29번째 메르센 소수는 30번째와 31번째 소수의 발견 '''이후'''에 발견되었다.

<sup>**</sup>''M''<sub>42,643,801</sub>는 2009년 4월 12일 컴퓨터에 의해 처음 발견되었다. 그러나 6월 4일까지 이 사실을 인지한 사람은 아무도 없었다. 그래서, 발견일을 4월 12일 또는 6월 4일로 간주한다. 발견자 스트린드모(Strindmo)는 alias Stig M. Valstad를 사용한 것으로 보인다.

<sup>***</sup>''M''<sub>74,207,281</sub>는 2015년 9월 17일 컴퓨터에 의해 처음 발견되었다. 그러나 2016년 1월 7일까지 이 사실을 인지한 사람은 아무도 없었다. 그래서, 발견일을 2015년 9월 17일 또는 2016년 1월 7일로 간주한다.

== 완전수 ==
{{본문|완전수}}

메르센 소수는 [[완전수]]와 여러 관련성이 있어 흥미롭다. 기원전 4세기에 [[유클리드]]는 <math>M_n</math>이 메르센 소수이면 다음과 같이 [[짝수]] 완전수임을 보였다.

: <math>2^{n-1} \cdot (2^n - 1) = \frac {M_n (M_n + 1)} 2 </math>

[[18세기]]에 [[레온하르트 오일러|오일러]]는 모든 [[짝수]] [[완전수]]는 이와 같은 형태를 갖는다는 것을 증명했다. [[홀수]] 완전수는 아직 발견되지 않았으며 존재하지 않는 것으로 추측된다.

== 일반화 ==
<math>2^n - 1</math>의 [[2진법]] 표현은 숫자 1이 <math>n</math>번 반복된다. 예를 들면, 2<sup>5</sup> - 1 = 11111<sub>2</sub>와 같이 표기된다. 그러므로 메르센 소수는 2를 밑으로 하는 [[단위 반복 소수]]이다.

== 같이 보기 ==
* [[페르마 소수]]
* [[하노이의 탑]] - n개의 원반을 모두 이동하기 위해서는 최소한 '''메르센 수'''(2<sup>n</sup>−1) 만큼 이동해야 한다.

== 각주 ==
{{각주}}

== 외부 링크 ==
* Mersenne prime section of the Prime Pages: http://www.utm.edu/research/primes/mersenne.shtml
* Mersenne Prime Search home page: http://www.mersenne.org
* GIMPS status page http://www.mersenne.org/status.htm gives various statistics on search progress, typically updated every week, including progress towards proving the ordering of primes 39-42
* [http://mathworld.wolfram.com/news/2005-02-26/mersenne/ Discovery of the 42nd]
* [http://mathworld.wolfram.com/MersenneNumber.html Mersenne numbers]
* [http://mathworld.wolfram.com/MersennePrime.html prime Mersenne numbers]
* [http://science.slashdot.org/science/05/02/26/1814202.shtml?tid=228 Slashdot - Discovery of the 42nd]
* <math>M_q = (8x)^2 - (3qy)^2 \,</math> [http://tony.reix.free.fr/Mersenne/Mersenne8x3qy.pdf Proof]
* <math>M_q = x^2 + d \cdot y^2</math> [https://web.archive.org/web/20050221194456/http://www.math.leidenuniv.nl/scripties/jansen.ps Thesis]
* [http://www.isthe.com/chongo/tech/math/prime/mersenne.html 알려진 메르센 소수의 모든 자릿수와 영어 이름]

{{소수}}

[[분류:수론]]
[[분류:소수]]
[[분류:완전수]]
[[분류:정수열]]
[[분류:사람 이름을 딴 낱말]]
[[분류:수론의 미해결 문제]]