소수와 합성수 에라토스테네스의 체 소수 판정법

이번 시간에는 소수와 합성수에 대해 정리하고 소수를 찾는 방법으로 에라토스테네스의 체에 대하여 학습하고 마지막으로 소수 판정법에 대해 학습하기로 하자.

먼저 두 가지 초등학교와 중학교에서 배우는 두 소수의 의미에 대해 간단히 정리하자.

• 小數 : 작은수라는 의미로 [소:수] 로 읽는다.
• 素數 : 자연수의 바탕이 되는 수로 [소쑤]로 읽는다.

초등학교 때 배운 소수는 소~수로 읽고 오늘 학습할 소수는 소쑤로 발음한다는 것을 기억하고 학습을 이어가자.

자연수의 ‘분해’

수학에서 분해는 주어진 수나 식을 곱셈으로 정리하는 것을 의미한다.

$12=2\times 6=2\times 2\times 3$

자연수 $12$를 이해하려면 곱셈을 이용해 분해하는 것이 가장 좋은 방법이다. 위의 식에서 $2,3$은 자신보다 작은 두 수의 곱으로 분해 할 수 없는 수 이고, 따라서$12$는 $2\times 2\times 3$으로 분해된다고 할 수있다.

$2,3$과 같은 수가 더 이상 분해 할 수 없는 이유는 약수가 $1$과 ‘자신’뿐이기 때문이다. 이렇게 약수가 2개 뿐인 수를 소수 라고 하고 다음과 같이 정의 한다.

소수와 합성수 정의

소수와 합성수는 두 가지 방법으로 정의 할 수 있고 둘은 정확히 동일한 의미를 갖는다. 먼저 약수의 개수에 따른 정의 부터 살펴보자.

소수와 합성수 정의1(약수의 개수)

자연수는 약수의 개수가 $1$개, $2$개, $3$개, $4$개 $\cdots$ 인 자연수들로 구성된다. 따라서 약수의 개수에 따라 다음과 같이 정의 할 수 있다.

