Def Prime

자연수 세계 - 서론과 이야기거리 로 돌아가기

소수의 정의

자연수는 하나로 부터 더하기로 세워진 수다. 그렇다면 곱하기로도 모든 자연수를 나타낼 수 있을까? 있다. 소수라고 하는 수가 그것인데, 하지만 그 수는 끝없이 많다. 나뉨의 관계로 두 자연수의 관계를 볼 수 있는데, 어떤 두 자연수도 나뉘거나 나뉘지 않거나 둘 중 하나다. 그런데 1을 빼고는 어떤 다른 자연수로도 나뉠 수 없는 수를 소수라고 한다. 특별한 수들이다. 어떤 자연수도 소수들의 곱으로 '유일하게' 표현된다. 따라서 어떤 자연수가 곱셈으로 어떻게 만들어졌는지 분해하면 자연수들 사이의 관계를 파악하기 쉽다. 따라서 인류는 오랫동안 소수들의 세계를 탐구해 오고 있다. 그러나 소수들의 세계는 좀처럼 쉽게 그 비밀을 드러내지 않고 있다. 자연수 세계의 여정을 소수의 길을 따라 가보자.

약수

10, 36, 121 과 같은 수를 더 작은 수의 곱으로 나눠보자. 10은 2와 5의 곱으로, 1과 10의 곱으로도 나타낼 수 있다. 이를 10 = 2∙5 = 1∙10 과 같은 방법으로 타낸다고 보면, 예를 들어, 36과 121은

$36=2\cdot 18=3\cdot 12=4\cdot 9=6\cdot 6=1\cdot 36$

$121=11\cdot 11=1\cdot 121$

이다.

10은 1, 2, 5, 10으로 나눌 때 모두 나머지가 0 이 된다. 121 은 1, 11, 121 이 그런 수들이고, 36 은 1, 2, 3, 4, 6, 9, 12, 18, 36이 그런 수들이다. 이런 수들을 주어진 수에 대한 약수라고 부른다.

(정의 : 약수) 주어진 자연수 a 에 대하여 어떤 자연수 b 가 a 를 나눌 때, b 을 a 의 약수(約數 ; divisor) 라고 한다.

다시 말해, a | b 이면 b 는 a 의 약수다.

다음에 주어진 수에 대하여 약수를 찾으시오. (되도록 암산으로 해보시오.) : 2, 9, 11, 35, 420, 432978, 1421805, 4294967297

주어진 수가 크지 않다면 약수를 찾는 것이 간단한 듯 보인다. 하지만 앞의 예에서 큰 수를 보라. 대단히 복잡하고 어려운 과정이다. 어떤 두 수의 약수를 찾으면 두 수의 관계를 파악하기 쉽다. 더 작은 수들의 곱으로 분해해서 나타내면 그 전보다 그 수의 구성을 더 쉽게 알 수 있다. 따라서 어떤 주어진 수에 대하여 그보다 작은 수로 나누어질 수 있는 조건을 찾는 문제는 수학적으로 중요한 문제가 된다. 가장 간단한 예를 들어보면, 10-진법 표현에서 0 이나 2로 끝나는 모든 자연수는 2로 나누어진다. 그리고 5 나 0 으로 끝나는 모든 자연수는 5로 나누어진다. 또 어떤 자연수가 3으로 나뉘는지 아닌지 아는 방법은 표현된 수자들에서 자릿수를 무시하고 숫자들을 모두 더해서 3으로 나뉘면 된다.

그런 조건을 말해주는 특별한 방법은 알려진 게 그리 많지 않다. 그런 특별한 성질을 모를 경우 어쩔 수 없이 더 이상 나눌 수 없는 작은 수들로 쪼개가보는 수밖에 없다. 이 때, 더이상 나눌 수 없는 작은 수들에 해당하는 수들이 소수다.

소수의 정의

위에서 본 것처럼 어떤 자연수는 더 작은 수들의 곱으로 쪼개질 수 있는데 어떤 자연수는 다른 나누는 수(약수)를 갖지 않는다. 1과 그 자신으로 나누는 것은 항상 성립하기 때문에 의미가 없다. 다른 말로 하면 자연수는 1과 그 자신만 약수로 가지는 수와 다른 수를 약수를 갖는 수로 분류할 수 있다. 앞의 경우는 특별한 경우라서 소수(素數; prime number)라고 따로 이름을 주어 부른다.

(정의 : 소수) 1 과 1이 아닌 그 자신으로만 나누어지는 자연수를 소수라고 부른다.

그리고 1 도 아니고 소수가 아닌 모든 자연수들은 '합성수'(合成數, 영어: composite number)라고 부른다. 모든 자연수가 1과 소수와 합성수로도 쪼개어진다는 것 분명하다. 집합의 언어로 쓰면 다음과 같이 쓸 수 있다.

$\mathbb {N} =\{1\}\ \cup \ {\mbox{Prime}}\ \cup \ {\mbox{Comp}}$

여기서 Prime 은 모든 소수(Prime number)의 모임을 뜻하고 Comp는 모든 합성수의 모임이다. 세 집합 중 두 집합에 동시에 속한 자연수는 없다.

작은 수부터 100 개의 소수를 모아보면 아래와 같다.

2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97 101 103 107 10 113 127 131 137 139 149 151 157 163 167 173 179 181 191 193 197 199 211 223 227 229 233 239 241 251 257 263 269 271 277 281 283 293 307 311 313 317 331 337 347 349 353 359 367 373 379 383 389 397 401 409 419 421 431 433 439 443 449 457 461 463 467 479 487 491 499 503 509 521 523 541.

