•  
  •  
  •  
  •  
  •  
  •  
  •  
  •  
  •  
  •  
더 보기

사용자:Acu/연습장(r101 Blame)

r101
r76
Acu
1[[분류:정수론]]
r89
Acu
2[include(틀:정수론)]
r76
Acu
3[목차]
4== 개요 ==
r82
Acu
5'''메르센 수''' [math(M_n)]은 [math(2^n-1)] 꼴의 수를 의미하고, '''메르센 소수'''는 [math(2^2-1=3)]와 같이 메르센 소수 중 소수인 수들을 뜻한다. 메르센 소수는 주로 큰 소수를 찾기 위해 탐색하는 유형의 수들이고, 그런 만큼 현재까지 발견된 가장 큰 5개의 소수까지는 모두 메르센 소수이다.
r76
Acu
6
r77
Acu
7== 수학적 성질 ==
r80
Acu
8 * [math(2^n-1)]이 소수라면 [math(n)]도 소수이다. 1이 아닌 두 자연수 [math(r)]와 [math(s)]을 두고 [math(x^r=a)]로 치환하면 [math(x^{rs}-1=a^s-1=(a-1)(a^{s-1}+a^{s-2}+\dots a+1))]로 인수분해가 되고, [math(rs)]는 합성수이므로 [math(2^n-1)]에서 [math(n)]이 합성수라면 대응하는 메르센 수도 합성수라는 의미이기 때문이다.
r81
Acu
9 * 짝수 완전수는 모두 [math(2^{n-1}M_{n})]의 형태를 가지므로 메르센 소수는 모두 짝수 완전수와 일대일 대응된다.
r82
Acu
10 * 이진수로 표현했을 때 [math(n)]개의 1만으로 이루어져 있다.
r90
Acu
11 * 홀수소수 [math(p)]를 지수로 갖는 메르센 수의 소인수 [math(q)]는 모두 [math(8k\pm 1)] 꼴이며, [math(q\equiv 1\pmod {2p})]를 만족한다.
12
13== 역사 ==
r93
Acu
14메르센 소수라는 이름은 17세기의 수학자 겸 철학자 [[마랭 메르센]]에서 왔다. 메르센은 1644년 [math(n)]이 257 이하일 때, [math(2^n-1)]이 소수가 되는 경우는 [math(n)]이 2, 3, 5, 7, 13, 19, 31, 67, 127, 257인 경우라는 것. 지수가 19인 메르센 수까지는 이미 알려져 있는 소수들이였고, [math(M_{31})][* 2147483647. 32비트 정수에서 표시할 수 있는 가장 큰 수이다.]이 소수라는 것까지는 사실이었지만 그 이후로는 정확성이 매우 떨어졌다. 애초에 메르센도 이것을 어떻게 알아냈는지에 대해 자세히 설명하지 않았고, 컴퓨터 등 검증할 수단도 발달하지 않았던 시대였으니 확인하기는 어려웠다. 틀린 부분은 지수가 61, 89, 107인 경우가 목록에서 빠져 있고 67, 257인 경우는 소수가 아님에도 포함되어 있다는 부분이다.
r94
Acu
15
r96
Acu
161772년에 [[레온하르트 오일러]]에 의해 [math(M_{31})]이 증명되었고, 100년이 넘는 기간 동안 가장 큰 메르센 소수의 자리를 지키다 에두아르 뤼카(Édouard Lucas)가 1876년에 [math(M_{127})]가 소수임을 증명했다. 그는 [math(M_{67})]이 소수가 아니라는 사실 또한 밝혀냈는데, 소인수를 찾아내지는 못했다. 그 뒤 1903년에 프랭크 넬슨 콜이 '큰 수의 소인수분해'라는 강연을 열었다. 미국 수학자 협회 회의실에서 그는 먼저 [math(M_{67})](147573952589676412927)을 써 내려갔다. 그 다음 [math(M_{67})]의 두 소인수(193707721, 761838257287)를 적은 후, 거의 한 시간 동안 아무 말도 하지않고 두 소인수를 곱해 M67과 같은 수를 얻었다. 그리고 그의 청중들은 우레 같은 박수를 보냈다고 한다. 이것을 증명하는 데에는 꼬박 3년 간의 일요일이 걸렸다고 한다. 1883년 이반 페르부신(Ivan Pervushin)이 [math(M_{61})], 1911년과 1914년에 랄프 어니스트 파워스(Ralph Ernest Powers)가 각각 [math(M_{89})]와 [math(M_{107})]를 발견함으로써 메르센의 추측에서 빠졌던 부분들이 모두 채워졌다.
r97
Acu
17
r98
Acu
181952년부터는 컴퓨터의 발달로 인해 메르센 소수 탐색에 속도가 붙기 시작했으며, 1952년 한 해에 [math(M_{521})], [math(M_{607})], [math(M_{1279})], [math(M_{2203})], [math(M_{2281})]이 줄줄이 발견되었다. 또한 1996년에는 [[GIMPS]]가 창설되어 더뎌지던 메르센 소수 탐색을 다시 한 번 가속화시켰다. 같은 해 발견된 [math(M_{1398269})]를 시작으로는 지금까지 발견된 모든 메르센 소수는 GIMPS에 의해 발견되었다.
r99
Acu
19
r100
Acu
202024년, 처음으로 PRP 테스트로 메르센 소수가 발견되었다. [math(M_{136279841})]으로, PRP를 사용하기 시작한 지 6년 만이다.
r101
Acu
21== 목록 ==
22|| No. || 메르센 소수 || 지수 || 자릿수 || 발견 연도 || 발견자 ||
23|| 1 || [math(M_{2})] || 2 || 1 || 기원전 500 || 고대 그리스 ||
24|| 2 || [math(M_{3})] || 3 || 1 || 기원전 500 || 고대 그리스 ||
25|| 3 || [math(M_{5})] || 5 || 2 || 기원전 275 || 고대 그리스 ||
26|| 4 || [math(M_{7})] || 7 || 3 || 기원전 275 || 고대 그리스 ||
27|| 5 || [math(M_{13})] || 13 || 4 || 1461 || (미상) ||
28|| 6 || [math(M_{17})] || 17 || 6 || 1588 || (미상) ||
29|| 7 || [math(M_{19})] || 19 || 6 || 1588 || (미상) ||
30|| 8 || [math(M_{31})] || 31 || 10 || 1772 || Leonhard Euler ||
31|| 9 || [math(M_{61})] || 61 || 19 || 1883 || I. M. Pervushin ||
32|| 10 || [math(M_{89})] || 89 || 27 || 1911 || R. E. Powers ||
33|| 11 || [math(M_{107})] || 107 || 33 || 1914 || R. E. Powers ||
34|| 12 || [math(M_{127})] || 127 || 39 || 1876 || Édouard Lucas ||
35|| 13 || [math(M_{521})] || 521 || 157 || 1952 || Raphael M. Robinson ||
36|| 14 || [math(M_{607})] || 607 || 183 || 1952 || Raphael M. Robinson ||
37|| 15 || [math(M_{1279})] || 1279 || 386 || 1952 || Raphael M. Robinson ||
38|| 16 || [math(M_{2203})] || 2203 || 664 || 1952 || Raphael M. Robinson ||
39|| 17 || [math(M_{2281})] || 2281 || 687 || 1952 || Raphael M. Robinson ||
40|| 18 || [math(M_{3217})] || 3217 || 969 || 1957 || Hans Riesel ||
41|| 19 || [math(M_{4253})] || 4253 || 1281 || 1961 || Alexander Hurwitz ||
42|| 20 || [math(M_{4423})] || 4423 || 1332 || 1961 || Alexander Hurwitz ||
43|| 21 || [math(M_{9689})] || 9689 || 2917 || 1963 || Gillies ||
44|| 22 || [math(M_{9941})] || 9941 || 2993 || 1963 || Gillies ||
45|| 23 || [math(M_{11213})] || 11213 || 3376 || 1963 || Gillies ||
46|| 24 || [math(M_{19937})] || 19937 || 6002 || 1971 || Tuckerman ||
47|| 25 || [math(M_{21701})] || 21701 || 6533 || 1978 || Noll & Nickel ||
48|| 26 || [math(M_{23209})] || 23209 || 6987 || 1979 || Noll ||
49|| 27 || [math(M_{44497})] || 44497 || 13395 || 1979 || Nelson & Slowinski ||
50|| 28 || [math(M_{86243})] || 86243 || 25962 || 1982 || Slowinski ||
51|| 29 || [math(M_{110503})] || 110503 || 33265 || 1988 || Colquitt & Welsh ||
52|| 30 || [math(M_{132049})] || 132049 || 39751 || 1983 || Slowinski ||
53|| 31 || [math(M_{216091})] || 216091 || 65050 || 1985 || Slowinski ||
54|| 32 || [math(M_{756839})] || 756839 || 227832 || 1992 || Slowinski & Gage ||
55|| 33 || [math(M_{859433})] || 859433 || 258716 || 1994 || Slowinski & Gage ||
56|| 34 || [math(M_{1257787})] || 1257787 || 378632 || 1996 || Slowinski & Gage ||
57|| 35 || [math(M_{1398269})] || 1398269 || 420921 || 1996 || Armengaud et al. ||
58|| 36 || [math(M_{2976221})] || 2976221 || 895932 || 1997 || Spence et al. ||
59|| 37 || [math(M_{3021377})] || 3021377 || 909526 || 1998 || Clarkson et al. ||
60|| 38 || [math(M_{6972593})] || 6972593 || 2098960 || 1999 || Hajratwala et al. ||
61|| 39 || [math(M_{13466917})] || 13466917 || 4053946 || 2001 || Cameron et al. ||
62|| 40 || [math(M_{20996011})] || 20996011 || 6320430 || 2003 || Shafer ||
63|| 41 || [math(M_{24036583})] || 24036583 || 7235733 || 2004 || Findley ||
64|| 42 || [math(M_{25964951})] || 25964951 || 7816230 || 2005 || Nowak ||
65|| 43 || [math(M_{30402457})] || 30402457 || 9152052 || 2005 || Cooper & Boone ||
66|| 44 || [math(M_{32582657})] || 32582657 || 9808358 || 2006 || Cooper & Boone ||
67|| 45 || [math(M_{37156667})] || 37156667 || 11185272 || 2008 || Cooper ||
68|| 46 || [math(M_{42643801})] || 42643801 || 12837064 || 2009 || Strindmo ||
69|| 47 || [math(M_{43112609})] || 43112609 || 12978189 || 2008 || Strindmo ||
70|| 48 || [math(M_{57885161})] || 57885161 || 17425170 || 2013 || Cooper ||
71|| 49 || [math(M_{74207281})] || 74207281 || 22338618 || 2016 || Cooper ||
72|| 50 || [math(M_{77232917})] || 77232917 || 23249425 || 2017 || Pace ||
73|| 51 || [math(M_{82589933})] || 82589933 || 24862048 || 2018 || Pace et al. ||
74|| 52 || [math(M_{136279841})] || 136279841 || 41024320 || 2024 || GIMPS ||