## Number Theory: Lecture 4

In which we study the structure of the multiplicative group $(\mathbb{Z}/p\mathbb{Z})^{\times}$, and start studying $(\mathbb{Z}/p^2\mathbb{Z})^{\times}$.

• Theorem 15: Let $p$ be prime.  Then the multiplicative group $(\mathbb{Z}/p\mathbb{Z})^{\times}$ is cyclic.  We proved this by showing that there are exactly $\phi(d)$ elements of order $d$, for each divisor $d$ of $p-1$.
• Definition of a primitive root modulo $p$.
• Lemma 16: Let $p$ be prime.  Then there is a primitive root modulo $p$, say $g$, such that $g^{p-1} = 1 + bp$ where $(b,p) = 1$.  We showed that if $a$ is a primitive root modulo $p$, then either $a$ or $a+p$ has the required additional property.
• Lemma 17: Let $p > 2$ be prime and let $j$ be a natural number.  Then there is a primitive root modulo $p$, say $g$, such that $g^{p^{j-1}(p-1)} \not\equiv 1 \pmod{p^{j+1}}$.  We proved this by induction, using similar ideas to those used in Lemma 16.

#### Understanding today’s lecture

Pick a prime $p$.  Can you find a generator (primitive root) modulo $p$?  How many can you find?  How little work can you get away with doing?  Can you write each element of the multiplicative group $(\mathbb{Z}/p\mathbb{Z})^{\times}$ as an explicit power of your primitive root?

Can you find any primes that have many primitive roots, or any primes that have very few primitive roots?

Pick a prime $p$.  Can you find a generator (primitive root) modulo $p^2$?  Modulo $p^3$?

Can you find an example to show that in Lemma 16 we cannot always use our first choice of primitive root $a$, we really do sometimes have to use $a+p$ instead?

Davenport (The Higher Arithmetic) presents a slightly different proof that $(\mathbb{Z}/p\mathbb{Z})^{\times}$ is cyclic; you might like to read that for another perspective.

#### Preparation for Lecture 5

Next time we’ll think about $(\mathbb{Z}/p^j \mathbb{Z})^{\times}$.  What structure will they turn out to have?