1 을 소수에서 왜 제외할까? 첫번째 이유라고 생각해볼 수 있는 것은 너무 뻔하다는 점이다. 어떤 자연수도 1로 나뉜다. 뻔해서 흥미거리가 아니다. 다음으로 생각할 수 있는 것은 소수와 관련한 성질을 이야기할 때마다 '1을 제외한 소수'라는 식으로 말을 붙이자면 불편하다는 점이다. 자연수 산술에게 기초 정리인 산술의 기본정리 를 예로들어보자. 산술의 기본 정리는 '1보다 큰 모든 자연수는 소수들의 곱으로 유일하게 표현할 수 있다' 다. 그런데 1이 소수라면 이렇게 바꿔써야 할 것l다. '1 보다 큰 모든 자연수는 1을 제외한 소수들의 곱으로 유일하게 표현할 수 있다'로 바꾸어야 한다. 만약 그렇지 않으면 6을 소수의 곱으로 표현할 경우,

$6=1\cdot 2\cdot 3=1\cdot 1\cdot 2\cdot 3=1\cdot 1\cdot 1\cdot 2\cdot 3=\cdots$

가 되기 때문이다. 번거롭다. 수학은 이런 걸 별로 좋아하지 않는다.

소수는 더이상 쪼갤 수 없는 수라고 직관적으로 이해할 때 기초 원소와 같은 역할을 한다. 뒤집어 생각해보면 모든 자연수는 소수들의 곱으로 표현할 수 있다는 말이다. 그런 뜻에서 소수 집합은 자연수 집합의 기초나 토대(base)의 역할을 한다. 물론 곱셈이라는 연산과 더불어.

앞의 큰수에 대한 약수를 찾는 예에서 보았듯이 어떤 자연수가 우리 앞에 툭 놓인다면 그 수가 소수인지 아닌지 고를 수 있는 것은 쉬운 일이 아니다. 소수인지 아닌지 판별할 수 있는 어떤 공식이 있다면 얼마나 좋겠는가? 그렇지만 소수를 모두 모은 집합은 간단한 구조를 갖지 않는다. 먼저 '실험'을 해보자.

아래 두 방식으로 1부터 100까지 숫자를 적어놓았다. 소수에 색을 칠해보고 그 어떤 규칙성이 있는지 확인해보라.

73	74	75	76	77	78	79	80	81	82
72	43	44	45	46	47	48	49	50	83
71	42	21	22	23	24	25	26	51	84
70	41	20	7	8	9	10	27	52	85
69	40	19	6	1	2	11	28	53	86
68	39	18	5	4	3	12	29	54	87
67	38	17	16	15	14	13	30	55	88
66	37	36	35	34	33	32	31	56	89
65	64	63	62	61	60	59	58	57	90
100	99	98	97	96	95	94	93	92	91

1	2	3	4	5	6	7	8	9	10
36	37	38	39	40	41	42	43	44	11
35	64	65	66	67	68	69	70	45	12
34	63	84	85	86	87	88	71	46	13
33	62	83	96	97	98	89	72	47	14
32	61	82	95	100	99	90	73	48	15
31	60	81	94	93	92	91	74	49	16
30	59	80	79	78	77	76	75	50	17
29	58	57	56	55	54	53	52	51	18
28	27	26	25	24	23	22	21	20	19

아래 $10\times 10$ 표에 어떤 규칙이든 좋으니 미리 규칙을 정한 다음 1부터 100까지를 채워 넣어보라. 100개의 수를 배열해보는 방법은 많이 있을 것이다. 규칙을 정한다는 것은 1부터 100까지를 넣는 프로그램을 짤 수 있다는 뜻이다. 달리 말하면 어떤 자연수가 몇 째 칸 몇 째 줄에 있는지 논리적으로 추측 가능하게 하라는 말이다. 수를 모두 넣었으면 소수에 색을 칠해보라. 소수들이 어느 정도 규칙성을 보이면서 나타나도록 1부터 100까지 넣는 방법을 고안해보라.

소수는 몇 개나 있을까? 다른 곳에 보이겠지만 끝없이 많다. 그렇다면 끝없이 빵을 찍어내는 기계를 상상할 수 있듯이 자연수를 반죽해서 소수를 계속 만들어 낼 기계를 만들 수 있을까? 다시 말해 모든 소수를 표현할 어떤 정해진 식이 있을까? 2부터 시작해서 (또는 처음의 어느 정도 유한한 것들을 빼고 나더라도 문제는 없을 것이다) 모든 소수를 만들어 낼 수 있는 알고리듬이 있는가? 얼마든지 저장할 수 있고 ,얼마든지 빠른 속도로 계산할 수 있고, C, Pascal, Basic, LISP 과 같은 컴퓨터 언어보다 얼마든지 좋은 언어를 사용하는 이상적인 컴퓨터가 있다 상상해보자. 그 컴퓨터에서 엔터키를 치면 주루룩 모든 소수를 만들어내는 그런 프로그램을 짤 수 있을까? 모든 소수를 생성할 알고리듬도 아직 없다. (어쩌면 영원히 없을 것이다.) 자연수 1, 2, 3, ... 에 따라 함수로 일대일 대응할 f(n) 은 아직 없다. 이는 자연수 전체에서 소수가 나타날 때 확실한 규칙을 가지고 나타나지 않는다는 말이다. 자연수 세계 - 서론과 이야기거리 로 돌아가기

Note

Math : Math글쓰기 | Math번역 | MathBoard | Math&Culture | MathMoim
OnLineMathCenter | MathCamp | SoftMathJournal | MathBook | CyberAcademia | Academia