메르센 소수

위키백과 ― 우리 모두의 백과사전.

메르센 수(Mersenne number)는 2의 거듭제곱에서 1이 모자란 숫자를 가리킨다. 지수 n에 대한 메르센 수는 Mn = 2n − 1로 나타내고 목록은 아래와 같다.

1, 3, 7, 15, 31, 63, 127, 255, 511, 1023, 2047, 4095... (OEIS의 수열 A000225)

메르센 소수(Mersenne prime)는 메르센 수 중에서 소수인 수이다. 예를 들면 3과 7은 둘 다 소수이고 3 = 22 − 1, 7 = 23 − 1이므로 3과 7은 둘 다 메르센 소수이다. 반대로 15 = 24 − 1은 소수가 아니다. 현대에 알려진 매우 큰 소수들 중에는 메르센 소수가 상당히 많다.

3, 7, 31, 127, 8191, 131091, 524187, 2147483647... (OEIS의 수열 A000668)

메르센 소수가 무한히 많이 존재하는지는 아직 알려져 있지 않다.

목차

[편집] 메르센 소수의 속성

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

Mn은 이항계수의 합이다.

M_n = \sum_{i=0}^{n} {n \choose i} - 1

[편집] 메르센 소수에 관한 정리

  • 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 = 2a, 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
= an − bn

[편집] 역사

1644년 마랭 메르센은 2n − 1 형태가 소수가 되는 것은, n \le 257 일때 n = 2,3,5,7,13,17,19,31,67,127,257 뿐이라고 발표하였다. 그러나 그 주장의 일부는 잘못임이 밝혀졌다. 목록에 포함되지 않은 M61, M89, M107는 소수이며, 목록에 포함되어 있는 M67, M257는 합성수이다.

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

[편집] 메르센 소수 찾기

다음 등식은 Mn이 메르센 소수가 되기 위해서는 n 자신이 소수여야 한다는 것을 알려준다.

(2^a - 1) (1 + 2^a + 2^{2a} + 2^{3a} + \cdots + 2^{(b-1)a}) = 2^{ab} - 1

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

[편집] 메르센 소수 목록

현재까지 발견한 메르센 소수 표 (OEIS의 수열 A000668):

