* 옛날 2014년에 썼던 글을 관련 내용을 크게 보강하여 리메이크 한 것이다.
디지털 컴퓨터라는 게 0과 1, 2진법을 사용하다 보니, 2^n이라 하면 정보량과 관련해서 특히 컴퓨터쟁이들에게 아주 친근한 수이다.
그런데 2^n보다 1 더 크거나 작은 수가 소수라면 제각각 수학적으로 좀 독특한 의미를 갖게 된다.
1.
2^n-1 형태인 수를 메르센 수라고 한다. n층짜리 하노이의 탑의 원반을 옆으로 모두 옮기기 위해서는 이 메르센 수만치 지수함수적으로 증가하는 횟수만치 원반을 이동시켜야 한다. 그리고 메르센 수 중에서 소수인 놈을 메르센 소수라고 한다.
얘가 소수이려면 n도 반드시 소수여야 한다. n을 a와 b라는 두 자연수의 곱이라고 생각하고 2^ab - 1을 인수분해해 보면 그래야만 하는 구조적인 이유를 알 수 있다.
(2^ab는 (2^a)^b 와 같다. 2^(a+b)하고 혼동하지 말 것.)
n이 합성수여서 2 이상인 두 자연수 a, b의 곱으로 나타내어질 수 있다면 2^n-1은 빼도 박도 못하고 무조건 합성수가 돼 버린다. 전체 결과가 소수가 되려면 a는 1이고 b는 소수로 귀착되는 것밖에 가능성이 없다. 비록 이 조건이 만족된다고 해서 2^n-1이 언제나 반드시 소수가 된다는 보장은 없지만 말이다.
가장 작은 반례는 2^11-1이다. 11은 소수이지만 2047은 23*89로 소인수분해 되는 합성수이다.
메르센 수는 2^n에서 1이 부족한 형태라는 특성상 2진법으로 나타내면 모든 자리수가 1이다. 컴퓨터에서 취급이 간편하기도 하고, 또 n의 소수 여부를 판정한 뒤에 곧장 무려 2^n-1이라는 방대한 수를 취급할 수 있다는 특성상.. 컴퓨터로 가장 큰 소수를 찾는 프로젝트는 대개 메르센 수를 대상으로 진행되곤 한다. 물론 실제로는 메르센 수가 아닌 소수도 많이 있으며, 반대로 메르센 수 중에서도 메르센 소수는 매우 드물다는 점을 감안할 필요가 있다.
저런 거 찾는 건 거의 애니메이션 렌더링과 같은 급으로 상상을 초월하는 계산량으로 컴퓨터를 열받게 하고 혹사시키는 작업이다. 그나마 양만 많지 내부 과정 자체는 단순무식한 편이니 병렬화가 수월한 건 다행인 점이다.
메르센 소수는 짝수 완전수와 필요충분 관계로 정확히 대응하는 것으로 유명하다. (약수의 합이 자신과 같은 6, 28, 496 같은 수) 메르센 소수 2^n-1에다가 2^(n-1)을 곱하면 완전수가 나오기 때문이다. 괄호 순서에 유의할 것. 즉, 저기서 n에다 소수를 집어넣으면 된다. 천재 수학자 오일러가 모든 짝수 완전수는 이런 형태라는 것을 증명했다.
현재까지 메르센 소수는 약 50여 개가 알려져 있으나, 무한히 존재하는지는 불명이다.
2.
그럼, 다음으로 2^n+1의 경우를 생각해 보자. +1은 -1보다 더 자비심이 없다. n은 소수가 아니라 반드시 2의 거듭제곱 형태여야 그 값이 소수일 일말의 가능성이 생긴다. 이는 n의 소인수 중에 홀수가 절대로 존재해서는 안 됨을 의미한다. 아까 전과 비슷한 방식으로 2^ab + 1을 인수분해해 보면 그 이유를 알 수 있다.
n의 소인수에 홀수가 존재해서 그걸 b라고 설정하면 아까 -1일 때와는 부호만 미묘하게 다르게 저렇게 인수분해가 되며, 이 수는 100% 합성수임이 보장돼 버린다. (2^a - 1)이라면 a=1인 걸로 맞춰서 없앨 수라도 있지만, (2^a + 1)은 도저히 처분할 방법이 없다.
하긴, 고등학교 공통수학 수준의 인수분해 공식을 생각해 봐도, n이 홀수일 때에 한해서 (a^n + b^n)은 a+b로 나눠 떨어지며 인수분해가 된다. 나눠진 몫에 해당하는 항은 a^n에서 b^n으로 a와 b의 차수가 조금씩 늘고 줄고 부호가 교대로 바뀐다.
이를 일반화하면, n이 굳이 홀수가 아니더라도 6이나 10처럼 홀수 소인수가 포함돼 있으면(3, 5) (a^n + b^n)은 굳이 a+b가 아니더라도 (a^2+b^2) 같은 것으로라도 나눠 떨어지며 인수분해가 된다. 그렇지 않고 홀수 소인수가 전혀 없다면 +의 경우는 인수분해를 할 수 없다.
부연 설명 차원에서 인수분해된 식들이 전개되는 양상을 시각적으로 살펴보면 이러하다.
a^n - b^n은 n의 값과 관계없이 언제나 a-b로 나눠 떨어지며, 나눠진 몫의 항들은 부호가 모두 +가 유지된다. 전부 +인 항들이 한 칸 옆으로 물러간 채 -로 바뀌어서 전부 +/-가 상쇄돼 버리고 맨 앞의 +와 -만 남는다
++++
----
+...- (a-b)
하지만 a^n + b^n일 때는 +와 -가 교차하는 항들이 한 칸 옆으로 맞물려서 상쇄돼야 맨 앞과 뒤의 +가 남을 수 있다. 그러니 이때는 항이 홀수 개여서 양 끝이 +가 유지돼야 인수분해가 가능해지는 것이다.
+-+-+
+-+-+
+....+ (a+b)
(쪼개고 쪼개도 분자 단위에서 계속 앞뒤로 + - 극을 갖는 자석 같아 보이기도 하고..;;)
이 두 경우를 모두 종합한 듯이 인상적인 상황은 (a^n - b^n)에서 n이 2의 거듭제곱 형태일 때이다. n=8인 경우를 예로 들어 보면, 이 식은 (a^4 + b^4)(a^2 + b^2)(a + b)(a - b)라고 아주 드라마틱하게 인수분해가 된다. n이 2의 거듭제곱이면 (a^n + b^n)은 -일 때와는 반대로 인수분해가 도저히 더 되지 않는 다항식계의 소수(?) 같은 존재가 된다.
그렇기에 2^n+1도 n이 반드시 2의 거듭제곱 형태여야만 구조적으로 인수분해가 되지 않고 소수일 가능성이 생기는 것이다. 그리고 2^(2^n)+1 형태인 수를 페르마 수라고 하며, 그 중 소수인 놈을 페르마 소수라고 한다. 간단하게 2^n-1로 정의되는 메르센 수와는 양상이 다르다.
그러니, 태생적으로 딱 봐도 페르마 소수는 메르센 소수보다도 더욱 드물 것 같이 생겼는데, 실제로 그러하다.
n에 비례해서 숫자가 넘사벽급으로 너무 폭발적으로 커지는 관계로, 페르마 소수는 n=0..4인 처음 겨우 5개밖에 알려져 있지 않다(3, 5, 17, 257, 65537). n이 아니라 2^n으로 계산한 것이다.
여기서 페르마란 "페르마의 마지막 정리" 내지 추측을 제시했던 17세기 프랑스의 그 엄친아 변호사 겸 아마추어 수학자를 가리키는 거 맞다..
페르마 자신은 저런 형태로 생성된 모든 수들이 소수일 거라고 1637년에 추측하였으나, 그로부터 100여 년 뒤인 1732년, 오일러가 n=5인 2^32+1은 소수가 아니라고 반증을 해 버렸다. 아까 그 메르센 소수와 완전수 관계를 증명한 그 오일러 말이다.
지금이야 그 정도 크기의 수는 컴퓨터로 소수 여부를 아주 간단히 판별할 수 있지만 오일러는 컴퓨터도 없던 시절에 저걸 도대체 어떻게 알아낸 걸까? 찰스 웨슬리가 찬송시 And can it be that I should gain을 쓰기도 전의 일이다(1738).
제곱근인 65536 이내의 모든 홀수들을 브루트 포스 식으로 일일이 주판 돌려서, 제자들까지 멀티코어로 동원해서 나눠 본 건 물론 아니고..
2^32 + 1의 소인수는 반드시 64k+1 의 형태라는 것을 어떤 계기로 알아내고는 찾았다고 한다. 범위를 많이 좁힌 것이다.
실제로 2^32 + 1은 641 * 6700417인데, 이는 (64*10+1)*(64*104694+1)이다.
그는 이를 일반화하여 페르마 수의 소인수는 반드시 "2의 거듭제곱의 a배 + 1"이라는 사실까지 정립했다.
n=5에 속하는 2^32+1에 이어 n=6 (2^64 + 1)의 경우도 합성수라는 게 추가로 밝혀진 건 오일러 이후로 또 100년이 넘게 지난 무려 1855년의 일이다(by Thomas Clausen). 나머지 페르마 수들도 대략 32까지 구해 보니 줄줄이 다 합성수라는 것이 계산을 통해 밝혀졌다. 페르마의 예상과는 정반대로 흘러간 셈이다.
그러니 65537을 끝으로 페르마 소수는 더 존재하지 않는 게 아닌가 추측되고 있으나, 이 역시 홀수 완전수의 존재 여부만큼이나 정식으로 증명된 것은 아니다.
메르센 소수가 짝수 완전수와 동치 관계이듯, 페르마 소수 역시 굉장히 의외의 곳에 큰 의미를 지니고 있다. 이것은 작도 가능한 정다각형의 특성과 관계가 있다. 변의 개수의 소인수가 2 and/or 페르마 소수들로만 이뤄진 정다각형은 눈금 없는 자와 컴퍼스를 이용해 작도 가능하다. 작도 가능한 수는 아무래도 사칙연산과 '제곱근'만으로 기술 가능한 수이니, 제곱근만을 연달아 적용하는 건 2의 거듭제곱만치 또 거듭제곱을 하는 것과 심상면에서 비슷해 보이긴 한다.
그렇기 때문에 작도 불가능한 최초의 정다각형은 정칠각형이며, 반대로 정17각형은 절차가 굉장히 복잡하고 까다롭긴 해도 작도 가능하다. 17은 페르마 소수이니까. 이걸 발견하여 증명한 사람은 오일러...는 아니고 18세기 독일의 천재 수학자인 가우스이며, 그것도 굉장히 어린 나이에 발견했다. sin 1도가 초월수가 아니라 대수적인 수이듯, cos 2*PI/17 역시 형태만 복잡할 뿐, 대수적인 수임을 의미한다.
(그림의 출처: 나무위키)
뭐, 이론적으로만 가능하다는 거지, 실제로 해 보면 누적되는 오차와 지저분한 보조선들 때문에 감당이 어려울 것이다. 하물며 정257각형과 심지어 정65537각형은? 이것도 이론에서나 작도 가능하다는 얘기다.
자, 지금까지 한 얘기들을 요약하면 다음과 같다.
- a^n-b^n은 언제나 a-b로 나눠 떨어지며 2^n-1 역시 그런 꼴의 수이므로, 얘를 소수로 만들려면 a-b가 반드시 1인 상황을 만들어야 한다. 그리고 메르센 수에서 그 경우란 n이 소수인 경우밖에 없다.
- 그리고 2^n+1의 일반형인 a^n+b^n은 아까처럼 한쪽 인수를 1로 만드는 게 불가능한 대신에, 인수분해 가능 여부가 n의 차수에 따라 조건부로 결정된다. 소수를 만들려면 물론 애초에 인수분해를 할 수 없는 상황을 만들어야 하며, n은 단순히 짝수인 정도를 넘어 소인수에 홀수가 전혀 없어야 한다. 그래서 n 자체가 2의 거듭제곱 형태인 것만 남는다.
그러고 보니 페르마뿐만 아니라 메르센도 17세기 동시대를 살았던 프랑스 사람이기 때문에 둘이 공통점이 있다. 메르센은 블레즈 파스칼의 스승이기도 했다. 프랑스, 독일 그쪽은 수학· 과학 쪽으로 그때로부터 지금까지 한가닥 하고 있는 대단한 동네이다.
* 소수 관련 여담
(1) 소수 자체가 안 그래도 수가 커질수록 (log n) / n 급의 스케일로 자연수에서 등장 빈도가 극도로 드물어진다. 그런데 그 소수들 중에서도 굉장히 까다로운 조건을 만족하는 메르센 내지 페르마 소수 같은 것들은 한계치 최대치가 존재한다 해도 이상할 게 없을 것이다. 굳이 수 자체가 특이한 게 아니더라도 2 간격으로 나란히 존재하는 쌍둥이 소수 쌍(5와 7, 11과 13, 17과 19..) 같은 것도 말이다. 그런데 한계치가 있다면 그 최대값이 알려져 있어야 할 텐데 그것이 수수께끼이다.
(2) 오일러의 업적 중에는 소수와 관련해서도 정말 살떨리는 것들이 많다. 자연수의 제곱의 역수의 무한합이 원주율과 관계 있는 수로 수렴한다는 것을 규명했을 뿐만 아니라 이건 소수의 분포와도 관계가 있기 때문에 임의의 두 수가 서로 소일 확률과 같다고 입증한 건 뭐.. 할 말을 잃게 만든다. 예전에 본인의 블로그에서 다룬 적이 있다.
(3) 또한 그는 소수의 개수가 무한한 건 말할 것도 없고, 소수의 역수의 무한합이 무한대로 발산한다는.. 거의 충격과 공포 안드로메다급의 명제도 증명했다. 물론 속도는 이중 로그(로그에다 또 로그) 급으로 끔찍하게 느리니 기대하지 말자. 그냥 자연수의 역수의 합만 해도 얼마나 느린데 하물며 소수의 역수는! 쉽게 말해 10에다 0을 10의 20승개만치 붙인 영역만치 소수의 역수를 더하면 합이 20이 될까말까 한다는 뜻이다. 쟤가 도대체 제곱의 역수의 무한합보다 뭐가 더 나은 구석이 있다고 발산을 하는 걸까?
단, 쌍둥이 소수들의 역수의 합은 유한으로 수렴한다고 한다. 쌍둥이 소수가 유한하다면 당연히 유한 수렴이겠지만, 무한하다 하더라도 얘는 발산하지 못한다고.. 구체적인 값은 모르겠지만 추세가 그렇게 된다는 큰 그림만 증명을 한 것이다. 어떻게 증명했는지는 나한테 묻지 마시길.
(4) 가우스, 오일러 등 인류 역사상 수많은 괴수 천재 수학자들이 초월적인 업적을 남기고 갔지만, 어떤 형태로든 소수 생성 규칙을 표방하는 모든 예측· 추측은 지금까지 하나도 완벽하게 적중한 게 없었다. 저 페르마의 추측처럼 말이다.
소수를 생성하는 규칙을 무슨 정보 검색이나 패턴 매칭에다가 비유해서 설명하자면, 정밀도와 재현율(precision & recall) 어느 것 하나라도 확실하게 잡는 규칙이 지금까지 발견된 적이 없다는 것이다. 정밀도가 100%라면 모든 소수를 커버하지는 못해도 일단 이 규칙이 생성하는 수는 다 소수임이 보장되는 것이고, 재현율이 100%라면 종종 소수가 아닌 놈(false alarm)이 섞여 있더라도 소수는 하나도 빠짐없이 커버한다는 뜻이다.
(5) partition number라는 게 있다. f(2)라면 1+1, 2 이렇게 2가지, f(3)이라면 1+1+1, 2+1, 3 이렇게 3가지, f(4)라면 1 1 1 1, 2 1 1, 2 2, 3 1, 4 이렇게 5... 뭔가 테트리스 조합처럼 올라가는데, 이 수열이 2 3 5 7 11 (15 22...) 이렇게 앞부분은 소수와 굉장히 비슷한 양상으로 시작한다. 무슨 파이의 그럴싸한 근사값을 보는 듯한 느낌이나, 얘는 실제로는 소수와는 수학적으로 아무런 관련이 없는 놈이다.
n에 대해서 f(n)의 값을 구하는 건 다이나믹 프로그래밍으로 해결 가능하다. 피보나치 수열 구하는 것보다는 어렵고 꽤 재미있는 프로그래밍 excercise이므로 관심 있으신 분은 도전해도 좋다. 참고로 점화식 함수 내지 테이블은 보기와는 달리 1변수로는 안 되고 2변수 형태로 짜야 한다.
Posted by 사무엘
