정의. 소수(prime numbers)

$p$가 음이 아닌 정수라 하자. 이 때, $p$의 양의 약수가 $1$과 자기 자신 $p$ 밖에 없으면 $p$를 소수(prime number)라 한다. 또한 소수가 아닌 수들은 합성수(composite number)라 한다.

 

모든 소수의 집합을 $\mathbb{P}$로 나타내기로 하자.

 

정리 2.4.1.

$a,\,b \in \Z$이고 $p \in \mathbb{P}$라 하자. 만약 $p \mid ab$이면 $p \mid a$이거나 $p \mid b$이다.

 

증명. $p \not\mid a$라 가정하자. $p$가 소수이기 때문에 $p$의 약수는 $1$ 또는 $p$ 밖에 존재하지 않고 따라서 $\gcd(a,\,p) = 1$이 성립한다. 그러므로 정리 x.x.에 의해 적당한 정수 $x,\,y \in \Z$가 존재하여 $1 = ax + py$를 만족한다. 그러므로 $b = abx + pby$이고 $p \mid b$가 성립한다..

 

정리 2.4.2. 산술의 기본정리(fundamental theorem of arithmetic)

$2$ 이상의 모든 정수 $n$는, 곱하는 순서를 무시하면, 소수의 곱으로 유일하게 표현할 수 있다. 즉, 다음 성질을 만족시키는 $p_{1},\, \ldots,\, p_{k} \in \mathbb{P}$ 및 $r_{1},\, \ldots,\, r_{k} \in \mathbb{N}$가 존재하며, 이는 $i = 1,\, \ldots,\, k$의 순열을 무시하면 유일하다. \[ n = p_{1}^{r_{1}} p_{2}^{r_{2}} \cdots p_{k}^{r_{k}} \]

 

증명. 먼저 수학적 귀납법을 이용하여 소수의 곱 표현의 존재성을 증명하자: 우선 자명하게 $2$는 소수의 곱으로 표현할 수 있다. 이제 $2 \leq m < n$인 모든 $m$에 대하여 $m$이 소수의 곱으로 나타낼 수 있다고 가정하자. 만약 $n$이 소수라면 자명하게 $n$은 소수의 곱으로 나타낼 수 있다. 이제 $n$이 합성수라 가정해 보자. 그러면 $2 \leq n_{1},\, n_{2} < n$이 존재하여 $n = n_{1}n_{2}$로 나타낼 수 있다. 하지만 귀납법 가정에 의해서 $n_{1}$과 $n_{2}$는 소수의 곱으로 나타낼 수 있고 따라서 $n = n_{1}n_{2}$ 또한 소수의 곱으로 나타낼 수 있다.

이제 소수의 곱 표현의 유일성을 증명하기 위하여, $n$이 아래와 같이 두가지 서로 다른 소수의 곱 표현이 존재한다고 가정해 보자. \[ n = p_{1}^{r_{1}} p_{2}^{r_{2}} \cdots p_{k}^{r_{k}} = q_{1}^{s_{1}} q_{2}^{s_{2}} \cdots q_{l}^{s_{l}} \tag*{($\ast)$}\] 단, $p_{1} < \cdots < p_{k}$와 $q_{1} < \cdots < q_{l}$을 가정하자. 먼저 $p_{1} \mid q_{1}^{s_{1}} q_{2}^{s_{2}} \cdots q_{l}^{s_{l}}$가 성립하므로 정리 2.4.2에 의해 $q_{1} \mid q_{j}$인 $1 \leq j \leq l$가 존재한다. 하지만 $p_{1}$과 $q_{j}$가 둘 다 소수이므로 $p_{1} = q_{j}$여야 함을 알 수 있다. 한편, $q_{1} \mid p_{1}^{r_{1}} p_{2}^{r_{2}} \cdots p_{k}^{r_{k}}$이므로 마찬가지 논리로 적당한 $1 \leq i \leq k$에 대하여 $q_{1} = p_{i}$를 얻는다. 따라서 \[ p_{1} \leq p_{i} = q_{1} \leq q_{j} = p_{1} \] 이므로 $p_{1} = q_{1}$임을 알 수 있다. 이제 편의상 $r_{1} < s_{1}$을 가정하자. 그러면 $(\ast)$의 양변을 $p_{1}^{r_{1}} = q_{1}^{r_{1}}$로 나누어 \[ p_{2}^{r_{2}} \cdots p_{k}^{r_{k}} = q_{1}^{s_{1} - r_{1}} q_{2}^{s_{2}} \cdots q_{l}^{s_{l}} \] 를 얻는다. 하지만 위와 비슷한 이유로 $p_{2} = q_{1}$이어야만 하는데 이는 $p_{1} < p_{2} = q_{1} = p_{1}$이 되어 모순이다. 마찬가지 논리로 $r_{1} > s_{1}$임을 가정해도 모순을 얻고 $r_{1} = s_{1}$임을 얻는다. 이와 같은 과정을 계속 반복하면, $k=l$이고 모든 $1 \leq i \leq k$에 대하여 $p_{i} = q_{i}$이고 $r_{i} = s_{i}$임을 보일 수 있다. 따라서 소수의 곱 표현은 유일하다..

 

$2$ 이상의 정수 $n$에 대하여, 위 산술의 기본정리에 의해 $n$은 유일한 소수의 곱 표현을 갖는데, 이 표현을 $n$의 소인수분해(factorization)라 한다.

 

예제. 예를 들어 $120$을 소인수분해하면 $120 = 2^{3} \cdot 3 \cdot 5$를 얻는다.

 

이제 소수에 관한 여러가지 기본 성질들에 대하여 알아보자. 가장 먼저 알아 볼 정리는 소수의 무한성이다.

 

정리 2.4.1.

집합 $\mathbb{P}$는 무한집합이다. 즉, 무한히 많은 소수가 존재한다.

 

증명. 결론에 반하여 $\mathbb{P}$가 유한집합이라 가정해보자. 그러면 $\mathbb{P} = \{ p_{1},\, p_{2},\, \ldots,\, p_{k} \}$라 가정할 수 있다. 이제 다음과 같이 $n \in \N$을 정의하자. \[ n = p_{1} p_{2} \cdots p_{k} + 1 \] 이 $n$ 모든 $p_{i}$보다 크므로 가정에 의해 $n$은 합성수여야 한다. 이제 산술의 기본정리에 의해 $n$의 소인수분해가 존재한다. 특히 적당한 $1 \leq i \leq k$에 대하여 $p_{i} \mid n$을 얻는데, $p_{i} \mid p_{1} \_{2} \cdot p_{k}$이므로 \[ p_{i} = (n - p_{1} p_{2} \cdot p_{k}) \implies p_{i} \mid 1 \] 이 되어 모순이 생긴다. 따라서 $\mathbb{P}$는 무한집합 이어야만 한다..

 

정리 2.4.1.

$n \in \N$이고 $p \in \mathbb{P}$라 하자. 그러면 $p^{k} \mid n!$을 만족하는 가장 큰 정수 $k$는 아래의 공식을 통해 얻을 수 있다. \[ k = \sum_{j=1}^{\infty} \left\lfloor \frac{n}{p^{j}} \right\rfloor \]

 

다음은 소수와 관련된 몇가지 잘 알려진 가설들이다.

1. [골드바흐의 추측] $2$보다 큰 모든 짝수는 두 소수의 합으로 나타낼 수 있다.
2. [쌍둥이소수 추측] 만약 $p$와 $p+2$가 모두 소수이면 $(p,\, p+2)$를 쌍둥이소수(twin prime)라 한다. 이 때, 쌍둥이 소수는 무한하다.