Arithfundth

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

산술의 기본정리 : 소수들만의 곱으로 나누는 방법은 하나뿐이다.

'1보다 큰 모든 자연수는 소수들의 곱으로 나타낼 수 있다'에 대하여 우리는 직관적으로 알 수 있다. 나눗셈을 반복해서 하면 더이상 나눌 수 없는 지경에 이르게 되고, 그때 남은 수들은 당연히 소수들만 남을 테니까. 물론 증명할 수도 있다. 수학적 귀납의 원칙을 써 볼 수 있다. 자연수 2 는 분명히 소수들로 표현이 되었다. 자연수 3도 마찬가지다. 그리고 어떤 k 라는 수가 소수들의 곱으로 표현되었으면, k+1 도 소수들의 곱으로 표현된다는 것을 보이면 된다. (증명해보라)

자연수가 소수들의 곱으로 표현할 수는 있다해도 그 방법이 '유일할까' ? 여기서 '유일하다'는 말은 곱셈의 순서와 상관없이 나타나는 소수들과 그 나타나는 횟수가 모두 같을까? 하는 뜻이다. 예를들어

$12=2\cdot 2\cdot 3=3\cdot 2\cdot 2=2\cdot 3\cdot 2$

처럼 여러 방식이 있지만, 순서를 무시하고, 참여하는 소수들이 무엇이고 몇 번씩 나왔는지로 기준을 정해보면 표현법은 유일하다. 그런데 이 정리는 너무 뻔한 것 아닌가? 12, 18, 100, 1000, 어떤 예를 들어보라 항상 유일하게 표현되는데 뭐 이런 뻔해 보이는 사실까지 증명할 필요가 있을까?

산술의 기본 정리는 당연한가?

그렇다. '1보다 큰 모든 자연수는 소수들의 곱으로 유일한 방법으로 나타낼 수 있다' 는 문장은 어찌보면 너무나 명확해서 증명이 불필요한 것처럼 보일 수 있다. 그런데 갑자기 유일하게 표현할 수 없는 자연수가 어딘가에 숨어있으리라고 확신할 수 있나? 모든 자연수에 대하여 이 성질이 적용되지 않는다면 자연수 세계에 대한 탐구는 지금보다 몇 백배 몇 천 배 어려워졌을 것이다. 하기야 오죽했으면 이 정리를 자연수 산술의 가장 기본이 되는(fundamental) 정리라고 불렀을까?

실제로 고대이후 근대에 이르기까지 이것에 대하여 의심을 한 기록은 발견되지 않았다. 모두들 당연한 것으로 썼고 수학을 건축하는데 아무런 문제가 없었다. 르장드르 같은 특급 수학자도 특별히 주목하지 않았다. 이에 의문을 제기한 첫 사람은 아마도 가우스일 것이다. 가우스는 이 '당연해 보이는 것'을 당연한 것으로 받아들이지 않았다. 가우스가 그렇게 의심한 데에는 여러가지 이유가 있었을 것이다. 의심할 만한 것을 다 물리치고 엄격한 논리적 기초를 다져야 한다는 수학 특유의 강박관념이라고만 할 수는 없다. 아래서 '왜 산술의 기본정리'는 당연하지 않아 보이는지 살피고 그 정리의 증명을 함께 볼 것이다.

큰 자연수를 나눌 때

우리는 초등학교부터 했던 소인수분해라는 것을 배워오고 있다. 어떤 수를 소수들로 쪼개 본다는 말이다. 어떤 자연수를 소수의 곱으로 될 때까지 나눗셈해가는 과정이다. 예를 들어, 420을 소인수분해.

$420=2\cdot 210=2\cdot 3\cdot 70=2\cdot 3\cdot 5\cdot 14=2\cdot 3\cdot 5\cdot 2\cdot 7$

$420=7\cdot 60=7\cdot 5\cdot 12=7\cdot 5\cdot 3\cdot 4=7\cdot 5\cdot 3\cdot 2\cdot 2$

