Number Theory: Lecture 1

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 $\pi(x)$ (which records the number of primes less than or equal to $x$ ).
Lemma 1: Let $n$ be a natural number greater than 1. Then $n$ 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 $a$ , $b$ and $c$ be natural numbers. There are integers $m$ and $n$ such that $am + bn = c$ if and only if $(a,b) | c$ . 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’.

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 $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 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 $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!

This entry was posted on October 7, 2011 at 12:30 pm and is filed under Cambridge Maths Tripos, II Number Theory, Lecture. You can follow any responses to this entry through the RSS 2.0 feed. You can leave a response, or trackback from your own site.

2 Responses to “Number Theory: Lecture 1”

Number Theory: Lecture 2 « Theorem of the week Says:
October 10, 2011 at 12:03 pm
[…] Theorem of the week Expositions of interesting mathematical results « Number Theory: Lecture 1 […]
Number Theory: Lecture 18 « Theorem of the week Says:
November 16, 2011 at 12:36 pm
[…] Lemma 57: There is a one-to-one correspondence between finite continued fractions and rational numbers. We saw the important point that the continued fraction of a rational number must terminate, and saw the link to Euclid’s algorithm. […]

Theorem of the week