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?

Further reading

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!


2 Responses to “Number Theory: Lecture 1”

  1. Number Theory: Lecture 2 | Theorem of the week Says:

    […] Expositions of interesting mathematical results « Number Theory: Lecture 1 […]

  2. Number Theory: Lecture 15 | Theorem of the week Says:

    […] Proposition 48 (Euler product for ): For , we have , where the product is over all primes .  We used the idea that , by the Fundamental Theorem of Arithmetic. […]

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: