프로젝트 오일러 120번

Let \(r\) be the remainder when \((a-1)^n +(a+1)^n\) is divided by \(a^2\).

For example, if \(a=7\) and \(n=3\), then \(r=42: \; 6^3 +8^3 = 728 \equiv 42 \; \rm mod\; 49\). And as \(n\) varies, so too will \(r\), but for \(a=7\) it turns out that \(r_{\rm max} =42\).

For \(3 \le a \le 1000\), find \(\sum r_{\rm max}\).

---

\((a-1)^n + (a+1)^n\) 을 \(a^2\) 으로 나누었을 때의 나머지를 \(r\) 라고 하자.

예를 들어, \(a=7\) 이고 \(n=3\) 이면 \(r\) 은 \(6^3 + 8^3\) 을 \(7^2\) 으로 나눈 나머지 \(42\) 가 된다. 만약 \(a=7\) 일 때, \(n\)이 자연수 범위에서 변한다면 \(r\) 의 최댓값 \(r_{\rm max} = 42\) 가 된다.

\(\sum \limits_{a=3}^{1000} r_{\rm max}\) 를 구하시오.  

이 문제는 도대체 \(n\) 을 얼마까지 계산해봐야 나머지의 최댓값을 구할수 있겠는가를 알면 빠르게 해결할 수 있다. 물론 \(n\) 을 충분히 큰 수까지 변화시키면서 계산하면 답이 나오기는 하는데, 생각보다 시간이 오래 걸린다. (\(n\) 을 1에서 2000까지 변화시키면서 계산했더니 답이 나오는 것을 확인했다.)

그렇다면 \(n\) 의 최댓값을 어떻게 결정해야 하겠는가?

\((a-1)^n\) 이나 \((a+1)^n\) 을 각각 \(a^2\) 으로 나누게 되면 그 나머지들은 주기를 가지고 순환하게 된다. 예를 들어, 문제에서 보여줬던 \(a=7\) 인 경우를 본다면 \(6^n\) 을 \(49\) 로 나눈 나머지는 다음과 같이 14개를 주기로 순환한다. \[6, \; 36, \; 20, \; 22, \; 34, \; 8,\; 48,\; 43,\; 13, \; 29,\; 27, \; 15, \; 41, \; 42\]

또한 \(8^n\) 을 \(49\) 로 나눈 나머지는 다음과 같이 7개를 주기로 순환한다.

\[8, \; 15,\; 22,\; 29,\; 36,\; 43,\; 1\]

따라서 이들의 주기인 \(14\) 와 \(7\) 의 최소공배수 14가 우리가 살펴봐야 할 범위가 되는 것이다. 즉, \(n\) 을 1부터 14까지만 변화시키면서 나머지의 최댓값을 구해내면 된다는 것이다.

이런식으로 접근해도 답이 나올 때까지는 수초 정도가 소요되게 된다. 

-----------------------------------------------------------------------------------

두 번째 방법은 이항정리에 대한 지식이 있는 사람들을 위한 풀이 법이다.

이항정리를 이용하면 다음과 같이 전개되는 것을 알 수 있다.

\[\begin{split} (a-1)^n &= {_n}{\rm C}_0 a^n (-1)^0 + {_n}{\rm C}_1 a^{n-1}(-1)^1 + \cdots + {_n}{\rm C}_{n-1} a^1 (-1)^{n-1} + {_n}{\rm C}_n a^0 (-1)^n \\ (a+1)^n &= {_n}{\rm C}_0 a^n 1^0 + {_n}{\rm C}_1 a^{n-1} 1^1 + \cdots + {_n}{\rm C}_{n-1} a^1 1^{n-1} + {_n}{\rm C}_n a^0 1^n \end{split}\]

위 두 식을 변변 더해주면 

\[(a-1)^n + (a+1)^n = 2 {_n}{\rm C}_0 a^n + 2{_n}{\rm C}_2 a^{n-2} + 2{_n}{\rm C}_4 a^{n-4} + \cdots \]

이제 위의 식을 \(a^2\) 으로 나눈 나머지를 구하는 것이므로 전개식에서 \(a\) 항과 상수항에만 관심을 가지면 된다. 예를 들어, 

\(n=1\) 인 경우는 \(2 {_1}{\rm C}_0 a^1 = 2a\) 이므로 나머지는 \(2a\) 가 된다.

\(n=2\) 인 경우는 \(2 {_n}{\rm C}_0 a^2 + 2 {_2}{\rm C}_2 a^0\) 이므로 나머지는 상수항인 \(2\) 가 된다. 

\(n=3\) 인 경우는 \(2 {_3}{\rm C}_0 a^3 + 2 {_3}{\rm C}_2 a^1\) 이므로 나머지는 \(a\) 항인 \(6a\) 가 된다. 

\(n=4\) 인 경우는 \(2 _{_4}{\rm C}_0 a^4 + 2 {_4}{\rm C}_2 a^2 + 2 {_4}{\rm C}_4 a^0\) 이므로 나머지는 \(a\) 항인 \(2\) 가 된다.

   \(\vdots\)

이런식으로 계산을 하다보면 \(n\) 이 짝수인 경우는 나머지가 \(2\) 가 되고, \(n\) 이 홀수인 경우는 \(2na\) 를 \(a^2\) 으로 나는 나머지가 되는 것을 알 수 있다. 

그렇다면 \(2na\) 를 \(a^2\) 으로 나눈 나머지가 최대가 될 때는 언제일까?

물론 우리는 \(n\) 이 홀수일 때만을 대상으로 나머지를 구해봐야 하겠지만, \(n\) 이 자연수인 경우를 생각하여 나머지를 구해도 나머지의 최댓값이 바뀌지 않는다는 것을 알 수 있고, 또한 \(2n\) 의 값이 \(a\) 보다 작지만 \(a\) 에 가장 근접할 때가 나머지가 최대라는 것을 알 수 있다. (이 부분이 이해가 가지 않는다면 실제로 계산을 해보자.)

따라서 \(a\) 가 짝수인 경우에는 \(n=\dfrac{a}{2}\) 일 때 정확히 \(a^2\) 이 되고 \(n\) 도 정수가 되므로 \(n=\dfrac{a}{2}-1\) 일 때 나머지가 최대가 되는 것을 알 수 있다. 또한 \(a\) 가 홀수인 경우에는 \(n=\dfrac{a-1}{2}\) 일 때 나머지가 최대인 것을 알 수 있다. (그래야만 \(n\) 이 정수가 되면서 \(2n\) 이 \(a^2\) 에 가장 가깝게 된다.

\(a\) 가 홀수, 짝수일 때를 묶어서 생각하면 \(n\) 은 \(\left [ \dfrac{a-1}{2} \right ] \) (단, \([x]\) 는 \(x\) 를 넘지 않는 최대 정수) 로 정의할 수 있다.

따라서 나머지의 최댓값은 \(2 \times a \times \left [ \dfrac{a-1}{2} \right ] \) 임을 알 수 있다.

결국 구하는 값은 \(a\) 가 \(3\) 부터 \(1000\) 까지 변하는 동안 \(2 \times a \times \left [ \dfrac{a-1}{2} \right ]\) 값들을 모두 더해주면 된다.