# n Mn Mn의 자리수 발견일 발견자
1 2 3 1 고대 고대
2 3 7 1 고대 고대
3 5 31 2 고대 고대
4 7 127 3 고대 고대
5 13 8191 4 1456년 아무개
6 17 131071 6 1588년 피에트로 카탈디
7 19 524287 6 1588년 피에트로 카탈디
8 31 2147483647 10 1772년 레온하르트 오일러
9 61 2305843009213693951 19 1883년 이반 미흐비치 페르부쉰
10 89 618970019…449562111 27 1911년 R. E. Powers
11 107 162259276…010288127 33 1914년 R. E. Powers
12 127 170141183…884105727 39 1876년 에두아르 뤼카
13 521 686479766…115057151 157 1952년 1월 30일 라파헬 로빈슨
14 607 531137992…031728127 183 1952년 1월 30일 라파헬 로빈슨
15 1,279 104079321…168729087 386 1952년 6월 25일 라파헬 로빈슨
16 2,203 147597991…697771007 664 1952년 10월 7일 라파헬 로빈슨
17 2,281 446087557…132836351 687 1952년 10월 9일 라파헬 로빈슨
18 3,217 259117086…909315071 969 1957년 9월 8일 한스 리젤
19 4,253 190797007…350484991 1,281 1961년 11월 3일 알렉산더 허비츠
20 4,423 285542542…608580607 1,332 1961년 11월 3일 알렉산더 허비츠
21 9,689 478220278…225754111 2,917 1963년 5월 11일 도널드 길리스
22 9,941 346088282…789463551 2,993 1963년 5월 16일 도널드 길리스
23 11,213 281411201…696392191 3,376 1963년 6월 2일 도널드 길리스
24 19,937 431542479…968041471 6,002 1971년 3월 4일 브리언트 터커맨
25 21,701 448679166…511882751 6,533 1978년 10월 30일 랜돈 커트 놀과 로라 니켈
26 23,209 402874115…779264511 6,987 1979년 2월 9일 랜돈 커트 놀
27 44,497 854509824…011228671 13,395 1979년 4월 8일 해리 넬슨과 데이빗 슬로빈스키
28 86,243 536927995…433438207 25,962 1982년 9월 25일 데이빗 슬로빈스키
29 110,503 521928313…465515007 33,265 1983년 1월 28일 월크 콜킷과 루크 웰시
30 132,049 512740276…730061311 39,751 1983년 9월 20일 데이빗 슬로빈스키
31 216,091 746093103…815528447 65,050 1985년 9월 6일 데이빗 슬로빈스키
32 756,839 174135906…544677887 227,832 1992년 2월 19일 데이빗 슬로빈스키와 폴 게이지
33 859,433 129498125…500142591 258,716 1994년 1월 10일 데이빗 슬로빈스키와 폴 게이지
34 1,257,787 412245773…089366527 378,632 1996년 9월 3일 데이빗 슬로빈스키와 폴 게이지 [1]
35 1,398,269 814717564…451315711 420,921 1996년 11월 13일 GIMPS / 조엘 아르멩고 [2]
36 2,976,221 623340076…729201151 895,932 1997년 8월 24일 GIMPS / 고든 스펜스 [3]
37 3,021,377 127411683…024694271 909,526 1998년 1월 27일 GIMPS / 롤랜드 클락슨 [4]
38 6,972,593 437075744…924193791 2,098,960 1999년 6월 11일 GIMPS / 난야 하이라트왈라 [5]
39 13,466,917 924947738…256259071 4,053,946 2001년 11월 14일 GIMPS / 마이클 카메론 [6]
40* 20,996,011 125976895…855682047 6,320,430 2003년 11월 17일 GIMPS / 마이클 셰이퍼 [7]
41* 24,036,583 299410429…733969407 7,235,733 2004년 5월 15일 GIMPS / 조지 핀들리 [8]
42* 25,964,951 122164630…577077247 7,816,230 2005년 2월 18일 GIMPS / 마르틴 노바크 [9]
43* 30,402,457 315416475…652943871 9,152,052 2005년 9월 15일 GIMPS / 커티스 쿠퍼와 스티븐 분 [10]
44* 32,582,657 124575026…053967871 9,808,358 2006년 9월 4일 GIMPS / 커티스 쿠퍼와 스티븐 분 [11]
45* 37,156,667 202254406…308220927 11,185,272 2008년 9월 6일 GIMPS / Hans-Michael Elvenich
46* 43,112,609 316470269…697152511 12,987,189 2008년 8월 23일 GIMPS / UCLA
위키뉴스
위키뉴스

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

*표의 39번째 수인 M13,466,917과 46번째 수인 M43,112,609 사이에 아직 발견되지 않은 다른 메르센 소수가 있는지는 아직 알려져 있지 않다. 따라서 이 번호들은 바뀔 수도 있다.

처음 30개의 메르센 소수의 모든 자리들을 보려면 위키문헌을 참고하라.

[편집] 완전수

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

2^{n-1} \cdot (2^n - 1) = \frac {M_n (M_n + 1)} 2

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

[편집] 일반화

2n − 1의 2진법 표현은 숫자 1이 n번 반복된다. 예를 들면, 25 - 1 = 111112와 같이 표기된다. 그러므로 메르센 소수는 2를 밑으로 하는 단위 반복 소수이다.

[편집] 관련 항목

[편집] 바깥 고리

원본 주소 ‘http://ko.wikipedia.org/wiki/%EB%A9%94%EB%A5%B4%EC%84%BC_%EC%86%8C%EC%88%98’