소수(Prime Number)의 의미는?

[김동석]

소수(Prime Number)의 의미는?

순수한 소수(素數)의 매력은 무엇일까? 현대 원자핵 물리학의 발달로 원자(atom)도 역시 발칸반도처럼 수많은 소립자들이 복잡하게 모인 한낱 조합물에 불과하다는 사실이 밝혀지기 이전만 해도, 소수는 곧잘 원자에 비유되곤 했다. 이처럼 소수는 더이상 쪼개질 수 없는 영원한 비분절성의 또 하나의 상징이었다. 두 정수의 곱으로 표현할 수 있는 합성수(composition nember)와 그렇지 않은 소수는 좋은 대조를 이룬다. 소수는 합성수처럼 표현될 수 없다. 고대 그리스 이래로 많은 사람들은 소수의 간명함과 손에 잡힐 듯한 순수함에 매료되어왔다. 그들은 "과연 얼마나 많은 소수가 존재할까?"하는 의문을 가지게 되었다. 4개의 바둑돌이 있을 때 이것을 직사각형 모양으로 늘어 놓는 방법은 몇 가지 있을까? 또, 12개의 바둑돌이 있을 때는 몇 가지 방법이 있을까?
아래 그림에서 가로, 세로로 늘어 놓은 바둑돌의 개수는 4또는 12의 약수이다.
그러나 11개의 바둑돌은 직사각형 모양으로 늘어 놓을 수가 없다. 왜냐하면 자기 자신과 1만을 약수로 갖는 수만큼의 바둑돌이 있다면 이때는 일직선으로 늘어 놓을 수밖에 없기 때문이다. 이런 수를 소수라고 한다. 그러면 소는 3자연수에서 어떤 의미를 지니는지 생각해 보자.
1을 한 번 더하면 1, 두 번 더하면 2, 세 번 더하면 3, ..., 이와 같이 1과 덧셈만 있으면 모든 자연수를 만들어 낼 수 있다. 이번에는 곱셈으로 자연수를 만들어 보자. 1을 한 번 곱하면 1, 두 번 곱해도 1, 세 번 곱해도 1, ..., 1은 아무리 여러 번 곱해도 항상 1이므로 1과 곱셈만으로는 자연수를 모두 만들어 낼 수 없다.
그러면 2를 여러 번 곱하면 모든 자연수를 다 만들어 낼 수 있을까? 2를 두 번 곱하면 4, 세 번 곱하면 8, .... 그러면 2를 몇 번 곱하면 6, 15를 만들 수 있을까? 이 수들은 2를 아무리 여러 번 곱해도 만들 수 없고, 3 또는 5가 필요하다. 그러면 곱셈으로 121을 만들기 위해서는 어떤 수가 필요할까? 이와 같이 곱셈으로 모든 자연수를 만들려면 2, 3, 5, 7, 11, ...등과 같은 소수가 모두 필요하게 된다.
이 때, 아주 중요한 성질을 하나 발견할 수 있다. 8은 2를 세 번 곱해서 만들어지는 수이므로 8의 성질은 2의 성질을 알면 추측할 수 있다. 또, 45는 3을 두 번, 5를 한 번 곱해서 만들어지는 수이므로 45는 3과 5의 공통적인 성질을 갖게 된다. 이런 이유로 수학자들은 소수에 관심을 갖게 되고, 자연수에 대하여 연구할 때도 소수에 대해서만 집중적으로 연구하면 되는 것이다. 소수의 목록을 계속 작성하다 보면, 소수가 점점 띄엄띄엄 나타난다는 사실을 발견하게 된다. 1에서 100사이에 들어 있는 소수의 개수는 101에서 200사이의 소수의 개수보다 많다. 0-10사이에는 4개(40%)의 소수가 있고, 0-100사이에는 25개(25%), 0-1000사이에 168개(16.8%), 0-10000사이에 1,229개(12.3%), 0-100000사이에 9592개(9.5%), 0-1000000사이에는 78,498개(7.8%)의 소수가 있다. 이처럼 소수의 백분율은 점차 감소한다. 소수의 발생은 불규칙적이면서 그 빈도가 점점 줄어든다. 자연스럽게 유사한 의문이 다시 제기된다. "소수의 발생 빈도가 점점 줄어들고 있으므로 결국 없어지지 않을까?" 즉, "소수의 개수는 유한하고 가장 큰 원자번호가 있듯이 가장 큰 소수가 있는 것이 아닐까?" 이러한 의문에 대한 답은 이미 B.C.300년경에 내려졌다. 강장 큰 소수란 존재하지 않으며, 따라서 무한히 많은 소수가 존재한다는 사실을 증명(소수의 무한성 증명)한 사람은 바로 유클리드였다. 그러면 소수는 현실적으로 어떤 쓰임새가 있을까? 은행에 가서 통장을 만들어 본 사람은 반드시 비밀번호를 써 넣었을 것이다. 이 비밀번호는 다른 사람으로부터 자신의 통장의 정보를 보호하는 역할을 한다. 잔액이 얼마인지 알려고 할 때나 돈을 찾으려고 할 때는 이 비밀번호를 알아야 한다. 일종의 암호인 것이다. 또, 어떤 회사의 지사에서 본사로 비밀을 요하는 서류를 통신으로 보낼 때도 다른 회사에서 풀 수 없는 암호를 써야할 것이다. 이런 암호는 기업 활동이나 전쟁 등과 같이 비밀을 요하는 일에 필수적이다. 전에는 숫자나 글자를 적당히 섞어서 암호를 만들었으나 암호 해독율이 높아지면서 풀기 어려운 암호를 만드는 것이 매우 중요한 일이 되었다.
이제 잠깐 어떤 수의 소인수 분해에 대하여 생각해 보자. 두 자리의 수나 세 자리의 수를 소인수분해하는 것은 쉬운 일이다. 그러면 1234353656537534와 같은 열여섯 자리의 수를 소인수분해하는 데는 얼마나 시간이 걸릴까? 컴퓨터의 힘을 빌리면 몇 분 만에 할 수 있을 것이다. 이 수 A를 암호로 쓸 때, 소인수인 a, b를 알아야 암호를 풀 수 있다고 하면 이 암호를 푸는데는 몇 시간이나 걸릴까? 아직까지는 컴퓨터의 힘을 빌리더라도 이런 수를 소인수분해하는 데는 무척 오랜 시간이 걸린다고 한다. 몇 년만에 소인수분해 해서 암호를 풀었다고 해도 그 때는 이미 소용없는 일이 되어 버렸을 가능성이 크다. 이와 같이 소수는 자연수의 성질을 알려줄 뿐만 아니라 암호를 만드는데도 요긴하게 쓰이고 있다.
소수에 대한 연구와 사색은 외관상 무익한 것처럼 보인다. 그러나 소수에 관한 연구는 실제 신용카드와 원거리 통신, 국가안보 장치 등 무거운 주제와 깊숙히 관련되어 있다. 그 기본 착상은 2개의 100자리 소수의 곱을 찾는 것이다. 만약 사전에 어떤 100자리 소수를 곱샜는지를 모른다면, 이렇게 생성된 자리수가 200인 합성수를 인수분해하기란 거의 불가능하다. 이런 점에 착안하여 우리는 소수의 몇 가지 특성과 함께 엄청나게 큰 200자리 수를, 그 숫자의 소수 인수를 알고 있는 극소수 특정인만이 해독할 수 있는 암호를 만든다. 이런 코드는 은행 거래에서 매일 이용된다. 그리고 극도의 보안을 요하는 국가 안보 기관에서도 군사적 목적이나 정보 처리를 위해 사용한다.
1990년 알려진 가장 큰 소수는 이다. 이 수를 발견하기까지 1년 이상 쉼없이 작동하는 초대형 컴퓨터가 필요했다. 1994년 1월 10일 미국의 크레이 리서치 사는 슈퍼컴퓨터를 이용해서 지금까지 확인된 것 중 가장 큰 25만 8천 7백 16자리의 소수를 발견했다고 발표했다. 이번에 찾아낸 소수는 로, 이 수를 적으려면 신문 8면 정도가 필요하다. 아마도 현재에는 어떤 새로운 수가 가장 큰 소수로 발견되어 있을 것이다.

