메르센 소수

메르센 수(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... (OEIS의 수열 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... (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의 거듭제곱 횟수는 소수이지만, 해당 메르센 수가 소수가 아닌 경우는 무수히 많다.

메르센 수의 속성

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

$M$ _$n$은 이항계수의 합에서 1을 뺀 값이다.

M_{n}=\sum _{i=0}^{n}{n \choose i}-1

메르센 수의 지수가 홀수소수 $=p$ 이면 소인수의 형태는 다음과 같음을 페르마가 증명하였다.

$'2pk+1'$ ( $k$ 는 음이 아닌 정수)

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

또한 n이 홀수 소수인 메르센 수들의 약수들은 모두 $8k\pm 1$ 꼴이다.

메르센 소수에 관한 정리

1) 만일 $n$ 이 하나의 양의 정수이면, 이항정리에 의해 다음과 같이 쓸 수 있다:

c^{n}-d^{n}=(c-d)\sum _{k=0}^{n-1}c^{k}d^{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^{k}b^{n-1-k}

=\sum _{k=0}^{n-1}a^{k+1}b^{n-1-k}-\sum _{k=0}^{n-1}a^{k}b^{n-k}

=a^{n}+\sum _{k=1}^{n-1}a^{k}b^{n-k}-\sum _{k=1}^{n-1}a^{k}b^{n-k}-b^{n}

=a^{n}-b^{n}

역사

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

리젤 수의 발견자이기도 한 스웨덴의 수학자인 한스 리젤이 1957년에 컴퓨터를 이용하여 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$ 로 소인수분해된다.

메르센 소수 목록

수학의 미해결 문제

메르센 소수는 무한한가?
(더 많은 수학의 미해결 문제 보기)

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

#	$n$	$M_{n}$	$M_{n}$ 의 자리수	발견일	발견자
1	2	3	1	기원전 430년 경	고대 그리스 수학자
2	3	7	1	기원전 430년 경	고대 그리스 수학자
3	5	31	2	기원전 300년 경	고대 그리스 수학자
4	7	127	3	기원전 300년 경	고대 그리스 수학자
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	61897001 9642690137449562111	27	1911년	R. E. Powers
11	107	16225927682921 3363391578010288127	33	1914년	R. E. Powers
12	127	17014118346046923173 1687303715884105727	39	1876년	에두아르 뤼카
13	521	6864797660130609714 9819007990813932172 6943530014330540939 4463459185543183397 6560521225596406614 5455497729631139148 0858037121987999716 6438125740282911150 57151	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	1988년 1월 28일	월크 콜킷과 루크 웰시
30	132,049	512740276…730061311	39,751	1983년 9월 19일^[1]	데이빗 슬로빈스키
31	216,091	746093103…815528447	65,050	1985년 9월 1일^[1]	데이빗 슬로빈스키
32	756,839	174135906…544677887	227,832	1992년 2월 19일	데이빗 슬로빈스키와 폴 게이지
33	859,433	129498125…500142591	258,716	1994년 1월 4일	데이빗 슬로빈스키와 폴 게이지
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 [12]
46^*	42,643,801	169873516…562314751	12,837,064	2009년 4월 12일^**	GIMPS / Odd Magnar Strindmo
47^*	43,112,609	316470269…697152511	12,978,189	2008년 8월 23일	GIMPS / Edson Smith [13]
48^*	57,885,161	581887266…724285951	17,425,170	2013년 1월 25일	GIMPS / Curtis Cooper [14]
49^*	74,207,281	300376418…086436351	22,338,618	2015년 9월 17일^***	GIMPS / Curtis Cooper [15]
50	77,232,917	467333183…762179071	23,249,425	2017년 12월 26일	GIMPS / Jon Pace
51	82,589,933	110847779…217902591	24,862,048	2018년 12월 7일	GIMPS / Patrick Laroche

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

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

^**M_42,643,801는 2009년 4월 12일 컴퓨터에 의해 처음 발견되었다. 그러나 6월 4일까지 이 사실을 인지한 사람은 아무도 없었다. 그래서, 발견일을 4월 12일 또는 6월 4일로 간주한다. 발견자 스트린드모(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세기에 오일러는 모든 짝수 완전수는 이와 같은 형태를 갖는다는 것을 증명했다. 홀수 완전수는 아직 발견되지 않았으며 존재하지 않는 것으로 추측된다.

일반화

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

같이 보기

페르마 소수
하노이의 탑 - n개의 원반을 모두 이동하기 위해서는 최소한 메르센 수(2ⁿ−1) 만큼 이동해야 한다.

각주

↑ ^가 ^나 Landon Curt Noll, Mersenne Prime Digits and Names.

외부 링크

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
Discovery of the 42nd
Mersenne numbers
prime Mersenne numbers
Slashdot - Discovery of the 42nd
$M_{q}=(8x)^{2}-(3qy)^{2}\,$ Proof
$M_{q}=x^{2}+d\cdot y^{2}$ Thesis
알려진 메르센 소수의 모든 자릿수와 영어 이름

[isthe-1] 가 ^나 Landon Curt Noll, Mersenne Prime Digits and Names.

[1]