PROOF 187
증명하라.
gcd(a,b) = ax + by 인 정수가 있다
정수 ℤ 위에서.
한 줄씩, 이유를 따라가 봅시다
먼저 이미 주어진 것과 앞으로 보여야 할 것을 나누어 읽어 보세요. 다음 줄로 넘어갈 때마다 어떤 정의나 앞의 결과를 사용했는지 묻습니다. 연결이 보이지 않으면 결론을 외우기보다 그 전제로 잠시 돌아가도 좋습니다.
정의 D1
c ∣ a 는 a = cm 인 정수 m 이 있음을 뜻한다.
증명.
약수와 배수를 이 한 줄로 쓴다.약속
∎
정의 D2
gcd(a, b) 는 a 와 b 의 공약수 가운데 가장 큰 것이다.
증명.
(1)공약수는 c ∣ a 이고 c ∣ b 인 c 이다.D1
(2)a, b 는 둘 다 0 은 아니라고 하자.가정
∎
정의 D3
S = { ax + by : x, y ∈ ℤ, ax + by > 0 } 으로 둔다.
증명.
a, b 의 정수 결합 가운데 양수인 것을 모두 모은 집합이다.약속
∎
보조정리 L1
S 는 비어 있지 않다.
증명.
(1)a, b 가 둘 다 0 은 아니므로, a ≠ 0 이라 해도 좋다.D2
(2)x = a, y = 0 으로 두면 ax + by = a·a + b·0 = a·a + 0 = a·a.A7, A8
(3)a·a > 0 이므로 a·a ∈ S.(1), (2), A3, D3
∎
보조정리 L2
S 는 최소 원소 d 를 갖는다. d = ax₀ + by₀ 로 쓴다.
증명.
(1)S 는 ∅ 아닌 양의 정수 집합이다.D3, L1
(2)최소 원소 d 가 존재한다.(1), A1
(3)d ∈ S 이므로 d = ax₀ + by₀ 인 x₀, y₀ 가 있고 0 < d 이다.(2), D3
∎
정리 T1
d 는 a 를 나누고 b 를 나눈다.
증명.
(1)a 를 d 로 나눈다: a = qd + r, 0 ≤ r < d.A2, L2
(2)r = a − qd = a − q(ax₀ + by₀)(1), L2, E
(3) = a(1 − qx₀) + b(−qy₀) — r 도 a, b 의 정수 결합이다.(2), A4, A5
(4)0 < r 이면 r ∈ S 이고 r < d — d 의 최소성에 모순.(1), (3), D3, L2
(5)그러므로 r = 0 이고 a = qd + 0 = dq — 즉 d ∣ a.(4), (1), A8, A5, D1
(6)b = q′d + r′ 에 같은 논증을 적용하면 d ∣ b.A2, (5)
∎
정리 T2
a, b 의 공약수 c 는 모두 d 를 나눈다.
증명.
(1)c ∣ a, c ∣ b 라 하자: a = cm, b = cn.가정, D1
(2)d = ax₀ + by₀ = (cm)x₀ + (cn)y₀L2, (1), E
(3) = c(mx₀ + ny₀)(2), A4, A5
(4)그러므로 c ∣ d.(3), D1
∎
따름정리 C
d = gcd(a, b) 이다. 그러므로 gcd(a, b) = ax₀ + by₀ 인 정수 x₀, y₀ 가 존재한다.
증명.
(1)d 는 a, b 의 공약수다.T1, D2
(2)임의의 공약수 c 는 c ∣ d 이고 0 < d 이므로 c ≤ d.T2, L2, A6
(3)공약수 가운데 가장 큰 것이 d — 즉 d = gcd(a, b).(1), (2), D2
(4)d = ax₀ + by₀ 이므로, gcd(a, b) 는 a 와 b 의 정수 결합이다.(3), L2
∎
비고
A1 은 이 증명에서 제거할 수 있는가.
d 는 '가장 작은 양수 결합'으로 정의되었다. 가장 작은 것이 있다는 보장이 어디서 오는지 확인하라.