- 관련 항목 : 수학 관련 정보
Fundamental Theorem of Arithmetic
1 개요
1보다 큰 모든 정수 n은 n=p1e1p2e2⋯pnen로 (순서가 바뀐 것을 제외하고) 유일하게 나타낼 수 있다. 단, 여기서 ei≥0이고, pi는 서로 다른 소수이다.
우리가 소인수분해를 당연하게 여길 수 있게 만들어 주는 정리. 이름이 비슷한 대수학의 기본정리는 듣기만 해도 정신이 날아갈 듯한 증명을 사용하지만, 이 산술의 기본정리는 좀 아주 많이 똑똑한초등학생도 증명을 할 수 있다. 증명은 존재성과 유일성, 두 파트로 나뉜다.
2 증명
정수는 UFD이므로 자명하다.
2.1 존재성
1보다 큰 임의의 양의 정수 n의 두번째로 작은 약수는 소수여야 한다.[1] 만약 m이 n의 두번째로 작은 약수인데 합성수라면, 합성수의 정의에 의해 l∣m,1\ltl\ltm인 자연수 l이 존재한다. 그런데 m∣n이므로 l∣n이고, 이는 m이 두번째로 작은 약수라는 정의에 모순된다. 따라서 m은 소수이다. 따라서, n=p1n1로 표현할 수 있고 (p1=m), n1이 소수라면 증명은 끝. 소수가 아니라면 위 과정을 계속 반복하여 n을 소수의 곱으로만 표현할 수 있다. 즉, 1보다 큰 임의의 양의 정수 n의 소인수분해가 존재한다.
2.2 유일성
- 증명 1
- 귀류법을 사용해 증명한다. 집합 A를 A={x∈ℕ|x>1,x의 소인수분해는 유일하지 않음}로 정의하자. 자연수의 well-ordering 성질에 의해 집합 A에는 가장 작은 원소가 존재한다.[2] 이를 n라 하자. 그럼, p1≤p2≤⋯≤pk,q1≤q2≤⋯≤ql을 만족하는 소수 p1,p2,⋯,pk,q1,q2,⋯,ql에 대해 n=p1p2⋯pk=q1q2⋯ql이 성립한다. 여기서 만약 어떤 i,j에 대해 pi=qj이면, n/pi도 소인수분해가 유일하지 않고, n\gtn/pi이므로 n이 A의 가장 작은 원소라는 사실에 모순된다. 즉, pi≠qj. 한편, p12≤n,q12≤n이고 p12와 q12은 동시에 n이 될 수 없으므로 [3], 0\ltp1q1\ltn이다. 이제 N=n−p1q1이라 정의하자. 0\ltN\ltn이고 p1∣N,q1∣N이므로, 1\ltN\ltn이 성립하고, N은 유일한 소인수분해를 가진다.[4] 또한 N의 유일한 소인수분해에는 p1과 q1이 둘 다 들어간다. 따라서 적당한 양의 정수 M에 대해 N=p1q1M. 이제 n=N+p1q1=p1q1(M+1)이고, 양변을 p1로 나누면 n/p1=q1(M+1). 곧, p2p3⋯pk=q1(M+1)이다. 여기서 q1≠pi이므로 n/p1는 유일하지 않은 소인수분해를 가진다.[5] 또한 1\ltn/p1이므로 n/p1∈A이고, 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의 배수이다.
- (1-1) 임의의 자연수 x, y에 대해 m이 x와 y의 최소공배수라고 하자. x, y의 모든 공배수는 m의 최소공배수이다.
- (2) A=pe11pe22pe33...=pf11pf22pf33... 라 하자. pi는 소수이며 ei나 fi는 0 이상의 정수이다. 그러면 모든 i에 대하여 ei=fi 이다.
- (2-1) 임의의 자연수 a1,a2,...,an에 대하여 a1a2...an 가 소수 p로 나누어지면 a1,a2,...,an 중 적어도 하나는 p로 나누어진다.
- 증명: a1(a2...an)가 p로 나누어지므로 a1과 a2...an 중 하나는 p로 나누어자는 것을 이용해서 증명한다.
- 단계 (2)의 증명: 어떤 i에 대하여 ei≠fi 라 하자. 일반성을 잃지 않고 ei>fi라 할 수 있다. 그러면 pe11...pei−1i−1pei−fiipei+1i+1...=pf11...pfi−1i−1pfi+1i+1... 이므로 pf11...pfi−1i−1pfi+1i+1...는 pi의 배수이다. 그러므로 (2-1)에 따라 pi가 pf11,...pfi−1i−1,pfi+1i+1,... 중 하나를 나누어야 한다. pi가 pfjj를 나누는 것은 fj가 0일 때는 불가능하며 fj≥1이면 (2-1)에 따라 pi 가 pj을 나누어야 하므로 역시 모순이다.
- (2-1) 임의의 자연수 a1,a2,...,an에 대하여 a1a2...an 가 소수 p로 나누어지면 a1,a2,...,an 중 적어도 하나는 p로 나누어진다.