소수
소수는 1과 자기 자신으로만 나누어떨어지는 수이다. 소수의 성질은 예를 들어 암호학에서 자주 쓰인다.
정의와 예
소수는 1과 자기 자신으로만 나누어떨어지는 자연수이다. 단, 1 자체는 소수가 아니다. 가장 작은 소수는 2이다. 2는 1과 2로 나누어떨어진다. 2는 짝수인 유일한 소수이기도 하다. 나머지 소수는 모두 홀수이다. 다른 짝수는 모두 1과 자기 자신 말고도 2로 나누어떨어지기 때문이다.
처음 몇 개의 소수를 나열하면 다음과 같다. 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199, 211, 223, 227, 229, 233, 239, 241, 251, 257, 263, 269, 271…
소수와 관련된 정리로 산술의 기본 정리가 있다. 이 정리에 따르면 1보다 큰 모든 정수는 소수의 곱으로 나타낼 수 있다.
소수인지 판별해 보기
소수의 성질
- 소수는 무한히 많다. 증명은 귀류법에 관한 글에 있다.
- 모든 정수 z>1에 대해 구간 (z, 2z)에는 소수가 적어도 하나 있다. 예를 들어 z = 2이면 구간 (2, 4)를 얻는다. 이 구간에 있는 정수는 3뿐이고, 3은 소수이다. z = 5이면 구간 (5, 10), 즉 수 6, 7, 8, 9를 얻는다. 7은 소수이다. 더 큰 z에 대해서도 마찬가지이다.
- 메르센 소수는 2의 거듭제곱(지수가 정수)보다 1 작은 소수이다. 그래서 메르센 소수 M은 M = 2z − 1 꼴이고, 여기서 z는 어떤 자연수이다. 예를 들어 22 − 1 = 3이므로 소수 3이 메르센 소수이다. 23 − 1 = 7이므로 7도 그렇다.
- 알려진 가장 큰 소수는 대개 메르센 소수이다. 예를 들어 2008년 8월 23일에 메르센 소수 M43112609가 발견되었다. 아래 첨자는 지수 z를 나타낸다. 즉 이 소수는 243112609 − 1이고, 12,978,189자리 수이며, 그 당시 알려진 가장 큰 소수였다.
소수가 없는 수열
연속한 자연수 가운데 소수가 하나도 없는 유한 수열은 얼마든지 길게 찾을 수 있다. 이런 수열은 k!+2, k!+3, …, k!+k 꼴로 만들 수 있고, 연속한 합성수 k − 1개로 이루어진다(느낌표는 계승이다).
예를 들어 k = 6이면 연속한 합성수 다섯 개 720 + 2, 720 + 3, 720 + 4, 720 + 5, 720 + 6을 얻는다. 이 수들은 차례로 2, 3, 4, 5, 6으로 나누어떨어진다. 6! = 720은 이 수들을 곱해서 만든 수이므로 당연히 이 수들로 모두 나누어떨어지기 때문이다. 6! = 6 · 5 · 4 · 3 · 2이다. 720이 3으로 나누어떨어지면 720 + 3도 3으로 나누어떨어져야 한다. 다른 수도 마찬가지이다.
페르마의 소정리
모든 소수 p와 모든 정수 z에 대해 수 zp − z는 소수 p로 나누어떨어진다.
예를 들어 소수 p = 3과 정수 z = 4를 택하자. 43 − 4를 계산하면 60이다. 그런데 60/3 = 20이므로 60은 3으로 나누어떨어지고, 이는 페르마의 정리와 맞는다. 다른 예로 p = 7, z = 10을 보자. 먼저 107 − 10 = 9999990을 계산하고 이 수를 7로 나누면 9999990/7 = 1428570이다. 이번에도 나누어떨어진다.
풀리지 않은 문제
소수에 관해서는 (2011년 기준) 아직 증명도 반증도 되지 않은 유명한 추측이 많다. 그 가운데 가장 유명한 두 가지는 다음과 같다.
- 쌍둥이 소수가 무한히 많은가: 쌍둥이 소수는 두 수가 모두 소수인 쌍 (z, z + 2)이다. 예를 들어 (3, 5)나 (29, 31)이 있다. 문제는 쌍둥이 소수가 무한히 많은가 하는 것이다. 그럴 것이라고 여겨지지만 증명은 없다.
- 리만 가설: 리만 제타 함수의 자명하지 않은 영점은 모두 실수부가