소수(Prime Number)의 무한성 증명

유클리드의 증명
시작부터 오직 유한 개의 소수만이 존재한다고 가정하고, 이 가정으로부터 모순을 끌어 내면 된다.
먼저 소수가 유한하다고 가정하자. 소수가 유한하면 우리는 소수를 2, 3, 5, ...., 151, ...P처럼 나열할 수 있다. 여기서 P는 가장 큰 소수이다. 이렇게 나열된 소수를 모두 곱하면, 우리는 새로운 수 N=2 X 3 X 5 x ... X 151 X ... X P를 얻게 된다. 이제 새로 만든 수 N 보다 1이 큰 N+1을 자세히 살펴보자. (N+1)이 2로 나누어 떨어지는지 살펴보자. 나누어지면 나머지는 0이 되고, 나누어 떨어지지 않으면 나머지는 1이 될 것이다. 그런데 2는 N의 인수이므로 (N=2 X 3 X ... X P), N은 2로 나누어진다. 이 사실은 동시에 (N=1)이 2로 나누어지지 않음을 의미한다. 즉 수 (N+1)을 2로 나눈 나머지는 1이다. 나아가 3 역시 N 의 인수이므로 N 은 3으로 나누어진다. 따라서 (N+1)은 N보다 1이 큰 수이므로 (N+1)을 3으로 나눈 나머지 또한 1이 된다. 5, 7, 그리고 P까지 모든 소수들의 경우에도 마찬가지다. 즉 N은 어떤 소수로도 나누어지는 반면에, (N+1)은 어떤 소수로도 나누어 떨어지지 않고 항상 나머지 1이 남는다.
이것은 무엇을 의미하는가? (N=1)은 모든 소수 2, 3, 5, ..., P에 대해 나누어지지 않으므로 수 (N+1)에 관해 우리는 다음 2가지 경우를 생각할 수 있다. 수 (N+1)은 P보다 더 큰 어쩐 소수에 의해 나누어진다. 우리는 이미 P가 가장 큰 소수라고 가정했으므로 첫번째 경우는 명백히 거짓이다. 따라서 두번째 경우가 성립해야 한다. 두번째 경우가 성립하려면 가장 큰 소수 P보다 더 큰 어떤 소수가 존재해야 한다. 이것 역시 소수가 유한하다는 원래 가정에 위배된다. 그러므로 가장 큰 소수란 없으며, 따라서, 무한히 많은 소수가 존재한다.