Communication Signal Design Lab.

한국어

송홍엽 교수의 잡글

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

2004.04.13 05:55

송홍엽 조회 수:17667 추천: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년 봄, 몇개가 추가되었습니다...