MA0111: Elementary Number Theory I

School Cardiff School of Mathematics
Department Code MATHS
Module Code MA0111
External Subject Code G100
Number of Credits 10
Level L4
Language of Delivery English
Module Leader Professor John Pryce
Semester Spring Semester
Academic Year 2015/6

Outline Description of Module

How do we determine the factors of an integer (a “whole number''), such as 120? There are far better methods than testing for divisibility by 2, 3, 4, 5, and so on, in turn. It is more efficient to invoke the factorisation of 120 as a product of primes.

A related question is that of determining the highest common factor of two numbers. A simple-minded approach might be to list the factors of both and then determine the largest number appearing in both lists. Better methods exist among those resting on prime factorisation, but a computationally more efficient way is that embodied in Euclid's Algorithm, which does not refer to primes and does not depend on factorising either number individually.

Euclid's Algorithm is also of great theoretical importance: it underlies the “Fundamental Theorem of Arithmetic'', to the general effect that if a prime divides a product then it divides one of the factors. This underlies the general proof of the (experimentally verifiable, but also provable) observation that any number is expressible as a product of primes in a unique way, apart from the variations induced by re-ordering the factors. It also provides an efficient procedure for finding the solutions x, y of an equation ax + by = c when integers a, b, and c are given.

An ancient observation due to Pythagoras (or some member of his school) is that there is no rational number (ratio of integers) a / b whose square is 2. One can prove the analogue for integers n other than 2, provided that n is not the square of an integer. Other simple examples of irrationalities include ratios of logarithms such as log 2 / log 3.

Many questions relating to integers are best expressed in congruence notation: we say that a is congruent to b mod m when a differs from b by a multiple of m. Thus ax is congruent to c mod b precisely when the equation ax + by = c can be satisfied. A simple instance in which congruence theory is a helpful concept is in the proposition that an integer is divisible by 9 precisely when the sum of its decimal digits is divisible by 9.

The theory of polynomials in a single variable is in many ways analogous to that relating to the integers. There is a Euclidean Algorithm for the highest common factor of two polynomials, a(x) and b(x), say. This is related to the partial fraction decomposition of 1 / a(x)b(x), though (as in the analogous problems about integers) there may in simple cases be easier ways of determining this decomposition.

It is known but not very easy to prove that a polynomial equation of degree d with real (or integer) coefficients has exactly d solutions in complex numbers, whence it has at most d real solutions. This last fact can be proved quite easily, by a method which also shows that a polynomial congruence of degree d mod p, where p is prime, has at most d solutions that are not congruent mod p to each other.

When a polynomial has integer coefficients it is in general not easy to decide whether it factorises into two such polynomials. It is however straightforward to determine all its linear factors. In this way we can quickly determine whether a given cubic polynomial factorises as a product of two polynomials with integer coefficients (it is guaranteed to factorise as a product of two polynomials with real but possibly irrational coefficients, but this is not the same question).

It is easily observed that the sequence of primes thins out as the numbers involved become larger: in the first ten numbers we find the primes 2, 3, 5, 7, but we never again find so many primes in an interval of length 10, because too many of them will be divisible by 2, 3 or 5. This raises the question whether the primes thin out so rapidly that there are only finitely many. The answer is that they do not, as was first shown by Euclid by a simple argument.

Also of interest is the occurrence of primes in sequences defined by simple expressions such as n4+n2+1 or 2n-1. Some of  the questions raised in this way remain unsolved, but a certain amount can be said by using considerations from polynomial algebra, in these instances using the polynomials x4+x2+1 and xn-1.

The Pigeonhole Principle (or Box Principle) states that if n + 1 objects are each placed in one of n boxes then at least one box must contain more than one object. This simple observation is extraordinarily useful if applied in an appropriate way. A simple example of this occurs in a proof that any recurring decimal represents a rational number (a number that is the ratio of two integers). Another occurs in Dirichlet's Theorem on approximation of irrationals by rationals, which leads to a criterion for irrationality that is sufficient, for example, to prove that the number e is irrational.

Free Standing Module Requirements:  A pass in A-Level Mathematics of at least Grade A

On completion of the module a student should be able to

  • Use prime factorisation to list the divisors of a number
  • Determine  highest common factors using prime factorisation and by using Euclid's Algorithm
  • Determine the integer solutions x, y of equations ax + by = c
  • Establish the irrationality of selected algebraic numbers and of quotients of logarithms
  • Apply congruences in simple arithmetical situations
  • Solve linear congruences and systems of two simultaneous linear congruences
  • Use the Remainder Theorem to determine linear factors of polynomials in one variable with integer coefficients
  • Use Euclid's Algorithm for polynomials, and apply it to problems involving partial fractions
  • Understand proofs of the results referred to in the Syllabus Content.

How the module will be delivered

27 - 50 minute lectures

5 - 50 minute tutorial classes

Some handouts will be provided in hard copy or via Learning Central, but students will be expected to take notes of lectures.

Students are also expected to undertake at least 50 hours private study including preparation of worked solutions for tutorial classes.

Skills that will be practised and developed

Skills:

Solving Linear Diophantine Equations and Congruences. Establishing irrationality of algebraic irrationals. Determination of linear factors of integer polynomials.

Transferable Skills:

Handling problems expressed in terms of variables constrained to be integers.

How the module will be assessed

Formative assessment is by means of regular tutorial exercises.  Feedback to students on their solutions and their progress towards learning outcomes is provided during lectures and tutorial classes.  

The summative assessment is the written examination at the end of the module.  This gives students the opportunity to demonstrate their overall achievement of learning outcomes.  It also allows them to give evidence of the higher levels of knowledge and understanding required for above average marks.

The examination paper has two sections of equal weight.  Section A contains a number of compulsory questions of variable length but normally short.  Section B has a choice of two from three equally weighted questions.

Assessment Breakdown

Type % Title Duration(hrs)
Exam - Spring Semester 100 Elementary Number Theory I 2

Syllabus content

  • Integers, Factors and Primes:
    • Highest Common Factors and Euclid's Algorithm.
    • Solutions in integers x, y of equations ax + by = c.
    • The “Fundamental Theorem of Arithmetic" and uniqueness of factorisation of integers into products of primes.
    • Applications to the irrationality of simple algebraic numbers and of quotients of logarithms of integers.
    • Congruences: simple applications and examples, including casting out nines and elevens. Inverses by Euclid's Algorithm. Linear Congruences. Simultaneous Linear Congruences.
  • Polynomials in One Indeterminate over the Rationals:
    • Degree Laws and the Division Algorithm.
    • Factor Theorem and the Remainder Theorem.
    • Determination of linear factors.
    • Euclid's Algorithm for polynomials, and its application to Partial Fractions. 
    • Uniqueness of factorisation into products of irreducible polynomials.
    • Bound for the number of roots of polynomial equations and of polynomial congruences, in terms of the degree.
  • Primes in Sequences:
    • Infinitude of primes.
    • Polynomial sequences containing or not containing primes.
    • Necessary conditions for 2n ±1 to be prime; Mersenne and Fermat Numbers.
  • Applications of the Pigeonhole Principle:
    • Expressibility of rational numbers as finite or recurring decimals.
    • Dirichlet's theorem on approximation of real numbers by rationals.
    • A test for irrationality; irrationality of e.

Essential Reading and Resource List

Please see Background Reading List for an indicative list.

Background Reading and Resource List

Elementary Number Theory (Springer), Jones, G. A. and Jones, J. M

Elementary Number Theory and its Applications (Addison-Wesley), Rosen, K. H.


Copyright Cardiff University. Registered charity no. 1136855