1
$\begingroup$

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$.

$\endgroup$
8
  • 1
    $\begingroup$ isnt the answer clearly infinite? for infinitely many values of $k$ we have $f(k)=0$. $\endgroup$
    – Asinomás
    Dec 28, 2016 at 1:41
  • $\begingroup$ @JorgeFernándezHidalgo Is there an easy way to prove the existence of a quadratic nonresidue without computation? $\endgroup$
    – TomGrubb
    Dec 28, 2016 at 1:46
  • 1
    $\begingroup$ @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 $\endgroup$
    – user399601
    Dec 28, 2016 at 1:48
  • $\begingroup$ heck yeah my man, $-1$ is not a quadratic residue $\bmod 3$ and hence $-1$ is not a quadratic residue $\bmod n$. $\endgroup$
    – Asinomás
    Dec 28, 2016 at 1:48
  • $\begingroup$ or the other thing works too, also sorry if you aren't a man, I got carried on. $\endgroup$
    – Asinomás
    Dec 28, 2016 at 1:49

1 Answer 1

0
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.