$\text{자연수}=\{\begin{array}{l}\text{약수의 개수 :}1\text{ 개}\to 1\\ \text{약수의 개수 :}2\text{ 개}\to \text{소수}\\ \text{약수의 개수 :}3\text{ 개 이상}\to \text{합성수}\end{array}$

약수의 개수가 $3$개 이상인 수에 대해 생각해 보자. 예를 들어 $4$의 경우 $1,2,4$를 약수로 갖는다 즉 $1$과 ‘자신’ 이외의 약수$2$가 있어 $4=2\times 2$이다. 약수의 개수가 3개 이상이면 1이 아닌 두 수의 곱으로 표현되고 이러한 성질에 따라 ‘합성수’라고 부른다.

소수와 합성수의 정의2

• 소수 : $1$ 보다 큰 자연수 중에 1과 자신만을 약수로 가지는 수
• 합성수 : $1$ 보다 큰 자연수 중에 1과 자신 이외의 수를 약수로 갖는 수

소수와 합성수의 성질

이제 정의를 토대로 알 수 있는 소수와 합성수에 대한 성질을 정리 보기로 하자.

1. $1$은 소수도 합성수도 아니다.
2. $2$를 제외한 소수는 모두 홀수이다.

첫 번째는 너무 당연하기 때문에 따로 다루지 않고 두 번째 성질에 대해 생각해 보자.

초보적인 논리 (귀류법의 기초)

$2$를 제외한 소수는 모두 홀수라는 것을 보이기 위해 무한한 소수를 다 찾아 확인한다면 죽을때 까지 이것을 증명하지 못한다. (왜냐면 소수는 무한히 많으니까..)

그렇다면 소수를 전부 찾지 않고 $2$를 제외한 소수가 모두 홀수 임을 논리적으로 보일 수 있는 방법에 대해 살펴보자.

정당화

2를 제외한 소수는 자연수 이고 자연수는 짝수와 홀수로 구분된다.

$\left(\begin{array}{c}2\text{를 제외한 소수}\\ \text{자연수}\end{array}\right)\to \{\begin{array}{l}\text{짝수}\\ \text{홀수}\end{array}$

위와 같은 이유로 두 주장은 정확히 같은 주장이다.

• $2\text{를 제외한 소수}$는 모두 $\text{홀수}$이다.
• $2\text{를 제외한 소수}$가 $\text{짝수}$이면 말도 안된다.

$2\text{를 제외한 소수}$는 ‘자연수’이므로 $\text{짝수}$ 또는 $\text{홀수}$ 이다. 즉 $2\text{를 제외한 소수}$가$\text{짝수}$라는 것이 말도 안된다면 $\text{홀수}$라고 할 수 있다.

이제 두 번째 주장을 보이면 충분하다.

$2\text{를 제외한 }\text{소수}$ 중에 $\text{짝수}$가 있다고 하면 약수로 ‘$1$’, ‘$\text{자신}$’ 그리고 ‘$2$’를 약수로 갖는다. 이는 $\text{소수}$가 약수를 $3$개 이상 갖게 되는 말도 안되는 상황이다.

따라서 $2\text{를 제외한 소수}$는 모두 $\text{홀수}$이다.

이제 소수를 체계적으로 찾는 방법인 에라토스테네스의 체에 대해 정리해 보기로 하자.

에라토스테네스의 체

에라토스테네스의 체는 소수의 약수가 자신을 제외하면 1 뿐임을 이용해 소수가 아닌 수를 제외하여 소수를 찾는 방법으로 다음과 같은 과정을 거친다.

• 소수가 아닌 $1$을 제거하고 다음을 반복한다.
• 남아있는 가장 작은 수($\mathrm{<img\; draggable="false"\; role="img"\; class="emoji"\; alt="◻"\; src="https://s.w.org/images/core/emoji/15.1.0/svg/25fb.svg">}$)에 대하여
  $\mathrm{<img\; draggable="false"\; role="img"\; class="emoji"\; alt="◻"\; src="https://s.w.org/images/core/emoji/15.1.0/svg/25fb.svg">}$를 제외한 $\mathrm{<img\; draggable="false"\; role="img"\; class="emoji"\; alt="◻"\; src="https://s.w.org/images/core/emoji/15.1.0/svg/25fb.svg">}$의 배수를 제거

---

이를 자연수에 적용하면 다음과 같다.

• 소수가 아닌 $1$을 지운다.
• $2$를 제외한 $2\text{의 배수}$ : $4,6,8,10,\cdots$ 제거
• $3$을 제외한 $3\text{의 배수}$ : $6,9,12,15,\cdots$ 제거
• $5$를 제외한 $5\text{의 배수}$ : $10,15,20,25,\cdots$ 제거
• $7$을 제외한 $7\text{의 배수}$ : $14,21,28,35,42,49\cdots$ 제거

위의 과정을 적용해 $150$ 까지 소수를 찾을 수 있다.

$1,2,3,4,5,6,7,8,9,10$
$11,12,13,14,15,16,17,18,19,20$
$21,22,23,24,25,26,27,28,29,30$
$31,32,33,34,35,36,37,38,39,40$
$41,42,43,44,45,46,47,48,49,50$

알고리즘을 조금더 자세히 살펴보면 다음과 같은 규칙을 찾을 수 있다.

• $2\text{의 배수}$로 처음 삭제되는 수 : $4$
• $3\text{의 배수}$로 처음 삭제되는 수 : $9$
• $5\text{의 배수}$로 처음 삭제되는 수 : $25$
• $7\text{의 배수}$로 처음 삭제되는 수 : $49$

소수 판정법

어떤 자연수가 소수임을 판단할 수 있는 방법에 대해 정리하고 학습을 마무리 하도록 하자. $101$이 소수인지 판정하는 것을 예로 설명해 보기로 하자.

$101$이 소수인지 확인하는 것은 $1$을 포함하지 않는 두 수의 곱으로 표현할 수 있는지 확인하면 충분하다.

• $100(10\times 10)<101<121(11\times 11)$이므로
• $101=\mathrm{△}\times \mathrm{<img\; draggable="false"\; role="img"\; class="emoji"\; alt="◻"\; src="https://s.w.org/images/core/emoji/15.1.0/svg/25fb.svg">}$ 일 때 $\mathrm{△},\mathrm{<img\; draggable="false"\; role="img"\; class="emoji"\; alt="◻"\; src="https://s.w.org/images/core/emoji/15.1.0/svg/25fb.svg">}$둘 중 하나는 $11$보다 작다.
• $101$이 $2,3,4,5,6,7,8,9,10$의 배수인지 아닌지 판단.
  약수가 있다면 $101$은 소수 $\times$
  약수가 없다면 $101$은 소수 $◯$

마지막 과정은 다음과 같이 더 축소 할 수 다.

• $101$에 대하여
  $2$의 배수 $\times \to 4,6,8,\cdots$의 배수도 $\times$
  $3$의 배수 $\times \to 6,9,12,\cdots$의 배수도 $\times$
  $5$의 배수 $\times \to 10,15,20,\cdots$의 배수도 $\times$
  $7$의 배수 $\times \to 14,21,28,\cdots$의 배수도 $\times$
  $\cdots$

이러한 사고는 에라토스테네스의 체와 동일한 알고리즘과 동일하다. 따라서 $2,3,4,5,6,7,8,9,10$에서 배수인지 확인해야 하는 수는 ‘체’로 걸러진 ‘소수’ $2,3,5,7$이다.

$101$의 소수 판정법은 다음과 같이 요약할 수 있다.

• ${10}^2=100<101<{11}^2=121$이므로
• $11\text{이하의 소수 :}2,3,5,7$에 대하여
• 어떤 하나의 수로 나누어지면$\to$합성수,
  어떤 수로도 나누어 지지 않으면$\to$소수

소수 판정법 정리(중3)

어떤 자연수 $N$이 다음을 만족하면 소수이다.

• $p(\text{소수})<\sqrt{N}$ 에 대해 $p$는 $N$의 약수가 아니다.