소수(Prime Numbers)

1보다 큰 자연수 $p$ 의 양의 약수가 1과 $p$ 밖에 없을 때, 정수 $p$ 를 소수라고 한다.
그리고 어떤 정수 $n$ 이 $\pm 1$ 과 $\pm p$ 이외의 약수를 가지면, 이 정수 $n$ 을 합성수라고 한다.

예를 들어, $18=2\times 9$ 이므로 2와 9는 18의 약수이다. 이때, 2와 9를 18의 인수(factors) 라고도 한다. 특히, 2는 소수이면서 18의 인수이다. 이러한 소수인 인수를 소인수(prime factors) 라고 한다.

특히,

$$18=2\times 3^2$$

와 같이 자연수를 소수들만의 곱으로 표현하는 것을 소인수분해(prime factorization) 라고 한다.

약수와 배수 (Divisors and Multiples)

정수 $a(\ne 0)$, $b\in \mathbb{Z}$ 에 대해, 어떤 정수 $c$ 가 존재하여

$$b=ac$$

이면, “$b$는 $a$로 나누어진다” 라고 말하며, $a$ 를 $b$ 의 약수(divisor) 라고 한다.
또한, $b$ 를 $a$ 의 배수(multiple) 라고 한다.

만약 $b=ac$ 를 만족하는 $c$ 가 없을 때, ” $a$ 는 $b$ 를 나누지 못한다” 라고 하며, $a\nmid b$ 로 표시한다.

소수의 개수가 무한히 많음을 증명하라

소수의 개수가 $n$ 개로 유한하다고 가정하자. 그러면 소수는 다음과 같이 $n$ 개로 나타낼 수 있다.

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

이제 새로운 수를 정의하면

$$q=p_1{p}_2{p}_3\cdots p_n+1$$

$n$개의 소수 중에 적어도 하나는 $q$를 나눈다. 그 수를 $p_i$ 라고 하면

$$p_i\mid q$$

이고,

$$p_i\mid p_1{p}_2{p}_3\cdots p_n$$

이므로, $p_i$ 는 1을 나누어야 한다.

$$p\mid q-p_1{p}_2{p}_3\cdots p_n=1$$

이는 모순이 된다. 따라서 처음 가정이 틀렸으므로 소수의 개수는 무한히 많다.

소수의 성질

만약 $p$ 가 소수이고 $p\mid ab$ 이면,

$$p\mid a\text{또는}p\mid b$$

증명

$p\mid ab$ 라고 가정하자. 그러면 $p$ 와 $a$ 가 서로소인 경우, 반드시

$$p\mid b$$

이어야 한다. 즉, 소수는 곱셈에서 하나의 인수에만 영향을 미친다.

산술의 기본정리

$1$을 제외한 모든 자연수는 소수들의 곱으로 표현되며, 그 표현 방법은 순서를 제외하면 유일하다. 즉, 각 수는 소수의 곱으로 나타낼 수 있으며, 이는 유일하다.

$n=p_1^{e_1}\cdot p_2^{e_2}\cdot p_3^{e_3}\cdots p_i^{e_i}$

증명

수학적 귀납법을 이용하여 정리의 앞부분을 증명하자. $S=\{n\in \mathbb{N}\mid n\ge 2\text{인 소수들의 곱}\}$이라고 놓으면, $2\in S$ 이다.

$k\ge 2$ 인 정수에 대하여 $2,\dots ,k\in S$ 라는 가정 하에 $k+1\in S$ 임을 보이면 된다.

• $k+1$ 이 소수이면, $k+1\in S$
• $k+1$ 이 소수가 아니면, $k+1=rs$ ($2\le r,s\le k$) 를 만족하는 정수 $r,s$ 가 존재하는데, 이들은 가정에 의해 $S$ 의 원소이므로 각각 소수들의 곱으로 표시된다.

따라서 $k+1$ 도 소수들의 곱으로서 $k+1\in S$ 이다.
그러므로 수학적 귀납법에 의하여 $S$ 는 2 이상의 모든 자연수의 집합이다.

표시 방법의 유일성의 증명을 위하여

$$n=p_1\cdot p_2\cdot p_3\cdots p_h=q_1\cdot q_2\cdot q_3\cdots q_k$$

라고 하자.

단, $p_1,p_2,p_3,\dots ,p_h,q_1,q_2,q_3,\dots ,q_k$ 는 모두 소수이다. 위의 정리 1에 의해서, $p_1\mid q_1\cdot q_2\cdot q_3\cdots q_k$ 로부터 $q_1,q_2,q_3,\dots ,q_k$ 중 적어도 하나는 $p_1$ 의 배수임을 알 수 있다.

