2021 Fall OMC 10 #13

Problem:

For how many even positive integers $n$ does the number ${18}^{18}$ leave a remainder of $\frac{n}{2}$ when divided by $n$?

$\mathbf{\text{(A) }}0\mathbf{\text{(B) }}19\mathbf{\text{(C) }}37\mathbf{\text{(D) }}361\mathbf{\text{(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}$$

$$⟹n(k+\frac{1}{2})={18}^{18}=2^{18}\cdot 3^{36}$$

$$⟹n(2k+1)=2^{19}\cdot 3^{36}(\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{{\displaystyle \mathbf{\text{(C)}}}}$.