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

### 3 Responses to “Number Theory: Lecture 4”

If g is a primitive root mod p but not mod p^2 we use g+p instead; but g and g+p are the same thing mod p. So I started wondering whether there always exists a primitive root mod p^2 smaller than p. I did not come up with anything and if it is not the case it will probably be pretty hard to find a counterexample since the chance of g not being a primitive root mod p^2 is 1/p. However, I have found a website (http://primes.utm.edu/curios/page.php/40487.html) according to which there are not many p^2 such that the smallest primitive root mod p is not a primitive root mod p^2 and, more interestingly, that it is not known whether there are infinitely many of those.

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

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