Quadratic residues mod 100000

Question

I was trying to solve a problem and it reduced to proving that none of the numbers $19910,19911,19912,...,19919$ were quadratic residues$\mod 10^5$. I found that the only quadratic residue mod 100 in the set {10,11,...19} is 16, so the problem reduces to proving there is no x such that $x^2 \equiv 19916 \mod 100000$, or equivalently, $k^2 \equiv 4979 \mod 25000$. This is where I got stuck. How would I finish off the proof?

Answer 1

Rather than work modulo $100000$, it's easier to work modulo some smaller factors of it that are sufficient. In particular, we only need to consider $2^5$ and $5^5$ separately: if a solution exists modulo $2^i$ and modulo $5^j$, then by the Chinese Remainder Theorem, a solution exists modulo $2^i \cdot 5^j$.

As you notice, $19916$ is divisible by $4$, so working modulo powers of $2$, we only need to check $4979$ instead. Everything is a quadratic residue modulo $2$, so we try $4979 \bmod 4$ and get $3$. There is no $k$ such that $k^2 \equiv 4979 \equiv 3 \pmod 4$, so there is no $k$ such that $k^2 \equiv 4979 \pmod {25000}$.

---

In fact, this produces easier solutions to the other cases, as well. The only values of $b$ such that $x^2 \equiv b \pmod {16}$ has a solution are $b = 0, 1, 4, 9$, so this only leaves $19913$ to consider, because $$19910, 19911, \dots, 19919 \equiv 6, 7, \dots, 15 \pmod {16}$$ respectively. But $x^2 \equiv 19913 \pmod 5$ has no solution, because $x^2 \equiv 3 \pmod 5$ has no solution.