Mathmatics13 국제수학올림피아드[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. 한국수학올림피아드[KMO] 2016 중등부 14번 풀이(정수론) 암호학을 공부하기 위해 정수론적인 지식 배경이 필요했고 원서를 공부하며 이론 - 증명 - 이론 - 증명만 되풀이하고있었다 증명은 수학에서 가장 중요한 부분이라고 생각하여 가장 큰 비중을 두고 공부해왔지만, 계속 증명 연습만 하다 보니 흥미를 잃게 되었고, 어떻게 하면 흥미를 잃지 않으며 공부할 수 있을까 하다가 KMO 중고등부 기출문제들 중 정수론 문제만을 골라서 풀어보기로 했다. 2016년도 제 30회 KMO에서 출제된 14번 정수론 문제다. 나눗셈의 정리를 통해 식을 세우면 생각보다 매우 간단히 풀 수 있는 문제다. "양의 정수 n을 100으로 나눈 몫을 q 나머지를 r이라고 하자" 위 부분을 읽고 다음 방정식과 등식을 세울 수가 있다. 나눗셈의 정리에 의거하여 n = 100 * q + r (0 r=.. 2022. 4. 12. Division Theorem(나눗셈 정리) 증명 나눗셈 정리란 다음과 같다 핵심은 다음과 같다. 위 조건을 만족시키는 정수 q와 r이 반드시 존재한다. 그리고 q와 r은 반드시 유일하다. 그러면 위 두 가지 사실을 증명해 보도록 하자. 1. b=aq+r을 만족시키는 정수 q와 r이 존재한다. 2. 이 q와 r은 유일하다. 존재성의 증명 집합 S = {b-na | n은 정수,b-na>=0} 여기서 a,b,n은 모두 정수이므로 b-na>=을 만족시키는 정수쌍(a,b,c)가 반드시 존재한다. 따라서 S는 공집합이 아니므로, 정렬 원리에 의하여 S는 가장 작은 원소 r을 가진다. 집합 S의 가장 작은 원소 r이 존재한다는 것을 증명하였다. 그러면 이 r이 반드시(0=0이므로 b-n(a+1)은 집합 S의 원소이며 r보다 작은 값을 가진다. 여기서 모순이 발생한.. 2022. 4. 12. 이전 1 2 3 4 다음
