Mathmatics/Number Theory11 한국수학올림피아드[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. 국제수학올림피아드[IMO] 1959 1번 문제 풀이 다른 대회도 아니고 무려, 세계의 수학 천재들은 다 모인다는 국제 수학 올림피아드 문제이다. 하지만 문제의 난이도는 지금 기준으로는 굉장히 쉬운 문제이다. 기원전 300년 경에 이미 발견된 Euclidean algorithm을 이용하면 단 두 줄에도 풀이가 가능한 문제이기 때문이다. 문제풀이 (21n + 4) / (14n + 3)이 irreducible(기약분수)임을 증명하라고 한다. 그러면 gcd(21n+4,14n+3) = 1임을 보이면 되겠다. 어떤 두 정수의 gcd를 구할 때, 두 정수가 충분히 작다면 손으로 구할 수 있겠지만. 두 정수가 너무 클 경우엔 어떻게 할까? 예를들어 133118과 4528의 최대공약수를 곧바로 구할 수 있겠는가? 이럴 때는 Euclideam Algorithm(유클리드 호.. 2022. 4. 13. 정수 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 2 3 다음
