Maximum remainder $(a-1)^n+(a+1)^n\mod a^2$ for $3\le a\le 1000$

Question

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?

Answer 1

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}