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

Without strenuous arithmetic.

Is there a program I can download to do so?

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

Thanks!

Solution 1:

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. :-)

Solution 2:

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