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 3 onwards, will be proved in detail, with nothing left to chance.

We begin in Section 1 with an introduction to Mathematical Logic and Proof, with the aim of introducing the language and basic concepts necessary for much of university level mathematics. We will try to be precise about what we can (and cannot) do in a proof, and crucially we will consider strategies for constructing a proof. The material is largely self-contained but see the books by Martin Liebek (Liebek 2015), Daniel Velleman (Velleman 2006) and Daniel Solow (Solow 2013) for some further reading material.

The Number Theory material in Sections 3 - 7 are based heavily on the course textbook Elementary Number Theory by Jones and Jones (Jones and Jones 2006). Our ultimate aim is to justify Euler’s Theorem, Theorem 7.3, which will prove the main mathematical device needed to describe and justify the RSA encryption scheme we shall meet in Section 8.

We end the course in Chapter 8 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 9 - 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).

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

Acknowledgements: Many thanks and much credit for these notes goes to Prof. Graham Niblo and Dr. Jim Renshaw. A large part of this course is based on notes written by Jim, which in turn were based in part on notes by Graham. Thanks are also due to Prof. and Dr. Jones for the Elementary Number Theory (Jones and Jones 2006) textbook upon which this course is based.