소수는 무한하다
수학이야기 2015. 2. 8. 21:14정의 정수 $p>1$가 약수가 오로지 $1$과 $p$ 뿐이라면 소수(prime number)라고 부른다. 소수가 아닌 수는 합성수(composite)이다. $1$은 소수도 합성수도 아니다.
정리 $p$가 소수이고 $p|ab$이면 $p|a$ 또는 $p|b$이다.
증명 $p|a$라면 더 따질 필요가 없으므로 $p\not|a$라고 하자.
$p\not|a$이면 $gcd(p,a)=1$이다. ($\because\;p$가 소수이므로 $gcd(p,a)=p$ 또는 $gcd(p,a)=1$)
그러므로 $p|b$이다.
따름정리 1. $p$가 소수이고 $p|a_1 a_2 a_3 \cdots a_n$이면 어떤 $k$에 대하여 $p|a_k \;\;(1\leq k\leq n)$이다.
따름정리 2. $p,q_1 , q_2, q_3 ,\cdots q_n$가 소수이고 $p|q_1 q_2 q_3 \cdots q_n$이면 어떤 $k$에 대하여 $p|q_k \;\;(1\leq k\leq n)$이다.
기본정리 1보다 큰 모든 정수는 소인수분해할 수 있고 소인수의 차례를 생각하지 않는다면 그 표현은 오로지 하나이다.
증명 $n$이 소수라면 이미 증명된 것이므로 합성수라고 하자.
합성수라면 반드시 약수 $d$가 존재한다. $d|n$이고 $1<d<n$이다.
약수 가운데 가장 작은 수를 $p_1$이라고 하면 $p_1$은 소수이다.
왜냐하면 $p_1$이 약수 $q$를 가지면 $1<q<p_1$이고 $q|p_1$이면 $p_1 |n$이므로 $q|n$이다. 이는 $p_1$이 최소라는데 모순이다.
이제 $n=p_1 n_1$으로 놓을 수 있다. ($1<n_1 <n$)
마찬가지로 $n_1 =p_2 n_2$인 두 번째 소수 $p_2$를 찾을 수 있다.
$$n=p_1 p_2 n_2 \quad\quad\;\;\;1<n_2<n_1$$
계속하여 소수 $p_k$를 찾을 수 있다.
$$n=p_1 p_2 p_3 n_3 \quad\quad\;\;\;1< n_3 <n_2$$
$$n>n_1 >n_2>\cdots>1$$
이므로 끝없이 할 수는 없다. $n_{k-1}$이 소수라면 $p_k$라고 쓰자.
$$n=p_1 p_2 p_3 \cdots p_k$$
이제 소인수분해가 하나뿐임을 증명하자.
$$n=p_1 p_2 p_3 \cdots p_r =q_1 q_2 q_3 \cdot q_s\quad\quad\;\;r\leq s$$
$p_i ,q_j$은 소수이고 번호에 따라 크기가 정해졌다고 하자.
$$p_1 \leq p_2 \leq \cdots \leq p_r ,\;\;q_1 \leq q_2 \leq \cdots \leq q_s$$
$p_1 |q_1 q_2 \cdots q_s$이므로 $p_1 |q_k$이다. 이것은 $p_1 =q_k$이므로 $q_1 \leq p_1$이다.
마찬가지로 $q_1 |p_1 p_2 \cdots p_r$이므로 $p_1 \leq q_1$이다.
그러므로 $p_1 =q_1$이다. 이제 $p_1$을 소거하고
$$ p_2 p_3 \cdots p_r = q_2 q_3 \cdots q_s\quad\quad\quad\;\;r\leq s$$
에서 $p_2 =q_2$를 얻는다. 같은 과정을 되풀이하면
$$1=q_{r+1}q_{r+2}\cdots q_s$$가 남는다.
$q_j >1$이므로 이런 일은 없다. 그러므로 $r=s$이다.
$$p_1 =q_1 ,p_2=q_2 , \cdots ,p_r =q_r$$
이므로 소인수분해는 오로지 하나만 존재한다.
정리 소수는 무한하다.
증명 소수가 유한하다고 하고 $p_n$이 마지막 소수라고 하자.
아래와 같은 합성수를 생각하자.
$$P=p_1 p_2 p_3 \cdots p_n +1$$
$P>1$이므로 소인수 $p$를 가진다고 하면 $p=p_k \;(1\leq k \leq n)$이다.
$p|P$이고 $p|p_1 p_2 p_3 \cdots p_n$이므로 $p|P-p_1 p_2 p_3 \cdots p_n$이다.
$p|1$이므로 모순이다.
따라서 소수는 무한하다.
어떤 방법으로 소수를 찾아나갈 수 있을까? 가장 오래된 방법은 에라토스테네스의 체(Sieve of Eratosthenes)이다.
이제 $p^\#$을 소수 $p$와 같거나 작은 모든 소수를 곱한 수라고 정의하면 $p^\# + 1$을 '유클리드 수(Euclidean numbers)로 부른다. $\displaystyle{p^\# =\prod_{p\in S}p=\prod_{i=1}^{n}p_i}$라고 표현하기도 한다.
$$2^\# +1=3$$
$$3^\# +1=2\cdot 3 +1=7$$
$$5^\# +1 =2\cdot 3\cdot 5 +1=31$$
$$7^\# +1=2\cdot 3\cdot 5\cdot 7 +1=211$$
$$11^\# +1=2\cdot 3\cdot 5\cdot 7 \cdot 11+1=2311$$
은 소수이지만 아래는 소수가 아니다.
$$13^\# +1=59\cdot 509$$
$$17^\# +1=19\cdot 97\cdot 277$$
$$19^\# +1=347\cdot 27953$$
여기에 아직 답이 알려지지 않은 한 가지 물음이 있다.
$p^\# + 1$이 소수가 되는 소수 $p$가 무한히 많은가? 합성수가 되는 소수가 무한히 많은가?
$p^\# +1$이 소수임이 밝혀진 소수 18개가 있다.
$$p=2,3,5,7,11,31,379,1019,1021,2657,3229,4547,11549,13649,18523,23081,204049$$
마지막 수는 1995년에 찾아냈는데 자리수가 무려 $10387$이나 되는 엄청나게 큰 수이다. $p\leq 35000$일 때 나머지는 모두 합성수임이 알려져 있다.
다음과 같은 수열을 생각하자.
$$\begin{array}{1}n_1&=2\\n_2&=n_1 +1\\n_3&=n_1 n_2 +1\\n_4 &=n_1 n_2 n_3 +1\\ &\vdots \\ n_k&=n_1 n_2 n_3 \cdots n_{k-1}+1\\ &\vdots\end{array}$$
$n_k >1$이므로 소인수를 가진다. 하지만 둘 이상의 $n_k$가 공통된 소인수를 가지지 않는다.
왜냐하면 $d=gcd(n_i , n_k)\;\;\;(i<k)$라고 하면 $d|n_k ,d|n_1 n_2 \cdots n_{k-1}$이므로 $d|1$이다.
따라서 $n_k$는 모두 서로소이다.
$n$번 째 소수를 $p_n$으로 나타낸다면 유클리드 증명에서 $p_1 p_2 p_3 \cdots p_n +1$이 소인수를 가진다면 새로운 소수 $p_{n+1}$이 있다는 것이다. 또 $p_{n+1}$는 $p_1 p_2 p_3 \cdots p_n +1$을 초과할 수 없다.
$$p_{n+1}\leq p_1 p_2 p_3 \cdots p_n +1\quad \quad \quad n\geq 1$$
다시 적으면
$$p_{n}\leq p_1 p_2 p_3 \cdots p_{n-1} +1\quad \quad \quad n\geq 2$$
이고
$$p_{n}\leq p_1 p_2 p_3 \cdots p_{n-1} -1\quad \quad \quad n\geq 3$$
$n=5$라면 아래와 같다.
$$11=p_5 \leq 2\cdot 3\cdot 5\cdot 7 -1=209$$
본즈 부등식(Bonse's inequality)에 의하여
$${p_{n} }^2 <p_1 p_2 p_3 \cdots p_{n-1}\quad \quad \quad n\geq 5$$
${p_{5}}^2 <210$이므로 $p_5 \leq 14$이다. 소수를 찾는 더 좋은 부등식은 아래와 같다.
$$p_{2n}=p_2 p_3 \cdots p_n -2\quad\quad n\geq 3$$
$$p_5 <p_6 \leq p_2 p_3 -2 =3\cdot5 -2=13$$
