# Finding all possible remainders of perfect squares mod $n$, $n\in \mathbb{Z_+}$

Is there a way to generalize what remainders of perfect squares to expect for different bases. for $a^2\equiv 0,1 \text{ mod } 3$. but what about $a^2\equiv r \text{ mod } n \in \mathbb{Z_+}$. For e.g if I want to know all the possible remainders $r$ for $a^2$ mod $117$, then will it still have $0,1$, if not, then how can I find all the remainders?

Edit Well clearly for the e.g I provided we'd have all $a^2\leq 117$ in $r$, but I guess the question was whether or not the $r$ that appear in base $5$ will also appear in base $22$, and the $r$ in base $q$ will also appear in base $k$, s.t $q<k$

Thanks

• en.wikipedia.org/wiki/Quadratic_residue – Mason Jul 14 '18 at 21:23
• For $n$ prime, it is always half of the non-zero remainders, and you can use quadratic reciprocity to check any particular $r$. – Thomas Andrews Jul 14 '18 at 21:23
• $0$ and $1$ will always be residues of perfect squares to any modulus, but there will generally be others. – Joffan Jul 14 '18 at 23:14

Yes, there's some machinery you can use to figure out if $r$ is a remainder of a perfect square mod $n$. These $r$'s are called quadratic residues, and the main technique at play to see if $r$ is a quadratic residue is quadratic reciprocity and properties of Legendre symbols.