PROOF 08
증명하라.
유클리드 호제법은 반드시 끝난다
자연수 ℕ 위에서.
한 줄씩, 이유를 따라가 봅시다
먼저 이미 주어진 것과 앞으로 보여야 할 것을 나누어 읽어 보세요. 다음 줄로 넘어갈 때마다 어떤 정의나 앞의 결과를 사용했는지 묻습니다. 연결이 보이지 않으면 결론을 외우기보다 그 전제로 잠시 돌아가도 좋습니다.
정의 D1
d | a 는 a = dk 를 만족하는 자연수 k 가 존재함을 뜻한다.
증명.
이때 d 를 a 의 약수, a 를 d 의 배수라 한다.약속
∎
정의 D2
gcd(a, b) 는 a 와 b 의 공약수 가운데 가장 큰 것이다.
증명.
두 쌍의 공약수 집합이 같으면 최대공약수도 같다.약속
∎
정의 D3
r₀ = a, r₁ = b 로 두고, rₖ > 0 인 동안 rₖ₋₁ = rₖqₖ + rₖ₊₁, 0 ≤ rₖ₊₁ < rₖ 로 다음 항을 정한다.
증명.
(1)각 단계의 qₖ 와 rₖ₊₁ 은 A1 이 하나로 정한다.A1
(2)rₖ = 0 이 되면 멈춘다.약속
∎
보조정리 L1
d | x 이면 모든 q 에 대하여 d | xq
증명.
(1)x = dm 인 m 이 있다.가정, D1
(2)xq = (dm)q(1), E
(3) = d(mq)A5
(4)그러므로 d | xq(3), D1
∎
보조정리 L2
a = bq + r 이면 gcd(a, b) = gcd(b, r)
증명.
(1)d 가 b 와 r 의 공약수라 하자.가정
(2)d | bq(1), L1
(3)d | bq + r, 즉 d | a(1), (2), A6, 가정
(4)이제 d 가 a 와 b 의 공약수라 하자.가정
(5)d | bq(4), L1
(6)a = bq + r 이고 d | a 이므로 d | r(4), (5), A7
(7)두 쌍의 공약수 집합은 같다.(3), (6)
(8)그러므로 최대공약수도 같다.(7), D2
∎
정리 T
호제법은 유한 번의 단계 뒤에 rₖ = 0 에 이른다.
증명.
(1)각 단계에서 0 ≤ rₖ₊₁ < rₖ 이다.D3, A1
(2)호제법이 끝나지 않는다고 하자.가정
(3)그러면 모든 k 에 대하여 rₖ > 0 이고 rₖ₊₁ < rₖ 이다.(1), (2)
(4)S = { r₁, r₂, r₃, … } 는 ℕ 의 공집합 아닌 부분집합이다.(3)
(5)S 에는 최소원 rₘ 이 있다.A2, (4)
(6)rₘ > 0 이므로 rₘ₊₁ 이 정해지고 rₘ₊₁ < rₘ 이다.(3), (5), D3
(7)rₘ₊₁ 은 S 의 원소다.(4), (6)
(8)이는 rₘ 이 S 의 최소원인 것에 모순이다.(5), (6), (7)
(9)그러므로 호제법은 유한 번에 끝난다.(8)
∎
따름정리 C
호제법이 rₙ₊₁ = 0 에서 멈추면 gcd(a, b) = rₙ 이다.
증명.
(1)gcd(r₀, r₁) = gcd(r₁, r₂) = … = gcd(rₙ₋₁, rₙ)L2, D3
(2)rₙ₋₁ = rₙqₙ + 0 = rₙqₙ가정, D3, A3
(3)그러므로 rₙ | rₙ₋₁(2), D1
(4)rₙ = rₙ × 1 이므로 rₙ | rₙA4, D1
(5)rₙ 은 rₙ₋₁ 과 rₙ 의 공약수다.(3), (4)
(6)rₙ > 0 이므로, d 가 그 공약수이면 d | rₙ 이고 d ≤ rₙD3, A8
(7)gcd(rₙ₋₁, rₙ) = rₙ(5), (6), D2
(8)그러므로 gcd(a, b) = rₙ(1), (7)
∎
비고
A2 는 이 증명에서 제거할 수 있는가.
나머지가 매 단계 줄어드는 것만으로 멈춤이 따라 나오는지 확인하라.