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

Further reading (and thinking!)

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

One Response to “Number Theory: Lecture 5”

  1. Theorem 38: There is a primitive root modulo a prime « Theorem of the week Says:

    […] let you experiment a bit to find an example of a modulus where there are no primitive roots.  But it turns out that if is an odd prime then there is a primitive root modulo any power of , and thanks to the […]

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s


%d bloggers like this: