2
$\begingroup$

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?

$\endgroup$
8
  • $\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

1
$\begingroup$

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.

$\endgroup$

You must log in to answer this question.

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