정의
[math]\displaystyle{ 2^n-1\; (n\ge 2) }[/math] 꼴의 정수를 메르센 수(Mersenne number)라고 한다. 메르센 수 중에서 소수인 수를 메르센 소수(Mersenne prime)라고 한다. 즉, 양의 소수 \(p\)에 대해 [math]\displaystyle{ M_p=2^p-1\;(p\ge 2) }[/math]가 소수이면 \(M_p\)를 메르센 소수라고 한다. 메르센 소수라는 이름은 프랑스의 수학자인 마랭 메르센(Marin Mersenne)에게서 따온 것이다.
성질
- 메르센 수 [math]\displaystyle{ M_n=2^n-1 }[/math]이 소수면 [math]\displaystyle{ n }[/math]도 소수이다.
- [math]\displaystyle{ n }[/math]이 소수가 아니라면, [math]\displaystyle{ 1\lt a\lt n }[/math]인 [math]\displaystyle{ n }[/math]의 약수 [math]\displaystyle{ a }[/math]가 존재한다. 그럼, [math]\displaystyle{ m\equiv 0\pmod a }[/math]이고, [math]\displaystyle{ 2^m-1\equiv2^0-1\pmod{2^a-1} }[/math]임을 유클리드 호제법을 사용해 보일 수 있다. 따라서, [math]\displaystyle{ 2^a-1\mid2^n-1 }[/math]이고, [math]\displaystyle{ M_n }[/math]은 소수가 아니다.
- [math]\displaystyle{ p }[/math]가 2가 아닌 소수라면, 메르센 수 [math]\displaystyle{ M_p }[/math]의 약수는 전부 [math]\displaystyle{ 2kp+1,\,k\in\mathbb{Z}^+ }[/math]의 형태이다.
- [math]\displaystyle{ q }[/math]를 [math]\displaystyle{ M_p=2^p-1 }[/math]의 소인수라 가정하자. 페르마의 소정리에 의해, [math]\displaystyle{ 2^{q-1}\equiv1\pmod q }[/math]이므로, [math]\displaystyle{ q\mid2^{q-1}-1 }[/math]이다. [math]\displaystyle{ q\mid2^p-1 }[/math]이기도 하므로, [math]\displaystyle{ q\mid\gcd\left(2^{q-1}-1,2^p-1\right) }[/math]이다. 한편, [math]\displaystyle{ \gcd\left(2^{q-1}-1,2^p-1\right)=2^{\gcd\left(q-1,p\right)}-1 }[/math]이다.[1] 따라서, [math]\displaystyle{ q\mid2^{\gcd\left(q-1,p\right)}-1 }[/math]이다. 그런데 [math]\displaystyle{ p }[/math]가 소수이므로, [math]\displaystyle{ \gcd\left(q-1,p\right) }[/math]은 1 또는 [math]\displaystyle{ p }[/math]이다. 만약 [math]\displaystyle{ \gcd\left(q-1,p\right)=1 }[/math]이라면, [math]\displaystyle{ q\mid2^{\gcd\left(q-1,p\right)}-1=2^1-1=1 }[/math]이므로, [math]\displaystyle{ q }[/math]가 소수라는 가정에 모순된다. 따라서 [math]\displaystyle{ \gcd\left(q-1,p\right)=p }[/math]이고, [math]\displaystyle{ p\mid q-1 }[/math]이다. 곧, 적당한 양의 정수 [math]\displaystyle{ m }[/math]에 대해 [math]\displaystyle{ q-1=mp }[/math]이다. [math]\displaystyle{ q }[/math]가 홀수이므로,[2] [math]\displaystyle{ q-1 }[/math]은 짝수이고, [math]\displaystyle{ p }[/math]는 홀수이므로, [math]\displaystyle{ m }[/math]은 짝수여야 한다. 즉, 적당한 양의 정수 [math]\displaystyle{ k }[/math]에 대해 [math]\displaystyle{ q=mp+1=2kp+1 }[/math]이다. 마지막으로, [math]\displaystyle{ M_p }[/math]의 약수는 [math]\displaystyle{ M_p }[/math]의 적당한 소인수들의 곱이고, 임의의 소인수는 [math]\displaystyle{ 2kp+1 }[/math]의 형태이므로, 저 형태를 가진 소인수를 곱한 임의의 약수도 같은 형태이다.
- [math]\displaystyle{ n }[/math]이 짝수인 완전수[3]라면 [math]\displaystyle{ n=2^{m-1}\left(2^m-1\right) }[/math]이다 (단, [math]\displaystyle{ m\geq2 }[/math]인 정수, [math]\displaystyle{ 2^m-1 }[/math]은 (메르센) 소수). 이 명제의 역도 성립한다.
- [math]\displaystyle{ n=2^{m-1}\left(2^m-1\right) }[/math]이고, [math]\displaystyle{ m\geq2 }[/math]인 정수, [math]\displaystyle{ 2^m-1 }[/math]은 소수라 가정하자. [math]\displaystyle{ 2^m-1 }[/math]은 홀수인 소수이므로, [math]\displaystyle{ \gcd\left(2^{m-1},2^m-1\right)=1 }[/math]이다. 즉, [math]\displaystyle{ \sigma\left(n\right)=\sigma\left(2^{m-1}\right)\sigma\left(2^m-1\right) }[/math][4][5][math]\displaystyle{ =\frac{2^m-1}{2-1}\left(2^m-1+1\right)=\left(2^m-1\right)2^m=2n }[/math]. 따라서, [math]\displaystyle{ n }[/math]은 완전수이다.
- 역으로, [math]\displaystyle{ n }[/math]이 짝수인 완전수라 가정하자. 일단, 적당한 홀수 [math]\displaystyle{ t }[/math]와 1이상인 정수 [math]\displaystyle{ s }[/math]에 대해 [math]\displaystyle{ n=2^st }[/math]로 나타낼 수 있다.[6] 그럼, [math]\displaystyle{ 2n=2^{s+1}t=\sigma\left(n\right)=\sigma\left(2^st\right) }[/math]. [math]\displaystyle{ \gcd\left(2^s,t\right)=1 }[/math]이므로, [math]\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{ 2^{s+1}t=\left(2^{s+1}-1\right)\sigma\left(t\right) }[/math]이고, [math]\displaystyle{ 2^{s+1}\mid\left(2^{s+1}-1\right)\sigma\left(t\right) }[/math]임을 알 수 있다. 한편, [math]\displaystyle{ \gcd\left(2^{s+1},2^{s+1}-1\right)=1 }[/math]이므로, [math]\displaystyle{ 2^{s+1}\mid\sigma\left(t\right) }[/math]이다. 따라서, 적당한 정수 [math]\displaystyle{ q }[/math]에 대해 [math]\displaystyle{ \sigma\left(t\right)=q2^{s+1} }[/math]이고, [math]\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{ t=q\left(2^{s+1}-1\right) }[/math]. 여기서, [math]\displaystyle{ t+q=2^{s+1}q=\sigma\left(t\right) }[/math]임을 알 수 있다. 한편, [math]\displaystyle{ q\mid t,\,q\neq t }[/math]이므로, [math]\displaystyle{ q=1 }[/math]이어야만 한다. 만약 아니라면, [math]\displaystyle{ t\mid t,q\mid t,1\mid t }[/math]이므로 [math]\displaystyle{ \sigma\left(t\right)\geq1+q+t }[/math]이라 모순이다. 따라서, [math]\displaystyle{ \sigma\left(t\right)=t+1 }[/math]이고, 이는 곧 [math]\displaystyle{ t=2^{s+1}-1 }[/math]가 소수임을 의미한다. 따라서, [math]\displaystyle{ n=2^st=2^s\left(2^{s+1}-1\right) }[/math]. 마지막으로, [math]\displaystyle{ s\geq1 }[/math]이므로, [math]\displaystyle{ m=s+1\geq2 }[/math].
- 이 성질은 곧 짝수인 완전수와 메르센 소수가 일대일 대응한다는 사실을 알려준다.
메르센 소수 목록
| 순서 | \(p\) | 자리수 | 발견 연도 및 발견자 |
|---|---|---|---|
| 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. |
외부 링크
각주
- ↑ [math]\displaystyle{ \gcd\left(2^a-1,2^b-1\right)=2^{\gcd\left(a,b\right)}-1 }[/math]임을 유클리드 호제법을 사용하여 보일 수 있다.
- ↑ [math]\displaystyle{ M_p }[/math]는 홀수이므로 2를 소인수로 가질 수 없다.
- ↑ 자기 자신을 제외한 약수의 합이 자기 자신과 같은 수
- ↑ [math]\displaystyle{ \sigma\left(n\right) }[/math]은 [math]\displaystyle{ n }[/math]의 양의 약수의 합
- ↑ [math]\displaystyle{ \sigma\left(n\right) }[/math]은 multiplicative 함수이므로 저렇게 쪼갤 수 있다. multiplicative 함수란, [math]\displaystyle{ m, n }[/math]이 서로소일 때 [math]\displaystyle{ f\left(mn\right)=f\left(m\right)f\left(n\right) }[/math]이 성립하는 함수 [math]\displaystyle{ f }[/math]를 말한다. 만약 [math]\displaystyle{ m, n }[/math]이 서로소가 아니여도 성립한다면 completely multiplicative라 부른다.
- ↑ 증명은 수학적 귀납법을 사용