## Number Theory: Lecture 5

In which we study the multiplicative groups $(\mathbb{Z}/p^j \mathbb{Z})^{\times}$.

• 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$ is coprime to $p$.  That is, $g^{p-1} \equiv 1 \pmod{p}$ but $g^{p-1} \not\equiv 1 \pmod{p^2}$. We saw last time that there is some primitive root $a$ modulo $p$; we proved this lemma by showing that either this $a$ or $a+p$ will do the job.
• Lemma 17: Let $p$ be a prime greater than 2, 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 on $j$, using the previous lemma to give the base case.
• Theorem 18: Let $p$ be a prime greater than 2, and let $j$ be a natural number.  Then $(\mathbb{Z}/p^j \mathbb{Z})^{\times}$ is cyclic.  We showed that the $g$ of the previous two lemmas is a primitive root modulo $p^j$ (so if $g$ is a primitive root modulo $p$ and also modulo $p^2$, then it is a primitive root modulo $p^j$ for all $j \geq 1$).  (Quick check: why did I bother to prove separately that $(\mathbb{Z}/p\mathbb{Z})^{\times}$ is cyclic, rather than deducing it as a special case of this theorem?)

You might well now wonder what the group $(\mathbb{Z}/2^j \mathbb{Z})^{\times}$ is like, and this would be a good question to investigate.  You could also try to classify those $n$ for which $(\mathbb{Z}/n\mathbb{Z})^{\times}$ is cyclic.  Baker (A concise introduction to the theory of numbers) deals with this 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.

#### Preparation for Lecture 6

Our next questions will be to do with when we can solve the congruence $x^2 \equiv a \pmod{p}$.  (We’ll look at moduli that aren’t prime too, but we’ll start with primes.)  Here are a few questions that you could usefully consider (you could try numerical examples to get a feel for what’s going on, then make some conjectures, and then try to prove those conjectures).

• How many squares are there modulo a prime $p$?  And how many proofs can you find for your answer?  (Example of what I mean: 1, 2 and 4 are squares modulo 7, because $1^2 \equiv 1 \pmod{7}$, $3^2 \equiv 2 \pmod{7}$, and $2^2 \equiv 4 \pmod{7}$, but 3, 5 and 6 are not squares modulo 7.  We tend not to worry too much about 0, since this is never going to be an interesting case.)
• Let $p$ be a prime.  Why must $a^{(p-1)/2}$ be congruent to $\pm 1$ modulo $p$?  Which $a$ give $+1$, and which give $-1$?
• For which primes $p$ is $-1$ a square?
• For which primes $p$ is $2$ a square?