BSc Computer Science and Mathematics with Industrial Experience

Year of entry: 2024

Course unit details:
Number Theory

Course unit fact file
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: 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 12
Tutorials 12
Independent study hours
Independent study 76

Teaching staff

Staff member Role
Hung Bui Unit coordinator

Additional notes

The independent study hours will normally comprise the following. During each week of the taught part of the semester:
 
•         You will normally have approximately 60-75 minutes of video content. Normally you would spend approximately 2-2.5 hrs per week studying this content independently
•         You will normally have exercise or problem sheets, on which you might spend approximately 1.5hrs per week
•         There may be other tasks assigned to you on Blackboard, for example short quizzes or short-answer formative exercises
•         In some weeks you may be preparing coursework or revising for mid-semester tests
 
Together with the timetabled classes, you should be spending approximately 6 hours per week on this course unit.
The remaining independent study time comprises revision for and taking the end-of-semester assessment.
 
The above times are indicative only and may vary depending on the week and the course unit. More information can be found on the course unit’s Blackboard page.

Return to course details