Processing math: 100%

산술의 기본정리

Fundamental Theorem of Arithmetic

1 개요

1보다 큰 모든 정수 nn=p1e1p2e2pnen로 (순서가 바뀐 것을 제외하고) 유일하게 나타낼 수 있다. 단, 여기서 ei0이고, pi는 서로 다른 소수이다.

우리가 소인수분해를 당연하게 여길 수 있게 만들어 주는 정리. 이름이 비슷한 대수학의 기본정리는 듣기만 해도 정신이 날아갈 듯한 증명을 사용하지만, 이 산술의 기본정리는 좀 아주 많이 똑똑한초등학생도 증명을 할 수 있다. 증명은 존재성유일성, 두 파트로 나뉜다.

2 증명

정수는 UFD이므로 자명하다.

2.1 존재성

1보다 큰 임의의 양의 정수 n의 두번째로 작은 약수는 소수여야 한다.[1] 만약 mn의 두번째로 작은 약수인데 합성수라면, 합성수의 정의에 의해 lm,1\ltl\ltm인 자연수 l이 존재한다. 그런데 mn이므로 ln이고, 이는 m이 두번째로 작은 약수라는 정의에 모순된다. 따라서 m은 소수이다. 따라서, n=p1n1로 표현할 수 있고 (p1=m), n1이 소수라면 증명은 끝. 소수가 아니라면 위 과정을 계속 반복하여 n을 소수의 곱으로만 표현할 수 있다. 즉, 1보다 큰 임의의 양의 정수 n의 소인수분해가 존재한다.

2.2 유일성

  • 증명 1
귀류법을 사용해 증명한다. 집합 AA={x|x>1,x의 소인수분해는 유일하지 않음}로 정의하자. 자연수의 well-ordering 성질에 의해 집합 A에는 가장 작은 원소가 존재한다.[2] 이를 n라 하자. 그럼, p1p2pk,q1q2ql을 만족하는 소수 p1,p2,,pk,q1,q2,,ql에 대해 n=p1p2pk=q1q2ql이 성립한다. 여기서 만약 어떤 i,j에 대해 pi=qj이면, n/pi도 소인수분해가 유일하지 않고, n\gtn/pi이므로 nA의 가장 작은 원소라는 사실에 모순된다. 즉, piqj. 한편, p12n,q12n이고 p12q12은 동시에 n이 될 수 없으므로 [3], 0\ltp1q1\ltn이다. 이제 N=np1q1이라 정의하자. 0\ltN\ltn이고 p1N,q1N이므로, 1\ltN\ltn이 성립하고, N은 유일한 소인수분해를 가진다.[4] 또한 N의 유일한 소인수분해에는 p1q1이 둘 다 들어간다. 따라서 적당한 양의 정수 M에 대해 N=p1q1M. 이제 n=N+p1q1=p1q1(M+1)이고, 양변을 p1로 나누면 n/p1=q1(M+1). 곧, p2p3pk=q1(M+1)이다. 여기서 q1pi이므로 n/p1는 유일하지 않은 소인수분해를 가진다.[5] 또한 1\ltn/p1이므로 n/p1A이고, n/p1\ltn이므로 이는 n이 집합 A의 가장 작은 원소라는 사실에 모순된다. 따라서 1보다 큰 임의의 양의 정수의 소인수분해는 유일하다.

이게 어딜 봐서 초등학생도 할 수 있냐

  • 증명 2
여기서는 개요만 설명한다.
(1) 임의의 자연수 a, b에 대해 ab가 소수 p로 나누어지면 a, b중 적어도 하나는 p로 나누어진다.
(1-1) 임의의 자연수 x, y에 대해 m이 x와 y의 최소공배수라고 하자. x, y의 모든 공배수는 m의 최소공배수이다.
증명: x, y의 공배수 M 에 대해서 M - m, M - 2m, M - 3m, ... 의 수열을 생각하자. 이 수열에서 0보다 큰 마지막 원소가 m보다 작다면 이는 x와 y의 'm보다 작은' 공배수가 되므로 m이 최소공배수라는 것에 모순이다. 즉 마지막 원소는 항상 m이 되어야 하고, 따라서 M은 항상 m의 배수이다.
(1-2) 임의의 자연수 x, y에 대해 m이 x와 y의 최소공배수라고 하자. d=xy/m인 d는 자연수이며 x와 y 의 공약수이다.[6]
증명: xy는 x와 y의 공배수이므로 m의 배수이다. 따라서 d는 자연수이다. x=(m/y)d 인데 m은 y의 배수이므로 m/y는 자연수이다. 따라서 d는 x의 약수이며, 같은 이유로 y의 약수이다.
단계 (1)의 증명: ab 가 소수 p로 나누어진다고 하자. 이제 a와 p의 최소공배수를 A라고 하자. t=ap/A는 p의 약수이므로 1 또는 p이다. t = p인 경우에는 a = A이고 A는 p의 배수이므로 a가 p의 배수이다. t = 1인 경우, A=ap 이다. ab는 a와 p의 공배수이므로 A의 배수이다. ab=Ah 라고 하자. b=(A/a)h=ph 이므로 b가 p의 배수이다.
(2) A=pe11pe22pe33...=pf11pf22pf33... 라 하자. pi는 소수이며 eifi는 0 이상의 정수이다. 그러면 모든 i에 대하여 ei=fi 이다.
(2-1) 임의의 자연수 a1,a2,...,an에 대하여 a1a2...an 가 소수 p로 나누어지면 a1,a2,...,an 중 적어도 하나는 p로 나누어진다.
증명: a1(a2...an)p로 나누어지므로 a1a2...an 중 하나는 p로 나누어자는 것을 이용해서 증명한다.
단계 (2)의 증명: 어떤 i에 대하여 eifi 라 하자. 일반성을 잃지 않고 ei>fi라 할 수 있다. 그러면 pe11...pei1i1peifiipei+1i+1...=pf11...pfi1i1pfi+1i+1... 이므로 pf11...pfi1i1pfi+1i+1...pi의 배수이다. 그러므로 (2-1)에 따라 pipf11,...pfi1i1,pfi+1i+1,... 중 하나를 나누어야 한다. pipfjj를 나누는 것은 fj가 0일 때는 불가능하며 fj1이면 (2-1)에 따라 pipj을 나누어야 하므로 역시 모순이다.

3 여담

산술이란 명칭이 정수론 일반을 지칭하는 용례가 희미하진 현대에 와서는 '정수론의 기본정리'라고 하는 게 나을 것 같기도 하다.
  1. 이동 제일 작은 약수는 당연히 1이다.
  2. 이동 정확히는 A가 공집합이 아니어야 존재한다. 헌데 A가 공집합이면 1보다 큰 모든 정수의 소인수분해가 유일함을 의미하게 된다.
  3. 이동 만약 둘이 동시에 n이면 p1=q1이고, 이는 위의 piqj에 모순된다.
  4. 이동 유일하지 않으면 NA이고, 이는 nA의 가장 작은 원소라는 사실에 모순이다.
  5. 이동 M+1이 어떻게 소인수분해 되는가와는 상관없다.
  6. 이동 d는 바로 x와 y의 최대공약수이지만 이 증명에서는 최대공약수라는 점은 이용하지 않는다.