In which we remind ourselves of some topics from Numbers and Sets. (With apologies to A.A. Milne.)
Here’s a quick summary of the ideas that we saw. The links are to places where you can read about the ideas in more detail.
- Definitions of divisor and prime number. Definition of the prime counting function (which records the number of primes less than or equal to ).
- Lemma 1: Let be a natural number greater than 1. Then has a prime factor. We proved this by a fairly easy induction.
- Theorem 2: There are infinitely many prime numbers. We saw Euclid‘s proof. We’ll return to the subject of the distribution of the primes (and another proof that there are infinitely many primes) later in the course.
- Definitions of highest common factor and coprime.
- Proposition 3: Euclid’s algorithm for finding the highest common factor of two natural numbers, including why it finds the hcf and why it always terminates. (You might like to look back at that picture at the end of the post from Lecture 0. How much can you extract from that one picture?)
- Theorem 4 (Bézout): Let , and be natural numbers. There are integers and such that if and only if . The easy direction follows from the definition of hcf (this is the direction that doesn’t really deserve to be called a theorem). We’ll use Euclid’s algorithm to prove the other (much more interesting) direction next time — I encourage you to prove it for yourself (/remind yourself how the proof goes) before then.
Make sure that you have a stock of some examples that illustrate these ideas. You might like to find some examples that are somehow ‘typical’, and some that are ‘extreme’.
You should be able to find these topics in any introduction to number theory. I find The Higher Arithmetic, by H. Davenport (published by CUP), to be a very readable treatment of the material, but there are plenty of others (including those mentioned in the Schedules). Feel free to recommend your favourites in the comments.
Preparation for Lecture 2
Lecture 2 will be another refresher of ideas from Numbers & Sets. We’ll start with a couple more key facts about primes, including the Fundamental Theorem of Arithmetic. Then we’ll see congruence notation (modular arithmetic), when multiplicative inverses exist in modular arithmetic, the result that the integers modulo a prime form a field, Fermat’s little theorem, and its generalisation to composite moduli (Fermat-Euler). Since these are again hopefully familiar concepts, I’m going to suggest the same question as last time: how would you explain the ideas to someone who doesn’t already know them? How will you motivate the ideas so that they seem natural to someone who hasn’t seen them before?
We’ll be moving on to new material soon, so you might like to start thinking ahead. We’re going to study the structure of the multiplicative groups modulo primes , and more generally modulo powers of primes . You might like to play with some examples (with particular primes), to try to get a feel for the structure of these groups. Maybe you’ll make some conjectures about the structure. Of course, if you can prove your conjectures then so much the better!