Show that

$$p \equiv 3\pmod 4~\land~\pmatrix{\frac{a}{p}}=-1~\rightarrow~ \pmatrix{\frac{a-1}{p}}=1$$

where p is a prime number and $\pmatrix{\frac{a}{p}}$ is a Legendre symbol.

This was incurred during I was studying to prove that

$$p: \text{odd prime}~\rightarrow~\text{There exist}~x,y:~x^2+y^2+1\equiv0 \pmod p~\land~0 \le x,y \le \frac{p-1}{2} $$

In the book, first it proves this theorem by using the concept of sets. Later, it also proves this theorem by using the Legendre symbol. On the way, it tries to show that when $p \equiv 3 \pmod4$, there exist $a$ which is a quadratic nonresidue of p. So $(-a)$ is a quadaratic residue of p, which means for some x,

$$x^2 \equiv -a \pmod p$$

Now we have to show that for some y,

$$y^2 \equiv a-1 \pmod p$$

which is exactly the same statement of the question I suggested. Actually, the book assumed that $a$ is the least possitive quadratic nonresidue, but I doubt if I should add that assumption. So it would be glad if someone could say to me if this assumption is required or not, too.

What I've tried is to solve this is by using Euler's Criterion, which means

$$(a-1)^{(p-1)/2} \equiv 1 \pmod p$$

But I got stuck... It seems to be really easy but... I failed, sadly.


  • 7
    $\begingroup$ "Actually, the book assumed that a is the least possitive quadratic nonresidue, but I doubt if I should add that assumption." You should. For example $$\left(\frac{8}{11}\right) = \left(\frac{7}{11}\right) = -1.$$ But if $a$ is the least quadratic nonresidue, then by the minimality $a-1$ is a quadratic residue. $\endgroup$ – Daniel Fischer Nov 15 '13 at 21:34
  • $\begingroup$ @DanielFischer Thanks, but I still cannot understand the logic 'by the minimality'. I think it should be very easy but I feel like I became a dumb for a while... $\endgroup$ – Taxxi Nov 15 '13 at 21:42
  • $\begingroup$ The least nonresidue means $1,\dotsc, a-1$ are all quadratic residues. (Worth noting, the least nonresidue is always a prime.) $\endgroup$ – Daniel Fischer Nov 15 '13 at 21:43
  • $\begingroup$ @DanielFischer Oh my shame... thanks $\endgroup$ – Taxxi Nov 15 '13 at 21:45

Lest it remains unanswered:

The assumption that $a$ is the least (positive) quadratic nonresidue is important. With that assumption, we have that $1,\, \dotsc,\, a-1$ are quadratic residues by definition of the least positive nonresidue, so the existence of a $y$ with $y^2 \equiv a-1 \pmod{p}$ follows directly.

Without that assumption, $a-1$ can be a quadratic nonresidue too, for example

$$\left(\frac{8}{11}\right) = \left(\frac{7}{11}\right) = -1.$$


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.