## Square remainders

### Problem 120

Published on Friday, 21st April 2006, 06:00 pm; Solved by 8625; Difficulty rating: 25%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 ≡ 42 mod 49. And as *n* varies, so too will *r*, but for *a* = 7 it turns out that *r*_{max} = 42.

For 3 ≤ *a* ≤ 1000, find ∑ *r*_{max}.