소수

정의 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$를 소수 목록에 추가하면 된다.

등차수열 속 소수의 개수

$\gcd (a,b)=1$이면 $an+b$ 꼴의 소수는 무수히 많다.  등차수열에 대한 디리클레의 정리

소수세기함수

양의 실수 $x$에 $x$ 이하인 소수의 개수를 대응하는 함수를 소수세기함수(prime counting function)라고 하고, 보통 $\pi (x)$로 표기한다. 소수 정리에 따르면 다음 식이 성립한다.  소수세기함수

$\underset{x\to \mathrm{\infty }}{\lim }\frac{\pi (x)\ln x}{x}=1$

$\underset{x\to \mathrm{\infty }}{\lim }\frac{\pi (x)}{\mathrm{li}(x)}=1$

이때 $\mathrm{li}(x)=\underset{0}{\overset{x}{\int }}\frac{dt}{\ln t}$는 로그적분함수이다.