Number Theory - 3.2 에라토스테네스의 체

소수 판별법과 에라토스테네스의 체

소수 판별법

$a$가 합성수라면 $a=bc(1 < b,c < a)$ 꼴이여야 한다.

$wlog) ~~ b \le c$ 일 때, $b^2 \le bc = a$ 이므로 $b \le \sqrt{a}$ 이다.

산술의 기본정리에 의해 $b$는 $1$개 이상의 소인수 $p$를 갖고, $p \le b$이기 때문에 $p \mid b \Rightarrow p \mid a$

따라서 $a$는 $p \le \sqrt{a}$를 만족하는 소인수 $p$를 항상 갖는다.

이는 $n$이 소수인지를 판단하거나 약수를 구함에 있어 항상 $\sqrt{n}$까지의 수만 본다면 된다는 이점을 주고 PS에서 필수 지식이다.

에라토스테네스의 체

앞서 살펴본 소수 판별법을 사용하여 $2 \le n \le M$ 인 정수 $n$ 들에 대해 $n$이 소수인지 모두 판별하고 싶을 때, $p_i \le \sqrt{M}$인 소수들 $p_i$에 대해 $2p_i \le x \le M$인 $x$들은 소수가 아니라고 체크하는 방법을 사용한다.

소수의 분포

무한히 많은 소수가 존재한다 by 유클리드

증명

소수의 집합이 유한하다고 하자.

$$ \{p_1, p_2, p_3, \cdots, p_n\} $$

$P=p_1p_2\cdots p_n+1$ 이라 하자.

산술의 기본 정리에 의해 $p \mid P$인 $p$가 존재한다. ($p$는 소수)

$p \mid p_1 p_2 \cdots p_n$ 이고 $p \mid P$ 이므로, $p \mid P-p_1p_2 \cdots p_n=1$

이는 $p \le 1$ 이 되어 모든 소수는 $2$이상이 되야해서 모순이다.

소수는 무한하다. $\square$

소수가 무한함을 보이는 수열

다음과 같은 수열을 보자.

$$ \begin{aligned} n_1&=2\\ n_2&=n_1+1\\ n_3&=n_1n_2+1\\ \vdots\\ n_k&=n_1n_2\cdots n_{k-1}+1 \end{aligned} $$

여기서 $n_i$ 끼리는 서로소이다.

$d=gcd(n_i, n_k)~~(i < k)$ 라 하자.

$d \mid n_i$ 이므로 $d \mid n_1n_2\cdots n_i \cdots n_{k-1}$이다.

$d \mid n_k$이므로, $d \mid n_k-n_1n_2\cdots n_i \cdots n_{k-1}=1$ 이 되어서

$gcd(n_i, n_k)=1$ 이다.

이러한 순서대로 무한개의 수열이 만들어지기 때문에 소수는 무한하다. $\square$

베르트랑 공준

베르트랑. $2$보다 큰 정수 $n$과 $2n$사이에는 적어도 하나의 소수가 존재한다.

이 추측은 PS에서 가끔 어케풀지? 싶은 문제의 시간복잡도를 증명해내는데 쓰이기도 한다.

이 추측은 완벽히 증명되지 못했지만, 쳬비셰프에 의해 이 추측이 사용되어

$$ p_n < 2^n~~(n \ge 2) $$

임이 보여졌다.

귀납적으로 보자.

$p_2=3 < 2^2$

베르트랑의 추측으로 $2^n < p < 2^{n+1}$인 소수가 존재하고,

이로부터 $p_{n+1} < 2^{n+1}$ 의 소수가 존재함이 보인다.