HMMT February

Note that, if $k$ is relatively prime to $n$, there exists a unique $0<k^{-1}<n$ such that $k k^{-1} \equiv 1(\bmod n)$. Hence, if $k^{2} \not \equiv 1(\bmod n)$, we can pair $k$ with its inverse to get a product of 1. If $k^{2} \equiv 1(\bmod n)$, then $(n-k)^{2} \equiv 1(\bmod n)$ as well, and $k(n-k) \equiv-k^{2} \equiv-1(\bmod n)$. Hence these $k$ can be paired up as well, giving products of -1. When $n \neq 2$, there is no $k$ such that $k^{2} \equiv 1$ $(\bmod n)$ and $k \equiv n-k(\bmod n)$, so the total product $(\bmod n)$ is $(-1)^{\frac{m}{2}}$, where $m$ is the number of $k$ such that $k^{2} \equiv 1(\bmod n)$. For prime $p$ and positive integer $i$, the number of solutions to $k^{2} \equiv 1\left(\bmod p^{i}\right)$ is 2 if $p$ is odd, 4 if $p=2$ and $i \geq 3$, and 2 if $p=i=2$. So, by Chinese remainder theorem, if we want the product to be -1, we need $n=p^{k}, 2 p^{k}$, or 4. We can also manually check the $n=2$ case to work. Counting the number of integers in the allowed range that are of one of these forms (or, easier, doing complementary counting), we get an answer of 30. (Note that this complicated argument basically reduces to wanting a primitive root.)