euclidean algorithm1 국제수학올림피아드[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. 이전 1 다음
