정수 m,n,k에 대하여 gcd(m,n) = gcd(m+kn) 증명

정수 m,n과 임의의 정수 k에 대하여 

gcd(m,n) = gcd(m+kn,n)이다

 

최대공약수와 관련된 정리는 여태까지 방정식을 세워 대수적으로 증명하였었다.

하지만 이 풀이는 집합이론을 이용하여 증명한다.

 

A집합은 B집합과 같은 원소를 가지는가를 증명할 때는 다음 두 가지만 증명하면 된다

1. A는 B의 부분집합이다

2. B또한 A의 부분집합이다

 

위 사실을 이용하여 증명해보도록 하자.

 

정수 m과 n의 공약수의 집합을 S,

정수 m +kn과 n의 공약수의 집합을 T라고 해보자.

 

1. S는 T의 부분집합임을 증명

 

S의 임의의 원소 x에 대하여 x | m,x | n이다.

따라서 위와 같은 성질을 가진 x에 대하여 다음 사실도 성립한다.

S의 임의의 원소 x에 대하여 x | m+nk, x | n (k는 정수이기 때문이다)

 

S의 모든 원소는 집합 T의 원소이기에

S는 T의 부분집합이다

 

2. T는 S의 부분집합임을 증명

T의 임의의 원소 y에 대하여 y | m + nk이고 y | n이다.

y | n 이기 때문에, 임의의 정수 k에 대하여 y | nk이며

따라서 다음도 성립한다

 

y | (m+nk) - (nk) = m

 

y | n, y | m이기 때문에

T의 임의의 원소 y는 집합 S에 속한다.

 

집합 S는 T의 부분집합이고

집합 T는 역시 S의 부분집합이다

 

따라서 집합 S와 T는 같다.

 

정수 m과 n의 공약수의 집합 S = 정수 m +kn과 n의 공약수의 집합 T

 

따라서, m과 n의 공약수의 집합 중 가장 큰 원소 = gcd(m, n)

m+kn과 n의 공약수 집합 중 가장 큰 원소 = gcd(m+kn, n)

 

gcd(m,n) = gcd(m + kn,n)이다