소수의 개수

소수(素數, prime number, 1보다 큰 자연수 중 1과 자기 자신만을 약수로 가지는 수) 보다) 큰 자연수 중 1과 자기 자신만을 약수로 가지는 수는 고대 이집트 파피루스에 기록이 남아있을 정도로 수학 정수론에서 매우 중요한 주제로 오랫동안 다루어져 왔고 현대에 와서는 암호 분야에서 그 중요성이 부각되고 있다. 어떤 임의의 수에 대하여 더 이상 쪼갤 수 없는 숫자(1은 제외)의 곱으로 나타낼 수 있다.

반응형

예를 들면,

로 나타낼 수 있다.

어떤 수를 곱으로 나타낼 때 더 이상 쪼갤 수 없는 씨앗이 되는 수를 소수라고 한다.

 

소수는 정수론에서 핵심이 되는 내용이다.

17세기 뉴턴과 라이프니츠에 의해 미적분이 발표되고 미적분을 중심으로 한 해석학의 연구가 활발히 진행되었다. 해석학은 대부분 연속함수를 대상으로 한 실수개념에서 시작한다. 정수론은 수학자들의 관심사에서 점점 소외되었다. 그러다가 컴퓨터가 개발되고 컴퓨터 공학이 발전하면서 컴퓨터가 해결하지 못하는 문제에 사람들은 관심을 갖기 시작했다. 컴퓨터가 해결하지 못하는 문제의 다수가 정수론 문제였고 이러한 정수론은 다시 각광받게 되었다. 컴퓨터가 해결하기 어려운 문제로 보안체계의 핵심기술로 등장하게 되었다. 그중에서 특히 소수와 관련된 내용이 많았다. 수 백자리에서 천 자리에 이르는 십진법의 수를 소인수분해할 경우 기존 컴퓨터로 풀려면 수십억 년이 걸릴 것으로 예측하고 있다.

 

1보다 큰 모든 양의 정수는 유한개의 소수의 곱으로 나타낼 수 있다는 정수론의 기본정리(fundamental theorem of arithmetic)는 유클리드가 최초로 제시했고 가우스에 의해서 수정되었다.

 

또, 소수의 개수가 무한하다는 소수의 무한성에 대한 증명은 열 가지가 넘게 알려져 있는데 가장 오래된 증명은 유클리드의 증명이다. 그 내용은 <원론(Elements)>에 나와 있는데

 

그 내용을 보면

 

유한개의 소수가 존재한다고 가정하자.

이 유한개의 소수들을 모두 곱한 값에 1을 더하자.

그 값은 어떤 소수로 나누어도 나머지가 1이므로 어떤 소수로도 나누어 떨어지지 않는 수가 된다.

따라서, 그 수 역시 소수이다. 처음 가정에서 모든 소수의 곱에 1을 더하였으므로 이수는 모든 소수보다 더 큰 소수가 된다.

이것은 소수가 유한하다는 가정에 위배되므로 소수의 개수는 무한하다.

 

이를 현대식으로 표현하면