# How can I find out whether a number is a quadratic residue in a large modulo?

Without strenuous arithmetic.

What are the quadratic residues modulo $5^4$ or $5^5$?

Thanks!

-
wolframalpha.com/input/… for example. – Asaf Karagila Sep 25 '10 at 11:22

If you want to know the squares modulo $p^m$ where $p$ is an odd prime, they are congruent to $0$ or to numbers $a p^{2k}$ where $0\le k < m/2$ and the Legendre symbol $\left(\frac ap\right)=1$. For large primes $p$, Legendre symbols can be calculated by regarding them as Jacobi symbols and using the law of quadratic reciprocity for Jacobi symbols.

I don't regard $5$ as a large prime. :-)

-
And there are many freely available software packages that use arbitrary-precision integers and can efficiently compute Legendre symbols. In linux, Pari would be one. The underlying code is called the GNU Multi-Precision library. As Asaf Karagila points out, there are on-line applications as well. – Ryan Budney Sep 25 '10 at 16:55
Pari is also available for Windows and Mac OS X. – Charles Sep 27 '10 at 19:33

The Euler criterion is easily generalized to yield the following test for squareness (mod $\rm n\:$).

THEOREM $\$ Let $\rm\ a,\:n\:$ be integers, with $\rm\:a\:$ coprime to $\rm\:n\ =\ 2^e \:p_1^{e_1}\cdots p_k^{e_k}\:,\ \ p_i\:$ primes.

$\rm\quad\quad \ x^2\ =\ a\ \ (mod\ n)\$ is solvable for $\rm\:x\:$

$\rm\quad\quad \: \iff\ \ \: a^{(p_i\ -\ 1)/2} \ \ \equiv\ \ 1\ \ (mod\ p_i)\quad\quad\ \$ for all $\rm\ i\le k$

$\quad\quad\$ and $\rm\quad\ \ e>1 \:\Rightarrow\: a\equiv 1\ \ (mod\ 2^{2+\delta}\:),\ \ \ \delta = 1\ \ if\ \ e\ge 3\ \ else\ \ \delta = 0$

Proof: See Ireland and Rosen, A Classical Introduction to Modern Number Theory, Proposition 5.1.1 p.50.

The above criterion is practical if one knows a full factorization of $\rm\:n\:$, since the exponentiations may be quickly computed by repeated squaring.

BEWARE $\$ The criterion cannot be expressed equivalently as a simple Jacobi symbol calculation. For example we have $\rm(8|15) = 1\$ but $8$ is not a square (mod $15$).

-