3
$\begingroup$

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

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

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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