소수의 유래

수학은 인류의 역사와 함께 시작된 양, 구조, 공간, 변화 등의 개념을 다루는 학문이다. 기원전 600년경 탈레스를 비롯한 고대 그리스의 철학자들은 숫자 세기, 계산, 측정, 물리적 현상 등을 추상화하고 이에 논리적 추론을 적용하는 등의 방법으로 수학의 기틀을 마련하였다. 가령 물건을 하나씩 헤아리는 것은 자연수라는 개념으로 발전하였다.

1. 무한히 많은 소수

고대 그리스에서부터 이어진 자연수에 대한 관심은 곧 수학의 발전으로 이어졌다. 특히 1과 자신으로 밖에 나누어지지 않는 1보다 큰 자연수인 소수에 대한 관심이 매우 높아서 소수는 초기의 수학부터 중요하게 다루어졌다. 중학교 수학 교과 과정에 나오는 소인수분해, 최대공약수, 최소공배수 등은 모두 개념을 기본으로 하고 있다.  많은 소수의 성질이 일찍부터 알려져 왔다. 가령 유클리드는 소수가 무한히 많다는 것을 다음과 같은 방법으로 증명하였다. 

 

소수가 유한하다고 가정하면 가장 큰 소수가 존재하고 이를 p라 하자. 그러면 p! + 1은 p 이하의 모든 수와 서로소이므로 p보다 큰 소인수를 가져야 한다. 따라서 가장 큰 소수가 p라는 것에 모순이므로, 소수가 유한하다는 가정이 틀렸다.

 

이후 오일러(1707~1783)는 위 정리보다 강한 명제인 모든 소수의 역수의 합이 발산한다는 것을 증명하기도 하였다.

2. 소수의 불규칙성

소수의 성질을 알아내는 것은 매우 어렵다. 많은 수학자들이 무한히 많은 소수의 분포나 규칙성을 밝혀내려고 했지만 누구도 정답이라고 할 만한 결과를 얻지는 못하였다. 현재까지도 수많은 소수에 대한 문제들이 많은 수학자들이 호기심을 자극하고 있다. 현대 수학자들은 소수의 분포에 대해서 순수하게 무작위적이라는 가설을 세우고 있다. 즉, 소수의 개수는 특정 평균선을 기준으로 변동하는데, 그 변동하는 양에서는 주기성 같은 경향을 더 찾을 수가 없다는 뜻으로 이는 소수의 쉬운 패턴을 찾기란 불가능함을 암시한다. 하지만 이러한 예측에 대한 것도 알려진 바가 많이 없어서 소수의 규칙성을 찾는 문제는 아직도 갈길이 멀다.

 

소수의 불규칙성 때문에 소수에 대한 새로운 발견은 늘 화제가 되곤 한다. 소수에 관련한 난제 중 2000년 이후인 최근에 가장 많은 성과를 보인 문제는 '쌍둥이 소수 문제'이다. 쌍둥이 소수 문제란 차이가 2이하인 소수의 쌍이 무한히 많다는 것을 증명 혹은 반증하라는 문제로 고대 그리스 시절부터 미해결 문제로 알려져 있었다. 소수가 무한히 많기 때문에 이 문제는 얼핏 그럴듯해 보이지만 소수 간격에 대해서는 알려진 바가 전혀 없기 때문에 기존의 명제로는 차이가 무한인 소수의 쌍이 무한히 많다는 이야기 밖에 할 수 없다. 2013년 미국의 수학자 장이탕은 차이가 7천만 이하인 소수의 쌍이 무한히 많다는 것을 증명하여 발표하였다. 이는 무한히 많은 소수의 쌍이 가질 수 있는 차이가 무한이라는 숫자에서 '7천만'으로 줄이는 데 성공한 것이고 이제 이 7천만이라는 숫자를 2로 줄일 수 있으면 고대 그리스 시절부터 이어진 미해결 난제가 해결되는 셈이다. 이러한 결과는 많은 수학자들에게 영감을 주었고 이후 많은 수학자들이 협동하여 일 년 남짓만에 7천만을 2백 정도로 줄이는 데 성공하였고 지금도 그 차이를 줄이기 위해 노력하고 있다.

3. 소인수분해 및 소수의 활용

어떤 자연수는 항상 소수의 곱으로 표현할 수 있는데, 이를 소인수분해라고 한다. 이는 소수와 소인수분해의 연구가 모든 수의 성질을 알아내는 데 도움이 된다는 뜻이므로 소수와 소인수분해는 자연수 연구에 중요한 역할을 한다. 산술의 기본정리란 모든 자연수의 소인수분해가 유일하게 존재한다는 것이다. 하지만 소수의 불규칙성 때문에, 실제 주어진 수를 소인수분해하는 것은 결코 쉬운 일이 아니다. 어떤 자연수 n을 소인수분해하기 위해서는 √n이하의 정수를 나누어 보아야 하는데, n이 매우 크다면 이 과정에 시간이 많이 걸릴 수밖에 없다. 가령 두 개의 소수를 곱해서 얻은 어떤 193자리수를 소인수분해하기 위하여 5개월간 30개의 컴퓨터가 사용된 바 있다. 이러한 소인수분해이 어려움은 오늘날 많은 암호 알고리즘의 핵심 부분이다. 대표적인 암호 알고리즘으로는 공개키암호시스템(RSA암호)등이 있고, RSA가 갖는 전자서명 기능은 오늘날 인증을 요구하는 전자 상거래 등에서 광범위하게 활용되고 있다. 현재까지 주어진 자연수를 빠른 시간 안에 소인수분해하는 알고리즘은 알려져 있지 않다. n에 관한 다항식 시간 내에 n자리 자연수가 소수인지 판별하는 알고리즘은 알려져 있지 않은 미해결 문제였으나, 2002년 인도의 아그라왈, 카얄, 삭세나가 처음으로 그러한 알고리즘을 발견하였고, 지금은 알고리즘이 AKS소수 판별법이라고 불린다.