1
$\begingroup$

While reading the book What is Mathematics? by Courant and Robbins, I've found a statement that I don't know how to prove, although it seems that it shouldn't be really difficult. Literally, they write:

We have just seen that every quadratic residue $a$ of $p$ satisfies the congruence $a^{(p-1)/2} \equiv 1$ (mod $p$). Whithout serious difficulty it can be proved that for every non-residue $b$ we have the congruence $b^{(p-1)/2} \equiv -1$ (mod $p$).

Here, $p$ is a prime number and $a$ and $b$ are any integers not multiples of $p$. The case of quadratic residues is quite easy, you only have to apply Fermat's little theorem, but although they say that it can be proved whithout serious difficulty, I can't see how to do the case of non-residues. I've been looking on the Internet for some ideas, but my knolewdge of the theory of numbers is quite elementary (in fact, I only know some facts which are mentioned in the book: congruences, Fermat's little theorem, ...) and all the proofs I've found are out of my reach. Is there any elementary proof of the fact that $b^{(p-1)/2} \equiv -1$ (mod $p$)?

$\endgroup$
  • 1
    $\begingroup$ A polynomial of degree $d$, considered modulo a prime, can have no more than $d$ zeros. There are $(p-1)/2$ quadratic residues, which uses up all the room for zeros of $x^{(p-1)/2}-1$. $\endgroup$ – Gerry Myerson Nov 19 '14 at 12:04
  • $\begingroup$ @Mike, done.${}$ $\endgroup$ – Gerry Myerson Nov 20 '14 at 1:29
2
$\begingroup$

Let $b$ be a quadratic non-residue modulo a prime $p$. Let $c=b^{(p-1)/2}$. By Fermat, $c^2\equiv1\pmod p$. It follows that either $c\equiv1\pmod p$ or else $c\equiv-1\pmod p$. Now, the congruence $x^{(p-1)/2}\equiv1\pmod p$ is of degree $(p-1)/2$ and has among its solutions all the quadratic residues, of which there are exactly $(p-1)/2$; therefore, its only solutions are the quadratic residues. So, we can't have $c\equiv1\pmod p$, and we must have $c\equiv-1\pmod p$.

We have used the fact that the integers modulo a prime form a field, and over a field the number of zeros of a polynomial can't exceed the degree of the polynomial.

$\endgroup$
-1
$\begingroup$

Note that $b^{p-1} \equiv 1 \pmod{p}$, assuming $p$ is a prime which does not divide $b$. Taking the square root of both sides, we get $b^{(p-1)/2} \equiv \pm 1 \pmod{p}$. Of course, it cannot be $1$, because it would then be a quadratic residue, so it has to be $-1$.

$\endgroup$
  • $\begingroup$ Yes, that was my first try... Maybe I'm losing something, but I can't see why if $b^{(p-1)/2} \equiv 1$ (mod $p$) then $b$ is a quadratic residue. The converse is obviously true, for if $b \equiv x^2$ (mod $p$) for some $x$ then $b^{(p-1)/2} \equiv x^{p-1} \equiv 1$ (mod $p$) because of Fermat's little theorem. $\endgroup$ – Alex V. Nov 19 '14 at 11:20
  • $\begingroup$ $b^{(p-1)/2}$ is nothing but $(b^{\frac{1}{2}})^{p-1}$, and it is congruent to $1$ modulo $p$. Thus $b^{\frac{1}{2}}$ is an integer, and $b$ is a square modulo $p$. $\endgroup$ – shardulc Nov 19 '14 at 11:26
  • 2
    $\begingroup$ I don't think that's a valid reasoning... You also have $$ 3^4 = 81 \equiv 1 \;(\text{mod }10) $$ And with your idea we could conclude that $3^{1/2}$ is an integer, because $(3^{1/2})^8 \equiv 1$ (mod $10$). $\endgroup$ – Alex V. Nov 19 '14 at 13:32
  • $\begingroup$ Here, you go modulo 10; I can't seem to think of an example with primes. $\endgroup$ – shardulc Nov 19 '14 at 16:10
  • 1
    $\begingroup$ When you work modulo 7, $2^{1/2}=\pm3$. $\endgroup$ – Gerry Myerson Nov 19 '14 at 23:06

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.