## 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$.
• 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).

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?