Problem 120

Square remainders

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

**
These problems are part of
Project Euler
and are licensed under
CC BY-NC-SA 2.0 UK
**