Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question

1 Answer 1

up vote 1 down vote accepted

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}$.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.