Am I using the Legendre/Jacobi symbols correctly?

Question

I want to check if $21$ is a square $\mod 25$, so the Jacobi symbol is: ${21 \choose 25}$. $25$ is not a prime, so I can't split up the numerator yet for the Legendre symbol. So I prime factorize the denominator into ${21 \choose 5} {21 \choose 5}$. I can use the Legendre symbol now, so we get ${3 \choose 5} {7 \choose 5} {3 \choose 5} {7 \choose 5}$. Is this correct usage/justification of the steps so far? I want to make sure I am using the steps for the correct reasons, and not obtain the correct results just by coincidence.

Answer 1

The$\newcommand\leg[2]{\left(\frac{#1}{#2}\right)}\newcommand\Z{\mathbb Z}$ Jacobi symbol is not useful for determining whether something is a quadratic residue modulo a composite number. For example, if $p$ is prime, then $\leg a{p^2}$ is defined as $$\leg ap\cdot\leg ap=\leg ap^2$$ and thus it is always $0$ or $1$, even if $a$ is a non-residue modulo $p^2$.

---

A first check would be whether $21$ is a square modulo $5$. Indeed, $21\equiv1^2\pmod5$. There are two ways to proceed:

Trial and error. Try to find $a$ such that $a^2\equiv21\pmod{25}$. Because you need $a^2\equiv1\pmod5$, you only have to check the values of $a$ that are $\equiv\pm\,1\pmod5$.
It turns out that $11^2=121\equiv21\pmod{25}$.

A clever argument. The group $(\Z/25\Z)^\times$ has even order and is known to be cyclic. Hence exactly half of its elements are squares.
On the other hand, if $a$ is a square modulo $25$, then $a$ is a square modulo $5$. Exactly half of the elements in $(\Z/5\Z)^\times$ are squares.
This implies that if $5\nmid a$ then $a$ is a square modulo $25$ if (and only if) $a$ is a square modulo $5$.
Because $21$ is a square modulo $5$, we are done.

Remark. In general we have:

Let $p$ be prime and $p\nmid a$. If $a$ is a square modulo some $p^n$, $n\geqslant1$, then $a$ is a square modulo all $p^m$, $m\geqslant1$.