Question regarding quadratic residue 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:


*

*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.

*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?

For the definition of a quadratic residue, the modulus doesn't have to be a prime number. However, the law of quadratic reciprocity is valid for primes.
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.
