유클리드 호제법2 국제수학올림피아드[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. 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 다음
