I am new to this and confused myself, but will try my best to explain the problem clearly.

An integer $a$ is a quadratic residue with respect to prime p if $a \equiv x^2 \mod{p}$ for some integer $x$.

Here are my questions:

1. Does $p$ need to be prime? I ask because definition from wolfram doesn't requires it to be so. And from Euler's criterion:

• If $a^\frac{p-1}{2} \equiv 1 \mod{p}$, it means $a$ is a quadratic residue module $p$.

• If $a^\frac{p-1}{2} \equiv -1 \mod{p}$, it means $a$ is a not a quadratic residue module $p$.

So if $p$ is not a prime then $a^{\frac{p-1}{2}}$ won't even be an integer. And so according to me it should be odd prime.

2. Should $0\lt x \lt p$ be true? What if we have $a\equiv x^2\mod{p}$, and $x \gt p$? The thing is I tried finding such $x$ by pen, but always found that there is always a $y \lt p$ such that $a\equiv y^2\mod{p}$. Is this always true? And how can we prove it?

• Quadratic residues are also defined for composite numbers. Euler's criterion deals in fact basically with odd primes. But $a^{p-1}\equiv 1\mod p$ can also be true for composite numbers (see Carmichael numbers or Fermat-pseudoprimes) Apr 2, 2018 at 12:08
• You can replace $x$ by its residue mod $p$ without changing $x^2$ modulo $p$ Apr 2, 2018 at 12:10
• It's just convenient to start exploring quadratic residues in $\mathbb Z_p$. Also, in $\mathbb Z_p$, we study $\bar x$ not $x$. In that case, $0 < x < p$ is irrelevant. Apr 2, 2018 at 12:12
• @Peter "You can replace $x$ by its residue $\mod p$ without changing $x^2 \mod p$". I can't understand this, can you please give an example? Apr 3, 2018 at 8:38
• @stevengregory excuse me for my ignorance, but what do you mean by: "we study $\bar x$ not $x$". Apr 3, 2018 at 8:39

For you second question, we usually choose $x<p$ for convenience. This is no loss of generality, since if $x\equiv x'\mod p$, then $x$ is a square $\bmod p$ if and only if $x'$ is. Computations with the Legendre symbol relies on this property and the fact this symbol is multiplicative.