Part A: Number Theory
Chapter 1: Foundations
- (a) Understand arithmetic progressions arising from polygonal and pyramidal numbers, and be able to find the sums of finite such sequences.
- (b) Be able to use, and understand the theoretical underpinnings of, mathematical induction.
- (c) Understand and be able to apply the Generalised Principle of Mathematical Induction and the Second Principle of Mathematical Induction.
- (d) Recognise the importance of the Division Algorithm, and be able to apply it in a variety of scenarios.
- (e) Know the meaning of and be able to use the terms ‘factor’, ‘highest common factor’, ‘integer combination’ and ‘coprime’; understand elementary results relating these terms.
- (f) Understand the term ‘least common multiple’, and be able to relate it to highest common factor.
- (g) Know how to apply the Euclidean Algorithm to find the highest common factor of two integers a and b, and express it as an integer combination of a and b.
- (h) Understand the general meaning of the term ‘Diophantine equation’.
- (i) Recognise when a linear Diophantine equation has solutions, and when it does not.
- (j) Be able to find particular and general solutions of given linear Diophantine equations through the application of the Euclidean Algorithm.
Chapter 2: Prime numbers
- (a) Understand the term ‘prime number’, and be able to recall basic properties of integers relating to prime numbers.
- (b) Be able to find all prime numbers in a given range using the sieve of Eratosthenes.
- (c) Understand the statement and proof of the Fundamental Theorem of Arithmetic.
- (d) Be able to list all factors of an integer given its prime decomposition; relate prime decompositions to highest common factors and least common multiples.
- (e) Know the meaning of τ(n), and how to compute it.
- (f) Understand Euclid’s proof of the infinitude of primes, and how this
- can be used to give an upper bound on the size of the nth prime.
- (g) Understand, and be able to adapt to other situations, the techniques
- in the proof that there are infinitely many primes of the form 4k + 3.
- (h) Appreciate the statements of famous conjectures such as the Twin Prime Conjecture and the Goldbach Conjecture, and the statement of the Prime Number Theorem.
- (i) Recall properties of the Fibonacci numbers relating to coprimality and divisibility, and be able to use these properties to solve related exercises.
Chapter 3: Congruence
- (a) Understand the meaning of the terms ‘congruence’ and ‘residue class’, and be confident in using these to manipulate expressions in modular arithmetic.
- (b) Recognise and be able to use the connection between divisibility tests and congruence.
- (c) Be able to distinguish between distinct solutions of polynomial congruences, and apply basic methods to solve basic polynomial congruences with low modulus.
- (d) Be able to use divisibility tests, in particular those for divisibility by 9 and 11, and explain why they work.
- (e) Understand the proof of the solution of linear congruences, and be able to apply the theory to specific examples.
- (f) Recall and be able to apply the strategy to solve linear congruences, and use this to solve certain linear Diophantine equations.
- (g) Understand the statement, proof and applications of the Chinese Remainder Theorem.
- (h) Be able to use a range of techniques to solve simultaneous linear congruences.
Chapter 4: Fermat & Wilsons Theorems
- (a) Understand the statement, proof and applications of Fermat’s Little Theorem and its alternative formulation; recognise which formulation to use in a given scenario.
- (b) Know the meaning of the term ‘pseudoprime’, and its connection with Fermat’s Little Theorem.
- (c) Be able to apply the Division Algorithm to compute decimal representations of fractions.
- (d) Understand the meaning of and be able to compute the ‘order’ of an integer modulo p; know what it means for the integer 10 to be a ‘primitive root’ of p; recognise the connection with the decimal representation of rational numbers with prime denominator.
- (e) Understand the statement and proof of Wilson’s Theorem, and its converse; be able to use Wilson’s Theorem to solve more complicated congruences.
- (f) Know the definition of the ‘degree’ of a polynomial congruence.
- (g) Understand the statement and proof of Lagrange’s Theorem.
- (h) Be able to use a variety of techniques to solve polynomial congruences with composite moduli.