An introduction to number theory

In this article we shall look at some elementary results in Number Theory, partly because they are interesting in themselves, partly because they are useful in other contexts (for example in olympiad problems), and partly because they will give you a flavour of what Number Theory is about.

You will require a little knowledge in advance, but not much: you need to be familiar with congruence notation, and you need to know that if $a$ and $n$ are coprime (have highest common factor $1$) then $a$ has a multiplicative inverse mod $n$ (that is, there is an integer $b$ such that $a\times b\equiv 1 \text{ mod } n$). You can find an explanation of all of this in the article called Modular Arithmetic . You might also find it useful to know that an integer is a whole number ($\ldots, -3, -2, -1, 0, 1, 2, 3, \ldots$ are all integers), and by natural number , I mean a positive integer ($1, 2, 3, \ldots$). Sometimes people include $0$ as a natural number, but I'm not going to in this article.

We say that $x$ divides $y$, written $x|y$, if there is an integer $c$ such that $y=c x$. So for example, $3|6$ (as $6=2\times 3$), but $3\nmid7$. We need a little property of primes to help us later. The property is that if $p$ is a prime and $p|a b$, then $p|a$ or $p|b$. Is this obvious? Well, no, not really, because it's not true unless $p$ is a prime. For example, $4$ divides $6\times 10=60$, but $4$ does not divide $6$ and $4$ does not divide $10$. Let's prove it (for primes, of course!). We know that $p|a b$. If $p|a$ or $p|b$, then obviously the result is true, so let's suppose that it doesn't. Now we're going to use Bezout's Theorem, which says that $m$ and $n$ are coprime if and only if there exist integers $h$ and $k$ such that $h m+k n=1$. Since $p\nmid a$, $a$ and $p$ are coprime (remember, $p$ is a prime). So there exist integers $h$ and $k$ such that $a h+p k=1$. Similarly, there are integers $H$ and $K$ such that $b H+p K=1$. Let's multiply these equations together. Then $1=(a h+p k)(b H+p K)=a b h H+p k b H+p K a h+p^2 k K= (a b)(h H)+p(k b H+K a h+p k K)$. But $p|a b$ and certainly $p|p$, so $p$ divides the right-hand side, so $p|1$. But this is absurd. So $p|a$ or $p|b$.

We can use this result and induction to prove the following very important theorem:

The Fundamental Theorem of Arithmetic

Every natural number $n> 1$ can be expressed in an essentially unique way as the product of prime numbers.

By "essentially unique", I mean "counting different orderings of the primes as the same": $12=2^2\times3=3\times2^2$, but I'm counting these products as essentially the same. You should also note the very important fact that $1$ is not a prime number - otherwise this theorem would clearly be false! I'm not going to prove this result here, but you might like to have a go yourself, or you can look it up in any introductory book on number theory.

The first theorem we're going to prove is called Fermat's Little Theorem , sometimes, confusingly, known as FLT (confusing because FLT is also used to refer to Fermat's Last Theorem, which is something quite different!). Here's what the theorem says:

Theorem: Let $p$ be a prime and $a$ a natural number not divisible by $p$. Then \begin{equation} a^{p-1}\equiv 1 \text{ mod } p. \end{equation} This is in essence the same as the following statement:

Let $p$ be a prime and $a$ a natural number. Then \begin{equation} a^p\equiv a \text{ mod } p. \end{equation} Why is this really the same? If $a\equiv 0 \text{ mod } p$, then it's pretty obvious that $a^p\equiv a \text{ mod } p$. If $a\not\equiv 0 \text{ mod } p$, then it has an inverse, so we can multiply both sides of (2) by the inverse and get back (1). Also, I hope it's clear that we can multiply both sides of (1) by $a$ to get (2).

Let's prove the theorem (we'll prove (1)). Consider the set $\{1,2,3,\ldots,p-1\}$. This contains all of the distinct non-zero elements mod $p$ (that is, they are all different, and none of them is zero mod $p$). Since they are all non-zero, if we multiply them all together, we'll get something non-zero mod $p$ (repeatedly using the result from earlier that if $p|a b$ then $p|a$ or $p|b$). Now consider the set $\{a,2a,3a,\ldots,(p-1)a\}$, where we reduce each element mod $p$ (so it lies between 0 and $p-1$). Now none of these numbers is 0 mod $p$, and they are all distinct (check this, if you don't believe me!). So it's the set of all of the non-zero elements mod $p$. So certainly multiplying all the numbers in the second set gives the same answer as multiplying all the numbers in the first set (mod $p$). In symbols, $1\times 2\times \ldots\times (p-1)\equiv a\times(2a)\times\ldots\times(p-1)a\equiv a^{p-1}\times 1\times 2\ldots\times (p-1) \text{ mod } p$. Since $1\times 2\times \ldots\times (p-1)\not\equiv 0 \text{ mod } p$, we can divide by it, leaving $a^{p-1}\equiv 1 \text{ mod } p$.