$q_1,q_2,q_3,\dots ,q_k$ 의 순서를 적당히 바꾸어서 $q_1$ 이 $p_1$ 의 배수라고 하자. 그런데 이런 경우 $q_1$ 도 소수이므로 사실은 $p_1=q_1$ 이다.

이제 $n$ 을 $p_1$ 로 나누면,

$$p_2\cdot p_3\cdots p_h=q_2\cdot q_3\cdots q_k$$

가 되고, 위와 같은 방법으로 $p_2=q_2$ 를 얻는다. 이렇게 계속하면 $h=k$ 이고, 모든 $i=1,2,\dots ,h$ 에 대하여 $p_i=q_i$ 임을 알 수 있다.

소수 판별법

양의 정수 $m$ 에 대해 $\sqrt{m}$ 보다 작거나 같은 최대 정수를 $I$ 라고 하자. 만약 $m$ 이 $I$ 보다 작거나 같은 소인수를 가지지 않으면, $m$ 은 소수이다. ($x^2=m$ ($m\ge 0$) 를 만족하는 $x$ 값 중 하나는 $\sqrt{m}$ 이며, 이를 $m$의 양의 제곱근이라고 한다.)

증명

$m$ 이 합성수라고 하면, 가정에 의하여 $m$ 은 $I$ 보다 큰 소인수 $p$ 를 가진다. 이때, $m=pq$ 로 소인수분해된다면 $q$ 도 $m$ 의 소인수이므로, 가정에 의해 $q>I$ 이다.

따라서,

$$p\ge I+1,q\ge I+1$$

이므로,

$$m=pq\ge (I+1{)}^2$$

그러나, 가정에 의해 $m\le I^2$, 즉

$$m<(I+1{)}^2$$

이므로 모순이 발생한다. 따라서, $m$ 은 소수이다.

예제

1. $16$을 소인수분해하라.¹

2. $108$을 소인수분해하라.²

3. $4k+3$꼴의 소수가 무한히 많음을 증명하라.³

4. $120$을 소인수분해하고, 양의 약수를 모두 구하여라.⁴

5. $2023$은 소수인가? 소수가 아니라면, 소인수분해하라.⁵

Footnotes

1. $16=2^4$ ↩

2. $108=2^2\times 3^3$ ↩

3. $4k+3$꼴의 소수가 유한 개뿐이라고 가정하고, 그러한 소수를 $p_1,p_2,p_3,\dots ,p_n$ 이라고 하자. 이제 새로운 수 $m=4p_1{p}_2{p}_3\cdots p_n-1$ 을 고려한다. 이 수는 $m=4(p_1{p}_2{p}_3\cdots p_n-1)+3$ 의 형태로 나타낼 수 있으므로, $m$은 홀수이다. 따라서 $m$을 나누는 소수들도 모두 $4k+1$ 또는 $4k+3$꼴이다. 그런데 기존의 $p_1,p_2,\dots ,p_n$이 모두 $4k+1$ 꼴이라면, $m$ 역시 $4k+1$꼴이어야만 한다. 그러나 $m$ 은 적어도 하나의 $4k+3$ 꼴 소수의 약수를 가져야 한다. 이 약수를 $p$ 라 하면, $p$ 는 $p_1,p_2,p_3,\dots ,p_n$ 중 하나이어야 한다. 즉, $p\mid 4p_1{p}_2{p}_3\cdots p_n$ 이어야 한다. 그러나 $p\mid m=4p_1{p}_2{p}_3\cdots p_n-1$ 이므로, $p\mid 1$ 이 되어 모순이 발생한다. 따라서, $4k+3$꼴의 소수는 무한히 많다. ↩

4. $120=2^3\times 3\times 5$ 이므로, 양의 약수는 $1,2,3,4,5,6,8,10,12,15,20,24,30,40,60,120$ 이다. ↩

5. $2023$이 소수인지 확인하려면 $\sqrt{2023}$ 보다 작거나 같은 최대 정수를 구해야 한다. $\sqrt{2023}\approx 44.98$ 즉, 44보다 작거나 같은 소수인 $2,3,5,7,11,13,17,19,23,29,31,37,41,43$를 이용하여 2023이 이들로 나누어지는지 조사하면 된다. $2023=17\times 119$ 이므로 $2023$은 소수가 아니다. ↩