Quadratic residue definition

Question

Why quadratic residue $\pmod n$ must be, by definition, relatively prime with $n$? So, for example $5$ is not quadratic residue modulo $10$? This seems unnatural. Any help?

Answer 1

There are two concepts here, hence two names:

• quadratic residue modulo $n$ = square in the group of units mod $n$

• square modulo $n$ = square in the ring of integers mod $n$

It seems the first one occurs more often.

Answer 2

Some authors include this requirement while others don’t. Wikipedia, for instance, doesn’t, but mentions this convention and explains why some authors adopt it:

Modulo a prime, the product of two nonresidues is a residue and the product of a nonresidue and a (nonzero) residue is a nonresidue. [...] Modulo a composite number, the product of two residues is a residue. The product of a residue and a nonresidue may be a residue, a nonresidue, or zero. [...] Also, the product of two nonresidues may be either a residue, a nonresidue, or zero. This phenomenon can best be described using the vocabulary of abstract algebra. The congruence classes relatively prime to the modulus are a group under multiplication, called the group of units of the ring $(\mathbb Z/n\mathbb Z)$, and the squares are a subgroup of it. Different nonresidues may belong to different cosets, and there is no simple rule that predicts which one their product will be in. Modulo a prime, there is only the subgroup of squares and a single coset.

The fact that, e.g., modulo $15$ the product of the nonresidues $3$ and $5$, or of the nonresidue $5$ and the residue $9$, or the two residues $9$ and $10$ are all zero comes from working in the full ring $(\mathbb Z/n\mathbb Z)$, which has zero divisors for composite $n$.

For this reason some authors add to the definition that a quadratic residue $a$ must not only be a square but must also be relatively prime to the modulus $n$.

One instance where you can see how adding this requirement can simplify things is the interpretation of the Jacobi symbol. The image caption in that article states that “if $k$ is a quadratic residue modulo a coprime $n$, then $\left(\frac kn\right)=1$”. If the coprimality requirement is included in the definition, this statement simplifies to “if $k$ is a quadratic residue, then $\left(\frac kn\right)=1$”.