소수(素數, 발음: /소쑤/, 문화어: 씨수, 영어: prime number)는 양의 약수가 1과 자기 자신 뿐인 1보다 큰 자연수로 정의된다.
정수론에서 매우 중요한 역할을 담당한다.현재에 와서는 암호 분야에서의 사용으로 그 중요성이 부각되고 있다.
100까지의 처음 25개의 소수는 다음과 같다. (OEIS의 수열 A000040)
- 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...
여기서, 2는 유일한 짝수 소수이다.
소수는 무한하다.
이 명제의 가장 오래된 증명은 그리스 수학자 유클리드의 《유클리드 원론》(제 9권, 정리 20)에서 볼 수 있다.
유클리드의 증명은 “어느 주어진 유한한 소수들 보다 더 많다.”라는 결론으로 표현되고, 그의 증명은 본래 아래와 같다.
- 유한 개의 소수가 존재한다고 가정하자. 이 유한 개의 소수들을 모두 곱한 값에 1을 더한다. (유클리드 수 참조)
- 그 결과값은 다른 어떤 소수로 나누어도 나머지가 1이므로 어떤 소수로도 나누어 떨어지지 않는 수가 된다.
- 따라서 이 수가 소수라면 기존의 최대소수보다 큰 소수가 있다는 것이 증명되고,
- 이 수가 소수가 아니라고 해도 기존의 최대소수보다 큰 소수가 있어야 한다는것을 의미하기 때문에
- 소수가 유한하다는 애초 가정에 모순이 존재함을 알 수 있다.
다른 수학자들도 각자의 증명을 내놓았다.
그 중 오일러에 의한 증명은 모든 소수들의 역수의 합이 발산한다는 증명으로부터 소수의 개수가 무한함을 보였다.