Communication Signal Design Lab.

한국어

송홍엽 교수의 잡글

[교양상식] 메르센 소수--Mersenne Prime

2004.04.13 05:55

송홍엽 조회 수:14139 추천:214

정수의 종류에는 다음의 4가지가 있습니다.
1. unit
2. prime
3. composite
4. 0

네째는 덧셈에 관한 항등원(identity)입니다.
첫째는 곱셈에 관한 역원(inverse)가 존재하는 놈들입니다. 정확히, +1과 -1입니다.
그리고 prime(소수)는 unit와 자기자신 만이 약수인 수입니다. 예를 들어 2,3,5,7,11, -3,... 등등입니다.
그 나머지는 모두 composite number라고 합니다. 간단하게는 소수를 정의할때 양의정수로 한정하기도 합니다.

소수중에 2^n -1 ("2의 n승 빼기 1"이라고 읽습니다.) 의 형태인 소수를 Mersenne prime이라고 합니다.
이러한 소수는 역사적으로 관심의 촛점에 있어왔는데, 그 이유중에 하나는 앞 글에서 소개한 바와 같이
완전수 한개에 메르센 소수 한개가 대응되기 때문입니다.

다음의 두 개의 명제는 서로 동치(equivalent)입니다. 하나가 참이면 다른 하나도 참이고
하나가 만일 거짓이면 다른 하나도 거짓입니다. 즉, 서로가 서로의 필요충분조건인 셈입니다.

1. 완전수는 무한히 많이 존재한다.

2. 메르센 소수는 무한히 많이 존재한다.

이러한 문제는 그 참과 거짓이 아직 밝혀지지 않았습니다.
즉, 정수집합 중에 완전수가(혹은 메르센 소수가)
무한히 많이 있는지 아니면 유한한 갯수만이 존재하는지에 대하여 우리 인간이 아는게 별로 없다는 뜻입니다.
이를 밝혀보기위하여 고민해보고싶지 않으십니까 ?


이와 관련된 한가지를 더 설명합니다.

정리: 2^n -1 >0 이 소수이면 정수 n>0 은 소수이다.

증명: 대우를 사용합니다.
만일 n>0 이 소수가 아니라면 n=ab, a>1, b>1 를 만족하며,
2^n -1
= 2^(ab) -1
= [ 2^a -1] [ 2^((b-1)a) + 2^((b-2)a) + .... + 2^a + 1 ]
에서 알수있듯이
2^n -1 는 소수가 아닙니다... (증명 끝)


역사적으로
메르센은 중세시대의 수도승이었습니다. 그는 정수론에 심취하여 2^n -1 의 형태의 수에 대하여 많은 연구를 하였습니다.
그는 위의 정리의 역도 참이라고 가설을 세웠으나 이는 곧 참이 아니라고 알려졌습니다.

2^2 -1 = 3 = 소수
2^3 -1 = 7 = 소수
2^5 -1 = 31 = 소수
2^7 -1 = 127 = 소수
2^11 -1 = 2047 = 복합수 = 23 x 89
2^13 -1 = 8191 = 소수
...
그래서 2^n -1 의 형태의 수를 일반적으로 Mersenne number라고 합니다. 이 수가 소수이면 이를 Mersenne prime이라고 하지요.
그럴때 정수 n을 Mersenne exponent 라고 합니다. 그러니까 메르센 지수들은 소수 전체 집합의 부분집합이고 이게 유한집합이냐
혹은 무한집합이냐가 문젭니다. 소수 전체의 집합이 유한집합이었던들 당연히 유한집합이겠지만
소수의 수가 무한히 많다는 것은 잘 알려진 사실입니다.......

위의 list는 현재 어디까지 알려져 있을까요.
90년대 초반에 미국 캘리포니아의 실리콘밸리에 있는 어느 engineer 겸 수학자는
이를 계산하는 방법을 인터넷에 올리고 소스프로그램을 다운받아서
전세계인에게 (집에 PC가 놀고있으며 관심있는 사람은 누구나) 이를 수행하여 위의 list를 늘려가자고 제안하였습니다.
현재까지 알려져 있는 메르센 소수의 갯수는 33개이며 이를 발견한 시기와 숫자의 십진표기등의 목록은 다음의 페이지에 올라있습니다.

메르센소수에 관한 홈페이지는
http://www.isthe.com/chongo/tech/math/prime/mersenne.html
입니다.

참고로
지금까지 알려진 것 중에서 가장 큰 메르센 소수는 2^(6972593) -1 이며
이는 33번째로 알려진 메르센 소수이고,
99년 6월 1일에 확인작업을 끝마쳤고,
이 숫자의 십진수 표기시 자릿수의 갯수는 2098960입니다.
추측컨데,
이 숫자는 지금까지 알려진 소수 중에서
가장 큰 놈이 아닐까 생각합니다.
이보다 도 큰 소수를 확인하려면 엄청시간이 걸린답니다....

참고: 이글은 2000년 9월에 작성한 글입니다. 2004년 봄, 몇개가 추가되었습니다...
번호 제목 글쓴이 날짜 조회 수
공지 논문에 영어작문 주의사항 몇 가지 송홍엽 2008.05.22 8448
공지 젊은 학부생 여러분에게... 송홍엽 2008.11.20 5822
공지 우리학과 대학원생 모두에게 (특히, 박사과정들에게) 하고싶은 말입니다. 송홍엽 2014.01.20 5787
89 2013년 12월 31일 오후에 작성한 글: 새해는 시속 1400키로의 속도로 달려온다. file 송홍엽 2014.01.17 1700
88 학위논문 작성에 관한 조언 file 송홍엽 2014.01.25 1890
87 [펀글] 한겨레 2011.12.23. 정봉주 유죄판결은 법적 착시현상 송홍엽 2011.12.25 2241
86 [펀글] 왜 우린 이런거 못만드냐고... 송홍엽 2010.05.09 2786
85 [펀글]프로운동선수의 대학학업 병행하기 송홍엽 2009.12.17 2811
84 [펀글] 교육의 의미 송홍엽 2008.02.19 2892
83 [펀글] 조선일보 1월2일 사설: 교육개혁 송홍엽 2008.01.03 2901
82 암호이야기 송홍엽 2008.05.21 2917
81 [펀글] 한반도 운하 건설을 반대하며 송홍엽 2008.02.20 3210
80 디지털 이야기... 송홍엽 2003.10.06 3236
79 [소고] 수학이란.... 송홍엽 2004.04.13 3313
78 [펀글-조선일보] 대중적인 책 내면 ‘이단아’ 취급 송홍엽 2006.09.18 3322
77 Re..랜덤변수의 variance가 0이면? 김태환 2005.07.30 3361
76 손바닥/손등 게임 송홍엽 2005.09.30 3366
75 유명한 퍼즐1 송홍엽 2004.04.01 3385
74 DMS와 정보량 송홍엽 2004.04.04 3430
73 [일반인을 위한 교양강좌] CDMA 통신기술 (2001.7) 송홍엽 2003.10.13 3470
72 수집합이란... 송홍엽 2004.04.13 3509
71 [교양상식] 정수와 암호 송홍엽 2004.04.13 3534
70 [퍼온글]독도대첩 송홍엽 2005.03.15 3535