이고, 다른 순서로 나누기 시작하더라도, 420은 결국 $2\cdot 2\cdot 3\cdot 5\cdot 7$으로, 순서를 고려하지 않을 경우, 단 하나의 소수들의 곱으로 나타낼 수 있다.

수를 조금만 키워보자. 예를 들어 740037721. 이 수는 어떤 수들의 곱으로 나타낼 수 있을까? 직접 시도해보라. 재수 좋으면 앉은 자리에서 바로 답을 낼 수도 있지만, 재수없으면 다른 문제를 안 풀고 한달을 꼬박들여 풀어도 못 풀 수 있다. 주어진 수가 커질수록 어떤 수를 나누어간다 것은 아주 어려워진다는 것에 대해서는 이미 여러번 말해왔다. 이 수가 소수일까 아닐까 아는 것 자체가 쉬운 일이 아니므로 한 단계만 도움을 받도록하자. 그 수는 아래와같이 두 자연수의 곱으로 표현할 수 있다.

$740037721=23623\cdot 31327$

이렇게 큰 수가 단 두 자연수의 곱으로 표현되었다. 하지만 이 수가 $23623\cdot 31327$가 아닌 다른 수들의 곱으로 나타낼 수 없다는 것을 확신할 수 있나 ?

예 하나 더. 자연수 45910043909 은 다음과 같이 두 개의 방식으로 나타낼 수 있다.

$45910043909=308911\cdot 148619=256379\cdot 179071$

자연수 45910043909는 $308911\cdot 148619$과 $256379\cdot 179071$의 두 방법으로 표현될 수 있다는 것을 뜻하는가?

위의 예들을 보면 자연스럽게 우리는 이런 질문을 던지게 된다. 어떤 자연수를 소수들의 곱으로 나타내는 방법은 정말로 유일할까? . 위의 예

$45910043909=331\cdot 449\cdot 541\cdot 571$

는 사실, 네 소수로 구성된 것이다. 곧 나눌 수 있는 소수를 찾아가면 결국 위의 수는 네 소수의 곱으로 표현하게 되고 그 방법은 유일하게 하나다. 그러나 위의 예보다 훨씬 큰 수를 생각해서 그 수도 과연 소수들의 곱으로 나타내는 방법이 딱 하나 말고는 없다는 것을 알아보는 것은 지구에 존재하는 가장 강력한 슈퍼컴퓨터로 지구가 존재해온 시간만큼 풀어도 불가능할 수 있다. 실제로 주어진 자연수를 나누는 소수를 찾아 곱으로 나타내는 인수분해의 문제는 알고리듬 중 가장 계산이 복잡한 것으로 알려져있다. 이런 이유로 소수로 나타내는 문제는 암호론에 중요한 주제가 되기도 한다. 가능한 빨리 찾을 수 있는 많은 알고리듬들이 개발되고 있다. 이렇게 더 좋은 알고리듬을 찾고 있는 것은 나눌 수 있는 방법이 결국은 하나 뿐이라는 것이 수학적으로 증명되었기 때문에 가능하다. (사실 과학과 문명 발전에 수학이 해줘야 하는 일이 참 많다.)

모든 자연수가 아닐 때

단지 어렵다는 것이 문제가 아니다. 더 근본적으로 의심을 일으키는 이유들이 있다. 자연수 전체가 아니라, 짝수들만 떼어 놓고 본다고 하자. 이렇게...

2, 4, 6, 8, 10, 12, 14, ...

이 수들만 따로 떼어서 그게 해당하는 관계와 연산을 보면, 그것들이 이루는 세계는 '짝수들의 산술체계' 라고 불러도 좋을 것이다. 짝수들의 산술체계에서는 '기본정리'가 통할까. 우선 이 수세계의 소수 또는 기초수 같은 역할을 할 수 있는 수는 어떤 것일까? 다른 짝수는 나누면서 더 작은 짝수로 나뉘지 않은 수일 것이다. 그렇다면

2, 6, 10, 14, 18, ...

