HMMT February, 2016

Solution:

Note that, if $k$ is relatively prime to $n$, there exists a unique $0 < k^{-1} < n$ such that $k k^{-1} \equiv 1 \pmod{n}$. Hence, if $k^{2} \not\equiv 1 \pmod{n}$, we can pair $k$ with its inverse to get a product of $1$.

If $k^{2} \equiv 1 \pmod{n}$, then $(n-k)^{2} \equiv 1 \pmod{n}$ as well, and $k(n-k) \equiv -k^{2} \equiv -1 \pmod{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 \pmod{n}$ and $k \equiv n-k \pmod{n}$, so the total product $\pmod{n}$ is $(-1)^{\frac{m}{2}}$, where $m$ is the number of $k$ such that $k^{2} \equiv 1 \pmod{n}$.

For prime $p$ and positive integer $i$, the number of solutions to $k^{2} \equiv 1 \pmod{p^{i}}$ 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}$, $2p^{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$.