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$: $6^3 + 8^3 = 728 \equiv 42 \mod 49$. And as $n$ varies, so too will $r$, but for $a = 7$ it turns out that $r_{\mathrm{max}} = 42$.
For $3 \le a \le 1000$, find $\sum r_{\mathrm{max}}$.
This problem can be solved using a bit of number theory and modular arithmetic. The trick to this problem is to realize the remainder $r$ depends on whether $n$ is odd or even.
When $n$ is even, we see that:
$$(a – 1)^n \equiv 1 \mod a^2$$
$$(a + 1)^n \equiv 1 \mod a^2$$
That’s because when expanding the binomial, all terms except for the last will have an $a$ in them and be divisible by $a^2$, and the last term $(\pm a)^0 \equiv 1 \mod a^2$.
Adding these two congruences, we get:
$$(a – 1)^n + (a + 1)^n \equiv 2 \mod a^2$$
So when $n$ is even, the remainder is simply $2$.
When $n$ is odd, we have:
$$(a – 1)^n \equiv -1 \mod a^2$$
$$(a + 1)^n \equiv 1 \mod a^2$$
The argument is similar to the one for even $n$, just that the last term is $(\pm a)^1 \equiv \pm1 \mod a^2$ in each case.
Adding these two congruences, we get:
$$(a – 1)^n + (a + 1)^n \equiv 0 \mod a^2$$
So when $n$ is odd, the remainder is $0$.
From here, it’s clear that the maximum remainder $r_{\mathrm{max}}$ for any $a$ occurs when $n$ is even, and $r_{\mathrm{max}} = 2$.
For $3 \le a \le 1000$, we simply compute $2*(1000-3+1) = 2*998 = 1996$.
Hence, the sum of all the $r_{\mathrm{max}}$ is $1996$.
More Answers:
[next_post_link]