Greatest Common Divisor1 정수 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는 정수이.. 2022. 4. 12. 이전 1 다음