The next theorem is a generalisation of Fermat's Little Theorem, but first we need to define a new function.

The Euler phi function , also known as the Euler totient function , is defined as the function $\phi:\mathbf{N}\rightarrow\mathbf{N}$ (that is, taking values in the natural numbers and giving values in the natural numbers) where $\phi(n)$ is the number of natural numbers less than or equal to $n$ that are coprime to $n$. So $\phi(p)=p-1$ for all primes $p$ (because everything less than $p$ is coprime to $p$), for example. Another example: $\phi(15)=8$, since $1, 2, 4, 7, 8, 11, 13$ and $14$ are exactly the natural numbers less than and coprime to $15$.

This function has a special property. If $m$ and $n$ are coprime , then $\phi(m n)=\phi(m)\phi(n)$. I'm going to leave the proof of this to you as an exercise, because with a couple of hints it's not too hard. We've already worked out what $\phi(p)$ is if $p$ is prime. Now work out $\phi(p^2)$ and then work out $\phi(p^k)$ where $k$ is a natural number. Now work out $\phi(p q)$, where $p$ and $q$ are different primes, and work up to $\phi(p^m q^n)$, again where $p$ and $q$ are distinct primes. Spotted the pattern? Now use the Fundamental Theorem of Arithmetic (see above) to prove that $\phi(m n)=\phi(m)\phi(n)$ for coprime $m$, $n$.

Now let's look at a generalisation of Fermat's Little Theorem, sometimes called the Fermat-Euler Theorem .

Theorem: Let $n> 1$ be a natural number and $a$ an integer coprime to $n$. Then $a^{\phi(n)}\equiv 1 \text{ mod } n$.

Why is this a generalisation of Fermat's Little Theorem? Well, consider when $n$ is prime. Then $\phi(n)=n-1$, and we get back exactly the statement of Fermat's Little Theorem.

I'm going to leave the proof as an exercise, as it's very similar to the proof of Fermat's Little Theorem.

We now come to the last theorem in this article, called Wilson's Theorem .

Theorem: Let $p$ be a prime number. Then $(p-1)!\equiv -1 \text{ mod } p$ (where ! denotes factorial, and $5! = 1\times 2 \times 3 \times 4 \times 5 $).

At first sight, it might seem totally unclear how one could go about proving this, but there is a beautiful and simple proof that I shall outline now. Remember that each of the numbers $1, 2, 3, \ldots, p-1$ has an inverse $\text{ mod } p$? So we can pair off numbers, so that a number in the pair is the inverse of the other number in the pair. But a number could be the inverse of itself. When does this happen? If you think about it, you'll see that $x$ is its own inverse only if $x^2\equiv 1 \text{ mod } p$. That is, $x$ is its own inverse only if $(x-1)(x+1)\equiv 0 \text{ mod } p$, and since $p$ is prime, we see that we must have $x-1\equiv 0 \text{ mod } p$ or $x+1\equiv 0 \text{ mod } p$, so the only numbers between $1$ and $p-1$ that are their own inverses are $1$ and $p-1$. Now let's think back to $(p-1)!$. Each pair $(a,a^{-1})$ contributes $1$ to this product, so the only things we have left to worry about are $1$ and $p-1$. So $(p-1)!\equiv 1\times(p-1)\equiv -1 \text{ mod } p$, as we wanted.

I hope this has given you a flavour of what Number Theory is about; there are numerous books available that continue to develop the theory, and large numbers of Olympiad problems you might like to tackle with your new knowledge!