# Introduction to Number Theory

Course category:
2nd year
Module code:
0590017
Year:
2010/11
Term:
Autumn
Credits:
10

## Aims

Number theory is one the most "venerable" fields of mathematics. Its roots lie way back in antiquity and yet it is still an area of very active research by many mathematicians to this day. It is a field that encompasses or touches upon almost the whole of (pure) mathematics.

## Learning objectives

At the end of the module you should be able to...

• know how the GCD and LCM are related to the prime factorizations of two numbers;
• understand the basic arithmetic of the number system formed by taking the integers modulo a fixed number m;
• know what a complete set of residues is; and think of taking congruences when investigating equations with integer coefficients.
• know the definition of Euler's ϕ-function and its expression in terms of prime factors;
• be familiar with linear congruences and know the Chinese remainder theorem;
• know Fermat's little theorem, and Euler's extension of it;
• understand the meaning of the order of a number with respect to a relatively prime modulus;
• know how many square residues there are for an odd prime modulus;
• be able to determine if a given number is a quadratic residue modulo an odd prime using the Legendre symbol;
• understand why primes of the form 4k + 1 are sums of two squares and those of the form 4k - 1 are not;
• understand which natural numbers are sums of two squares;
• be able to find an actual sum should it exist, using Fermat's method of descent;
• be familiar with common arithmetic functions such as τ and σ and their expressions in terms of prime factors;
• know the definition of a multiplicative function and how new multiplicative functions can be made up from others by summing over divisors;
• have tried all the exercises in the module and read the solutions on the web;
• be able to communicate number theory clearly using standard notation.

## Syllabus

to include

• Congruences & arithmetic modulo m.
• Linear congruences
• The Chinese remainder theorem
• Euler's theorem
• Higher order congruences
• Primitive roots, order and indices
• Legendre symbols
• Gauss's law of Quadratic Reciprocity
• Arithmetic functions including Euler's ϕ function
• Fermat's method of infinite descent
• The sum of two squares theorem

Note that the basic notions of divisibility, primeness and the consequences of a number being prime, the division algorithm and the Euclidean algorithm, the highest common factor of two integers and the fact that it can be expressed as the linear combination of the two integers was all taught in the Foundations module and will be assumed without further notice. Though a pre-course handout will be posted for you to revise from along with a set of exercises that you can use for revision purposes before the course proper begins.

## Recommended texts

In no particular order. Though the first two books offer excellent (introductory) treatment.

* A. Baker, A concise introduction to the theory of numbers, CUP.
* G.H. Hardy and E.M. Wright, An introduction to the theory of numbers.
Oxford University Press.
* H.E. Rose, A Course in Number Theory, OUP.
* D M Burton, Elementary Number Theory, Allyn and Bacon (S 2.81 BUR).
* U Dudley, Elementary Number Theory, W H Freeman (S 2.81 DUD).
* K H Rosen, Elementary Number Theory and its Applications, Addison-Wesley (S 2.81 ROS).

## Teaching

• Autumn Term
• 2 lectures per week
• Weekly seminar

## Assessment

Example: One and a half hour closed examination in week 1 Spring Term (90%), Coursework (10%). Note that coursework submitted after the advertised deadlines will be given a mark of zero.

## Elective information

Please check prerequisites carefully before asking to take this module as an elective.

## Prerequisites

• The basics of natural numbers; including primes, congruences, arithmetic functions and sums of squares. Taught in: Core Mathematics