## Number Theory: Lecture 6

In which we study quadratic residues, and meet Euler‘s criterion

• Theorem 20 (Euler’s criterion): Let $p$ be an odd prime, and let $a$ be an integer.  Then $a^{\frac{p-1}{2}} \equiv \genfrac{(}{)}{}{}{a}{p} \pmod{p}$.  We proved this by first showing that $a^{\frac{p-1}{2}} \equiv \pm 1 \pmod{p}$ and then using Lagrange’s theorem to show that the even powers of a primitive root ‘use up’ all the possible solutions to $x^{\frac{p-1}{2}} \equiv 1 \pmod{p}$.
• Corollary 21: The Legendre symbol is completely multiplicative.  That is, if $p$ is prime and $a$ and $b$ are integers, then $\genfrac{(}{)}{}{}{a}{p}\genfrac{(}{)}{}{}{b}{p} = \genfrac{(}{)}{}{}{ab}{p}$.  This followed from Euler’s criterion.  We noted that the possible values of $\genfrac{(}{)}{}{}{a}{p} \genfrac{(}{)}{}{}{b}{p}$ and $\genfrac{(}{)}{}{}{ab}{p}$ are $-1$, $0$ and $1$, so if they are congruent modulo $p$ then they are in fact equal.
• We used Corollary 21 to give a third proof of Lemma 19: we showed that $\displaystyle \sum_{a=1}^{p-1} \genfrac{(}{)}{}{}{a}{p} = 0$.
• Corollary 22: Let $p$ be an odd prime.  Then $\genfrac{(}{)}{}{}{-1}{p} = (-1)^{\frac{p-1}{2}}$.  That is, $-1$ is a quadratic residue if $p \equiv 1 \pmod{4}$ and $-1$ is a quadratic non-residue if $p \equiv 3 \pmod{4}$.  We proved this using Euler’s criterion and the fact that in this case once again congruence modulo $p$ implies equality.
• Definition of the notation $\langle b \rangle$ (or $\langle b \rangle_p$) for the unique number congruent to $b$ modulo $p$ that lies in the interval $[-\frac{p}{2},\frac{p}{2}]$.  (Note that this is not standard notation!)

I lectured this course two years ago, and wrote blog posts then too.  I’m writing these ones afresh (although I am copying and pasting some of the further reading), so if you don’t like my summaries this time then you could refer back to the corresponding posts from two years ago, when I might have summarised the material differently.  For example, here’s Lecture 6 from two years ago.

#### Understanding today’s lecture

Can you find another proof of Corollary 22 (not using Euler’s criterion)?  Perhaps you can do it using material from the Numbers & Sets course…

Can you build on the work we did today to find the primes for which $2$ is a quadratic residue?

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 presentation (or come up with your own alternative proofs).  Please suggest your own favourites in the comments below.

#### Preparation for Lecture 7

Can you come up with a useful way to compute $a^{\frac{p-1}{2}}$ modulo $p$, to help with finding $\genfrac{(}{)}{}{}{a}{p}$?

If $p$ and $q$ are odd primes, is there anything you can say about the relationship between $\genfrac{(}{)}{}{}{p}{q}$ and $\genfrac{(}{)}{}{}{q}{p}$?