한국수학올림피아드[KMO] 2016 중등부 14번 풀이(정수론)

암호학을 공부하기 위해 정수론적인 지식 배경이 필요했고

원서를 공부하며 이론 - 증명 - 이론 - 증명만 되풀이하고있었다

 

증명은 수학에서 가장 중요한 부분이라고 생각하여 가장 큰 비중을 두고 공부해왔지만,

계속 증명 연습만 하다 보니 흥미를 잃게 되었고,

어떻게 하면 흥미를 잃지 않으며 공부할 수 있을까 하다가

KMO 중고등부 기출문제들 중 정수론 문제만을 골라서 풀어보기로 했다.

2016년도 제 30회 KMO에서 출제된 14번 정수론 문제다.

나눗셈의 정리를 통해 식을 세우면 생각보다 매우 간단히 풀 수 있는 문제다.

 

"양의 정수 n을 100으로 나눈 몫을 q 나머지를 r이라고 하자"

위 부분을 읽고 다음 방정식과 등식을 세울 수가 있다.

 

나눗셈의 정리에 의거하여

n = 100 * q + r (0 <= r < 100) .. 1

 

"q^2 + r + 1을 74로 나눈 몫이 r+1이고 나머지는 q일 때"

위 부분을 읽고서는 다음 방정식과 등식을 세울 수가 있다

 

q^2 + r + 1 = 74 * (r+1) + q (0 <= q < 74) .. 2

이 식의 양변을 정리하면 다음과 같은 식이 나온다

 

q(q-1) = 73(r+1)

73이라는 숫자는 Prime Number이므로 다음과 같은 Case로 바로 나눌 수가 있다

Case1 : q(q-1) = 73 * 74인 경우 > r=73이고 q = 74 (모순 : 두 번째 식에 의해 q는 74보다 작은 양의 정수다)

 

Case2 : q(q-1) = 73 * 72인 경우 > r=71이고 q = 73

 

Case1은 모순이므로 Case2로 가정하고,

이를 첫 번째 식에 대입하면

n = 100 * 73 + 71 = 7371이다

따라서 n을 1000으로 나눈 나머지는 371,

 

정답은 371이다

 

 

수학에 있어 증명은 논리력이 중요하지만

문제푸는 데는 Guessing과 직관이 매우매우 중요하다는 걸 느꼈다