제 22 회 한국수학올림피아드 1차 시험 (중등부)

2008년 5월 24일 ; 제한시간 4시간

문제 16. 다음과 같이 정의된 수열을 생각하자.

이 때 다음 두 정수의 최대공약수를 구하여라.

풀이 : 일단 모든 에 대해서 임을 수학적 귀납법으로 증명하자.

i) = 1 이면, (1, 1) = 1 로 성립한다.

ii) 일 때 성립한다면, 이므로,

일 때도 성립한다.

다음으로

를 이용하자.

그럼 이므로,

두 수의 최대공약수는 4 이다.