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

- Theorem 20 (Euler’s criterion):
*Let be an odd prime, and let be an integer. Then .*We proved this by first showing that and then using Lagrange’s theorem to show that the even powers of a primitive root ‘use up’ all the possible solutions to . - Corollary 21:
*The Legendre symbol is completely multiplicative. That is, if is prime and and are integers, then .*This followed from Euler’s criterion. We noted that the possible values of and are , and , so if they are congruent modulo then they are in fact equal. - We used Corollary 21 to give a third proof of Lemma 19: we showed that .
- Corollary 22:
*Let be an odd prime. Then . That is, is a quadratic residue if and is a quadratic non-residue if .*We proved this using Euler’s criterion and the fact that in this case once again congruence modulo implies equality. - Definition of the notation (or ) for the unique number congruent to modulo that lies in the interval . (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 is a quadratic residue?

#### 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 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 modulo , to help with finding ?

If and are odd primes, is there anything you can say about the relationship between and ?

November 25, 2013 at 11:33 am

[…] a few results 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 […]

November 27, 2013 at 11:31 am

[…] example of a result of the form “if is prime, then …”. Another such result is Euler’s criterion. Does that give us anything useful for primality testing? It would be useful if you tested a […]