# Compute the number of integers $k$ such that $k\mid{f(k)}$

Let $n=2^83^95^{10}7^{11}$ and for $k$ a positive integer let $f(k)$ be the number of integers $0\leq x \leq n$ such that $x^2 \equiv k \pmod{n}$. Compute the number of integers $k$ such that $k\mid{f(k)}$.

I didn't see an easy way of counting the number of solutions $x$ to $x^2 \equiv k \pmod{n}$. If $k = 1$ then we need $n\mid(x^2-1) = (x-1)(x+1)$, but I didn't see how to generalize this argument for an arbitrary $k$.

• isnt the answer clearly infinite? for infinitely many values of $k$ we have $f(k)=0$. Dec 28, 2016 at 1:41
• @JorgeFernándezHidalgo Is there an easy way to prove the existence of a quadratic nonresidue without computation? Dec 28, 2016 at 1:46
• @ThomasGrubb The map $\mathbb{Z}/n\mathbb{Z} \rightarrow \mathbb{Z}/n\mathbb{Z}$ $x \mapsto x^2$ is not injective since $\pm 1 \mapsto 1$ so it cannot be surjective either Dec 28, 2016 at 1:48
• heck yeah my man, $-1$ is not a quadratic residue $\bmod 3$ and hence $-1$ is not a quadratic residue $\bmod n$. Dec 28, 2016 at 1:48
• or the other thing works too, also sorry if you aren't a man, I got carried on. Dec 28, 2016 at 1:49

Assume we are not considering the cases when $f(k) = 0.$ The number of solutions to $x^2 \equiv k$ mod $n$ is usually either $0$ or $16$, so we have to decide whether the divisors of $16$ are squares mod $n$.
Clearly $1,4,16$ are squares. However $2,8$ are not squares because they are already not squares mod $2^8$, since they are odd powers of $2$.
There are special cases when $k \equiv 0$ modulo one of the factors $2^8, 3^9, 5^{10}$, $7^{11}$ in which $f(k)$ can be smaller, but then $k$ is so large that $k | f(k)$ will never occur.