소수

II-eugene-II Note

Home Math Code

소수

소수 (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$ 는 자연로그함수 입니다.

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