In which we start to explore the structure of the multiplicative group .
- Theorem 9 (Chinese Remainder Theorem): Let and be coprime natural numbers greater than 1, and let and be integers. Then there is a solution to the simultaneous congruences , , and moreover this solution is unique modulo . We saw that if (where the are distinct primes), then and are isomorphic as rings. (So we can sometimes reduce problems to studying behaviour modulo powers of primes.)
- Corollary 10: Let and be coprime natural numbers greater than 1. Let and be integers with and . Then there is a solution to the simultaneous congruences , , and such a solution satisfies . More algebraically, we saw that if then and are isomorphic as groups.
- Corollary 11: The Euler totient function is multiplicative, in the sense that if and are coprime, then . (So we can sometimes reduce problems to studying the behaviour for powers of primes.)
- Lemma 12: Let be prime, and let be a natural number. Then .
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 (where is a fixed natural number, and the sum is over all divisors of ). What can you say about this sum? (Perhaps try some examples with particular values of .)
Our next job is to explore the structure of the multiplicative group where is prime, before we move on to . 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.