정의 1. 1보다 크고 양의 약수가 1과 자신뿐인 자연수를 소수(prime number)라고 한다.
산술의 기본정리
1보다 큰 임의의 자연수의 소인수분해는 소인수를 곱하는 순서를 무시하면 유일하다.
산술의 기본정리
소수의 개수
유클리드의 정리
소수의 개수는 무수히 많다.
유클리드의 정리
Proof
서로 다른 유한 개 소수를
이라 하고,
이라 하자.
가 소수라면
를 소수 목록에 추가하면 된다.
가 합성수일 때
를
의 소인수라 하자. 그러면
는
이 될 수 없고 따라서
는
과 다른 소수이므로
를 소수 목록에 추가하면 된다.
등차수열 속 소수의 개수
이면
꼴의 소수는 무수히 많다.
등차수열에 대한 디리클레의 정리
소수세기함수
양의 실수
에
이하인 소수의 개수를 대응하는 함수를 소수세기함수(prime counting function)라고 하고, 보통
로 표기한다. 소수 정리에 따르면 다음 식이 성립한다.
소수세기함수
이때
는 로그적분함수이다.