## Number Theory: Lecture 1

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 $n$ be a natural number greater than $1$.  Then $n$ has a prime factor.  Proof by induction.
• Definition of the prime counting function $\pi(x)$.
• Theorem 2: There are infinitely many primes.  That is, $\pi(x) \to \infty$ as $x \to \infty$.  Proof: Euclid‘s argument.
• Definitions of highest common factor and coprime.
• Review of Euclid’s algorithm.
• Proposition 3: Let $a$ and $b$ be natural numbers with $a > b$, and let $q_i$, $r_j$ be obtained from Euclid’s algorithm in the usual way.  Then there is some $k$ such that $r_{k-1} = q_{k+1} r_k$ (with $r_k \neq 0$) — that is, the algorithm necessarily terminates.  Moreover, $\mathrm{hcf}(a,b) = r_k$.  To show that the algorithm terminates, we noted that the remainders form a strictly decreasing sequence of non-negative integers.  To show that $r_k$ is a common factor of $a$ and $b$, work from the bottom equation up.  To show that it’s the highest, work from the top equation down.
• Theorem 4 (Bézout): Let $a$, $b$ and $c$ be natural numbers.  There are integers $m$ and $n$ such that $am + bn = c$ if and only if $(a,b) \mid c$.  The easy direction is easy.  The harder direction follows from running Euclid’s algorithm and working backwards.
• Proposition 5: Let $p$ be a prime that divides the product $ab$.  Then $p \mid a$ or $p \mid b$.  We proved this using Bézout.
• Theorem 6 (Fundamental Theorem of Arithmetic): Let $n$ be a natural number.  Then $n$ 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 $10m + 13n = 1$.  Can you find all the integer solutions?  What about $10m + 13n = 7$?

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 $p$ 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 $p$, and more generally modulo powers of primes $p^j$.  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!