메르센느 소수

보다 큰 소수를 추적하는 작업은 17세기부터 내려온 유서깊은 전통을 가진 작업이다.
19세기의 파리 수도사 마랭 메르센 Marin Marsenne(1588-1648)는 수도원 일과 중에 틈틈이 소수를 찾아나섰다. 알려진 가장 큰 2^25,964,951-1 같은 소수는 소위 메르센 수라고 하는 2ⁿ-1의 형태를 취하고 있다. 메르센 수가 소수가 되기 위해서는 n 그 자체가 소수가 되어야 한다. 그래서 2^25,964,951-1이 소수이므로 25,964,951도 소수가 되어야 한다. 그러나 n 이 소수라고 해서 메르센 수가 반드시 소수가 되는 것은 아니다.

    n 이 첫 네 소수(2, 3, 5, 7)일 때 메르센 수는 소수이다.
            n = 2 일 때, 2²-1 = 3
            n = 3 일 때, 2³-1 = 7
            n = 5 일 때, 2⁵-1 = 31
            n = 7 일 때, 2⁷-1 = 127
   그러나, n = 11 일 때,  2¹¹-1 = 2,047 = 23 × 89 (1536년 Hudalrichus Regius)
            n = 13 일 때, 2¹³-1 = 8,191      (Hudalrichus Regius)
            n = 17 일 때, 2¹⁷-1 = 131,071 (1588년 Cataldi)
            n = 19 일 때, 2¹⁹-1 = 524,287  (1588년 Cataldi)

    메르센은 또 n = 67 일 때, 2⁶⁷-1 이 소수라고 과감하게 주장했다. 이 주장은 거의 250여년 동안 의문시되지 않았다. 그러다가 1903년 미국 수학협회의 한 강연에서 콜롬비아 대학의 프랭크 넬슨 콜 Frank Nelson Cole 이 "큰 수의 인수분해에 대하여" 라는 평범한 제목으로 강연을 했다. 그때 그 강연을 들었던 에릭 템플 벨 Eric Temple Bell 은 이렇게 회상했다.

1603년 피에트로 카탈디 Pietro Cataldi가 2¹⁷-1 과 2¹⁹-1 은 모두가 소수라는 것을 정확히 설명했지만 23, 29, 31, 37 일 때에도 2ⁿ-1 이 소수라고 부정확하게 말했다. 1640년에 페르마가 23과 37일 때 카탈디가 틀렸음을 보였다. 1738년에 오일러는 29일 때에도 카탈디가 역시 틀렸음을 밝혔다. 그 후 오일러가 31에 대해서는 카탈디의 주장이 옳았음을 증명했다.

1644년 메르센은 그의 책 서문에 'n = 2, 3, 5, 7, 13, 17, 19, 31, 67, 127 과 257 일 때 2ⁿ-1 은 소수이고, n 이 257보다 작은 정수(n<257)일 경우에는 합성수'라는 메르센느의 (틀린) 추측을 발표했다. 그러나 이런 수에 그의 이름이 붙여졌다.

메르센의 동료들은 카탈디의 소수를 모두 테스트해 보지 않은 것은 분명하다. 그렇다고 전혀 테스트를 하지 않았다는 말은 아니다. 100년이 지나기 바로 직전인, 1750년에 오일러가 2³¹-1 이 소수라는 카탈디의 주장이 옳았음을 증명했다. 다시 100년이 지나 1876년 루카스Lucas가 2¹²⁷-1 이 또한 소수라는 것을 설명했다. 7년 후 페르보차인Pervouchine이 2⁶¹-1 이 소수라는 것을 보였다. 즉 메르센은 이것을 빠뜨린 것이다. 1900년대 초 파우어스Powers가 메르센이 빠뜨린 2⁸⁹-1 과 2¹⁰⁷-1 를 찾아냈다. 마침내 1947년 258 이하의 모든 메르센의 범위에 대해서 완전히 체크하였다. 정확한 범위는 다음과 같다.

    메르센 소수는 완전수하고도 깊은 관계가 있다.
   M(p) =2ⁿ-1, P(p)=2^n-1(2ⁿ-1) 라고 하자. 알려진 모든 소수 p 에 대하여 M(p)가 메르센 소수이면,

   P(p)는 무조건 완전수이다.

