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