# Chapter 1: Foundations

## Learning Outcomes

1. (a) Understand arithmetic progressions arising from polygonal and pyramidal numbers, and be able to find the sums of finite such sequences.
2. (b) Be able to use, and understand the theoretical underpinnings of, mathematical induction.
3. (c) Understand and be able to apply the Generalised Principle of Mathematical Induction and the Second Principle of Mathematical Induction.
4. (d) Recognise the importance of the Division Algorithm, and be able to apply it in a variety of scenarios.
5. (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.
6. (f) Understand the term ‘least common multiple’, and be able to relate it to highest common factor.
7. (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.
8. (h) Understand the general meaning of the term ‘Diophantine equation’.
9. (i) Recognise when a linear Diophantine equation has solutions, and when it does not.
10. (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

## Learning Outcomes

1. (a) Understand the term ‘prime number’, and be able to recall basic properties of integers relating to prime numbers.
2. (b) Be able to find all prime numbers in a given range using the sieve of Eratosthenes.
3. (c) Understand the statement and proof of the Fundamental Theorem of Arithmetic.
4. (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.
5. (e) Know the meaning of τ(n), and how to compute it.
6. (f) Understand Euclid’s proof of the infinitude of primes, and how this
7. can be used to give an upper bound on the size of the nth prime.
8. (g) Understand, and be able to adapt to other situations, the techniques
9. in the proof that there are infinitely many primes of the form 4k + 3.
10. (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.
11. (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

## Learning Outcomes

1. (a) Understand the meaning of the terms ‘congruence’ and ‘residue class’, and be confident in using these to manipulate expressions in modular arithmetic.
2. (b) Recognise and be able to use the connection between divisibility tests and congruence.
3. (c) Be able to distinguish between distinct solutions of polynomial congruences, and apply basic methods to solve basic polynomial congruences with low modulus.
4. (d) Be able to use divisibility tests, in particular those for divisibility by 9 and 11, and explain why they work.
5. (e) Understand the proof of the solution of linear congruences, and be able to apply the theory to specific examples.
6. (f) Recall and be able to apply the strategy to solve linear congruences, and use this to solve certain linear Diophantine equations.
7. (g) Understand the statement, proof and applications of the Chinese Remainder Theorem.
8. (h) Be able to use a range of techniques to solve simultaneous linear congruences.

# Chapter 4: Fermat & Wilsons Theorems

## Learning Outcomes

1. (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.
2. (b) Know the meaning of the term ‘pseudoprime’, and its connection with Fermat’s Little Theorem.
3. (c) Be able to apply the Division Algorithm to compute decimal representations of fractions.
4. (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.
5. (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.
6. (f) Know the definition of the ‘degree’ of a polynomial congruence.
7. (g) Understand the statement and proof of Lagrange’s Theorem.
8. (h) Be able to use a variety of techniques to solve polynomial congruences with composite moduli.