# How to maximize $n!\sum^n_{k = 0}\frac{a^k(1+(-1)^{n-k})}{k!(n-k)!} \pmod{a^2}$ for a given $a$?

Short Version of the Question:

How do I maximize the value of $n!\sum^n_{k = 0}\frac{a^k(1+(-1)^{n-k})}{k!(n-k)!} \pmod{a^2}$ for a given $a$?

Long Version of the Question:

I'm currently attempting a Project Euler question using as much mathematics as possible before resorting to coding.

The problem itself is as follows:

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: 63^3 + 83^3 = 728  42 mod 49. And as n varies, so too will r, but for a = 7 it turns out that rmax = 42.

For 3 < a < 1000, find the sum of all rmax.


My first attempt at this problem was to change $(a-1)^n + (a + 1)^n$ to make it easier for coding purposes. And so I used the binomial theorem to come up with the following:

$(a-1)^n + (a + 1)^n$ = $n!\sum^n_{k = 0}\frac{a^k(1+(-1)^{n-k})}{k!(n-k)!}$

Obviously what I want to do now, is to maximize this new equation with the modulo. However, I cannot come up with how to do this. It may very well be that the original statement would be easier to simplify!

Nonetheless, I've come to ask: how can I maximize the value of $n!\sum^n_{k = 0}\frac{a^k(1+(-1)^{n-k})}{k!(n-k)!} \pmod{a^2}$ for a given $a$?

On this point, I would rather a hint, as opposed to a full answer. That would ruin the fun!

Note: I have a limited knowledge of calculus, and have yet to find the derivative of a modulo statement, or a summation. Would this need to be learned?

-

Hint: If you expand $(a-1)^n$, you will find that every term but two are multiples of $a^2$. Similarly for $(a+1)^n$. Hence you can have a much simpler expression, with no $\Sigma$, $\mod{a^2}$.