들이 짝수들의 소수라고 보는 것은 합리적이다. 4 는 2와 2의 곱으로, 12 는 2와 6의 곱으로, 24는 2와 2와 6의 곱으로, 유일한 방법으로 쪼개진다. 짝수들의 산술 체계도 '기본정리'가 통하겠지 짐작하기 쉽다.

(가설 : 짝수 산술의 기본정리) : 2 보다 큰 모든 짝수를 짝수-소수들만의 곱으로 나타내는 방법은 하나 밖에 없다.

그런데 이제 60 을 곱으로 나타내보자.

$60=2\cdot 30=6\cdot 10$

이다. 두 가지 방식으로 쪼개진 것이다 ! 반례(conterexample) 가 등장했다. 짝수 산술의 기본정리는 참이 아니다.

자연수보다 넓은 수개념에서

자연수보다 넓은 의미의 수개념, 그래서 자연수보다 복잡한 성격을 갖는 수 집합, 예를들어 '정수인 대수적 수'의 세계와 그 '나눗셈의 기초법칙' 을 연구하는데 있어 전혀 다른 성격을 갖게 되는 경우가 발견되었다. 다시 말해 '기초원소로 나뉘는데' '유일하게는 나뉘지 않는' 수의 영역들이 발견된 것이다. 이는 수학을 총체적인 세계로 인식하는 데 있어서 매우 중요한 문제가 된다. 이에 대해서는 따로 알아보기로 한다. 자연수(정수) 전체가 아닌 짝수 같은 부분들이나 자연수보다 넓은 수의 세계에서는 이 법칙이 통하지 않는다는 것으로부터 그렇다면 자연수들 전체에 대해서는 꼭 이 법칙이 통할까. 여기서는 그 물음표를 하나 던진 것으로 충분하다.

산술의 기본 정리 증명

자연수의 세계 전체로 과연 '기본정리'라는 성질이 관통할까? 증명의 방법은 여러가지다. 주춧돌 역할을 하기 때문에 그만큼 조심스럽게 다가가면서 의심할만한 것들은 다 쳐내기로 하자.

산술의 기본정리 : 1보다 큰 모든 자연수를 소수들만의 곱으로 나타내는 방법은 하나 밖에 없다.

다시 말해, 1보다 큰 자연수 n 에 대해

$n=p_{1}\cdot p_{2}\cdots p_{r}$

이 되는 소수들의 모임 $\{p_{1},p_{2},\dots ,p_{r}\}$ 은 유일하다 : 여기서 두 소수 $p_{i},p_{j}$는 같을 수 있다. n 이라는 연극을 올리는 데, 먼저 나오든, 나중에 나오든 상관않고, 등장 인물이나 등장 횟수는 같다는 말이다.

증명

원칙적으로 '유일하게 존재함'을 보일 때 증명은 보통 두 가지 사실을 증명한다.

• 존재한다를 보이고
• 두개 이상이 될 수 없음, 즉, 유일성을 보인다.

첫번째 항목은 이글을 읽는 이들에게 선물로 남긴다. 바로 두번째 항목으로 넘어가도록 하자.

산술의 기본정리 : 증명 하나

산술의 기본정리 : 증명 둘

두 증명은 사실 본질적으로는 같다. 두 증명 모두

• 유일하게 존재한다는 것을 부정해본다.
• 그랬을 때 모순이 나올 수 밖에 없다는 것을 보여서 유일하게 존재하지 않으면 안된다. 라고 보이는 방식이다.

다만, 증명 1 에서는 최소원소의 원칙을 썼고, 두번째 증명은 두 표현법에서 같은 것이 있다면 계속 덜어낸다라는 방식을 썼다. 두 증명에서 모두 한가지 사실은 슬쩍 넘어갔다. 그 부분에 의심이 든 사람이라면 아래에서 의심의 거미줄을 걷어낼 수 있다. 증명에서 들었던 의심의 실타래를 풀어가보자. 아래의 증명은 교과서적인 풀이다. 이 증명 방법은 어쩌면 복잡해보일지 모르지만, 앞으로 대수로 확장해서 방정식에 대해서도 폭넓게 응용할 수 있는 증명이니 익혀두는 게 좋다. 하지만, 더 읽어가기 가기 전에 나름대의 방식으로 증명을 시도해보길 바란다.

