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?

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 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}?

2 Responses to “Number Theory: Lecture 6”

  1. Number Theory: Lecture 20 | Theorem of the week Says:

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

  2. Number Theory: Lecture 21 | Theorem of the week Says:

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

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: