PROOF 12
증명하라.
소인수분해는 하나뿐이다
자연수 ℕ 위에서.
한 줄씩, 이유를 따라가 봅시다
먼저 이미 주어진 것과 앞으로 보여야 할 것을 나누어 읽어 보세요. 다음 줄로 넘어갈 때마다 어떤 정의나 앞의 결과를 사용했는지 묻습니다. 연결이 보이지 않으면 결론을 외우기보다 그 전제로 잠시 돌아가도 좋습니다.
정의 D1
b | a 는 a = bk 인 자연수 k 가 존재함을 뜻한다.
증명.
약수를 곱셈 하나로 옮긴 것이다.약속
∎
정의 D2
p 가 소수라는 것은 p > 1 이고 p 의 약수가 1 과 p 뿐임을 뜻한다.
증명.
1 은 이 정의에서 빠진다. p > 1 이 요구되기 때문이다.약속
∎
보조정리 L1
p 가 소수이고 p | ab 이면, p | a 또는 p | b 이다.
증명.
(1)p ∤ a 라 하자. p | b 임을 보인다.가정
(2)p 의 약수는 1 과 p 뿐이므로 gcd(p, a) 는 1 또는 p 이다.D2, D1
(3)gcd(p, a) = p 이면 p | a 이므로, gcd(p, a) = 1 이다.(1), (2), D1
(4)1 = px + ay 인 정수 x, y 가 있다.A3, (3)
(5)b = b × 1 = (px + ay)bA6, E, (4)
(6) = (bp)x + (ab)yA7, A4, A5
(7)(bp)x = p(bx) 이므로 p | (bp)x 이다.A4, A5, D1
(8)ab = pc 라 하면 (ab)y = p(cy) 이므로 p | (ab)y 이다.가정, D1, A4
(9)b = p(bx) + p(cy) = p(bx + cy)(6), (7), (8), A7
(10)그러므로 p | b 이다.(9), D1
∎
정리 T1
1 보다 큰 모든 자연수는 소수들의 곱이다.
증명.
(1)소수들의 곱으로 쓸 수 없는, 1 보다 큰 자연수 전체를 S 라 하자.약속
(2)S ≠ ∅ 라 하자.가정
(3)S 에 최소원 m 이 있다.A2
(4)m 이 소수이면 m 은 소수 하나의 곱이므로 m ∉ S 이다.D2, (1)
(5)그러므로 m 은 소수가 아니고, m = ab 이며 a 는 1 도 m 도 아니다.D2, D1, (4)
(6)b = 1 이면 m = a 이므로 b ≠ 1 이다.A6, (5)
(7)1 < a 이고 1 < b 이므로 a < ab = m 이고 b < m 이다.A1, A6, A8, (5), (6)
(8)a 와 b 는 1 보다 크고 m 보다 작으므로 S 에 속하지 않는다.(3), (7)
(9)그러므로 a 와 b 는 각각 소수들의 곱이다.(8), (1)
(10)m = ab 도 소수들의 곱이다. 이는 (3)에 모순이다.(9), (5), (1)
(11)그러므로 S = ∅ 이다.(10)
∎
정리 T2
그 곱은 순서를 빼면 하나뿐이다.
증명.
(1)소수들의 곱으로 두 가지로 쓰이는, 1 보다 큰 자연수 전체를 S 라 하자.약속
(2)S ≠ ∅ 라 하고, 최소원을 m 이라 하자.가정, A2
(3)m = p₁p₂⋯p_r = q₁q₂⋯q_s 라 하자.(1)
(4)p₁ | q₁q₂⋯q_s 이다.(3), A4, A5, D1
(5)L1 을 되풀이 쓰면 어떤 j 에 대하여 p₁ | q_j 이다.L1, (4)
(6)q_j 는 소수이고 p₁ > 1 이므로 p₁ = q_j 이다.D2, (5)
(7)p₁ > 1 이므로 양변에서 p₁ 을 지우면 p₂⋯p_r 과 q_j 를 뺀 곱이 같다.(3), (6), A4, A5, A9
(8)그 값이 1 이면 양변에 소수가 남지 않으므로, 두 표현은 모두 p₁ 하나다.(7), (6)
(9)그 값이 1 보다 크면 m 보다 작으므로 S 에 속하지 않는다.(7), (2), A1, A6, A8
(10)그러므로 (7)의 두 표현은 순서를 빼면 같다.(9), (1)
(11)p₁ = q_j 를 되돌리면 m 의 두 표현도 순서를 빼면 같다.(10), (6)
(12)이는 m ∈ S 에 모순이다. 그러므로 S = ∅ 이다.(11), (1)
∎
비고
A3 은 이 증명에서 제거할 수 있는가.
유일성은 유클리드 보조정리에 걸려 있고, 그 보조정리는 A3 하나에서 나온다. 제거하면 어디까지 남는지 확인하라.