PROOF 83
증명하라.
호제법의 마지막 나머지가 최대공약수다
자연수 ℕ 위에서.
한 줄씩, 이유를 따라가 봅시다
먼저 이미 주어진 것과 앞으로 보여야 할 것을 나누어 읽어 보세요. 다음 줄로 넘어갈 때마다 어떤 정의나 앞의 결과를 사용했는지 묻습니다. 연결이 보이지 않으면 결론을 외우기보다 그 전제로 잠시 돌아가도 좋습니다.
정의 D1
d | a 는 a = dk 인 자연수 k 가 존재함을 뜻한다.
증명.
이때 d 를 a 의 약수라 한다.약속
∎
정의 D2
C(a, b) 는 a 와 b 의 공약수 전체이고, gcd(a, b) 는 C(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 이면 C(a, b) = C(b, r) 이고 gcd(a, b) = gcd(b, r)
증명.
(1)먼저 d ∈ C(b, r) 라 하자.가정, D2
(2)d | b 이므로 d | bq(1), L1
(3)d | r 이므로 d | bq + r, 즉 d | a(1), (2), A2, 가정
(4)그러므로 C(b, r) ⊆ C(a, b)(1), (3), D2
(5)이제 d ∈ C(a, b) 라 하자.가정, D2
(6)d | b 이므로 d | bq(5), L1
(7)a = bq + r 이고 d | a 이므로 d | r(5), (6), A3, 가정
(8)그러므로 C(a, b) ⊆ C(b, r)(5), (7), D2
(9)서로를 포함하므로 두 집합은 같다.(4), (8)
(10)같은 집합의 최대는 같다.(9), D2
∎
보조정리 L3
rₖ 가 정해지는 모든 k 에 대하여 gcd(a, b) = gcd(rₖ, rₖ₊₁)
증명.
(1)P(k) 를 gcd(a, b) = gcd(rₖ, rₖ₊₁) 로 둔다.약속
(2)r₀ = a, r₁ = b 이므로 P(0) 이 성립한다.(1), D3
(3)P(k) 가 성립하고 rₖ₊₁ > 0 이라 하자.가정
(4)rₖ = rₖ₊₁qₖ₊₁ + rₖ₊₂ 인 qₖ₊₁ 과 rₖ₊₂ 가 있다.(3), D3, A1
(5)gcd(rₖ, rₖ₊₁) = gcd(rₖ₊₁, rₖ₊₂)(4), L2
(6)그러므로 P(k+1) 이 성립한다.(3), (5)
(7)귀납법으로 모든 k 에 대하여 P(k) 이다.(2), (6), A8
∎
정리 T
호제법이 rₙ > 0, rₙ₊₁ = 0 에서 멈추면 gcd(a, b) = rₙ 이다.
증명.
(1)rₙ₋₁ = rₙqₙ + 0 = rₙqₙ가정, D3, A7
(2)그러므로 rₙ | rₙ₋₁(1), D1
(3)rₙ = rₙ × 1 이므로 rₙ | rₙA6, D1
(4)rₙ ∈ C(rₙ₋₁, rₙ)(2), (3), D2
(5)d ∈ C(rₙ₋₁, rₙ) 이면 d | rₙ 이고 rₙ > 0 이므로 d ≤ rₙ가정, D2, A4
(6)그러므로 gcd(rₙ₋₁, rₙ) = rₙ(4), (5), D2
(7)gcd(a, b) = gcd(rₙ₋₁, rₙ)L3
(8)그러므로 gcd(a, b) = rₙ(6), (7)
∎
비고
A1 은 이 증명에서 제거할 수 있는가.
L2 는 조건문이다. 그 조건을 만들어 주는 것이 무엇인지 확인하라.