메르센 소수

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

메르센 수(영어: Mersenne number)는 2의 거듭제곱에서 1이 모자란 숫자를 가리킨다. 지수 n에 대한 메르센 수는 $M n = 2 n - 1$ 로 나타낸다.

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

메르센 소수는 그 자신의 수를 뺀 모든 약수의 합이 원래의 수가 되는 자연수인 완전수와 밀접한 연관성을 가지고 있다. 역사적으로 메르센 소수의 연구는 이 연관성을 밝히려는 동기에 의해 이루어졌다. 기원전 4세기에 유클리드는 M이 메르센 소수이면 M(M+1)/2가 완전수임을 증명했으며, 18세기에 오일러는 모든 짝수 완전수는 이와 같은 형태를 갖는다는 것을 증명했다. (홀수 완전수는 아직 발견되지 않았으며 존재하지 않는 것으로 추측된다.)

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

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

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

M_n은 이항계수의 합이다.

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

[편집] 메르센 소수 찾기

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

$(2^a-1)\cdot (1+2^a+2^{2a}+2^{3a}+\dots+2^{(b-1)a})=2^{ab}-1$

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

[편집] 메르센 소수 리스트

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

#	n	M_n	M_n의 자리수	발견일	발견자
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년	Powers
11	107	162259276…010288127	33	1914년	Powers
12	127	170141183…884105727	39	1876년	Lucas
13	521	686479766…115057151	157	1952년 1월 30일	Robinson
14	607	531137992…031728127	183	1952년 1월 30일	Robinson
15	1,279	104079321…168729087	386	1952년 6월 25일	Robinson
16	2,203	147597991…697771007	664	1952년 10월 7일	Robinson
17	2,281	446087557…132836351	687	1952년 10월 9일	Robinson
18	3,217	259117086…909315071	969	1957년 9월 8일	Riesel
19	4,253	190797007…350484991	1,281	1961년 11월 3일	Hurwitz
20	4,423	285542542…608580607	1,332	1961년 11월 3일	Hurwitz
21	9,689	478220278…225754111	2,917	1963년 5월 11일	Gillies
22	9,941	346088282…789463551	2,993	1963년 5월 16일	Gillies
23	11,213	281411201…696392191	3,376	1963년 6월 2일	Gillies
24	19,937	431542479…968041471	6,002	1971년 3월 4일	Tuckerman
25	21,701	448679166…511882751	6,533	1978년 10월 30일	Noll & Nickel
26	23,209	402874115…779264511	6,987	1979년 2월 9일	Noll
27	44,497	854509824…011228671	13,395	1979년 4월 8일	Nelson & Slowinski
28	86,243	536927995…433438207	25,962	1982년 9월 25일	Slowinski
29	110,503	521928313…465515007	33,265	1983년 1월 28일	Colquitt & Welsh
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]

위키뉴스에 관련 뉴스가 있습니다:

분산컴퓨팅으로 가장 큰 소수를 발견하다

위키뉴스에 관련 뉴스가 있습니다:

CMSU컴퓨터팀이 또 다른 기록적인 크기의 소수를 발견하다

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

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

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

[편집] 관련 항목

페르마 소수

[편집] 바깥 고리

Mersenne prime section of the Prime Pages: http://www.utm.edu/research/primes/mersenne.shtml
Mersenne Prime Search home page: http://www.mersenne.org
The first 30 Mersenne primes written out in decimal
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.y^2 Thesis

분류: 수론 | 소수

See also ebooksgratis.com: no banners, no cookies, totally FREE.