Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Without strenuous arithmetic.

Is there a program I can download to do so?

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


share|cite|improve this question
2… 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. :-)

share|cite|improve this answer
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$).

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.