Number Theory: Lecture 4

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

We saw last time that we could reduce the problem of understanding the multiplicative group $(\mathbb{Z}/n\mathbb{Z})^{\times}$ to studying the groups $(\mathbb{Z}/p^j \mathbb{Z})^{\times}$ for primes $p$ and for $j\geq 1$ . Today we began on this new task, starting with the case of $(\mathbb{Z}/p \mathbb{Z})^{\times}$ for prime $p$ .

Lemma 13: For any $n$ , we have $\sum_{d|n} \phi(d) = n$ (where the sum is over all divisors $d$ of $n$ ). We proved first that the function $F(n) := \sum_{d|n} \phi(d)$ is multiplicative, and then that $F(p^j) = p^j$ when $p$ is prime. We also noted that the only property of $\phi$ that we used to show that $F$ is multiplicative is that $\phi$ is multiplicative, and so our proof showed that if $f : \mathbb{N} \to \mathbb{N}$ is a multiplicative function, then $\sum_{d|n} f(d)$ is also multiplicative.
Theorem 14 (Lagrange): Let $p$ be a prime. Let $f(x) = a_n x^n + a_{n-1} x^{n-1} + \dotsb + a_1 x + a_0$ be a polynomial with integer coefficients, with $a_n$ not divisible by $p$ . Then the polynomial congruence $f(x) \equiv 0 \pmod{p}$ has at most $n$ solutions. We saw that this can be proved in a similar way to the analogous result in ordinary arithmetic (by induction on the degree of the polynomial), making use of the fact that $ab \equiv 0 \pmod{p}$ implies $a \equiv 0 \pmod{p}$ or $b \equiv 0 \pmod{p}$ (that is, $\mathbb{Z}/p\mathbb{Z}$ is an integral domain). We saw an example that shows that the result does not hold if the requirement that $p$ is prime is relaxed. We also saw that the result does not (indeed, cannot) tell us that the congruence has exactly $n$ solutions, because there are some polynomial congruences with fewer (indeed, with none).
Theorem 15: Let $p$ be a prime. Then the multiplicative group $(\mathbb{Z}/p\mathbb{Z})^{\times}$ is cyclic. That is, there is some element $a$ so that the $p-1$ numbers $1$ , $a$ , $a^2$ , …, $a^{p-2}$ give the whole group. We call such an element $a$ a primitive root modulo $p$ . (Quick check: find all the primitive roots modulo 11, for example. Try to do this with as little work as possible! Can you say anything interesting about which primes have many primitive roots and which have only a few?) We proved this by showing that in $(\mathbb{Z}/p\mathbb{Z})^{\times}$ , for each divisor $d$ of $p-1$ there are exactly $\phi(d)$ elements of order $d$ .
Definition of primitive roots (in the statement of the above result).

Postscript

I had a question via e-mail from someone who wasn’t quite comfortable with part of the proof that $(\mathbb{Z}/p\mathbb{Z})^{\times}$ is cyclic. That particular part was the point where I mentioned during the lecture that we were going to use an idea repeatedly, so I’d like people to be clear about it. I’ll state the more general fact here, and hopefully that will be useful to you when you’re working through your lecture notes.

Lemma: Let $G$ be a finite group, and let $g$ be an element of $G$ with order $k$ . Suppose that $g^d = 1$ (using multiplicative notation, so $1$ is the multiplicative identity in $G$ ). Then $k|d$ . How could you prove this? You’d like to show that $k$ divides $d$ , so why not try dividing $d$ by $k$ , to get say $d = qk + r$ where $0 \leq r < k$ ? Then what might you do?

Preparation for Lecture 5

Next time we’ll move on to $(\mathbb{Z}/p^j \mathbb{Z})^{\times}$ . Will these groups also turn out to be cyclic?

Like this:

One blogger likes this post.

This entry was posted on October 14, 2011 at 12:30 pm and is filed under Cambridge Maths Tripos, II Number Theory, Lecture. You can follow any responses to this entry through the RSS 2.0 feed. You can leave a response, or trackback from your own site.

6 Responses to “Number Theory: Lecture 4”

Saddam Says:
October 15, 2011 at 5:07 pm
Hi i have something written in my notes that says “log p prime power”.

But i don’t see how log p can be a prime? i mean it isn’t even an integer usually (i tried p = 1,2,3,4 up to 20 and they’re all fractions). Have i misunderstood something?
Saddam Says:
October 15, 2011 at 5:09 pm
Oh wait. Is it log based then? so log 100 = 2 which is a prime e.g.
theoremoftheweek Says:
October 15, 2011 at 5:17 pm
I’m not quite sure where you mean. Can you be a bit more precise about where this was in your notes?
Saddam Says:
October 15, 2011 at 10:52 pm
I’ve been a bit of a tfool. i t actually said “wlog p a prime power”.
Number Theory: Lecture 6 « Theorem of the week Says:
October 19, 2011 at 12:08 pm
[...] In one we proved that if and only if , which gives the result. In the second, we used the existence of a primitive root modulo , say , and showed that is a quadratic residue if and only if is even. And in the third [...]
Theorem 38: There is a primitive root modulo a prime « Theorem of the week Says:
October 23, 2011 at 4:32 pm
[...] is something that I was lecturing on the other day. There I was talking to third-year Cambridge undergraduates, who know quite a bit of mathematics [...]

Theorem of the week