In which we get started, and remind ourselves of some key points from Numbers & Sets.
Here’s a quick summary of what we did in the lecture. The links are to places where you can read more (sometimes about the maths, sometimes about the mathematicians). Please feel free to use the comments facility!
- Definitions of the natural numbers, of what it means for one integer to divide another, and of prime and composite numbers.
- Lemma 1: Let be a natural number greater than . Then has a prime factor. Proof by induction.
- Definition of the prime counting function .
- Theorem 2: There are infinitely many primes. That is, as . Proof: Euclid‘s argument.
- Definitions of highest common factor and coprime.
- Review of Euclid’s algorithm.
- Proposition 3: Let and be natural numbers with , and let , be obtained from Euclid’s algorithm in the usual way. Then there is some such that (with ) — that is, the algorithm necessarily terminates. Moreover, . To show that the algorithm terminates, we noted that the remainders form a strictly decreasing sequence of non-negative integers. To show that is a common factor of and , work from the bottom equation up. To show that it’s the highest, work from the top equation down.
- Theorem 4 (Bézout): Let , and be natural numbers. There are integers and such that if and only if . The easy direction is easy. The harder direction follows from running Euclid’s algorithm and working backwards.
- Proposition 5: Let be a prime that divides the product . Then or . We proved this using Bézout.
- Theorem 6 (Fundamental Theorem of Arithmetic): Let be a natural number. Then can be written as a product of primes, in an essentially unique way. Existence follows by induction, uniqueness using Proposition 5.
Understanding today’s lecture
Can you prove that there are infinitely many primes that are one less than a multiple of six?
If you need a reminder, it would be a good idea to practise running Euclid’s algorithm on some pairs of numbers.
Can you find an integer solution to the equation . Can you find all the integer solutions? What about ?
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 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 that you think about how you would 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!