HMMT November, 2015

Solution:
Call a number good if it is not bad. We claim all good numbers are products of distinct primes, none of which are equivalent to $1$ modulo another.

We first show that all such numbers are good. Consider $n = p_{1} p_{2} \ldots p_{k}$, and let $x$ be a number satisfying $x \equiv c \pmod{p_{1} p_{2} \ldots p_{k}}$ and $x \equiv 1 \pmod{(p_{1}-1)(p_{2}-1) \ldots (p_{k}-1)}$. Since, by assumption, $p_{1} p_{2} \ldots p_{k}$ and $(p_{1}-1)(p_{2}-1) \ldots (p_{k}-1)$ are relatively prime, such an $x$ must exist by CRT. Then $x^{x} \equiv c^{1} = c \pmod{n}$, for any $c$, as desired.

We now show that all other numbers are bad. Suppose that there exist some $p_{1}, p_{2} \mid n$ such that $\gcd(p_{1}, p_{2}-1) \neq 1$ (which must hold for some two primes by assumption), and hence $\gcd(p_{1}, p_{2}-1) = p_{1}$. Consider some $c$ for which $p_{1} c$ is not a $p_{1}$th power modulo $p_{2}$, which must exist as $p_{1} c$ can take any value modulo $p_{2}$ (as $p_{1}, p_{2}$ are relatively prime). We then claim that $x^{x} \equiv p_{1} c \pmod{n}$ is not solvable.

Since $p_{1} p_{2} \mid n$, we have $x^{x} \equiv p_{1} c \pmod{p_{1} p_{2}}$, hence $p_{1} \mid x$. But then $x^{x} \equiv p_{1} c$ is a $p_{1}$th power modulo $p_{2}$ as $p_{1} \mid x$, contradicting our choice of $c$. As a result, all such numbers are bad.

Finally, it is easy to see that $n$ is bad if it is not squarefree. If $p_{1}$ divides $n$ twice, then letting $c = p_{1}$ makes the given equivalence unsolvable.

Hence, there are $16$ numbers (13 primes: $2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41$; and 3 semiprimes: $3 \cdot 5 = 15$, $3 \cdot 11 = 33$, $5 \cdot 7 = 35$) that are good, which means that $41 - 16 = 25$ numbers are bad.