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?

  • $\begingroup$ 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) $\endgroup$
    – Peter
    Apr 2, 2018 at 12:08
  • $\begingroup$ You can replace $x$ by its residue mod $p$ without changing $x^2$ modulo $p$ $\endgroup$
    – Peter
    Apr 2, 2018 at 12:10
  • $\begingroup$ 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. $\endgroup$ Apr 2, 2018 at 12:12
  • $\begingroup$ @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? $\endgroup$
    – shiva
    Apr 3, 2018 at 8:38
  • $\begingroup$ @stevengregory excuse me for my ignorance, but what do you mean by: "we study $\bar x$ not $x$". $\endgroup$
    – shiva
    Apr 3, 2018 at 8:39

1 Answer 1


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.


You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .