View source for 2019 Mock AMC 10B Problems/Problem 22

==Problem==

Let <math>S = \{r_1, r_2, r_3, ..., r_{\mu}\}</math> be the set of all possible remainders when <math>15^{n} - 7^{n}</math> is divided by <math>256</math>, where <math>n</math> is a positive integer and <math>\mu</math> is the number of elements in <math>S</math>. The sum <math>r_1 + r_2 + r_3 + ... + r_{\mu}</math> can be expressed as<cmath>p^qr,</cmath>where <math>p, q, r</math> are positive integers and <math>p</math> and <math>r</math> are as small as possible. Find <math>p+q+r</math>.

==Solution==

S15^n - 7^n =\equiv 7^n - 7^n \equiv 0<math> </math>\text{mod}<math> </math>8<math> for all integer </math>n<math>. Therefore, </math>S = \{0, 8, 16, 24,...,248\}<math>. Since the sum of the elements in </math>S<math> is </math>8 + 16 + 24 + ... + 248 = 8(1 + 2 + 3 + ... + 31) = 8 \cdot \frac{31(31 + 1)}{2} = 2^7 \cdot 31<math>, so the answer is </math>2 + 7 + 31 = \boxed{\text{(A)} 40}$.