Difference between revisions of "2019 Mock AMC 10B Problems/Problem 22"
(One intermediate revision by the same user not shown) | |||
Line 2: | Line 2: | ||
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>. | 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>. | ||
+ | |||
+ | <math>\textbf{(A)}\ 40\qquad\textbf{(B)}\ 41\qquad\textbf{(C)}\ 42\qquad\textbf{(D)}\ 43\qquad\textbf{(E)}\ 44</math> | ||
==Solution== | ==Solution== | ||
− | <math>15^n - 7^n \equiv 7^n - 7^n \equiv 0</math> <math>\text{mod}</math> <math>8</math> for all integer <math>n > 0</math>. Therefore, <math>S = \{0, 8, 16, 24,...,248\}</math>. Since the sum of | + | <math>15^n - 7^n \equiv 7^n - 7^n \equiv 0</math> <math>\text{mod}</math> <math>8</math> for all integer <math>n > 0</math>. Therefore, <math>S = \{0, 8, 16, 24,...,248\}</math>. Since the sum of all 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>, the answer is <math>2 + 7 + 31 = \boxed{\text{(A)} 40}</math>. |
Latest revision as of 22:05, 3 November 2019
Problem
Let be the set of all possible remainders when
is divided by
, where
is a positive integer and
is the number of elements in
. The sum
can be expressed as
where
are positive integers and
and
are as small as possible. Find
.
Solution
for all integer
. Therefore,
. Since the sum of all elements in
is
, the answer is
.