Detailed mathematical approach

Problem Summary

For each integer \(a\) with \(3 \le a \le 1000\), define \(r_n(a)\) to be the remainder when \((a-1)^n + (a+1)^n\) is divided by \(a^2\). The problem asks for the largest possible remainder \(r_{\max}(a)\) for each fixed \(a\), and then for the sum of these maxima over the whole range. The important point is that the exponent \(n\) is not fixed: we are free to choose the value of \(n\) that makes the remainder as large as possible.

A brute-force search over many exponents would miss the main structure. Once the expression is reduced modulo \(a^2\), almost the entire binomial expansion disappears, and the problem collapses to a short parity argument together with a small modular-arithmetic case split on whether \(a\) is odd or even.

Mathematical Approach

The quantity to analyze is

$r_n(a) \equiv (a-1)^n + (a+1)^n \pmod{a^2}.$

The whole solution comes from understanding which terms of the two powers can survive modulo \(a^2\).

Binomial collapse modulo \(a^2\)

Expand both powers around \(\pm 1\):

$ (a+1)^n = 1 + na + \binom{n}{2}a^2 + \cdots, $

$ (a-1)^n = (-1)^n + n(-1)^{n-1}a + \binom{n}{2}(-1)^{n-2}a^2 + \cdots. $

Modulo \(a^2\), every term containing \(a^2\) or a higher power vanishes. Only the constant and linear terms matter, so

$ (a+1)^n \equiv 1 + na \pmod{a^2}, \qquad (a-1)^n \equiv (-1)^n + n(-1)^{n-1}a \pmod{a^2}. $

Adding them gives a complete reduction:

$ r_n(a) \equiv \begin{cases} 2 \pmod{a^2}, & n \text{ even},\\ 2an \pmod{a^2}, & n \text{ odd}. \end{cases} $

So the enormous-looking expression is really governed by only two pieces of data: the parity of \(n\), and, for odd \(n\), the residue of \(2n\) modulo \(a\).

Why only odd exponents can produce the maximum

When \(n\) is even, the remainder is always exactly \(2\). For \(a \ge 3\), the values obtained from odd exponents are much larger, because they are multiples of \(a\). In fact, once \(n\) is odd we can write

$ r_n(a) = a \cdot (2n \bmod a), $

where the factor \(2n \bmod a\) is taken in the range \(0,1,\dots,a-1\). Therefore maximizing the remainder is equivalent to maximizing the reachable residue \(2n \bmod a\) while keeping \(n\) odd.

The residue pattern for odd \(n\)

Let \(n=2k+1\). Then

$ 2n \equiv 4k+2 \pmod a. $

As \(k\) increases by 1, this residue advances by \(4\) modulo \(a\). That turns the original problem into a very small orbit question in the ring \(\mathbb{Z}/a\mathbb{Z}\).

If \(a\) is odd, then \(\gcd(4,a)=1\). Repeatedly adding \(4\) modulo \(a\) visits every residue class, so among odd exponents we can reach every possible value from \(0\) to \(a-1\). In particular, the largest residue \(a-1\) is attainable, and therefore

$ r_{\max}(a) = a(a-1) \qquad (a \text{ odd}). $

If \(a\) is even, then \(2n\) is always even, so the residue \(a-1\) can never occur. The largest possible residue below \(a\) with the correct parity is \(a-2\). It is actually attained: choosing \(n=a-1\), which is odd, gives \(2n=2a-2 \equiv a-2 \pmod a\). Hence

$ r_{\max}(a) = a(a-2) \qquad (a \text{ even}). $

Closed form for the maximum remainder

The case split can be written compactly as

$ r_{\max}(a)= \begin{cases} a(a-2), & a \text{ even},\\ a(a-1), & a \text{ odd}. \end{cases} $

This is exactly the formula used by the implementations. Once it has been proved, the original number-theory problem becomes a direct summation over \(a=3,4,\dots,1000\).

Worked examples

Take \(a=7\). For odd exponents, the coefficient \(2n \bmod 7\) runs through

$ 2,6,3,0,4,1,5,\dots $

so the largest reachable value is \(6\). Therefore \(r_{\max}(7)=7\cdot 6=42\).

Now take \(a=8\). For odd exponents, the coefficient \(2n \bmod 8\) runs through

$ 2,6,2,6,\dots $

Only even residues occur, and the best one is \(6=8-2\). Thus \(r_{\max}(8)=8\cdot 6=48\). These two examples show exactly why the final formula depends only on the parity of \(a\).

How the Code Works

The C++, Python, and Java implementations do not search over exponents at all. They rely on the closed form above, loop over every integer \(a\) from \(3\) to \(1000\), determine whether \(a\) is odd or even, and add the corresponding contribution \(a(a-1)\) or \(a(a-2)\) to a running total.

This means the code is already working at the final mathematical level. All of the difficult reasoning is pushed into the derivation of \(r_{\max}(a)\); once that derivation is known, the implementation is just a short accumulation over 998 values of \(a\).

Complexity Analysis

There is one pass through the integers \(a=3\) to \(1000\), and each iteration performs only a parity test, two small multiplications, and one addition. The running time is therefore \(O(1000)\), or more generally \(O(A)\) if the upper bound is \(A\). The memory usage is \(O(1)\), since the implementation stores only the running total and a few temporary integer values.

Footnotes and References

1. Problem page: Project Euler 120 - Square remainders
2. Binomial theorem: Wikipedia - Binomial theorem
3. Modular arithmetic: Wikipedia - Modular arithmetic
4. Congruence relation: Wikipedia - Congruence relation
5. Parity: Wikipedia - Parity