2
$\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$
2
  • 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, 2014 at 12:04
  • $\begingroup$ @Mike, done.${}$ $\endgroup$
    – Gerry Myerson
    Nov 20, 2014 at 1:29

2 Answers 2

Reset to default
4
$\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$
6
  • $\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, 2014 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, 2014 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, 2014 at 13:32
  • $\begingroup$ Here, you go modulo 10; I can't seem to think of an example with primes. $\endgroup$
    – shardulc
    Nov 19, 2014 at 16:10
  • 1
    $\begingroup$ When you work modulo 7, $2^{1/2}=\pm3$. $\endgroup$
    – Gerry Myerson
    Nov 19, 2014 at 23:06

You must log in to answer this question.

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