Discrete Mathematics

Lecturer: Dr P. Robinson (pr@cl.cam.ac.uk)

No. of lectures: 16 (Continued into Lent Term)

This course is a prerequisite for Introduction to Security (Part IB), Information Theory and Coding (Part II) and Security (Part II).

Part A. Integers

Proof.

Deduction, contradiction. Integers, mathematical induction. [2 lectures]

Factorisation.

Highest common factors and least common multiples. Euclid's algorithm: solution in integers of ax+by=c. The complexity of Euclid's algorithm. Primes. Euclid's proof of the infinity of primes. Existence and uniqueness of prime factorisation. Irrationality of root(p); brief discussion of rational and algebraic numbers. [3 lectures]

Modular arithmetic.

Solving congruences. Units modulo n, Euler's totient function. Wilson's theorem. Chinese remainder theorem. The Fermat-Euler theorems. Public key cryptography. [3 lectures]

Part B. Sets, functions and relations.

Sets, subsets and Boolean operations.

Indicator (characteristic) functions and their algebra. Principle of inclusion-exclusion, with applications to Euler's function. [2 lectures]

Binary relations.

Equivalence relations and quotients of sets. Closures and Warshall's algorithm. Partial orders, total orders and well-ordering. Hasse diagrams. Structural induction. [3 lectures]

Functions.

Injective, surjective and bijective functions. Numbers of such functions between sets. The Schröder-Bernstein theorem. Countability. A countable union of countable sets is countable. The uncountability of R. Existence of transcendental numbers. [3 lectures]

Recommended books:

Humphreys, J.F. & Prest, M.Y. (1989). Numbers, Groups and Codes. Cambridge University Press (particularly recommended).

Biggs, N.L. (1989). Discrete Mathematics. Oxford University Press.

Conway, J.H. & Guy, R.K. (1996). The Book of Numbers. Springer-Verlag.

Davenport, H. (1992). The Higher Arithmetic. Cambridge University Press (6th ed.).

Giblin, P. (1993). Primes and Programming. Cambridge University Press.

Graham, R.L., Knuth, D.E. & Patashnik, O. (1994). Concrete Mathematics. Addison Wesley (2nd ed.).

Mattson, H.F. Jr (1993). Discrete Mathematics. Wiley.

Pólya, G. (1980). How to Solve It. Penguin.