소수

소수 (Prime Number) 의 정의는 다음과 같습니다.

$1$과 자기 자신만을 약수 로 가지는 정수 $p$를 소수라고 한다.

모든 소수의 집합을 Prime의 첫 글자 P에서 따온 $\mathbb{P}$로 표기합니다.
$n$번째 소수 는 특별히 $p_{n}$으로 표기하기도 합니다.
$1$은 소수도 아니고 합성수로도 치지 않습니다. 산술의 기본정리 에 따른 소인수분해의 유일성 때문입니다. $1$을 소수로 치면 $36 = 2^{2} \times 3^{2}$로 소인수 분해하면 될 것을 $36 = 1^{100} \times 2^{2} \times 3^{2} = 1^{10^{100}} \times 2^{2} \times 3^{2}$같이 쓸 수도 있기때문에, 굳이 $1$은 소수로 보지 않습니다.
소수가 무한하다는 것은 유클리드의 정리 로 잘 알려져 있습니다.
소수의 특징으로 다음과 같은 것들이 있습니다.

윌슨의 정리
1. $(n - 1)! \equiv -1 \pmod{n}$ 이다.
2. $n$ 이 소수이다.

두 명제는 동치이다.

페르마의 소정리
1. 모든 소수 $p$와 모든 자연수 $a$에 대하여 $a^{p} \equiv a \pmod{p}$ 이다.
2. 소수 $p$와 $a$가 서로소 이면 $a^{p - 1} \equiv 1 \pmod{p}$ 이다.

어떤 정수 $n$이 소수인지 아닌지를 판별하는 방법으로는 밀러-라빈 소수 판별법 등이 있습니다.
큰 범위의 (1부터 1천만까지, 혹은 1부터 5천만까지 같은) 소수들 전체를 얻으려면 에라토스테네스의 체 등을 사용해야 합니다.

$x$ 이하의 소수의 개수를 소수 계량 함수 $\pi(x)$ 로 표기합니다.
소수의 개수에 대한 정리로 다음이 알려져 있습니다.

소수 정리 (Prime Number Theorem) $$ \lim_{x \to \infty} \frac{\pi(x) \ln x}{x} = 1 $$

$\ln x$는 자연로그함수 입니다.

지극히 제 개인적인 주관으로 모아둔 주요 소수 리스트 가 있습니다.