Number Theory: Lecture 5

In which we study the structure of the multiplicative group (\mathbb{Z}/p^j \mathbb{Z})^{\times} and start thinking about quadratic residues.

  • Theorem 18: Let p > 2 be a prime and let j be a natural number.  Then (\mathbb{Z}/p^j \mathbb{Z})^{\times} is cyclic.  We proved that the g given by Lemma 17 has order \phi(p^i) = p^{i-1}(p-1) modulo p^i, for each i \geq 1.
  • Definition of quadratic residues and quadratic non-residues.
  • Lemma 19: Let p be an odd prime.  Then there are exactly \frac{p-1}{2} quadratic residues modulo p (and so \frac{p-1}{2} quadratic non-residues).  We gave two proofs of this.  For the first, we thought about when we have x^2 \equiv y^2 \pmod{p}.  For the second, we thought about which powers of a primitive root are quadratic residues.  Both proofs have ideas that are useful elsewhere.
  • Definition of the Legendre symbol.

Understanding today’s lecture

I suggested three exercises during the lecture.

What is the structure of (\mathbb{Z}/2^j \mathbb{Z})^{\times}?

For which n is (\mathbb{Z}/n \mathbb{Z})^{\times} cyclic?

If g is a primitive root modulo p^2, must it also be a primitive root modulo p?

You could also practise evaluating some Legendre symbols (with actual numbers).

Further reading

Baker (A concise introduction to the theory of numbers) deals with some of the exercises I suggested above and the material from today’s lecture in an extremely concise way; Jones and Jones (Elementary Number Theory) explain it in gory detail, with examples.  Take your pick.

Preparation for Lecture 6

We know from Fermat’s Little Theorem that if p is prime and a is coprime to p then a^{p-1} \equiv 1 \pmod{p}.  Why does that mean that a^{\frac{p-1}{2}} \equiv \pm 1 \pmod{p}?  Which a give +1 and which give -1?

For which primes p is -1 a quadratic residue?

For which primes p is 2 a quadratic residue?

Advertisements

One Response to “Number Theory: Lecture 5”

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

    […] Expositions of interesting mathematical results « Number Theory: Lecture 5 […]

Leave a Reply

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

WordPress.com Logo

You are commenting using your WordPress.com 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: