본문 바로가기

수학

정수론 문제

반응형

네이버 검색을 하던 도중 흥미로운 정수론 문제를 발견해서 그 문제와 풀이를 올리려고 한다. 물론 내가 푼 방법보다 좀 더 간단하면서도 정석적인 풀이가 있을 수도 있지만 아직은 생각나지 않아 그냥 한 가지 풀이로만 작성을 하고자 한다.


문제


$2009^{2009}$의 자릿수를 모두 더해서 나온 수의 자릿수를 다시 더하고, ..., 이런 식으로 한 자리 수가 될 때까지 반복하자. 이렇게 얻은 한 자리의 수는 얼마인지 구하시오.



풀이


이 문제에서 요구하는 답은 한 자리 수를 원하고 있다. 그렇기 때문에 답이 될 수 있는 숫자는 1~9의 9개의 숫자 중 하나가 가능하다. 계속 자릿수를 더하는 과정을 거치기 때문에 0은 절대로 나올 수가 없다.


이 문제와는 상관이 없어보일수도 있지만, 다음의 아이디어를 사용하도록 하겠다.

『어떤 자연수를 9로 나눈 나머지는 그 자연수의 자릿수를 모두 더한 값을 9로 나눈 나머지와 같다.』

이 내용은 9의 배수를 판정하는 방법을 약간 확장한 것으로 증명은 어려운 것이 아니니 스킵하도록 하겠다.


위 아이디어에 의해서 어떤 자연수가 있을 때 그 자연수의 자릿수를 모두 더하더라도 9로 나눈 나머지는 그대로 유지된다는 사실을 알 수 있다.

즉, 어떠한 자연수를 한자리 수가 될 때까지 자연수의 자릿수를 모두 더하는 과정을 계속 하게 되더라도 9로 나눈 나머지는 그대로 유지된다는 것이다.


그래서 $2009^{2009}$를 9로 나눈 나머지와 정답을 9로 나눈 나머지가 같기 때문에 $2009^{2009}$를 9로 나눈 나머지를 계산하면 답을 구할 수 있다는 것이다.


$2009^{ 2009 }\equiv 2^{ 2009 }\equiv (2^{ 3 })^{ 669 }\times 2^{ 2 }\equiv (-1)^{ 669 }\times 4\equiv -4\equiv 5\quad (mod~9) $


이므로 $2009^{2009}$를 9로 나눈 나머지는 5라는 것을 알 수 있다. 그러므로 한 자리 수인 정답을 9로 나눈 나머지가 5이고, 9로 나눈 나머지가 5이면서 한 자리 자연수는 5만 존재하기 때문에 답은 5라는 것을 알 수 있다.


 : 5


반응형

'수학' 카테고리의 다른 글

정수론 문제 2  (0) 2016.03.06
정수론 문제  (0) 2016.02.26

태그