In which we recap some more ideas from Numbers and Sets.
Here’s a quick summary of what we did (again, the links are to other places where you can find more information). I have not included examples in this summary, not because they are not important (on the contrary, they’re very important), but because I want to encourage you to develop your own collection of examples.
- Theorem 4 (Bézout): Let , and be natural numbers. There are integers and such that if and only if . We proved the easy direction (‘only if’) last time. Today we reminded ourselves how to use Euclid’s algorithm to prove the interesting direction (‘if’).
- Proposition 5: Let be a prime number, and suppose that divides the product . Then or . Proof using Bézout (Theorem 4). This is a good illustration of how useful Bézout is.
- Theorem 6 (Fundamental Theorem of Arithmetic): Let be a natural number. Then can be factorised as a product of primes, in an essentially unique way. (Remember that we do not count different orderings of the same factors as different factorisations. With the phrasing here, we consider 1 as being factorised into the ‘empty product‘. If you prefer, simply state the result for .) Proof of existence using induction (very similar to Lemma 1), and uniqueness using the previous result (about primes dividing products).
- Definition of congruence notation, and the notation .
- Exercise: Show that we can add, subtract and multiply congruences. Show that these make into a ring.
- Lemma 7: Let be a natural number, and an integer coprime to . Then has a multiplicative inverse modulo . That is, there is an integer such that . We proved this very quickly using Bézout. Exercise: show that if then does not have a multiplicative inverse modulo .
- We noted the special case of Lemma 7 that shows that if is prime then is a field.
- Definition of the multiplicative group .
- Definition of the Euler totient function : we define . So records the number of elements of the set that are coprime to .
- Theorem 8 (Fermat–Euler): Let be a natural number, and let be an integer coprime to . Then . We saw that this follows from an application of Lagrange‘s theorem (applied to the group ). And of course Fermat’s Little Theorem is then a special case of this theorem.
Your favourite introductory number theory book(s), or your Numbers & Sets lecture notes.
Preparation for Lecture 3
We’re going to start studying the structure of and next time. This would be a good time to remind yourself of the Chinese Remainder Theorem, and to try to see what it tells us about and . If you like, you could start by considering particular values of .