# Am I using the Legendre/Jacobi symbols correctly?

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.

• That is bogus. After all, the value will be 1, so if the Jacobi symbol truly determined when numbers are squares or not then this would mean every invertible number mod 25 is a square, or more generally mod $m^2$ for every odd $m$ and that is false. For example, $2 \bmod 9$ is not a square and $2 \bmod 25$ is not a square.
– KCd
Mar 25, 2015 at 0:50

The$\newcommand\leg{\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$.

• Where by "prime" you mean "odd prime". Mar 5, 2018 at 4:09