## Number Theory: Lecture 6

In which we meet quadratic residues.

• Lemma 19: Let $p$ be an odd prime.  Then there are exactly $(p-1)/2$ quadratic residues modulo $p$ (and so $(p-1)/2$ quadratic non-residues).  During the course of the lecture, we saw three proofs of this.  In one we proved that $x^2 \equiv y^2 \pmod{p}$ if and only if $x \equiv \pm y \pmod{p}$, which gives the result.  In the second, we used the existence of a primitive root modulo $p$, say $g$, and showed that $g^i$ is a quadratic residue if and only if $i$ is even.  And in the third we studied the sum $\sum_{a = 1}^{p-1} \genfrac{(}{)}{}{}{a}{p}$ (but this came a little later in the lecture).
• Definition of the Legendre symbol $\genfrac{(}{)}{}{}{a}{p}$ for prime $p$.
• Theorem 20 (Euler‘s criterion): Let $p$ be an odd prime, and let $a$ be an integer.  Then $a^{(p-1)/2} \equiv \genfrac{(}{)}{}{}{a}{p} \pmod{p}$.  This is interesting only when $a$ is coprime to $p$.  From Fermat’s Little Theorem (in Lecture 2), we know that $a^{p-1} \equiv 1 \pmod{p}$, and we can then deduce that $a^{(p-1)/2} \equiv \pm 1 \pmod{p}$.  We can take a primitive root $g$ modulo $p$, and writing $a = g^i$, we find that $a^{(p-1)/2} \equiv 1 \pmod{p}$ if and only if the index $i$ is even, and as above that occurs if and only if $a$ is a quadratic residue modulo $p$.
• Corollary 21: The Legendre symbol is totally multiplicative, in the sense that if $p$ is a prime then for any integers $a$ and $b$ we have $\genfrac{(}{)}{}{}{a}{p} \genfrac{(}{)}{}{}{b}{p} = \genfrac{(}{)}{}{}{ab}{p}$.  We also viewed this as saying that the map $\chi : (\mathbb{Z}/p\mathbb{Z})^{\times} \to \{-1,1\}$ defined by $\chi(a) = \genfrac{(}{)}{}{}{a}{p}$ is a group homomorphism.  Using Euler’s criterion (when $p$ is odd), we deduced that $\genfrac{(}{)}{}{}{a}{p} \genfrac{(}{)}{}{}{b}{p}$ and $\genfrac{(}{)}{}{}{ab}{p}$ must be congruent modulo $p$, and since both sides come from the set $\{-1, 0, 1\}$ we must in fact have equality.
• Corollary 22: Let $p$ be an odd prime.  Then $\genfrac{(}{)}{}{}{-1}{p} = (-1)^{(p-1)/2}$.  That is, $-1$ is a quadratic residue modulo $p$ if $p \equiv 1 \pmod{4}$, and is a quadratic non-residue modulo $p$ if $p \equiv 3 \pmod{4}$.  This follows immediately from Euler’s criterion.  (Can you also prove it without Euler’s criterion, using just knowledge from IA Numbers and Sets?)

Davenport (The Higher Arithmetic), Baker (A concise introduction to the theory of numbers) and the other usual classics cover this.  There are various ways of covering the material from this lecture; you might like to read another one.  Please suggest your own favourites in the comments below.

#### Preparation for Lecture 7

How many of the questions from the end of the last post can you now answer?

In addition, here is another question.  We’re going to be interested in links between primes.  If $p$ and $q$ are two primes, what is the relationship between $\genfrac{(}{)}{}{}{p}{q}$ and $\genfrac{(}{)}{}{}{q}{p}$?  As usual, try some numerical examples and make some conjectures…

### 4 Responses to “Number Theory: Lecture 6”

1. Number Theory: Lecture 7 « Theorem of the week Says:

[…] Theorem of the week Expositions of interesting mathematical results « Number Theory: Lecture 6 […]

2. Number Theory: Lecture 8 « Theorem of the week Says:

[…] of the Jacobi symbol and the multiplicative property of the Legendre symbol (which we saw in Lecture 6), and the latter from the definition of the Jacobi […]

3. Number Theory: Lecture 20 « Theorem of the week Says:

[…] of the form “If is prime, then …”, for example Fermat’s Little Theorem and Euler’s criterion.  It would be helpful to go back to those two results in particular, to think about whether the […]

4. Number Theory: Lecture 6 | Theorem of the week Says:

[…] two years ago, when I might have summarised the material differently.  For example, here’s Lecture 6 from two years […]