국제수학올림피아드[IMO] 1959 1번 문제 풀이

1959 IMO 1번 문제

다른 대회도 아니고 무려, 세계의 수학 천재들은 다 모인다는 국제 수학 올림피아드 문제이다.

하지만 문제의 난이도는 지금 기준으로는 굉장히 쉬운 문제이다.

기원전 300년 경에 이미 발견된 Euclidean algorithm을 이용하면 단 두 줄에도 풀이가 가능한 문제이기 때문이다.

 

문제풀이

 

(21n + 4) / (14n + 3)이 irreducible(기약분수)임을 증명하라고 한다.

 

그러면 gcd(21n+4,14n+3) = 1임을 보이면 되겠다.

 

어떤 두 정수의 gcd를 구할 때,

두 정수가 충분히 작다면 손으로 구할 수 있겠지만.

 

두 정수가 너무 클 경우엔 어떻게 할까?

예를들어 133118과 4528의 최대공약수를 곧바로 구할 수 있겠는가?

 

이럴 때는 Euclideam Algorithm(유클리드 호제법)을 이용한다.

 

두 정수 a,b에 대하여

a = b*q + r (0 <= r < b) 에서

gcd(a,b) = gcd(b,r)이다.

 

21n + 4 = (14n + 3) * 1 + (7n + 1)

14n + 3 = (7n + 1) * 2 + 1

 

따라서 gcd(21n + 4,14n + 3) = gcd(14n + 3, 7n + 1) = gcd(7n + 1,1) = 1

21n + 4와 14n + 3의 최대공약수는 1이므로 위 분수는 기약분수이다.