Solution

Answer: 333082500

We seek the maximum remainder

$$r = (a-1)^n + (a+1)^n \pmod{a^2}$$

for each integer $3 \le a \le 1000$, and then compute

$$\sum_{a=3}^{1000} r_{\max}.$$

The key is to simplify the expression modulo $a^2$.

Step 1 — Expand with the Binomial Theorem

Consider

$$(a+1)^n.$$

Using the binomial theorem,

$$(a+1)^n = \sum_{k=0}^n \binom{n}{k} a^k.$$

Modulo $a^2$, every term containing $a^2$ or higher vanishes, so only the first two terms matter:

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

Similarly,

$$(a-1)^n = \sum_{k=0}^n \binom{n}{k} a^k (-1)^{n-k}.$$

Again keeping only terms below $a^2$,

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

Now add the two expressions:

$$r \equiv \left[1 + na\right] + \left[(-1)^n + n(-1)^{n-1}a\right] \pmod{a^2}.$$

We separate cases by parity of $n$.

Step 2 — Even and Odd $n$

Case 1: $n$ even

Then

$$(-1)^n = 1, \qquad (-1)^{n-1} = -1.$$

$$r \equiv (1+na)+(1-na)=2 \pmod{a^2}.$$

Thus every even $n$ gives

$$r=2.$$

Case 2: $n$ odd

Then

$$(-1)^n=-1, \qquad (-1)^{n-1}=1.$$

Hence

$$r \equiv (1+na)+(-1+na)=2na \pmod{a^2}.$$

So for odd $n$,

$$r \equiv 2an \pmod{a^2}.$$

Therefore the problem reduces to maximizing

$$2an \bmod a^2.$$

Factor out $a$:

$$r = a(2n \bmod a).$$

Thus we want the largest possible multiple of $a$ below $a^2$.

Because $2n$ is even, the largest attainable residue depends on the parity of $a$.

Step 3 — Determine $r_{\max}$

If $a$ is odd

Then $a-1$ is even, so we can choose

$$2n \equiv a-1 \pmod a.$$

This gives

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

If $a$ is even

Then the largest even residue below $a$ is $a-2$, so

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

We can combine both cases neatly:

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

Step 4 — Compute the Sum

We now evaluate

$$\sum_{a=3}^{1000} r_{\max}.$$

Python Implementation

total = 0

for a in range(3, 1001):

    # If a is odd:
    # r_max = a(a - 1)
    if a % 2 == 1:
        r_max = a * (a - 1)

    # If a is even:
    # r_max = a(a - 2)
    else:
        r_max = a * (a - 2)

    total += r_max

print(total)

Code Walkthrough

total = 0

Initialize the running sum.

for a in range(3, 1001):

Loop through all integers $a$ from $3$ to $1000$.

if a % 2 == 1:

Check whether $a$ is odd.

For odd $a$,

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

else:
    r_max = a * (a - 2)

For even $a$,

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

total += r_max

Accumulate the maximum remainder.

print(total)

Output the final sum.

Small Example Check

The problem states that for $a=7$,

$$r_{\max}=42.$$

Our formula gives:

$$7(7-1)=42,$$

which matches perfectly.

For $a=6$,

$$r_{\max}=6(6-2)=24.$$

Indeed, odd powers produce residues

$$2an \bmod 36,$$

whose maximum is $24$.

Final Verification

The dominant term is approximately $a^2$, so the total should be on the order of

$$\sum_{a=1}^{1000} a^2 \approx \frac{1000^3}{3}\approx 3.3\times10^8.$$

Our final value is in exactly that range, which is a good sanity check.

Evaluating the sum gives:

$$333082500.$$

Answer: 333082500

Project Euler Problem 120