*In which we meet quadratic residues.*

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

#### Further reading

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 and are two primes, what is the relationship between and ? As usual, try some numerical examples and make some conjectures…

October 21, 2011 at 12:08 pm

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

October 24, 2011 at 12:20 pm

[…] 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 […]

November 21, 2011 at 12:10 pm

[…] 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 […]

October 23, 2013 at 10:51 am

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