Let $d$ be a fixed, square-free integer, and let $M$ be some very large number. I would like to count the numbers $m \leq M$ such that $m \perp d$ and $d$ is a quadratic residue modulo $m$. Call this quanitity $S$. Are there some asymtpotics known for this quantity?
Obviously, $S \leq M$. On the other hand, if we just compute primes $p \leq M$ such that $d$ is a square modulo $p$, then we find: $$ S \gtrsim \frac{M}{\log M} \frac{\# \{ p \leq M, \text{ prime}, \ \left( {{d}\over{p}} \right) = 1 \} }{\#\{p \leq M, \text{ prime}\}} \geq \frac{M}{\log M} c $$ for some constant $c$. This is true because the primes with $\left( {{d}\over{p}} \right) = 1 $ have positive relative density, which can be deduced from quadratic reciprocity and Dirichlet's theorem. Thus, $M \geq S \gg \frac{M}{\log M}$. What better better bounds be given?
By quadratic reciprocity, the condition that $d$ is a quadratic residue modulo $m$ is equivalent to a certain pattern of requiring that $m$ is or is not a quadratic residue modulo $p$ for each prime $p\mid d$, where the pattern may depend on $m\bmod 4$. At any rate, each odd prime exactly multiplies the density of valid $m$ by $\frac{p-1}{2p}$ (this also uses the Chinese Remainder Theorem). So $$S\sim M\cdot\prod_{p\mid d}\frac{p-1}{2p} $$ if $d$ is odd. The case that $d$ is even is left as an exercise.