Discrete Mathematics

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

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

Part A. Integers

Proof.

Contradiction. Mathematical induction.

Factorisation.

Highest common factors and least common multiples. Euclid's algorithm: solution in integers of ax+by=c. 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. The complexity of Euclid's algorithm.

Modular arithmetic.

Units modulo n. Chinese remainder theorem. Wilson's theorem. Euler's totient function and the Fermat-Euler theorems. Public key cryptography.

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.

Binary relations.

Equivalence relations and quotients of sets. Partial orders, total orders and well-ordering. Hasse diagrams. Structural induction.

Functions.

Injective, surjective and bijective functions. Numbers of such functions between sets. Countability. A countable union of countable sets is countable. The uncountability of R. Existence of transcendental numbers.

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.