*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.

#### Further reading

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.

October 12, 2011 at 10:36 pm

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

October 12, 2011 at 10:54 pm

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?

October 23, 2011 at 4:32 pm

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

November 4, 2011 at 12:12 pm

[…] 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 […]