PROOF 82
증명하라.
gcd(a,b) × lcm(a,b) = ab
자연수 ℕ 위에서.
한 줄씩, 이유를 따라가 봅시다
먼저 이미 주어진 것과 앞으로 보여야 할 것을 나누어 읽어 보세요. 다음 줄로 넘어갈 때마다 어떤 정의나 앞의 결과를 사용했는지 묻습니다. 연결이 보이지 않으면 결론을 외우기보다 그 전제로 잠시 돌아가도 좋습니다.
정의 D1
d | a 는 a = dk 인 자연수 k 가 존재함을 뜻한다.
증명.
a 와 b 는 1 이상의 자연수로 두고, 1 은 지수가 모두 0 인 곱으로 본다.약속
∎
정의 D2
gcd(a, b) 는 공약수 가운데 가장 큰 것, lcm(a, b) 는 공배수 가운데 가장 작은 것이다.
증명.
가장 큰 공약수와 가장 작은 공배수가 실제로 있다는 것은 L3 과 L4 에서 보인다.약속
∎
정의 D3
min(x, y) 는 두 수 가운데 크지 않은 쪽, max(x, y) 는 작지 않은 쪽이다.
증명.
(1)A3 이 둘의 비교를 보장하므로 두 값은 언제나 정해진다.A3
(2)min ≤ x, min ≤ y, x ≤ max, y ≤ max 는 정의에서 곧바로 나온다.(1)
(3)z ≤ x 이고 z ≤ y 이면 z ≤ min 이고, x ≤ w 이고 y ≤ w 이면 max ≤ w(1)
∎
보조정리 L1
a = ∏ p^xₚ, d = ∏ p^zₚ 일 때, d | a 인 것과 모든 p 에서 zₚ ≤ xₚ 인 것은 같다.
증명.
(1)두 수의 소인수분해는 A1 이 하나로 정한다.A1
(2)모든 p 에서 zₚ ≤ xₚ 라 하자.가정
(3)zₚ + wₚ = xₚ 인 wₚ 가 있다.(2), A5
(4)k = ∏ p^wₚ 로 두면 dk = ∏ p^(zₚ+wₚ) = a(1), (3), A2, A7, A8, E
(5)그러므로 d | a(4), D1
(6)이제 d | a 라 하자.가정
(7)a = dk 인 k 가 있고 k = ∏ p^wₚ 로 쓸 수 있다.(6), D1, A1
(8)dk = ∏ p^(zₚ+wₚ)(7), A2, A7, A8
(9)소인수분해는 하나뿐이므로 xₚ = zₚ + wₚ(8), A1
(10)그러므로 zₚ ≤ xₚ(9), A5
∎
보조정리 L2
모든 x, y 에 대하여 min(x, y) + max(x, y) = x + y
증명.
(1)x ≤ y 또는 y ≤ x 이다.A3
(2)x ≤ y 이면 min = x, max = y 이므로 합은 x + y 이다.(1), D3
(3)y ≤ x 이면 min = y, max = x 이므로 합은 y + x 이다.(1), D3
(4)y + x = x + yA4
(5)두 경우 모두 합은 x + y 이다.(2), (3), (4)
∎
보조정리 L3
gcd(a, b) = ∏ p^min(xₚ, yₚ)
증명.
(1)g = ∏ p^min(xₚ, yₚ) 로 둔다.약속
(2)min ≤ xₚ 이고 min ≤ yₚ 이므로 g | a 이고 g | bD3, L1
(3)d = ∏ p^zₚ 가 공약수라 하자.가정, A1
(4)모든 p 에서 zₚ ≤ xₚ 이고 zₚ ≤ yₚ(3), L1
(5)zₚ ≤ min(xₚ, yₚ)(4), D3
(6)그러므로 d | g(5), L1
(7)g ≥ 1 이므로 d ≤ g(6), A6
(8)g 는 공약수이고 모든 공약수보다 작지 않다.(2), (7)
(9)그러므로 gcd(a, b) = g(8), D2
∎
보조정리 L4
lcm(a, b) = ∏ p^max(xₚ, yₚ)
증명.
(1)ℓ = ∏ p^max(xₚ, yₚ) 로 둔다.약속
(2)xₚ ≤ max 이고 yₚ ≤ max 이므로 a | ℓ 이고 b | ℓD3, L1
(3)m = ∏ p^wₚ 가 공배수라 하자.가정, A1
(4)모든 p 에서 xₚ ≤ wₚ 이고 yₚ ≤ wₚ(3), L1
(5)max(xₚ, yₚ) ≤ wₚ(4), D3
(6)그러므로 ℓ | m(5), L1
(7)m ≥ 1 이므로 ℓ ≤ m(6), A6
(8)ℓ 은 공배수이고 모든 공배수보다 크지 않다.(2), (7)
(9)그러므로 lcm(a, b) = ℓ(8), D2
∎
정리 T
gcd(a, b) × lcm(a, b) = ab
증명.
(1)gcd(a,b) × lcm(a,b) = (∏ p^min)(∏ p^max)L3, L4, E
(2) = ∏ p^(min + max)A2, A7, A8
(3) = ∏ p^(xₚ + yₚ)(2), L2
(4) = (∏ p^xₚ)(∏ p^yₚ)A2, A7, A8
(5) = ab(4), A1
∎
비고
A1 은 이 증명에서 제거할 수 있는가.
증명의 핵심은 지수 하나짜리 항등식이다. 그 항등식과, 그것을 두 수에 걸어 주는 다리를 나누어 보라.