# BSc Computer Science and Mathematics / Course details

Year of entry: 2020

## Course unit details:

Number Theory

Unit code | MATH32072 |
---|---|

Credit rating | 10 |

Unit level | Level 3 |

Teaching period(s) | Semester 2 |

Offered by | Department of Mathematics |

Available as a free choice unit? | No |

### Overview

Number theory is arguably one of the oldest and most fascinating branches of mathematics. This fascination stems from the fact that there are a great many theorems concerning the integers, which are extremely simple to state, but turn out to be rather hard to prove. Even more tantalisingly, there are many simple questions that one can ask about the integers, to which no answer is yet known. It may come as no surprise to you that many of these theorems and open problems relate to the mysterious nature of prime numbers.

In this course we will use a few elementary ideas along with one or two algebraic concepts to prove some appealing statements such as every positive integer is the sum of four squares and there are infinitely many primes of the form 4n+1. We will conclude the course by mentioning a few interesting open problems.

### Aims

This lecture course aims to introduce students to some elementary concepts in number theory. We shall apply some basic algebraic concepts in order to study integer solutions of certain polynomial equations with integer coefficients, such as x^2 - dy^2 = 1 (Pell’s equation).

Whilst there are no official prerequisites for this course, please note that:

- Students who already have some familiarity with groups and other basic algebraic structures may find the material slightly easier than those students who don't.
- A certain level of mathematical maturity is required and you will be expected to work hard!

### Learning outcomes

On successful completion of this course unit students will:

- Describe the Euclidean algorithm and use it to solve linear Diophantine equations.,
- Explain the continued fraction algorithm and use it to (a) find representations of rationals and quadratic irrationals, (b) obtain rational approximations to real numbers and (c) find solutions to Pells equations,
- Describe the group of units modulo n and determine the existence of a primitive root modulo n for a given value of n,
- Prove basic facts about Legendre symbols and quadratic residues,
- State the theorem of quadratic reciprocity and use it to determine whether a given integer is a quadratic residue modulo a given prime.

### Syllabus

Division, primes and the Euclidean algorithm [2 lectures]

- Introduction to the course and discussion of puzzles and problems involving Diophantine equations.

- A review of basic notions (divisibility, primes, greatest common divisor).

Finite continued fractions [3 lectures]

- Finite simple continued fractions and the continued fraction algorithm.

- Connection to the Euclidean algorithm.

Infinite simple continued fractions [4 lectures]

- Definitions and convergence properties.

- Representation of real numbers; finite/periodic/purely periodic continued fractions.

- Rational approximations of real numbers.

Pell's equations [3 lectures]

- Definitions and examples; trivial solutions and generating positive solutions.

- Using continued fractions to find solutions.

The group of units modulo n [2 lectures]

- A review of basic concepts (modular arithmetic, groups, units) with examples.

- Wilson's theorem, Euler's theorem and Fermat's little theorem

- An application of Euler's theorem (RSA)

Polynomial congruences and primitive roots [3 lectures]

- Applications to Diophantine equations.

- Primitive roots and the structure of the group of units modulo n.

Quadratic residues [3 lectures]

- The group of quadratic residues modulo n.

- Legendre symbols and Quadratic reciprocity.

Sums of squares [2 lectures]

- Fermat's ‘two squares’ theorem.

- Lagrange’s ‘four squares’ theorem.

### Assessment methods

Method | Weight |
---|---|

Other | 20% |

Written exam | 80% |

Coursework: weighting 20%

End of semester examination: two hours, weighting 80%

### Feedback methods

Feedback tutorials will provide an opportunity for students' work to be discussed and provide feedback on their understanding. Coursework or in-class tests (where applicable) also provide an opportunity for students to receive feedback. Students can also get feedback on their understanding directly from the lecturer, for example during the lecturer's office hour.

### Recommended reading

- Elementary number theory, Jones and Jones
- Elements of number theory, Stillwell

### Study hours

Scheduled activity hours | |
---|---|

Lectures | 22 |

Tutorials | 11 |

Independent study hours | |
---|---|

Independent study | 67 |

### Teaching staff

Staff member | Role |
---|---|

Hung Bui | Unit coordinator |