다음은 지금까지 찾아낸 알려진 41개의 메르센 소수들의 표이다.

번호	메르센 소수	Mp의 자릿수	Pp의 자릿수	언제	누가
1	2²-1	1	1	500BC?	----
2	2³-1	1	2	500BC?	----
3	2⁵-1	2	3	275BC?	----
4	2⁷-1	3	4	275BC?	----
5	2¹³-1	4	8	1456	anonymous
6	2¹⁷-1	6	10	1588	Cataldi
7	2¹⁹-1	6	12	1588	Cataldi
8	2³¹-1	10	19	1772	Euler
9	2⁶¹-1	19	37	1883	Pervushin
10	2⁸⁹-1	27	54	1911	Powers
11	2¹⁰⁷-1	33	65	1914	Powers
12	2¹²⁷-1	39	77	1876	Lucas
13	2⁵²¹-1	157	314	1952	Robinson
14	2⁶⁰⁷-1	183	366	1952	Robinson
15	2¹²⁷⁹-1	386	770	1952	Robinson
16	2²²⁰³-1	664	1327	1952	Robinson
17	2²²⁸¹-1	687	1373	1952	Robinson
18	2³²¹⁷-1	969	1937	1957	Riesel
19	2⁴²⁵³-1	1281	2561	1961	Hurwitz
20	2⁴⁴²³-1	1332	2663	1961	Hurwitz
21	2⁹⁶⁸⁹-1	2917	5834	1963	Gillies
22	2⁹⁹⁴¹-1	2993	5985	1963	Gillies
23	2¹¹²¹³-1	3376	6751	1963	Gillies
24	2¹⁹⁹³⁷-1	6002	12003	1971	Tuckerman
25	2²¹⁷⁰¹-1	6533	13066	1978	Noll & Nickel
26	2²³²⁰⁹-1	6987	13973	1979	Noll
27	2⁴⁴⁴⁹⁷-1	13395	26790	1979	Nelson & Slowinski
28	2²⁸⁶²⁴³-1	25962	51924	1982	Slowinski
29	2¹¹⁰⁵⁰³-1	33265	66530	1988	Colquitt & Welsh
30	2¹³²⁰⁴⁹-1	39751	79502	1983	Slowinski
31	2²¹⁶⁰⁹¹-1	65050	130100	1985	Slowinski
32	2⁷⁵⁶⁸³⁹-1	227832	155663	1982	Slowinski & Gage
33	2⁸⁵⁹⁴³³-1	258716	517430	1994	Slowinski & Gagei
34	2^1257787-1	378632	757263	1996	Slowinski & Gage
35	2^1398269-1	420921	841842	1996	Armengaud, Woltman, et. al. (GIMPS)
36	2^2976221-1	895932	1791864	1997	Spence, Woltman, et. al. (GIMPS)
37	2^3021377-1	909526	1819050	1998	Clarkson, Woltman, Kurowski et. al. (GIMPS, PrimeNet)
38	2^6972593-1	2098960	4197919	1999	Hajratwala, Woltman, Kurowski et. al. (GIMPS, PrimeNet)
39	2^13466917-1	4053946	8107892	2001	Cameron, Woltman, Kurowski, GIMPS
40	2^20996011-1	6320430	12640858	2003	Michel Shafer, GIMPS
41?	2^24036583-1	7235733	14471465	2004	Josh Findley, GIMPS
42?	2^25964951-1	7816230	15632458	2005	Dr. Martin Nowak, GIMPS
43?	2^30402457-1	9152052	18304103	2005	Josh Findley, GIMPS
44?	2^32582657-1	9808358	19616714	2006	Dr. Martin Nowak, GIMPS