최대공약수4 Bezout's Identity(베주 항등식) 증명 완벽 이해 오늘은 Bezout's Identity의 증명을 완벽하게 이해 하는 시간을 가져 보겠습니다. 베주의 항등식이란? 베주의 항등식의 내용은 다음과 같습니다. 저번에 방정식의 정수해만을 고려하는 부정 방정식의 해법인 1차 Diopantine Equation에 관하여 포스팅을 한 바 있습니다. 해당 방정식의 정수쌍 (x,y)의 해가 존재할 필요충분조건에 관한 증명을 할 때 Bezout's Identity가 사용이 되었습니다. ax + by = gcd(a,b) 라는 형태의 방정식이 있을 때, 이를 만족시키는 정수쌍 x,y가 반드시 존재한다는 정리입니다. 증명을 해보도록 하겠습니다. 베주의 항등식 증명 "위 식을 만족시키는 정수쌍 x와 y가 존재한다"와 같은 어떤 대상에 대한 존재성을 증명하고자 할 때에는 집합을 .. 2022. 4. 21. 한국수학올림피아드[KMO] 2018 중등부 12번 풀이 1번과 2번 식이 주어져 있고, 이 식들을 이용하여 a + b를 구하는 문제이다. 최대공약수와 최소공배수를 식으로 나타내고 정리해서 몇가지 Case로 나눠 추론하면 풀리는 문제이다. 두 양의 정수 a와 b를 다음과 같이 나타내보자 두 양의 정수 a와 b의 최대공약수를 d라고 정의하면, a = d * s b = d * t (s와 t는 Relatively Prime) 위와 같은 식을 세울 수가 있다. 위 값을 2번 식에 대입해 보자 ab + lcm(a,b) = 432이므로 ds * dt + dst = dst(d + 1) = d(d+1)st = 432이다 432를 소인수분해하면 d(d+1)st = 2*2*2*2*3*3*3 으로 나타낼 수 있다. 우리가 정리한 식을 다시 한번 자세히 보자 d(d+1)st = 2.. 2022. 4. 15. 1차 Diophantine equation 해 존재 조건과 증명 디오판토스 방정식이란 부정방정식에서 정수해만을 고려한 방정식을 말한다 ax + by = c라는 indeterminate equation이 주어져 있을 때 정수해 (x , y)쌍이 존재할 필요충분조건은 다음과 같다. d | c 증명 다음 두 가지를 증명하면 된다 1 ) ax + by = c 의 정수해 x1와 y1가 존재하면 d | c이다. 2 ) d | c 이면 ax + by = c 의 정수쌍 x와 y가 존재한다. 1) 증명 Z는 정수의 집합이다 d를 gcd(a,b)로 정의하고 aZ + bZ 집합을 {ax + by | x,y는 Z의 원소} 이라고 정의하면 aZ + bZ = dZ를 만족한다. 그러면 당연히 ax + by = c에 대하여 c 는 dZ의 원소이므로 d|c를 만족한다. 2) 증명 d | c에서 다.. 2022. 4. 14. 정수 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 다음
