로그인하고 있지 않습니다. 편집하면 당신의 IP 주소가 공개적으로 기록됩니다. 계정을 만들고 로그인하면 편집 시 사용자 이름만 보이며, 위키 이용에 여러 가지 편의가 주어집니다.스팸 방지 검사입니다. 이것을 입력하지 마세요!== 정의 == '''메르센 수'''(Mersenne number)는 <math>\displaystyle 2^n-1\; (n\ge 2)</math> 꼴로 표현되는 [[정수]]를 의미한다. '''메르센 소수'''(Mersenne prime)는 메르센 수 중 [[소수]]인 [[수]]이다. 즉, 양의 정수 <math>\displaystyle n</math>에 대해 <math>\displaystyle M_n=2^n-1\;(n\ge 2)</math>가 소수이면 <math>\displaystyle M_n</math>를 메르센 소수라고 한다. 메르센 소수라는 이름은 프랑스의 수학자인 마랭 메르센(Marin Mersenne)에게서 따온 것이다. 처음 10개 메르센 소수의 값은 아래와 같다. *3, 7, 31, 127, 8191, 131071, 524287, 2147483647, 2305843009213693951, 618970019642690137449562111, … == 성질 == 메르센 수는 <math>\displaystyle M_n= 2^{n-1}+2^{n-2}+\cdots+2+1</math> 꼴로 나타낼 수 있으므로 111…11<sub>(2)</sub>과 같이 써지며, 1이 <math>n</math>개 들어간다. 즉 [[이진법]] 표현 시 모든 자리수가 1로 표시되므로 메르센 소수는 이진법 [[단위 반복 소수]]이다. === 기본 성질 === #메르센 수 <math>\displaystyle M_n=2^n-1</math>이 소수면 <math>\displaystyle n</math>도 소수이다. #*'''증명 ①''': <math>\displaystyle n</math>이 소수가 아니라면, <math>\displaystyle 1< a< n</math>인 <math>\displaystyle n</math>의 약수 <math>\displaystyle a</math>가 존재한다. 그럼, <math>\displaystyle n\equiv 0\pmod a</math>이고, <math>\displaystyle 2^n-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 n</math>이 합성수이면, <math>\displaystyle n=ab,\ 1<a,b<n </math>인 약수 <math>a, b</math>가 존재한다. <math>\displaystyle 2^a=x</math>로 치환하면 <math>\displaystyle x\ge 4, M_n = 2^{ab}-1 = x^b-1 = (x-1)(x^{b-1} + x^{b-2} +\cdots+ x+1)</math>과 같이 쓸 수 있다. 따라서 <math>x-1 \mid M_n</math>이다. 이때 <math>\displaystyle 3 \le x-1 < M_n</math>이므로 <math>M_n</math>은 합성수가 된다. #*두 증명은 표현 방식만 다를 뿐 접근 방법은 같다. 메르센 수는 주로 소수 찾기 및 탐구에 중점을 두며, 지수가 합성수인 수는 보통 관심의 대상이 아니다. #*'''위 명제의 역은 성립하지 않는다.''' 즉 지수가 소수라고 해서 해당 메르센 수는 소수라고 할 수 없다. 가령 11은 소수이지만 <math>M_{11}=2047= 23\cdot 89</math>로 반례가 존재한다. 사실 <math>p</math>가 소수이지만 <math>M_p</math>는 합성수인 예가 메르센 소수인 경우보다 훨씬 많으며, 수가 커질수록 메르센 소수 찾기란 하늘의 별 따기다. #<math>n</math>이 3 이상의 홀수일 때, <math>M_n</math>을 120으로 나눈 나머지는 7 또는 31이다. #*'''증명''': <math>\displaystyle 2^7\equiv 2^3 \pmod{120}</math>이므로 임의의 자연수 <math>k</math>에 대해 <math>\displaystyle 2^{4k+3}\equiv 8 \pmod{120},\ 2^{4k+5}\equiv 32 \pmod{120}</math>가 성립한다. <math>n \equiv 3 \pmod 4 </math>이면 <math>\displaystyle 2^n \equiv 8 \pmod{120} \Leftrightarrow M_n \equiv 7 \pmod{120}</math>가 성립하고, <math>n \equiv 1 \pmod 4,\ n \ge 5</math>이면 <math>\displaystyle 2^n \equiv 32 \pmod{120} \Leftrightarrow M_n \equiv 31 \pmod{120}</math>임을 알 수 있다. #*따라서 지수가 3 이상인 메르센 소수를 십진법으로 쓰면 일의 자리수는 1또는 7이다. #서로 다른 소수 <math>p,q</math>에 대해 <math>M_p,M_q</math>는 [[서로소]]이다. #*'''증명''': <math>\displaystyle \gcd \left(M_p,M_q \right) = 2^{\gcd(p,q)}-1</math>인데, 서로 다른 소수는 서로소이므로 <math>\gcd(p,q)=1</math> 즉 <math>\gcd \left(M_p,M_q \right)=1</math>이 성립한다. 따라서 <math>M_p,M_q</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>이다.<ref><math>\displaystyle \gcd\left(2^a-1,2^b-1\right)=2^{\gcd\left(a,b\right)}-1</math>임을 [[유클리드 호제법]]을 사용하여 보일 수 있다.</ref> 따라서, <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>가 홀수이므로,<ref><math>\displaystyle M_p</math>는 홀수이므로 2를 소인수로 가질 수 없다.</ref> <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>의 형태이므로, 저 형태를 가진 소인수를 곱한 임의의 약수도 같은 형태이다. #* 예를 들어, 370052357은 소수이고 88940026013534293337은 <math>\displaystyle 2^{370052357}-1</math>의 약수인데, <math>\displaystyle 88940026013534293337=2\cdot 120172219324\cdot 370052357+1</math>임을 확인할 수 있다. #<math>n</math>이 홀수일 때, <math>M_n</math>의 약수를 8로 나눈 나머지는 1 또는 7이다. (이때 <math>n</math>이 소수일 필요는 없다) #*'''증명''': <math>M_n</math>의 소인수 <math>q</math>를 가정하자. 그러면 <math>\displaystyle 2^n \equiv 1 \pmod q</math>가 성립한다. 여기서 양변에 2를 곱하면 <math>\displaystyle 2^{n+1} \equiv 2 \pmod q</math>이다. 이 식에서 좌변은 2의 지수가 짝수이므로 [[제곱수]]이며, <math>\displaystyle 2^{\frac{n+1}{2}}=x</math>라 하면 <math>\displaystyle x^2 \equiv 2 \pmod q</math>가 된다. 다시 말해 2는 법 <math>q</math>에 대한 [[이차잉여]]이며, 이를 만족하는 <math>q</math>의 조건은 <math>q \equiv \pm 1 \pmod 8</math>이다. 또한 어떤 <math>M_n</math>의 약수 <math>r</math>를 <math>r=q_1 q_2 \cdots q_k</math>와 같이 소인수<math>q_j (1\le j \le k)</math>의 곱으로 쓸 때, <math>q_j \equiv \pm 1 \pmod 8</math>이므로 <math>r \equiv \pm 1 \pmod 8</math>도 성립한다. #* 예: <math>M_{29} = 233 \cdot 1103 \cdot 2289</math> 에서 각 소인수를 8로 나눈 나머지는 각각 1, 7, 1이다. #소수 <math>p</math>가 [[소피 제르맹 소수]]이고 4로 나눈 나머지가 3이면 <math>2p+1</math>은 <math>M_p</math>의 약수이다. #*'''증명''': <math>p</math>가 소피 제르맹 소수이면 <math>2p+1</math>도 소수이다. 또한 <math>p \equiv 3 \pmod 4</math>이면 <math>2p+1 \equiv 7 \pmod 8</math>이므로, 2는 법 <math>2p+1</math>에 대한 이차잉여이다. 즉 [[오일러의 규준]]에 따르면 <math>\displaystyle 2^{\frac{(2p+1)-1}{2}} \equiv 1 \pmod{2p+1}</math>이 성립한다. 간단히 정리하면 <math>\displaystyle 2^p \equiv 1 \pmod{2p+1}</math>이고, <math>\displaystyle 2p+1 \mid 2^p-1</math>을 만족한다. #* 예: <math>\displaystyle 7 \mid M_{3}(=7),\ 23 \mid M_{11},\ 47 \mid M_{23},\ 4007 \mid M_{2003},\ 4079 \mid M_{2039}</math> #* 참고: <math>p</math>가 소피 제르맹 소수이지만 4로 나눈 나머지가 1이면 <math>2p+1</math>은 <math>M_p</math>의 약수가 아니다. 또, 2와 3을 제외한 모든 소피 제르맹 소수는 <math>p=6k-1</math> 형태이므로, 여기에 4로 나눈 나머지가 3이라는 조건이 붙으면 <math>p=12k-1</math> 꼴로 표현된다. === [[완전수]]와의 관계 === #<math>\displaystyle n</math>이 짝수인 [[완전수]]<ref>자기 자신을 제외한 약수의 합이 자기 자신과 같은 수</ref>라면 <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><ref><math>\displaystyle \sigma\left(n\right)</math>은 <math>\displaystyle n</math>의 양의 약수의 합. [[약수함수]]를 참조하라.</ref><ref><math>\displaystyle \sigma\left(n\right)</math>은 [[곱셈적 함수]]이므로 저렇게 쪼갤 수 있다. 자세한 것은 항목 참조.</ref><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>로 나타낼 수 있다.<ref>증명은 [[수학적 귀납법]]을 사용</ref> 그럼, <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)q2^{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>. #*이 성질은 곧 짝수인 [[완전수]]와 메르센 소수가 일대일 대응한다는 사실을 알려주며, 유클리드-오일러 정리라고도 부른다. 유클리드는 자신의 저서<ref>Euclid, Prop. IX.36</ref>에<math>\displaystyle 2^m-1</math>이 소수면 <math>\displaystyle 2^{m-1}\left(2^m-1\right)</math>이 완전수임을 증명하였다. 일대일 대응한다는 성질은 19세기에 이르러 오일러가 증명하였다.<ref>Euler, Leonhard (1849), "De numeris amicibilibus"</ref> == 발견 과정 == 2의 지수가 작은 메르센 수는 직접 나누기로 소수 여부를 알 수 있다. 처음 네 개 항인 3, 7, 31, 127은 기원전부터 소수라는 사실을 알 수 있었다. 다섯 번째인 8191(p=13)은 89 이하의 소수까지 나눗셈을 시도하면 된다. 다음 항인 131071(p=17)은 359 이하, 그 다음 항인 524287(p=19)은 719 이하의 소수까지 나눠보면 소수임을 밝혀낼 수 있다. 실제로 이탈리아의 수학자인 피에트로 카탈디(Pietro Cataldi)는 이 방법으로 1588년에 소수임을 알아냈다. <ref>[https://primes.utm.edu/notes/by_year.html PrimePages, "The Largest Known prime by Year: A Brief History"]</ref> <math>M_{23}</math>은 1640년 [[피에르 드 페르마|페르마]]가 소인수 47을 찾으면서 합성수임이 판명 났다. <math>M_{29}</math>는 크기는 앞선 항들보다 훨씬 커지지만 1738년 [[레온하르트 오일러]]가 233과 1103을 약수로 가진다는 걸 알아냈다. 두 수는 직접 나누기로 그나마 어렵지 않게 소인수분해가 된다. 하지만 <math>M_{31}</math>, 즉 2147483647<ref>프로그램 언어에서 int형 변수의 최댓값</ref>은 제곱근 이하의 소수가 46337까지인데, 컴퓨터가 없던 시절에는 직접 나누기로 밝히기란 매우 버거운 수준이었다. 한편 마랭 메르센은 17세기에 <math>\displaystyle M_p=2^p-1</math> 형태의 수 중 2의 지수가 257 이하에서 아래 값일 때 <math>M_p</math>는 소수일 것이라는 추측을 내놓았다. *<math>p \in \{2, 3, 5, 7, 13, 17, 19, 31, 67, 127, 257 \}</math> 당시에는 첫 일곱 항인 <math>M_{19}</math>까지는 소수라는 걸 알고 있었고 그 다음 수들은 어마무시한 크기 때문에 확인을 다 할 수 없었다. 이후 [[레온하르트 오일러|오일러]]가 1772년에 직접 나누기의 발전된 방법으로 <math>M_{31}</math>이 소수임을 밝혀냈다. (아래 문단 참조) 이로써 위 후보 중 31까지는 참이 된다. 그런데 메르센이 제시한 후보 중 빠진 것과 잘못 넣은 것이 있다. <math>M_{61}, M_{89}, M_{107}</math>은 실제로 소수가 맞지만 메르센이 빠뜨린 수이고, <math>M_{67}, M_{257}</math>은 소수가 아니지만 목록에 넣은 것이다. === 열 자리 이상의 메르센 소수 === 오일러는 위의 "약수 관련 성질" 문단의 정리를 이용하여 약수 후보를 먼저 추리고 <math>M_{31}</math>가 소수임을 증명했다. 구체적인 과정은 아래와 같다. *<math>q \mid M_{31}</math>인 소인수를 찾으려고 한다. 위에서 증명한 정리를 가져오면 <math>q \equiv 1 \pmod{62},\ q \equiv \pm 1 \pmod 8 </math>을 만족해야 한다. 이 조건식은 <math>q \equiv 1 \ \text{or}\ 63 \pmod {248}</math>과 같이 쓸 수 있다. *바로 위 조건을 만족하는 수를 나열한다. <math>q \in \{63,249,311,497,559,\cdots\}</math> 그 다음 소수가 아닌 수를 제외한다. 어떤 수의 약수가 합성수이면 그 합성수의 소인수도 원래 수의 약수이므로, 작은 수부터 차례대로 올라갈 때는 소수인 경우만 알아보면 된다. 그러면 <math>q \in \{311,1303,1489,2543,\cdots\}</math> 과 같이 추려져서 <math>M_{31}</math>의 제곱근 이하의 가장 큰 소수까지 빠르게 도달하고, 이들 중 어떤 수로도 나누어 떨어지지 않음을 확인할 수 있다. 물론 메르센 수는 자릿수가 지수에 비례하여 커져서, 저렇게 약수 후보를 솎아낸다 해도 소요시간은 마찬가지로 급격히 증가한다. 이 경우 보다 빠른 소수 판별법이 필요하다. <math>M_{31}</math> 다음으로 발견된 수는 <math>M_{127}</math>이다. [[에두아르 뤼카]]는 <math>M_2=3,\ M_3=7,\ M_7=127</math>이 메르센 소수이니까 혹시 <math>M_{127}</math>도 소수가 아닐까 하는 추측을 하였고<ref>물론 이 논리는 항상 맞지는 않다. 가령 <math>M_{13}=8191</math>은 소수이지만 <math>M_{8191}</math>은 338193759479로 나누어 떨어진다.</ref>, 1876년 실제로 소수가 맞다는 걸 증명해내었다. 그 다음으로 발견된 세 개는 이보다 작은 값이다. 1883년 페르부신(Ivan Pervushin)은 <math>M_{61}</math>을, 1911년·1914년 파워스(R.E. Powers)는 각 연도에 <math>M_{89},M_{107}</math>이 소수임을 밝혀냈다. 19세기까지 발견된 메르센 소수는 위 목록까지 총 12개이다. === 컴퓨터 도입 이후 === 역사상 발견된 가장 큰 소수의 지위는 보통 메르센 소수가 차지했다. 자리수가 10만 혹은 100만을 넘어가는 소수는 컴퓨터가 발달하면서 다수 발견할 수 있게 되었는데, 메르센 소수는 <math>\displaystyle M_p=2^p-1</math> 형태의 특수성을 이용하여 소수 여부를 빠르게 확인할 수 있다. 메르센 수가 소수인지 여부는 '''[[뤼카-레머 소수판정법]]'''(Lucas-Lehmer primality test)으로 밝혀낼 수 있다. 구체적인 정리와 증명은 해당 문서 참고. 이 판별법은 20세기 중반 컴퓨터가 들어서면서 위력을 발하기 시작하였다. 1952년 라파엘 로빈슨(Raphael Mitchel Robinson)은 컴퓨터의 도움을 받아 <math>M_{521}, M_{601}, M_{1279}, M_{2203}, M_{2281}</math>을 한 해동안 발견하였다. 이후 컴퓨터의 성능이 발달하면서 여러 수학자들이 훨씬 더 큰 소수들을 찾았고, 1996년 9월까지 발견된 메르센 소수는 34개로 늘어났다. 1996년부터 메르센 소수 찾기 프로젝트를 진행하는 [[GIMPS]]에서도 이 판별법을 이용한다. 35번째 메르센 소수인 <math>M_{1398269}</math>부터는 모두 이 프로젝트에서 찾아내었다. 테스트 대상은 2의 지수가 소수인 모든 메르센 수로, 현재 활발하게 진행 중인 범위는 2의 10억 제곱 미만이다. == 메르센 소수 목록 == 2021년 10월 13일까지 발견된 메르센 소수는 모두 51개로, 가장 큰 항은 <math>M_{82589933}</math>이다. 48번째 소수인 <math>M_{57885161}</math> 밑으로는 모든 소수 지수에 해당하는 메르센 수의 소수 여부를 초검 및 재검까지 마쳤다. 지수가 1억 500만 미만인 모든 메르센 수도 초검을 마쳤으나, 일부 재검은 아직 거치지 않았기에 2의 5820만 제곱부터 1억 500만 제곱 사이에서 혹시 발견하지 못한 메르센 소수가 존재할 수 있다. 따라서 아래 표에서 48번째까지가 확정된 순번이며, ? 표시된 49, 50, 51번째는 순번이 밀릴 여지가 희박하게나마 남아 있다. {| class="wikitable" ! 순서 ! <math>\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. |- | 50? | 77232917 | 23249425 | 2017 Jon Pace |- | 51? | 82589933 | 24862048 | 2018 Patrick Laroche |} == 기타 == [[하노이의 탑]]에서 원반 <math>n</math>개를 옮기는 데 필요한 최소 횟수는 <math>2^n-1</math>회이다. == 관련 문서 및 외부 링크 == * [[뤼카-레머 소수판정법]] * [[페르마 수]] * [[와그스태프 소수]] * [[단위 반복 소수]] * [http://www.mersenne.org/ Great Internet Mersenne Prime Search - GIMPS] {{각주}} {{소수}} [[분류:정수론]] 요약: 리브레 위키에서의 모든 기여는 크리에이티브 커먼즈 저작자표시-동일조건변경허락 3.0 라이선스로 배포됩니다(자세한 내용에 대해서는 리브레 위키:저작권 문서를 읽어주세요). 만약 여기에 동의하지 않는다면 문서를 저장하지 말아 주세요. 글이 직접 작성되었거나 호환되는 라이선스인지 확인해주세요. 리그베다 위키, 나무위키, 오리위키, 구스위키, 디시위키 및 CCL 미적용 사이트 등에서 글을 가져오실 때는 본인이 문서의 유일한 기여자여야 하고, 만약 본인이 문서의 유일한 기여자라는 증거가 없다면 그 문서는 불시에 삭제될 수 있습니다. 취소 편집 도움말 (새 창에서 열림) | () [] [[]] {{}} {{{}}} · <!-- --> · [[분류:]] · [[파일:]] · [[미디어:]] · #넘겨주기 [[]] · {{ㅊ|}} · <onlyinclude></onlyinclude> · <includeonly></includeonly> · <noinclude></noinclude> · <br /> · <ref></ref> · {{각주}} · {|class="wikitable" · |- · rowspan=""| · colspan=""| · |} {{lang|}} · {{llang||}} · {{인용문|}} · {{인용문2|}} · {{유튜브|}} · {{다음팟|}} · {{니코|}} · {{토막글}} {{삭제|}} · {{특정판삭제|}}(이유를 적지 않을 경우 기각될 가능성이 높습니다. 반드시 이유를 적어주세요.) {{#expr:}} · {{#if:}} · {{#ifeq:}} · {{#iferror:}} · {{#ifexist:}} · {{#switch:}} · {{#time:}} · {{#timel:}} · {{#titleparts:}} __NOTOC__ · __FORCETOC__ · __TOC__ · {{PAGENAME}} · {{SITENAME}} · {{localurl:}} · {{fullurl:}} · {{ns:}} –(대시) ‘’(작은따옴표) “”(큰따옴표) ·(가운뎃점) …(말줄임표) ‽(물음느낌표) 〈〉(홑화살괄호) 《》(겹화살괄호) ± − × ÷ ≈ ≠ ∓ ≤ ≥ ∞ ¬ ¹ ² ³ ⁿ ¼ ½ ¾ § € £ ₩ ¥ ¢ † ‡ • ← → ↔ ‰ °C µ(마이크로) Å °(도) ′(분) ″(초) Α α Β β Γ γ Δ δ Ε ε Ζ ζ Η η Θ θ Ι ι Κ κ Λ λ Μ μ(뮤) Ν ν Ξ ξ Ο ο Π π Ρ ρ Σ σ ς Τ τ Υ υ Φ φ Χ χ Ψ ψ Ω ω · Ά ά Έ έ Ή ή Ί ί Ό ό Ύ ύ Ώ ώ · Ϊ ϊ Ϋ ϋ · ΐ ΰ Æ æ Đ(D with stroke) đ Ð(eth) ð ı Ł ł Ø ø Œ œ ß Þ þ · Á á Ć ć É é Í í Ĺ ĺ Ḿ ḿ Ń ń Ó ó Ŕ ŕ Ś ś Ú ú Ý ý Ź ź · À à È è Ì ì Ǹ ǹ Ò ò Ù ù · İ Ż ż ·  â Ĉ ĉ Ê ê Ĝ ĝ Ĥ ĥ Î î Ĵ ĵ Ô ô Ŝ ŝ Û û · Ä ä Ë ë Ï ï Ö ö Ü ü Ÿ ÿ · ǘ ǜ ǚ ǖ · caron/háček: Ǎ ǎ Č č Ď ď Ě ě Ǐ ǐ Ľ ľ Ň ň Ǒ ǒ Ř ř Š š Ť ť Ǔ ǔ Ž ž · breve: Ă ă Ğ ğ Ŏ ŏ Ŭ ŭ · Ā ā Ē ē Ī ī Ō ō Ū ū · à ã Ñ ñ Õ õ · Å å Ů ů · Ą ą Ę ę · Ç ç Ş ş Ţ ţ · Ő ő Ű ű · Ș ș Ț ț 이 문서에서 사용한 틀: 틀:Skin (원본 보기) (준보호됨)틀:각주 (원본 보기) (준보호됨)틀:둘러보기 상자 (원본 보기) (보호됨)틀:둘러보기 상자/핵심 (원본 보기) (보호됨)틀:소수 (편집) 틀:틀바 (원본 보기) (준보호됨)