두 증명에서 슬쩍 넘긴 부분은 정수 전체에 산술의 기본정리를 보이기 위해서도 꼭 확인해야 할 부분이다. 아래 두 사실을 확인해서 그 빈틈을 메울 수 있다.

기초 정리1 : 소수 p가 두 수의 곱 ab를 나누면 p는 a를 나누거나 b를 나눈다.

라는 사실이다. 이로부터 수학적 귀납법을 이용하여 다음을 증명할 수 있고 이것은 산술의 기본정리를 증명하는데 핵심적인 역할을 한다.

기초 정리2 : 소수 p가 어떤 수들의 곱인 수 $a_{1}a_{2}a_{3}\cdots a_{n}$를 나누면 p는 $a_{i}$ 중 하나를 나눈다. (i는 1부터 n사이의 자연수)

정수세계까지 확장해서 일반적으로 보기로 한다. 이 사실을 증명하기 위하여 먼저 아래의 사실에 주목할 필요가 있다.

기초 정리0 : (a, b) = 1 이면 ay - bx = 1 이 참이게 하는 정수 x, y 를 항상 찾을 수 있다

여기서 (a,b)=1 이라는 말은 두 정수의 최대 공약수가 1 이라는 말로, a 와 b 가 서로 나뉨관계에 있지 않다는 말이다. '서로 소' 라고 부르기도 한다. 스스로 기초정리 0 을 증명하고, 다음 기초정리 1을, 그리고 기초정리 2를 증명해보라. 그리고 아래와 비교해보라.

기초 정리들의 증명

기초정리 0 에 대한 추가 설명

기초정리 0 의 기하학적인 설명

증명이라기 보다 기초정리 0 을 기하학적으로 이해하기 위한 설명이다. 다음의 집합을 보자.

$\{(x,y)\ |0\leq x\geq a\ ,\ 0\leq ay-bx\leq a\ \}$

이 점들의 집합을 좌표로 표시하면 중점을 지나는 ay - bx = 0 이라는 직선과 ay - bx = a 라는 직선의 '사이'의 점들의 집합이다. 이는 x 가 1, 2, 3, ... , a - 1 일 때마다 하나씩 (x,y) 의 해를 갖는다. 따라서 이 '사이' 에는 a - 1 개의 정수해가 있다. ('보완 필요')

기초정리 0 의 다른 표현

기초 정리0 은 다음과 같이 바꾸어 쓸 수 있다.

(a,b) =1 이고 $a|b\cdot c$ 이면 $a|c$

또는

(a,b) =1 이고 $ax=by$ 이면 x = at 이고 y = bt 인 t 가 존재한다.

마지막 부분은 좌표에 정수로 만나는 점으로 나타낼 수도 있다. 먼저 예를들면, 3y = 2x 라면 x = 3t 이고 y = 2t 인 정수 t 들이 존재한다. 그럴 때 ... , (-3, -2), (0,0) , (3,2) (6,4), ... 같은 점들은 정수의 교차점들을 뜻한다. 다시 말해, 정수마다 줄들이 그어진 모눈 종이 위에 적당히 좌표축을 표시했을때 3y - 2x = 0 의 직선이 모눈종이의 만나는 점들을 말하게 된다. 따라서, 예를들어, 28 y - 20 x = 22 라는 직선은 정수근을 가질까 ? 하는 문제에 대해 우리는 '정수론적으로' 금방 해결할 수 있다. 4는 28과 20 을 나누지만 22를 나누지는 않기 때문이다. 그에 비해 28 y - 20 x = 12 라면 무한개의 정수근을 갖는다.

$28y-20x=22\Leftrightarrow 7y-5x=3$ 이고 이때 한 근은 (5,4) 일 때다. 따라서 (5+7t, 4+5t)는 모든 정수근을 나타낸다. 이에 대해서는 유클리드 알고리듬의 응용 부분이나 최대공약수의 응용 부분을 참고하라.

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

Note

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