Problem:
For how many even positive integers $n$ does the number $18^{18}$ leave a remainder of $\frac{n}{2}$ when divided by $n$?
$\textbf{(A) } 0 \qquad \textbf{(B) } 19 \qquad \textbf{(C) } 37 \qquad \textbf{(D) } 361 \qquad \textbf{(E) } 703$
Solution:
Let the number of complete "groups" the number $18^{18}$ is divided into be an integer $k$. Then, we have $$nk + \frac{n}{2} = 18^{18}$$
$$\implies n(k+\frac{1}{2})=18^{18}=2^{18} \cdot 3^{36}$$
$$\implies n(2k+1)=2^{19} \cdot 3^{36} \qquad (\star)$$
Note that $2k+1$ is an odd number, and looking at the RHS, we can conclude that it must be a power of $3$. Specifically, it can take on the values $3^0, 3^1, 3^2, \dots, 3^{36}$. For every possible value of $k$ in this list, there exists a value of $n$ which can be found from $(\star)$. Hence, there are $37$ values of $n$, which is answer choice $\boxed{\textbf{(C)}}$.
Comments
Post a Comment