|
정수론 Number Theory |
|||
|
{{{#!wiki style="margin: 0 -10px -5px; min-height: calc(1.5em + 5px)" {{{#!folding [ 펼치기 · 접기 ] {{{#!wiki style="margin: -5px -1px -11px" |
공리 | ||
| 페아노 공리계 · 정렬 원리 · 수학적 귀납법 · 아르키메데스 성질 | |||
| 산술 | |||
| 나눗셈 | 약수· 배수 | 배수 · 약수( 소인수) · 소인수분해( 목록 · 알고리즘) · 공배수 · 공약수 · 최소공배수 · 최대공약수 | |
| 약수들의 합에 따른 수의 분류 | 완전수 · 부족수 · 과잉수 · 친화수 · 사교수 · 혼약수 · 반완전수 · 불가촉 수 · 괴짜수 | ||
| 정리 | 베주 항등식 · 산술의 기본정리 · 나눗셈 정리 | ||
| 기타 | 유클리드 호제법 · 서로소 | ||
| 디오판토스 방정식 | 페르마의 마지막 정리 · 피타고라스 세 쌍 · 버치-스위너턴다이어 추측(미해결) | ||
| 모듈러 연산 | |||
| 잉여역수 · 2차 잉여 · 기약잉여계 · 완전잉여계 · 중국인의 나머지 정리 · 합동식 · 페르마의 소정리 · 오일러 정리 · 윌슨의 정리 | |||
| 소수론 | |||
| 수의 분류 | 소수 · 합성수 · 메르센 소수 · 쌍둥이 소수( 사촌 소수 · 섹시 소수) · 페르마 소수 · 레퓨닛 수 | ||
| 분야 | 대수적 정수론( 국소체) · 해석적 정수론 | ||
| 산술함수 | 뫼비우스 함수 · 소수 계량 함수 · 소인수 계량 함수 · 약수 함수 · 오일러 파이 함수 · 폰 망골트 함수 · 체비쇼프 함수 · 소수생성다항식 | ||
| 정리 | 그린 타오 정리 · 페르마의 두 제곱수 정리 · 디리클레 정리 · 소피 제르맹의 정리 · 리만 가설(미해결) · 골드바흐 추측(미해결)( 천의 정리) · 폴리냑 추측(미해결) · 소수 정리 | ||
| 기타 | 에라토스테네스의 체 · 윌런스의 공식 | ||
1. 개요
메르센 수 [math(M(n))]은 [math(2^n-1)] 형태의 수를 말한다.[1] 메르센 소수는 메르센 수 중 소수인 것들을 가리킨다. [math(M(n))]이 메르센 소수이면 [math(n)]도 소수이다. 하지만 역으로 [math(n)]이 소수라고 해서 항상 [math(M(n))]도 소수가 되는 것은 아니다. 처음 네 개, 즉 [math(n=2,\,3,\,5,\,7)]일 때는 성립하지만 [math(2^{11}-1=2047=23\times89)]이고, [math(2^{23}-1=8388607=47\times178481)]인 것이 함정.참고로 [math(n=mk)]이 합성수인 경우, [math(m)]과 [math(k)]는 각각 2 이상의 자연수라 하면 [math(2^n-1=(2^m-1)(2^{(k-1)m}+2^{(k-2)m}+\dots+2^m+1))]이고 여기서 [math(m)], [math(k)]는 2 이상의 자연수라고 했으므로 [math(2^m-1)]과 [math(2^{(k-1)m}+2^{(k-2)m}+\dots+2^m+1)] 은 각각 2 이상의 자연수이다. 따라서 [math(2^n-1)]은 [math(2^m-1)]과 [math(2^k-1)]을 약수로 가지므로 합성수이다. [math(n=1)]일 경우에도 [math(2^1-1=1)]이니 소수가 아니다.
2. 역사
프랑스의 수도자이자 수학자인 마랭 메르센(1588~1648)은 [math(M(n))]이 소수가 되도록 하는 258보다 작은 수는 [math(n=2,\,3,\,5,\,7,\,13,\,17,\,19,\,31,\,\boldsymbol{67},\,127,\,\boldsymbol{257})] 이 전부라고 생각하였다. 하지만 그가 이 수들이 소수인지를 전부 확인해본 것은 아니었고, 틀린 것과 빠진 것이 있었다. 후에 [math(M(67))]과 [math(M(257))]은 소수가 아닌 것으로 판명되었고, 대신 [math(M(61))], [math(M(89))], [math(M(107))]이 추가되어 1947년에 [math(n\lt258)]일 때 [math(n=2,\,3,\,5,\,7,\,13,\,17,\,19,\,31,\,\boldsymbol{61},\,\boldsymbol{89},\,\boldsymbol{107},\,127)] 인 경우가 소수임을 확인했다.[math(M(31))] = 2147483647[2]이 소수임을 1772년 레온하르트 오일러가 증명했다. 1876년 루카스가 [math(M(127))]이 소수라고 확인하기 전까지는, [math(M(31))]은 알려진 소수들 중 가장 큰 수였다. 1883년 페르보차인이 [math(M(61))]이 소수임을 증명했는데, 이것이 메르센이 빠뜨린 것이었다. 이후 파우어스가 [math(M(89))], [math(M(107))]이 소수라는 사실도 확인했다.
1903년, 미국 수학자 학회에서 넬슨 콜이라는 교수가 " 큰 수의 소인수분해"라는 강연을 했다. 그는 아무 말 없이 [math(2^{67}-1)]을 칠판에 쓴 후 계산해서 [math(147,573,952,589,676,412,927)]을 얻었다. 그리고 다른 쪽 칠판에 [math(193,707,721\times761,838,257,287)]을 계산해서 똑같은 값인 [math(147,573,952,589,676,412,927)]을 얻었다. 그는 강의 도중 한 마디도 하지 않았지만 계산이 끝나자 온 강의실이 박수갈채로 메워졌다. 당시에 컴퓨터는커녕 제대로 된 계산기도 없었다는 사실을 생각하면...
그래도 메르센의 방법을 응용하면 큰 소수를 찾는 데 유용하게 쓸 수 있다. 예를 들어 현대적인 암호체계는 큰 소수를 사용하는데, 여기서 소수를 찾을 때 사용하는 페르마의 소정리는 메르센의 식에서 -1을 이항한 것이라 보면 된다.
컴퓨터가 발전한 덕에 메르센 소수의 발견이 급격히 진행되었다. 1952년 컴퓨터의 도움을 받아 [math(M(521))], [math(M(607))], [math(M(1279))], [math(M(2203))], [math(M(2281))] 등이 줄줄이 발견되었고, 1992년 32번째 메르센 소수인 M(756,839)이 발견되어 10만 자리(정확히는 227,832자리)를 돌파하였다. 그리고, 1999년에는 M(6,972,593)이 발견되면서 백만 자리(정확히는 2,098,960자리)를 돌파하였다.
2008년 8월 23일, UCLA 수학과의 에드슨 스미스가 [math(M(43,112,609))]을 발견하여 1천만 자리를 돌파하였다. 발견 당시는 45번째였으나, 이후에 2주 뒤에 이 수보다 작은 메르센 소수가 하나 발견되었고, 그 후로 10달 뒤에 또 하나가 더 발견되면서 이보다 작은 2개가 더 발견되어 크기순으로 47번째(추정)으로 순서가 재조정, 2018년 4월에 47번째로 확정되었다. 2017년 기준 45번째 메르센 소수인 [math(M(37,156,667))]까지는 모두 검증이 끝났으므로 순서를 확정지었다.
2013년 1월 25일 커티스 쿠퍼 교수가 이끄는 연구팀이 [math(M(57,885,161))]을 발견하였고, 48번째 메르센 소수로 기록되었다. 17,425,170자리의 수이며, 당시에는 그때까지 알려진 가장 큰 소수였다. 8년이 넘게 48번째 메르센 소수로 추정되다가 2021년 10월 6일 48번째 메르센 소수로 확정되었다. 이보다 큰 소수에 대해서는 미발견된 메르센 소수가 있는지는 아직 정확히 확인되지 않았기에 순서가 확정되지 않았으며, 중간에 다른 메르센 소수가 존재할 가능성도 있기 때문에 이후 메르센 소수의 순서에는 (추정)이 붙는다.
2016년 1월 7일 역시 쿠퍼 교수의 연구팀이 [math(M(74,207,281))]를 발견했다. 22,338,618자리 수이며, 3003으로 시작해서 6351로 끝난다. 참고로, 여기서부터는 메르센 소수에 대한 검증이 완전히 끝나지 않은 상태라서 중간에 발견되지 않은 다른 메르센 소수가 있을 가능성도 있기에 순서에 추정이 붙는다. 현재 49번째 메르센 소수로 추정되고 있다.
2017년 12월 [math(M(77,232,917))]가 발견되었다. 23,249,425자리이며, 50번째 메르센 소수로 추정되고 있다.
2018년 12월 [math(M(82,589,933))]가 발견되었다. 24,862,048자리이며, 51번째 메르센 소수로 추정되고 있다.
2024년 10월 [math(M(136,279,841))]가 발견되었다. 41,024,320자리이며, 52번째 메르센 소수로 추정되고 있다.
참고로 GIMPS에서는 메르센 소수 발견자에게 포상금을 지급하는데, 최초로 1천만 자리를 넘는 소수를 발견한 에드슨 스미스가 속한 UCLA 수학과에 5만 달러를 지급했다. 1억 자리를 넘는 소수에 대해서도 새롭게 5만 달러 포상금을 걸었다. 또한, 새로운 메르센 소수를 발견할 때마다 포상금 3천 달러를 지급한다.
현재 GIMPS에서는 지속적으로 메르센 소수의 발견과 검증을 진행하고 있는데, 2020년 12월 4일, 1억 이하의 소수들이 메르센 소수인지 최초 검사가 끝났으며, 이 수들의 자세한 검증, 또 그 위의 수들의 발견을 계속 시도하고 있다.
3. 메르센 소수의 예
이곳에 가면 모든 예시를 확인할 수 있다.3.1. 작은 메르센 소수
| 순서 | 표기 | 값 | 대응하는 완전수 |
| 1 | [math(M(2))] | 3 | 6 |
| 2 | [math(M(3))] | 7 | 28 |
| 3 | [math(M(5))] | 31 | 496 |
| 4 | [math(M(7))] | 127 | 8,128 |
| 5 | [math(M(13))] | 8,191 | 33,550,336 |
| 6 | [math(M(17))] | 131,071 | 8,589,869,056 |
| 7 | [math(M(19))] | 524,287 | 137,438,691,328 |
| 8 | [math(M(31))] | 2,147,483,647 | 2,305,843,008,139,952,128 |
| 9 | [math(M(61))] | 2,305,843,009,213,693,951 | 2,658,455,991,569,831,744,654,692,615,953,842,176 |
3.2. 큰 메르센 소수
순서에 (추정)이 붙은 이유는 이보다 작은 수들에 대해서 완전히 검증이 끝나지 않았기 때문이다. 실제로 [math(M(43,112,609))]가 발견되었을 때는 45번째로 추정되었지만, 바로 한 달 뒤에 [math(M(37,156,667))]가 발견되었고, 그 다음 해에도 [math(M(42,643,801))]가 발견되어 순서를 재조정했다.|| 순서 || 표기 ||<width=150> 자릿수 || 비고 ||
| 44 | [math(M(32,582,657))] | 약 980만 자리 | 1천만 자리에서 2% 모자란 덕분에 1천만 자리 소수 상금 획득에는 실패했다. |
| 45 | [math(M(37,156,667))] | 약 1,118만 자리 | |
| 46 | [math(M(42,643,801))] | 약 1,283만 자리 | |
| 47 | [math(M(43,112,609))] | 약 1,297만 자리 | 앞의 소수 2개보다 먼저 발견되었기에, 최초로 발견된 1천만 자리가 넘는 소수로 기록되었다. |
| 48 | [math(M(57,885,161))] | 약 1,754만 자리 | 이보다 작은 모든 메르센 소수 후보는 모두 검증이 끝났기에 2021년 10월 6일, 공식적으로 48번째로 확정되었다. |
|
49 (추정) |
[math(M(74,207,281))] | 약 2,200만 자리 | 최초로 2천만 자리를 넘는 소수. 위에 언급한 대로 2016년 1월에 발견되었다. |
|
50 (추정) |
[math(M(77,232,917))] | 약 2,324만 자리 | 2017년 12월 26일에 발견되었고 검증 작업은 2018년 1월 3일에 종료. |
|
51 (추정) |
[math(M(82,589,933))] | 약 2,486만 자리 | 2018년 12월에 발견되었다. |
|
52 (추정) |
[math(M(136,279,841))] | 약 4,102만 자리 | 2024년 10월에 발견되었다. |
[4]
4. 기타
2진법으로 나타낼 경우 1이 늘어선 형태를 하게 되며, 늘어선 1의 개수가 즉 n에 해당하므로 소수다.메르센 소수는 짝수인 완전수와 일대일 대응한다.[5] 그 수가 유한인지 무한인지는 알려지지 않았지만, 2024년 10월까지 메르센 소수는 52개가 알려졌다.
메르센 수는 [math(M(n)=\displaystyle \sum_{k=0}^{n}a_k=2^k)]으로 표현할 수 있다. 증명은 간단한 데 이 수열을 공비가 1:2인 등비수열로 놓고 계산하면 등비수열 합 공식 [math(S_n=a*\frac{r^n-1}{r-1})]을 적용하면 [math(\frac{2^{n+1}-1}{2-1} = 2^{n+1}-1)]이 성립하므로 [math(M(n)=\displaystyle \sum_{k=0}^{n}(a_k=2^k) = 2^{n+1}-1)]으로 표현할 수 있다.
[math(M(M(2))=M(2^2-1)=M(3)=7)], [math(M(M(3))=M(2^3-1)=M(7)=127)], [math(M(M(5))=M(2^5-1)=M(31)=2 147483647)], [math(M(M(7))=M(2^7-1)=M(127))][전체]의 경우처럼 2에 메르센 소수를 제곱한 뒤에 1을 빼서 나온 소수는 "이중 메르센 소수"([math(M^2)])라 하며, 총 4개가 발견되었다. [math(M(7))]은 삼중 메르센 소수([math(M^3)])이기도 하고, [math(M(127))]은 사중 메르센 소수([math(M^4)])이기도 하다. 다만 그 외의 [math(M(31))] 이상의 메르센 수들은 모두 너무 커서 2의 거듭제곱 횟수(지수)에 들어가면 숫자가 2024년 10월에 발견된 52번째일 것으로 추정되는 메르센 소수보다도 훨씬 더 커지게 되므로 2를 그렇게나 큰 메르센 소수만큼 거듭제곱하고 나서 1을 뺀 수가 소수인지를 알아보기는 매우 힘들다.
아마존에 'Largest Prime Number'등으로 검색해보면 메르센 소수 하나만으로 책 한권을 쓴 괴문서가 나온다. 수백페이지에 걸쳐서 깨알같은 숫자가 주르륵 늘어서 있는 모습을 보면 혹여나 오타라도 났으면 어쩔려나 싶다.
6002자리 수인 [math(M(19937))]은 난수생성 중의 한 방법인 메르센 트위스터에 자주 쓰인다.
[1]
메르센 수 중에 최초의
과잉수는 [math(M(12)=2^{12}-1=4095)]로 진약수의 합은 4641이다. 여담으로 이 수는 메르센 수이면서 동시에 삼각수인 자연수 중 가장 큰 수이기도 하다.
[2]
프로그래밍을 할 줄 알면 혹은 게임 치트를 쓰다보면 익숙한 그 수. 변수 타입 중 자주 쓰는 정수형의 표현 가능 범위가 –2,147,483,648에서 2,147,483,647이다. 크기가 32비트이고 부호 표시를 제외하면 31비트이므로 2의 31제곱까지 표현이 가능하다. 오버플로 문제와 관련이 있기 때문에 익숙한 것.
[3]
37자리 수라서 평소에 보던 수에 비해 엄청 크게 느껴질 수 있으나 아래의 예를 보면 티끌만한 수로 보일 것이다.
[4]
각 메르센 소수별로 크기 차이가 엄청나다.
[5]
[math(2^p-1)] 이 소수일 때 [math(2^{p-1}(2^p-1))]은 짝수 완전수가 되고, 역도 성립한다. 반면 [math(2^p-1)]이 소수가 아닐 경우 그 수는 과잉수가 된다.
[전체]
170,141,183,460,469,231,731,687,303,715,884,105,727