Number Theory: Lecture 6

In which we meet quadratic residues.

Definition of quadratic residue and quadratic non-residue.
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?)

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…

Like this:

One blogger likes this post.

This entry was posted on October 19, 2011 at 12:08 pm and is filed under Cambridge Maths Tripos, II Number Theory, Lecture. You can follow any responses to this entry through the RSS 2.0 feed. You can leave a response, or trackback from your own site.

3 Responses to “Number Theory: Lecture 6”

Number Theory: Lecture 7 « Theorem of the week Says:
October 21, 2011 at 12:08 pm
[...] Theorem of the week Expositions of interesting mathematical results « Number Theory: Lecture 6 [...]
Number Theory: Lecture 8 « Theorem of the week Says:
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 [...]
Number Theory: Lecture 20 « Theorem of the week Says:
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 [...]

Theorem of the week

Number Theory: Lecture 6

Further reading

Preparation for Lecture 7

Like this:

3 Responses to “Number Theory: Lecture 6”

Leave a Reply Cancel reply

Follow “Theorem of the week”