<s>[INST] Maximum remainder $(a-1)^n+(a+1)^n\mod a^2$ for $3\le a\le 1000$ Here's the problem:

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$ since $63 + 83 = 728 \equiv 42 \pmod{49}$. And as $n$ varies, so too will $r$, but for $a = 7$ it turns out that $r_{max} = 42$.
For $3 \le a \le 1000$, find $\sum r_{max}$.
Source


What I've tried:
$$X=(a-1)^n+(a+1)^n=2\sum_{r=0,2|n-r}^n {}^n{\rm C}_ra^r$$
So:
$$X\mod a^2 = \begin{cases}2&2|n\\2an&2\not|n\end{cases}$$
Now I think $n_{(r_{max})}$therefore should be the largest odd number strictly less than $a/2$ and $r_{max}$ should be $2an_{(r_{max})}$.
So answer should be :
$$\sum_{r=3}^{1000}2an_{(r_{max})}$$
Am I correct?
Do you have any other better ideas?
 [/INST] As you said the remainder is
$$r\mod a^2 = \begin{cases}2&2|n\\2an&2\not|n\end{cases}.$$
Now observe that the maximum value of $2an \mod a^2$ could be $a(a-1)$. IT holds if and only if the following system of congruence 
$$\begin{cases}n\equiv1&\mod 2\\
           2an\equiv a(a-1)&\mod a^2
    \end{cases}$$
has solution for some $n$.
For $a$ odd this system has solution. In fact write $a=2b+1$, then
$$\begin{cases}n\equiv1&\mod 2\\
           2(2b+1)n\equiv 2b(2b+1)&\mod (2b+1)^2
    \end{cases}$$
becomes
$$\begin{cases}n\equiv1&\mod 2\\
           n\equiv b&\mod (2b+1)
    \end{cases}$$
that admits solution because $\gcd(2,2b+1)=1$.
With a similar argument you can show that this system does not have solutions for $a$ even. Write $a=2b$. Then
$$\begin{cases}n\equiv1&\mod 2\\
           4bn\equiv 2b(2b-1)&\mod 4b^2
    \end{cases}$$
becomes
$$\begin{cases}n\equiv1&\mod 2\\
           2n\equiv -1&\mod (2b)
    \end{cases}$$
that has not solution. So in this case the maximum has to be less than 
$a(a-1)$ and you can show with the same argument that
$$\begin{cases}n\equiv1&\mod 2\\
           2an\equiv a(a-2)&\mod a^2
    \end{cases}$$
    has solution.
Hence the value that you are looking for is
\begin{align}&\sum_{a \mbox{ odd}}a(a-1) +\sum_{a \mbox{ even}} a(a-2) \\
= &\sum_{a=3}^{1000}a^2-\sum_{a \mbox{ odd}}a -\sum_{a \mbox{ even}}2a \\ 
= &\sum_{a=3}^{1000}a^2-\sum_{k=2}^{500}(6k-1) \\
= &\frac{1000\cdot1001 \cdot 2001}{6}-5-6\cdot\frac{500\cdot501}{2}-6-499
\end{align}
</s>