All the material you need to know is in this script, but you might find some of the books below useful for an alternative viewpoint on the same topics:

• Chapters I–III of Davenport’s classic text The Higher Arithmetic are a very readable account of elementary number theory (i.e. everything in chapters 1–4 and 6–7 of these notes). Since Davenport died in 1969, the copyright on this book expired long ago and you can download it for free – entirely legally – from
  https://archive.org/details/h.-davenport-the-higher-arithmetic/.

• RSA cryptography (chapter 5) is too recent to be in Davenport’s book, but is covered in many more recent texts, such as Coutinho’s book The Mathematics of Ciphers.

• For algebraic number fields (chapters 8–10), I highly recommend Stewart and Tall’s Algebraic Number Theory and Fermat’s Last Theorem, although this goes a long way beyond what we can cover here. Cox’s lovely book Primes of the form \(x^2 + n y^2\) gives a very interesting and original perspective on some of these ideas.

• Gouvêa’s book P-adic Numbers: An Introduction is an excellent reference for p-adic arithmetic (chapters 10–11). There is also a (somewhat more advanced) text by Koblitz, P-adic numbers, p-adic analysis and zeta-functions, which is a good read.

In this module we use the following symbols:

• \(\mathbb{N}\) denotes the natural numbers \(\{0, 1, 2, 3, \dots \}\);

• \(\mathbb{Z}\) the integers (positive, negative or zero);

• \(\mathbb{Q}, \mathbb{R}, \mathbb{C}\) the fields of rational, real, and complex numbers respectively.

• \(\mathbb{N}_+\) denotes the positive¹

  Beware that some other texts use \(\mathbb{N}\) for positive integers!

  integers \(\{1, 2, 3, \dots\}.\)

• If \(a\) is in \(\mathbb{R}\) (and in particular if \(a \in \mathbb{Z}\)), the symbol \(|a|\) means the absolute value of \(a,\) i.e. \(|a| = a\) if \(a \geqslant 0,\) and \(|a| = -a\) if \(a \leqslant 0.\)

• For \(n \in \mathbb{N},\) we write \(n!\) (read as “\(n\) factorial”) for the product \(1 \times 2 \times \dots \times n,\) with \(0!\) defined to be 1.

• The logical symbols \(\Rightarrow,\) \(\iff,\) \(\exists,\) \(\forall\) have their usual meanings.

• The symbol \(\square\) denotes the end of a proof.

• The symbol \(\circledast\) is used to mark unsolved problems and conjectures.

We’re going to use induction quite a lot in this module, so it might be a good idea to revise it if your memory has got rusty.

As a reminder: the principle of mathematical induction, which you saw way back in M01 Algorithmics, is a very powerful tool for proving statements about \(\mathbb{N}.\) It goes as follows. Suppose \(P(n)\) is some statement about the natural number \(n,\) and:

• \(P(0)\) is true,

• for any \(n \in \mathbb{N}\) the implication \(P(n) \implies P(n+1)\) is true.

Then \(P(n)\) is true for all \(n.\)

There are a few variants of induction which are useful:

Different starting points: Let \(t \in \mathbb{N}\) be given. If \(P(t)\) is true, and for any \(n \geqslant t\) we have \(P(n) \implies P(n+1),\) then \(P(n)\) is true for all \(n \geqslant t.\) (The usual induction is \(t = 0,\) but the \(t = 1\) case also occurs frequently.)

This can, of course, easily be derived from “usual” induction applied to the new statement \(Q(n)\) defined by “if \(n \geqslant t\) then \(P(n)\)”, which is vacuously true for \(n < t.\)

Strong induction: Suppose \(P\) is a statement such that:

• for any \(n \in \mathbb{N},\) if \(P(r)\) is true for all \(r < n,\) then \(P(n)\) is true.

Then \(P(n)\) holds for all \(n.\)

This looks far more powerful than usual induction (because we have to prove only one thing, and we’re allowed to assume something that looks a lot stronger); but in fact it easily follows from usual induction.

Minimal elements: Our final induction variant is known as the well-ordering principle for \(\mathbb{N}.\)

• Let \(S \subset \mathbb{N}\) be a non-empty set. Then \(S\) has a minimal element; that is, there exists \(n \in S\) such that every \(m \in S\) satisfies \(m \geqslant n.\)

To see this, suppose \(S\) doesn’t have a minimal element, and let \(P(n)\) be the statement “\(m \geqslant n\) for all \(m \in S\)”. Clearly \(P(0)\) holds, since every natural number is \(\geqslant 0.\) Now, if \(P(n)\) holds, then we must have \(n \notin S,\) since otherwise \(n\) would be the minimal element of \(S.\) So for \(m \in S,\) we have \(m \geqslant n\) and \(m \ne n.\) So \(m \geqslant n + 1,\) and thus \(P(n+1)\) holds. By induction, \(P(n)\) holds \(\forall n\); so \(S\) is empty, a contradiction.

The “divides” symbol is a relation: for any given values of \(a\) and \(b,\) “\(a \mid b\)” is a self-contained statement which is either true or false. Don’t confuse it with division \(a / b,\) which is a number (if it is defined at all, which it might not be if \(b = 0\)).

More concretely, if \(a > 0,\) then \(q\) is given by \(\lfloor b / a \rfloor,\) where \(\lfloor x \rfloor\) is the floor function: the function which converts a real (or rational) number to an integer by rounding towards \(-\infty\) (meaning that \(\lfloor 1.5 \rfloor = 1\) and \(\lfloor -1.5\rfloor = -2\)). Thus we can easily compute \(q\) and \(r\) from the decimal expansion of \(b / a.\)

Note that (except in the trivial case \(a = b = 0\)), the greatest common divisor \(\gcd(a, b)\) is, as its name suggests, the largest element of the set of common divisors of \(a\) and \(b\) (the set \(\{x \in \mathbb{Z}: x \mid a\ \text{and}\ x \mid b\}\)). This follows from the much stronger fact proved above that this set consists precisely of the divisors of \(c\) (and since \(c > 0,\) the largest divisor of \(c\) is clearly \(c\) itself).

However, if we just defined \(\gcd(a, b)\) to be the largest element of this set, it wouldn’t be clear that all other elements of this set divided it.