Introduction

Although this course is ostensibly about Number Theory, one of it’s main aims is to introduce you to the concepts and ideas surrounding mathematical proofs. Virtually all of the important ideas in chapters 2 onwards, will be proved in detail, with nothing left to chance.

We begin in Section 1 with an introduction to Mathematical Logic and Proof Theory, and although we shall try to be fairly precise, we shall not attempt a formal treatment of logic here, but focus more on the language and basic concepts necessary for most first year University programmes in Mathematics. The material is largely self-contained but see the books by Martin Liebek (Liebek 2015) and Daniel Velleman (Velleman 2006) for some further reading material.

The Number Theory material in Sections 2 - 6 are based heavily on the course textbook Elementary Number Theory by Jones and Jones (Jones and Jones 2006), and much of this was originally typeset for this module by Professor GA Niblo. Our ultimate aim is to justify Euler’s Theorem, Theorem 6.4, which will prove the main mathematical device needed to describe and justify the RSA encryption scheme we shall meet in Section 7.

We end the course in Chapter 7 with a brief look at some modern cryptography based on elementary Number Theory. In particular we aim to describe the workings of the RSA cryptographic system and the Diffie-Helman-Merkle key exchange system. (If we have time we shall cover a small amount of “extra” cryptography in Chapter 8 - however this will not be examinable!)

The book by Jones and Jones (Jones and Jones 2006) is the principal source but a good alternative is that by Kenneth Rosen (Rosen 2010).

There are ten worksheets in this module, one to be attempted for each week. They are included at the end of these notes and solutions will be posted on blackboard after the hand-in deadline has passed. You should hand-in your solutions to these sheets in the appropriate manner and by the indicated deadline, and feedback and credit will be given. The best 8 out of 10 marks will count towards the final assessment of the module.

With the online version of these notes, we have provided a number of Appendices, which we encourage the interested reader to consult.

Acknowledgement: These lecture notes were written by Dr Jim Renshaw and all credit for them belongs to him.