PROOF 87
증명하라.
합성수는 √n 이하의 소인수를 갖는다
자연수 ℕ 위에서.
한 줄씩, 이유를 따라가 봅시다
먼저 이미 주어진 것과 앞으로 보여야 할 것을 나누어 읽어 보세요. 다음 줄로 넘어갈 때마다 어떤 정의나 앞의 결과를 사용했는지 묻습니다. 연결이 보이지 않으면 결론을 외우기보다 그 전제로 잠시 돌아가도 좋습니다.
정의 D1
b | a 는 a = bk 인 자연수 k 가 존재함을 뜻한다.
증명.
b 가 a 의 약수라는 말을 곱셈 하나로 옮긴 것이다.약속
∎
정의 D2
p 가 소수라는 것은 p > 1 이고 p 의 약수가 1 과 p 뿐임을 뜻한다.
증명.
조건은 둘이다. 1 보다 크다는 것, 약수가 그 둘뿐이라는 것.약속
∎
정의 D3
n 이 합성수라는 것은 n > 1 이고 n 이 소수가 아님을 뜻한다.
증명.
1 은 합성수가 아니다. 1 보다 크다는 조건이 그것을 막는다.약속, D2
∎
정의 D4
√n 은 x × x = n 을 만족하는 음이 아닌 x 이며, 자연수 p 에 대하여 p ≤ √n 과 p × p ≤ n 은 같은 조건이다.
증명.
이하에서는 근호 없이 p × p ≤ n 으로 쓴다.약속
∎
보조정리 L1
n 이 합성수이면 n = ab 이고 1 < a ≤ b 인 자연수 a, b 가 있다.
증명.
(1)n 은 1 보다 크고 소수가 아니다.가정, D3
(2)1 도 n 도 아닌 약수 c 가 있다.(1), D2
(3)n = cd 인 d 가 있다.(2), D1
(4)1 ≤ c 이고 c ≠ 1 이므로 1 < c 이다.(2), A1, A4
(5)d = 1 이면 n = c × 1 = c 이므로 c ≠ n 에 어긋난다.(2), (3), A8
(6)1 ≤ d 이고 d ≠ 1 이므로 1 < d 이다.(5), A1, A4
(7)c ≤ d 이면 a = c, b = d 로, 그렇지 않으면 a = d, b = c 로 둔다.A3, A4
(8)어느 경우에나 n = ab 이고 1 < a ≤ b 이다.(3), (4), (6), (7), A6
∎
보조정리 L2
p 가 a 의 약수이면 p ≤ a
증명.
(1)a = pk 인 k 가 있다.가정, D1
(2)1 ≤ kA1
(3)1 × p ≤ k × p(2), A5
(4)1 × p = p 이고 k × p = pk = a(1), A6, A8
(5)그러므로 p ≤ a 이다.(3), (4), E
∎
정리 T
합성수 n 은 p × p ≤ n 인 소인수 p 를 갖는다.
증명.
(1)n = ab 이고 1 < a ≤ b 인 a, b 가 있다.L1
(2)n < a × a 라 하자.가정
(3)a ≤ b 이므로 a × a ≤ b × a 이다.(1), A5
(4)b × a = ab = n(1), A6
(5)그러므로 a × a ≤ n 이다.(3), (4), E
(6)n < a × a 와 a × a ≤ n 은 함께 설 수 없다.(2), (5), A4, A3
(7)그러므로 a × a ≤ n 이다.(6), A3, A4
(8)1 < a 이므로 a 는 소인수 p 를 갖는다.(1), A9
(9)p ≤ a(8), L2
(10)p × p ≤ a × p 이고 a × p = p × a ≤ a × a 이다.(9), A5, A6
(11)p × p ≤ a × a(10), A2
(12)p × p ≤ n(11), (7), A2
(13)a = pk 이고 n = ab = (pk)b = p(kb) 이므로 p | n 이다.(1), (8), D1, A7
(14)p 는 n 의 소인수이고 p × p ≤ n 이다.(12), (13), D2
∎
따름정리 C
n > 1 이고 p × p ≤ n 인 소수 p 가 모두 n 을 나누지 못하면 n 은 소수다.
증명.
(1)그러한 n 이 소수가 아니라고 하자.가정
(2)n 은 1 보다 크고 소수가 아니므로 합성수다.(1), D3
(3)n 은 p × p ≤ n 인 소인수 p 를 갖는다.(2), T
(4)이는 가정에 어긋난다.(1), (3)
(5)그러므로 n 은 소수다.(4), D2
(6)확인할 소수는 p × p ≤ n, 곧 p ≤ √n 인 것뿐이다.(5), D4
∎
비고
A5 는 이 증명에서 제거할 수 있는가.
합성수를 두 인수로 쪼개는 데까지는 순서가 필요 없다. 어디서부터 크기를 재기 시작하는지 확인하라.