MAS330 Topics in Number Theory

Semester 1, 2021/22 10 Credits
Lecturer: Dr Ananyo Dan Home page Timetable Reading List
Aims Outcomes Teaching Methods Assessment Full Syllabus

The course covers topics in elementary Number Theory. This includes Modular Arithmetic, and properties of primes and integers. Most of the material (with the notable exception of the RSA cryptosystem) has been introduced by Fermat, Euler and Gauss in the 17th, 18th and 19th centuries.

Prerequisites: MAS211 (Advanced Calculus and Linear Algebra)

The following modules have this module as a prerequisite:

MAS345Codes and Cryptography

Outline syllabus


    1. Modular Arithmetic
    • Linear Congruences
    • Fermat's Little Theorem and the RSA cryptosystem.
    • Arithmetic functions.
    • Euler's function and Euler's theorem.
    • Gauss' Quadratic Reciprocity Law.

    2. Primes, Integers and Equations
    • Perfect numbers, Mersenne primes, Fermat primes.
    • Pythagorean triples and Fermat Last Theorem.
    • Generating functions and partitions.
    • Continued fractions.
    • Pell's equation.


Aims

  • To introduce various topics in number theory

Learning outcomes

By the end of the modules students should be able to: - Solve linear and quadratic congruences Know and use Fermat's Little Theorem and Wilson's Theorem Code and decode numbers in the RSA cryptosystem Determine whether a number is a quadratic residue modulo an odd prime using the Law of Quadratic Reciprocity. Show that there are infinitely many primes of certain types Verify that certain Mersenne numbers are prime Know Euclid's description of an even perfect number Work out all Pythagorean triples containing a given number Know the statement of Fermat's Last Theorem and something of its history Express a rational number as a finite continued fraction and hence solve a linear diophantine equation Express a given repeated continued fraction in terms of a surd Expand a surd as an infinite continued fraction and hence find a convergent which is an approximation to the given surd to a given degree of accuracy Solve a Pell equation from a continued fraction expansion

Teaching methods

Lectures, problem sheets. It is highly recommended to work on the problems and submit the assigned problems which will be marked for feedback.


20 lectures, no tutorials

Assessment

Assessment: online written examination (2 questions out of 2, about half-length compared to pre-covid exams). On the exam you will be solving problems using methods we learnt in class.

Full syllabus

Week 1: Linear Congruences
Fundamental theorem of arithmetic; Euclidean algorithm; review of modular arithmetic; solving linear congruences with Euclidean algorithm; Chinese remainder theorem.

Week 2: Fermat's Little Theorem, The RSA cryptosystem.
Fermat's Little Theorem, the RSA algorithm.
Week 3: Arithmetic functions.
The functions τ and σ; multiplicativity of τ and σ; the Möbius inversion formula.
Week 4: Euler's function and Euler's theorem.
Euler's ϕ-function; multiplictivity of ϕ; Euler's theorem; quadratic residues and non-residues; Euler's criterion;.
Week 5: Gauss' Quadratic Reciprocity Law.
Quadratic congruences; the Legendre symbol; quadratic reciprocity.
Week 6: Perfect numbers, Mersenne primes, Fermat primes.
Formula for even perfect numbers; Mersenne primes, Fermat primes.
Week 7: Reading week
Week 8: Pythagorean triples and Fermat Last Theorem.
Finding all solutions of x2 + y2 = z2; statement of the Fermat Last Theorem; equation m = x2 + y2.
Week 9: Generating series and partitions.
Generating series. Partitions.
Week 10: Continued fractions.
Representing rational numbers as a finite continued fraction; the convergents; numbers pk, qk; ratio of two consequtive Fibonacci numbers; representing irrational numbers as infinite continued fractions; periodic continued fractions.
Week 11: Pell's equation.
Solving Pell's equation using continued fractions; the fundamental solution; all solutions may be obtained from the fundamental solution.
Week 12: Reading week

Reading list

Type Author(s) Title Library Blackwells Amazon
B Burton Elementary number theory 512.81 (B) Blackwells Amazon
B Rose A course in number theory

(A = essential, B = recommended, C = background.)

Most books on reading lists should also be available from the Blackwells shop at Jessop West.