PROOF 11
증명하라.
소수는 무한히 많다
자연수 ℕ 위에서.
한 줄씩, 이유를 따라가 봅시다
먼저 이미 주어진 것과 앞으로 보여야 할 것을 나누어 읽어 보세요. 다음 줄로 넘어갈 때마다 어떤 정의나 앞의 결과를 사용했는지 묻습니다. 연결이 보이지 않으면 결론을 외우기보다 그 전제로 잠시 돌아가도 좋습니다.
정의 D1
b | a 는 a = bk 인 자연수 k 가 존재함을 뜻한다.
증명.
b 가 a 의 약수라는 말을 곱셈 하나로 옮긴 것이다.약속
∎
정의 D2
p 가 소수라는 것은 p > 1 이고 p 의 약수가 1 과 p 뿐임을 뜻한다.
증명.
조건은 둘이다. 1 보다 크다는 것, 약수가 그 둘뿐이라는 것.약속
∎
보조정리 L1
p | a 이고 a | m 이면 p | m
증명.
(1)a = pk 이고 m = al 인 k, l 이 있다.가정, D1
(2)m = (pk)l(1), E
(3) = p(kl)A4
(4)그러므로 p | m 이다.(3), D1
∎
보조정리 L2
1 보다 큰 모든 자연수는 소수인 약수를 갖는다.
증명.
(1)소인수를 갖지 않는, 1 보다 큰 자연수 전체를 S 라 하자.약속
(2)S ≠ ∅ 라 하자.가정
(3)S 에 최소원 m 이 있다.A2
(4)m = m × 1 이므로 m | m 이다.A6, D1
(5)m 이 소수라면 (4)에 의해 m 이 m 의 소인수이므로 m ∉ S 이다.D2, (4), (1)
(6)그러므로 m 은 소수가 아니고, 1 도 m 도 아닌 약수 a 를 갖는다.D2, (5)
(7)m = ak 인 k 가 있고, a ≠ m 이므로 k ≠ 1 이다.(6), D1, A6
(8)1 ≤ k 이므로 1 < k 이고, a = a × 1 ≤ ak = m 이다.(7), A1, A6, A7
(9)a 는 1 도 m 도 아니므로 1 < a < m 이다.(6), (8), A1
(10)m 은 S 의 최소원이므로 a ∉ S 이다. 즉 a 는 소인수 p 를 갖는다.(3), (9), (1)
(11)p | a 이고 a | m 이므로 p | m 이다.(10), L1
(12)m 이 소인수를 가지므로 m ∉ S 이다. 이는 (3)에 모순이다.(11), (1)
(13)그러므로 S = ∅ 이다.(12)
∎
정리 T
소수는 무한히 많다.
증명.
(1)소수가 유한하다고 하고, 그 전부를 p₁, p₂, …, pₙ 이라 하자.가정
(2)P = p₁p₂⋯pₙ 로 두고, N = P + 1 로 둔다.약속
(3)각 i 에 대하여 P 는 pᵢ 와 나머지 소수들의 곱으로 묶인다.A4, A5
(4)그러므로 P = pᵢ t 인 t 가 있고, pᵢ | P 이다.(3), D1
(5)N = pᵢ t + 1 이고, pᵢ > 1 이므로 0 ≤ 1 < pᵢ 이다.(2), (4), D2
(6)몫과 나머지는 유일하므로, N 을 pᵢ 로 나눈 나머지는 1 이다.A3, (5)
(7)pᵢ | N 이라면 N = pᵢ s + 0 이므로 나머지는 0 이다.D1, A3
(8)1 ≠ 0 이므로 어떤 pᵢ 도 N 을 나누지 못한다.(6), (7)
(9)1 ≤ P 이므로 N = P + 1 > 1 이다.A1, (2)
(10)그러므로 N 은 소인수 q 를 갖는다.(9), L2
(11)q | N 이므로 (8)에 의해 q 는 어떤 pᵢ 와도 같지 않다.(10), (8)
(12)q 는 (1)의 목록에 없는 소수다. 이는 (1)에 모순이다.(11), (1)
(13)그러므로 소수는 유한하지 않다.(12)
∎
비고
A2 는 이 증명에서 제거할 수 있는가.
정렬성은 세지 않고도 최소원의 존재를 준다. 제거하면 어느 줄이 근거를 잃는지 확인하라.