Number Theory: Lecture 24

In which we conclude our study of methods of factorising large numbers, and, indeed, the course.

  • Lemma 76: Let \frac{p_n}{q_n} be a convergent to \sqrt{N}.  Then \langle p_n^2 \rangle = p_n^2 - q_n^2 N, and moreover we have |\langle p_n^2 \rangle| \leq 2 \sqrt{N}.  (The angle bracket notation is the same as that introduced in Lecture 7).  We proved this using our upper bound on |p_n - q_n \sqrt{N}|, which in turn we proved in Lecture 19.
  • Description of the continued-fraction method, which is really a variant of the factor-base method that we saw last time, using Lemma 76 as a crucial ingredient.
  • Description of Pollard’s p-1 method.

Further reading

Koblitz (A Course in Number Theory and Cryptography) and Davenport (The Higher Arithmetic) both discuss these methods, together with other variants.  Right at the end, I mentioned Shor’s algorithm for factorisation using a quantum computer; Scott Aaronson has written a lovely non-technical description on his blog, and he includes links to a number of sources of more information.

I hope that some of you may be inspired to read in more depth about the ideas of this course, and about other aspects of number theory.  Of course, there are many number theory books and many websites where you can do this, so I shan’t try to list them (but please do share your favourites in the comments below).

I’ll just mention one book, The Princeton Companion to Mathematics, edited by Tim Gowers (with associate editors June Barrow-Green and Imre Leader).  This has short sections on various important concepts in pure mathematics, including several from number theory (such as elliptic curves, the Euclidean algorithm and continued fractions, the ideal class group, L-functions, modular arithmetic, number fields, the Riemann zeta function and many more).  Perhaps even more interestingly, it has slightly longer articles (10–20 pages) on branches of mathematics, written by leading mathematicians in those areas.  So there’s “Algebraic Numbers” by Barry Mazur, “Analytic Number Theory” by Andrew Granville, “Computational Number Theory” by Carl Pomerance, “Arithmetic Geometry” by Jordan S. Ellenberg, and many more (they aren’t all about number theory!).  And then there are short pieces about particular theorems and problems, such as the ABC conjecture, the Birch–Swinnerton-Dyer conjecture, Fermat’s last theorem, the Prime Number Theorem and the Riemann Hypothesis, Problems and Results in Additive Number Theory, and so on.  If you want a broader picture of mathematics and how the ideas from your various lecture courses are used, and if you want to know what current research mathematicians in the area are thinking about, this would be a great place to start reading.  Perhaps your college library has a copy?

Preparation for Lectu… oh, this is the end of the course!

I plan to write about some of the topics from this course in more detail over the next few months (in the style of the `Theorem’ posts on this blog), so you might want to keep an eye out for them.  And of course the comment facility is still there for asking questions.  I hope that this course has inspired you to find out more about Number Theory!

About these ads

3 Responses to “Number Theory: Lecture 24”

  1. outofthenormmaths Says:

    Your link to Scott Aaronson’s blog seems to be faulty. Did you mean this blog post?: http://www.scottaaronson.com/blog/?p=208

  2. theoremoftheweek Says:

    Yes, I certainly did. I carefully found the link, but then obviously copied and pasted the wrong one! Thanks for pointing it out — I’ve (hopefully) now corrected the link in the post.

  3. theoremoftheweek Says:

    I’ve just put a couple of notes about questions on the fourth examples sheet on the blog post in which I gave out the sheet. I hope that might clarify one or two things.

Leave a Reply

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

WordPress.com Logo

You are commenting using your WordPress.com 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


Follow

Get every new post delivered to your Inbox.

Join 148 other followers

%d bloggers like this: