PROOF 185
증명하라.
약수의 개수가 홀수면 제곱수다
자연수 ℕ 위에서.
한 줄씩, 이유를 따라가 봅시다
먼저 이미 주어진 것과 앞으로 보여야 할 것을 나누어 읽어 보세요. 다음 줄로 넘어갈 때마다 어떤 정의나 앞의 결과를 사용했는지 묻습니다. 연결이 보이지 않으면 결론을 외우기보다 그 전제로 잠시 돌아가도 좋습니다.
정의 D1
자연수 d 가 n 의 약수라는 것은 n = d · e 인 자연수 e 가 있다는 뜻이며, 이를 d ∣ n 으로 적는다.
증명.
n = d·e = e·d 이므로 e 도 n 의 약수다.약속, A1
∎
정의 D2
D(n) = { d : d ∣ n } 이라 하고, 그 원소의 개수를 d(n) 이라 한다.
증명.
(1)d ∈ D(n) 이면 n = d·e 이고 e ≥ 1 이므로 n = d·e ≥ d 이다.D1, O1, O2
(2)약수는 모두 n 이하이므로 D(n) 은 유한집합이다.(1)
∎
보조정리 L1
각 d ∈ D(n) 에 대하여 n = d · x 인 자연수 x 는 하나뿐이다. 그 x 를 φ(d) 라 하면 φ 는 D(n) 을 D(n) 으로 옮기고 φ(φ(d)) = d 이다.
증명.
(1)d ∈ D(n) 이면 n = d·e 인 자연수 e 가 있다.D1
(2)d 는 자연수이므로 d ≥ 1 이고 d ≠ 0O1
(3)d·e = d·e′ 이면 d ≠ 0 이므로 e = e′ 다. 그러한 e 는 하나뿐이다.(1), (2), A1, A2
(4)그 e 를 φ(d) 라 쓴다.(3), 약속
(5)n = d·φ(d) = φ(d)·d 이므로 φ(d) ∈ D(n)(4), A1, D1
(6)φ(φ(d)) 는 n = φ(d)·x 인 유일한 x 이고, n = φ(d)·d 이므로 φ(φ(d)) = d(3), (5)
∎
보조정리 L2
d ∈ D(n) 에 대하여 φ(d) = d 인 것과 d · d = n 인 것은 같다.
증명.
(1)φ(d) 는 n = d·φ(d) 를 만족한다.L1
(2)φ(d) = d 이면 n = d·d(1), E
(3)거꾸로 n = d·d 이면 d ∈ D(n) 이고, φ(d) 는 n = d·x 인 유일한 x 이므로 φ(d) = dD1, L1
∎
보조정리 L3
F = { d ∈ D(n) : φ(d) = d } 라 하고 R = D(n) ∖ F 라 하면, |R| 은 짝수다.
증명.
(1)F 와 R 은 D(n) 을 남김없이 둘로 나눈다.약속, D2
(2)d ∈ R 이면 φ(d) ∈ R 이다. φ(d) 가 고정점이면 φ(φ(d)) = φ(d) 이고, φ(φ(d)) = d 이므로 φ(d) = d 가 되어 d ∈ R 에 모순이다.(1), L1
(3)R 에서 d ~ d′ 를 「d′ = d 또는 d′ = φ(d)」로 정하면, φ(φ(d)) = d 이므로 이 관계는 반사·대칭·추이적이다.(2), L1, E
(4)그러므로 R 은 이 관계의 조각들로 분할된다.(3), A4
(5)각 조각은 { d, φ(d) } 이고 d ∈ R 이므로 φ(d) ≠ d 다. 조각의 원소는 2 개다.(1), (3), (4)
(6)조각이 k 개라 하면 |R| = 2k(5), A5
(7)그러므로 |R| 은 짝수다.(6), A7
∎
보조정리 L4
F 의 원소는 많아야 하나다.
증명.
(1)d, d′ ∈ F 라 하자.가정
(2)d·d = n 이고 d′·d′ = n 이므로 d·d = d′·d′(1), L2, E
(3)제곱이 같은 자연수는 같으므로 d = d′(2), A3
∎
정리 T1
d(n) 이 홀수이면 n 은 제곱수다.
증명.
(1)d(n) 이 홀수라 하자.가정
(2)d(n) = |F| + |R|D2, L3, A6
(3)|R| 은 짝수다.L3
(4)짝수를 더해도 홀짝은 그대로이므로 |F| 는 홀수다.(1), (2), (3), A8
(5)0 은 짝수이므로 |F| ≠ 0 이고, F 에는 원소가 있다.(4), A7, A9
(6)d ∈ F 이면 d·d = n 이므로 n 은 제곱수다.(5), L2
∎
정리 T2
n 이 제곱수이면 d(n) 은 홀수다.
증명.
(1)n = d·d 인 자연수 d 가 있다고 하자.가정
(2)그러면 φ(d) = d 이므로 d ∈ F(1), L2
(3)F 의 원소는 많아야 하나이므로 |F| = 1(2), L4
(4)d(n) = |F| + |R| = 1 + |R| 이고 |R| 은 짝수다.(3), L3, A6
(5)그러므로 d(n) 은 홀수다.(4), A8, A7
∎
비고
A3 은 이 증명에서 제거할 수 있는가.
제곱근이 하나뿐이라는 것은 어느 방향에 필요한지 확인하라.