정의
[math]\displaystyle{ \displaystyle 2^n-1\; (n\ge 2) }[/math] 꼴의 정수를 메르센 수(Mersenne number)라고 한다. 메르센 수 중에서 소수인 수를 메르센 소수(Mersenne prime)라고 한다. 즉, 양의 정수 [math]\displaystyle{ \displaystyle n }[/math]에 대해 [math]\displaystyle{ \displaystyle M_n=2^n-1\;(n\ge 2) }[/math]가 소수이면 [math]\displaystyle{ \displaystyle M_n }[/math]를 메르센 소수라고 한다. 메르센 소수라는 이름은 프랑스의 수학자인 마랭 메르센(Marin Mersenne)에게서 따온 것이다.
성질
- 메르센 수 [math]\displaystyle{ \displaystyle M_n=2^n-1 }[/math]이 소수면 [math]\displaystyle{ \displaystyle n }[/math]도 소수이다.
- [math]\displaystyle{ \displaystyle n }[/math]이 소수가 아니라면, [math]\displaystyle{ \displaystyle 1\lt a\lt n }[/math]인 [math]\displaystyle{ \displaystyle n }[/math]의 약수 [math]\displaystyle{ \displaystyle a }[/math]가 존재한다. 그럼, [math]\displaystyle{ \displaystyle m\equiv 0\pmod a }[/math]이고, [math]\displaystyle{ \displaystyle 2^m-1\equiv2^0-1\pmod{2^a-1} }[/math]임을 유클리드 호제법을 사용해 보일 수 있다. 따라서, [math]\displaystyle{ \displaystyle 2^a-1\mid2^n-1 }[/math]이고, [math]\displaystyle{ \displaystyle M_n }[/math]은 소수가 아니다.
- [math]\displaystyle{ \displaystyle p }[/math]가 2가 아닌 소수라면, 메르센 수 [math]\displaystyle{ \displaystyle M_p }[/math]의 약수는 전부 [math]\displaystyle{ \displaystyle 2kp+1,\,k\in\mathbb{Z}^+ }[/math]의 형태이다.
- [math]\displaystyle{ \displaystyle q }[/math]를 [math]\displaystyle{ \displaystyle M_p=2^p-1 }[/math]의 소인수라 가정하자. 페르마의 소정리에 의해, [math]\displaystyle{ \displaystyle 2^{q-1}\equiv1\pmod q }[/math]이므로, [math]\displaystyle{ \displaystyle q\mid2^{q-1}-1 }[/math]이다. [math]\displaystyle{ \displaystyle q\mid2^p-1 }[/math]이기도 하므로, [math]\displaystyle{ \displaystyle q\mid\gcd\left(2^{q-1}-1,2^p-1\right) }[/math]이다. 한편, [math]\displaystyle{ \displaystyle \gcd\left(2^{q-1}-1,2^p-1\right)=2^{\gcd\left(q-1,p\right)}-1 }[/math]이다.[1] 따라서, [math]\displaystyle{ \displaystyle q\mid2^{\gcd\left(q-1,p\right)}-1 }[/math]이다. 그런데 [math]\displaystyle{ \displaystyle p }[/math]가 소수이므로, [math]\displaystyle{ \displaystyle \gcd\left(q-1,p\right) }[/math]은 1 또는 [math]\displaystyle{ \displaystyle p }[/math]이다. 만약 [math]\displaystyle{ \displaystyle \gcd\left(q-1,p\right)=1 }[/math]이라면, [math]\displaystyle{ \displaystyle q\mid2^{\gcd\left(q-1,p\right)}-1=2^1-1=1 }[/math]이므로, [math]\displaystyle{ \displaystyle q }[/math]가 소수라는 가정에 모순된다. 따라서 [math]\displaystyle{ \displaystyle \gcd\left(q-1,p\right)=p }[/math]이고, [math]\displaystyle{ \displaystyle p\mid q-1 }[/math]이다. 곧, 적당한 양의 정수 [math]\displaystyle{ \displaystyle m }[/math]에 대해 [math]\displaystyle{ \displaystyle q-1=mp }[/math]이다. [math]\displaystyle{ \displaystyle q }[/math]가 홀수이므로,[2] [math]\displaystyle{ \displaystyle q-1 }[/math]은 짝수이고, [math]\displaystyle{ \displaystyle p }[/math]는 홀수이므로, [math]\displaystyle{ \displaystyle m }[/math]은 짝수여야 한다. 즉, 적당한 양의 정수 [math]\displaystyle{ \displaystyle k }[/math]에 대해 [math]\displaystyle{ \displaystyle q=mp+1=2kp+1 }[/math]이다. 마지막으로, [math]\displaystyle{ \displaystyle M_p }[/math]의 약수는 [math]\displaystyle{ \displaystyle M_p }[/math]의 적당한 소인수들의 곱이고, 임의의 소인수는 [math]\displaystyle{ \displaystyle 2kp+1 }[/math]의 형태이므로, 저 형태를 가진 소인수를 곱한 임의의 약수도 같은 형태이다.
- 예를 들어, 370052357은 소수이고 88940026013534293337은 [math]\displaystyle{ \displaystyle 2^{370052357}-1 }[/math]의 약수인데, [math]\displaystyle{ \displaystyle 88940026013534293337=2\cdot 120172219324\cdot 370052357+1 }[/math]임을 확인할 수 있다.
- [math]\displaystyle{ \displaystyle n }[/math]이 짝수인 완전수[3]라면 [math]\displaystyle{ \displaystyle n=2^{m-1}\left(2^m-1\right) }[/math]이다 (단, [math]\displaystyle{ \displaystyle m\geq2 }[/math]인 정수, [math]\displaystyle{ \displaystyle 2^m-1 }[/math]은 (메르센) 소수). 이 명제의 역도 성립한다.
- [math]\displaystyle{ \displaystyle n=2^{m-1}\left(2^m-1\right) }[/math]이고, [math]\displaystyle{ \displaystyle m\geq2 }[/math]인 정수, [math]\displaystyle{ \displaystyle 2^m-1 }[/math]은 소수라 가정하자. [math]\displaystyle{ \displaystyle 2^m-1 }[/math]은 홀수인 소수이므로, [math]\displaystyle{ \displaystyle \gcd\left(2^{m-1},2^m-1\right)=1 }[/math]이다. 즉, [math]\displaystyle{ \displaystyle \sigma\left(n\right)=\sigma\left(2^{m-1}\right)\sigma\left(2^m-1\right) }[/math][4][5][math]\displaystyle{ \displaystyle =\frac{2^m-1}{2-1}\left(2^m-1+1\right)=\left(2^m-1\right)2^m=2n }[/math]. 따라서, [math]\displaystyle{ \displaystyle n }[/math]은 완전수이다.
- 역으로, [math]\displaystyle{ \displaystyle n }[/math]이 짝수인 완전수라 가정하자. 일단, 적당한 홀수 [math]\displaystyle{ \displaystyle t }[/math]와 1이상인 정수 [math]\displaystyle{ \displaystyle s }[/math]에 대해 [math]\displaystyle{ \displaystyle n=2^st }[/math]로 나타낼 수 있다.[6] 그럼, [math]\displaystyle{ \displaystyle 2n=2^{s+1}t=\sigma\left(n\right)=\sigma\left(2^st\right) }[/math]. [math]\displaystyle{ \displaystyle \gcd\left(2^s,t\right)=1 }[/math]이므로, [math]\displaystyle{ \displaystyle \sigma\left(2^st\right)=\sigma\left(2^s\right)\sigma\left(t\right)=\left(2^{s+1}-1\right)\sigma\left(t\right) }[/math]이다. 따라서, [math]\displaystyle{ \displaystyle 2^{s+1}t=\left(2^{s+1}-1\right)\sigma\left(t\right) }[/math]이고, [math]\displaystyle{ \displaystyle 2^{s+1}\mid\left(2^{s+1}-1\right)\sigma\left(t\right) }[/math]임을 알 수 있다. 한편, [math]\displaystyle{ \displaystyle \gcd\left(2^{s+1},2^{s+1}-1\right)=1 }[/math]이므로, [math]\displaystyle{ \displaystyle 2^{s+1}\mid\sigma\left(t\right) }[/math]이다. 따라서, 적당한 정수 [math]\displaystyle{ \displaystyle q }[/math]에 대해 [math]\displaystyle{ \displaystyle \sigma\left(t\right)=q2^{s+1} }[/math]이고, [math]\displaystyle{ \displaystyle 2^{s+1}t=\left(2^{s+1}-1\right)\sigma\left(t\right)=\left(2^{s+1}-1\right)qs^{s+1} }[/math]이다. 곧, [math]\displaystyle{ \displaystyle t=q\left(2^{s+1}-1\right) }[/math]. 여기서, [math]\displaystyle{ \displaystyle t+q=2^{s+1}q=\sigma\left(t\right) }[/math]임을 알 수 있다. 한편, [math]\displaystyle{ \displaystyle q\mid t,\,q\neq t }[/math]이므로, [math]\displaystyle{ \displaystyle q=1 }[/math]이어야만 한다. 만약 아니라면, [math]\displaystyle{ \displaystyle t\mid t,q\mid t,1\mid t }[/math]이므로 [math]\displaystyle{ \displaystyle \sigma\left(t\right)\geq1+q+t }[/math]이라 모순이다. 따라서, [math]\displaystyle{ \displaystyle \sigma\left(t\right)=t+1 }[/math]이고, 이는 곧 [math]\displaystyle{ \displaystyle t=2^{s+1}-1 }[/math]가 소수임을 의미한다. 따라서, [math]\displaystyle{ \displaystyle n=2^st=2^s\left(2^{s+1}-1\right) }[/math]. 마지막으로, [math]\displaystyle{ \displaystyle s\geq1 }[/math]이므로, [math]\displaystyle{ \displaystyle m=s+1\geq2 }[/math].
- 이 성질은 곧 짝수인 완전수와 메르센 소수가 일대일 대응한다는 사실을 알려주며, 유클리드-오일러 정리라고도 부른다. 유클리드는 자신의 저서[7]에[math]\displaystyle{ \displaystyle 2^m-1 }[/math]이 소수면 [math]\displaystyle{ \displaystyle 2^{m-1}\left(2^m-1\right) }[/math]이 완전수임을 증명하였다. 일대일 대응한다는 성질은 19세기에 와서야 오일러에 의해 증명되었다.[8]
메르센 소수 목록
순서
|
[math]\displaystyle{ \displaystyle p }[/math]
|
자리수
|
발견 연도 및 발견자
|
1
|
2
|
1
|
|
2
|
3
|
1
|
|
3
|
5
|
2
|
|
4
|
7
|
3
|
|
5
|
13
|
4
|
1456 미상
|
6
|
17
|
6
|
1588 Cataldi
|
7
|
19
|
6
|
1588 Cataldi
|
8
|
31
|
10
|
1772 Euler
|
9
|
61
|
19
|
1883 Pervushin
|
10
|
89
|
27
|
1911 Powers
|
11
|
107
|
33
|
1914 Powers
|
12
|
127
|
39
|
1876 Lucas
|
13
|
521
|
157
|
1952 Robinson
|
14
|
607
|
183
|
1952 Robinson
|
15
|
1279
|
386
|
1952 Robinson
|
16
|
2203
|
664
|
1952 Robinson
|
17
|
2281
|
687
|
1952 Robinson
|
18
|
3217
|
969
|
1957 Riesel
|
19
|
4253
|
1281
|
1961 Hurwitz
|
20
|
4423
|
1332
|
1961 Hurwitz
|
21
|
9689
|
2917
|
1963 Gillies
|
22
|
9941
|
2993
|
1963 Gillies
|
23
|
11213
|
3376
|
1963 Gillies
|
24
|
19937
|
6002
|
1971 Tucker
|
25
|
21701
|
6533
|
1978 Noll, Nickel
|
26
|
23209
|
6987
|
1979 Noll
|
27
|
44497
|
13395
|
1979 Nelson, Slowinski
|
28
|
86243
|
25962
|
1982 Slowinski
|
29
|
110543
|
33265
|
1988 Colquitt, Welch
|
30
|
132049
|
39751
|
1983 Slowinski
|
31
|
216091
|
65050
|
1985 Slowinski
|
32
|
756839
|
227832
|
1992 Slowinski, Gage
|
33
|
859433
|
258716
|
1994 Slowinski, Gage
|
34
|
1257787
|
378632
|
1996 Slowinski, Gage
|
35
|
1398269
|
420921
|
1996 Armengaud, Woltman, et al.
|
36
|
2976221
|
895932
|
1997 Spence, Woltman
|
37
|
3021377
|
909526
|
1998 Clarkson, Woltman, Kurowski, et al.
|
38
|
6972593
|
2098960
|
1999 Hajratwala, Woltman Kurowski, et al.
|
39
|
13466917
|
4053946
|
2001 Clarkson, Woltman, Kurowski et al.
|
40
|
20996011
|
6320430
|
2003 Schafer
|
41
|
24036583
|
7235733
|
2004 Findley
|
42
|
25964951
|
7816230
|
2005 Nowak
|
43
|
30402457
|
9152052
|
2005 Cooper, Boone
|
44
|
32582657
|
9808358
|
2006 Cooper, Boone
|
45?
|
37156667
|
11185272
|
2008, Elvenich, Woltman, Kurowski, et al.
|
46?
|
42643801
|
12837064
|
2009 Odd Magnar
|
47?
|
43112609
|
12978189
|
2008 Smith, Woltman, Kurowski, et al.
|
48?
|
57885161
|
17425170
|
2013 Cooper, Woltman, Kurowski, et al.
|
49?
|
74207281
|
22338618
|
2016 Cooper, et al.
|
외부 링크
각주
- ↑ [math]\displaystyle{ \displaystyle \gcd\left(2^a-1,2^b-1\right)=2^{\gcd\left(a,b\right)}-1 }[/math]임을 유클리드 호제법을 사용하여 보일 수 있다.
- ↑ [math]\displaystyle{ \displaystyle M_p }[/math]는 홀수이므로 2를 소인수로 가질 수 없다.
- ↑ 자기 자신을 제외한 약수의 합이 자기 자신과 같은 수
- ↑ [math]\displaystyle{ \displaystyle \sigma\left(n\right) }[/math]은 [math]\displaystyle{ \displaystyle n }[/math]의 양의 약수의 합. 약수함수를 참조하라.
- ↑ [math]\displaystyle{ \displaystyle \sigma\left(n\right) }[/math]은 곱셈적 함수이므로 저렇게 쪼갤 수 있다. 자세한 것은 항목 참조.
- ↑ 증명은 수학적 귀납법을 사용
- ↑ Euclid, Prop. IX.36
- ↑ Euler, Leonhard (1849), "De numeris amicibilibus"
|
수의 종류 |
|
---|
수학 상수 | |
자연수 및 정수 | |
---|
유리수 및 실수 | |
---|
복소수 및 확장 | |
---|
|