소수

정의 1. 1보다 크고 양의 약수가 1과 자신뿐인 자연수를 소수(prime number)라고 한다.

산술의 기본정리

 산술의 기본정리 1보다 큰 임의의 자연수의 소인수분해는 소인수를 곱하는 순서를 무시하면 유일하다.

소수의 개수

유클리드의 정리

 유클리드의 정리 소수의 개수는 무수히 많다.

Proof

서로 다른 유한 개 소수를 $p_{1},p_{2},\dots ,p_{n}$이라 하고, $Q=p_{1}p_{2}\cdots p_{n}+1$이라 하자. $Q$가 소수라면 $Q$를 소수 목록에 추가하면 된다. $Q$가 합성수일 때 $p$를 $Q$의 소인수라 하자. 그러면 $p$는 $p_{1},p_{2},\dots ,p_{n}$이 될 수 없고 따라서 $p$는 $p_{1},p_{2},\dots ,p_{n}$과 다른 소수이므로 $p$를 소수 목록에 추가하면 된다.