## Number Theory: Lecture 3

In which we start to explore the structure of the multiplicative group $(\mathbb{Z}/n\mathbb{Z})^{\times}$.

• Theorem 9 (Chinese Remainder Theorem): Let $m_1$ and $m_2$ be coprime natural numbers greater than 1, and let $a_1$ and $a_2$ be integers.  Then there is a solution to the simultaneous congruences $n \equiv a_1 \pmod{m_1}$, $n \equiv a_2 \pmod{m_2}$, and moreover this solution is unique modulo $m_1 m_2$.  We saw that if $n = p_1^{\alpha_1} \dotsm p_k^{\alpha_k}$ (where the $p_i$ are distinct primes), then $\mathbb{Z}/n\mathbb{Z}$ and $\mathbb{Z}/p_1^{\alpha_1} \mathbb{Z} \times \dotsb \times \mathbb{Z}/p_k^{\alpha_k} \mathbb{Z}$ are isomorphic as rings.  (So we can sometimes reduce problems to studying behaviour modulo powers of primes.)
• Corollary 10: Let $m_1$ and $m_2$ be coprime natural numbers greater than 1.  Let $a_1$ and $a_2$ be integers with $(a_1, m_1) = 1$ and $(a_2, m_2) = 1$.  Then there is a solution to the simultaneous congruences $n \equiv a_1 \pmod{m_1}$, $n \equiv a_2 \pmod{m_2}$, and such a solution satisfies $(n,m_1 m_2) = 1$.  More algebraically, we saw that if $n = p_1^{\alpha_1} \dotsm p_k^{\alpha_k}$ then $(\mathbb{Z}/n\mathbb{Z})^{\times}$ and $(\mathbb{Z}/p_1^{\alpha_1} \mathbb{Z})^{\times} \times \dotsb \times (\mathbb{Z}/p_k^{\alpha_k} \mathbb{Z})^{\times}$ are isomorphic as groups.
• Corollary 11: The Euler totient function $\phi$ is multiplicative, in the sense that if $m$ and $n$ are coprime, then $\phi(mn) = \phi(m)\phi(n)$.  (So we can sometimes reduce problems to studying the behaviour for powers of primes.)
• Lemma 12: Let $p$ be prime, and let $k$ be a natural number.  Then $\phi(p^k) = p^{k-1}(p-1)$.

I gave out the first examples sheet today; you can find it on the course page.

Davenport (The Higher Arithmetic) discusses some of the above topics in the way that I’ve presented them, but not all.  Baker (A concise introduction to the theory of numbers), Koblitz (A Course in Number Theory and Cryptography), and Jones and Jones (Elementary Number Theory) all also discuss these topics, although again not necessarily following exactly the approach that I’ve used.

#### Preparation for Lecture 4

As I mentioned at the end of today’s lecture, we are going to want to know about the sum $\sum_{d|n} \phi(d)$ (where $n$ is a fixed natural number, and the sum is over all divisors $d$ of $n$).  What can you say about this sum?  (Perhaps try some examples with particular values of $n$.)

Our next job is to explore the structure of the multiplicative group $(\mathbb{Z}/p\mathbb{Z})^{\times}$ where $p$ is prime, before we move on to $(\mathbb{Z}/p^j \mathbb{Z})^{\times}$.  So see what you can discover, perhaps by starting with examples and going from there.  Are the groups cyclic, or products of cyclic groups, or something more complicated?

It would also be helpful to think about analogues of the Fundamental Theorem of Algebra.  In ordinary arithmetic, we know how many solutions there are to polynomial equations.  What happens with polynomial congruences?  You might like to experiment with a range of moduli, including both composite and prime, to get a feeling for where the interesting features occur.

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

1. Vaidotas Says:

In 1st example sheet, problem 2, I substitute a=5,b=3, and get LHS=3 less than or equal to 2=RHS. Is there a mistake, or am I counting in too many Euclid applications? (5=1*3+2, 3=1*2+1, 2=2*1 – 3 applications ).

2. theoremoftheweek Says:

You’re right, it depends how you count the applications of Euclid. I think that if I get to a division that leaves remainder 1, then I can stop (because I am sure that the next line will have remainder 0). That wouldn’t be true for any larger remainder, but 1 is a bit of a special case.

So you have two options at this point. Either you slightly tweak the way you count applications of Euclid (as I’ve done), or you slightly tweak the bound to get something that you’re able to prove. There’s a sense in which the precise details are not too important: what matters is that the bound is basically logarithmic. So if you want to prove a slightly weaker bound of a similar shape, that would be fine.

Does that help?

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

[…] there is a primitive root modulo any power of , and thanks to the Chinese Remainder Theorem this gets us a long […]

4. Number Theory: Lecture 13 « Theorem of the week Says:

[…] properly represented by if and only if there is a solution to the congruence .  We then used the Chinese Remainder Theorem, Hensel’s lemma (above), and a quick check modulo powers of 2, to reduce this to the […]