1 Introduction

Number Theory is that part of mathematics that studies the properties of numbers. At its core lie the prime numbers. Starting with simple results like the prime decomposition, and simple algorithms like Euclid's algorithm, Number Theory builds up to ideas that underpin the security of the internet.

2 Clock Arithmetic

The key idea of clock arithmetic is to do your arithmetic as if on a clock face. When you go past $12$, you “wrap around". Thus $13$ becomes $1$, $14$ becomes $2$, and so on. In clock arithmetic, then, $2\times 7=14$ which becomes $2$. Thus we might write $2\times 7{=}_{ca}2$ where the subscript stands for “clock arithmetic".

There's one slight difference with clock arithmetic in mathematics: we use $0$ instead of $12$. Thus our clock face starts at $0$ and ends at $11$. So $2\times 6{=}_{ca}0$.

We can also generalise to different clocks with different numbers. We could imagine a clock with only four numbers: $0,1,2,3$. On this clock, we would have $3\times 3=9{=}_{ca}1$ (since we wrap around twice).

Our notation gets a bit unwieldy here since it ought to record the “clock number". The proper notation is to write:

$$\begin{array}{rl}2\times 7& \equiv 2mod12\\ 2\times 6& \equiv 0mod12\\ 3\times 3& \equiv 1mod4\end{array}$$

We read this as, for example, “$2$ times $7$ is equivalent to $2$ modulo $12$".

As we're using correct notation, we should use correct terminology as well. The topic is known as modular arithmetic, not “clock arithmetic", and the clock number is known as the modulus.

If you think what is going on when doing the “wrap around", we can add or subtract multiples of the modulus without changing what it is equivalent to. So two numbers, say $a$ and $b$, are equivalent modulo $n$ if $n$ divides their difference, $b-a$.

We'll assume that modular arithmetic works. That is, there's never any ambiguity in working out the value of an expression.

3 Multiplication Tables

In modular arithmetic, there are only a finite number of “numbers". For example, with modulus $4$ then every number is equivalent to one of $0$, $1$, $2$, or $3$.

This means that we can write out all the possible multiplications in a multiplication table. For example, here's the multiplication table with modulus $4$:

The row and column corresponding to $0$ is a bit dull, so we'll leave that out and just write:

4 Division

Let's look at one of the “special" rows, for example the $3$–row in the multiplication table for $4$. Since each number appears there, we can say that for any number $a$, there is some number $b$ such that $3b\equiv amod4$.

Now in normal arithmetic, we would say that if $3b=a$ then $b=a/3$. We don't have fractions in modular arithmetic, but we can still say that if $3b\equiv amod4$ then there is some $d$ such that $b\equiv admod4$.

Hopefully you noticed that you got the same $d$ each time. In fact, in this case $d=3$. It is a coincidence that $d=3$ but not a coincidence that $3\times 3\equiv 1mod4$.

When we have this situation, we can “undo" multiplication. For example, working modulo $9$ (that is, with modulus $9$) then $4$ has this property. To undo multiplication by $4$, we multiply by $7$. So $7$ behaves like $1/4$. Another way of writing $1/4$ is $4^{-1}$ and we use this notation and refer to the reciprocal of $4$. Thus: $4^{-1}\equiv 7mod9$.

Our conclusion is that for every “special" modulus, then every non-zero number has a reciprocal and so we can “do division".

5 Powers

Let's move on to powers. Just as with multiplication, we can do powers and write out a “power table". Also just as with multiplication, it makes sense to ignore powers of $0$ but we will include $a^0=1$ as our first column. We'll write it out up to $a^{n-1}$, where $n$ is our modulus. Thus for $4$ our “power table" looks like this:

In this case, only some moduli have “special rows" where every number appears, but even when some rows are “special" then not every row is. A number $a$ such that $a^0$, $a^1$, $a^2$, etc. generates all the numbers is called a primitive root.

6 Cryptography

At the heart of modern cryptography lies the ability to have a secret conversation even in the presence of eavesdroppers. The key to this is that it is possible for two people to both know something without actually exchanging that information.

Let's see how this works. It is traditional for the two protagonists in cryptography to be called Alice and Bob. Let's keep the traditions.

1. In plain sight of everyone, Alice and Bob pick a nice prime number, say $p$, and a smaller number, say $g$. So everyone knows $p$ and $g$, including any eavesdroppers.

2. Alice and Bob then each choose another number in secret.

   So Alice chooses a number, say $n$, and Bob chooses a number, say $m$.

3. Alice and Bob each calculates the corresponding power of $g$ modulo $p$.

   So Alice calculates $g^{n}modp$ and Bob $g^{m}modp$. Let's call these $a$ and $b$ respectively.

4. These two numbers are exchanged, again in plain sight.

5. Then Alice computes $b^{n}modp$ and Bob computes $a^{m}modp$. The crucial fact is that these two produce exactly the same number, which is $s=g^{mn}modp$.

6. Alice and Bob can then use this number in some secret code, and any eavesdropper doesn't know either $m$ or $n$ so can't figure out $s$.

Of course, given enough time and computing power, the evil eavesdropper could compute every single $g^{k}modp$ and eventually figure out $n$ and $m$. Looking at your “power tables", you should see that there is no particular pattern to the numbers $g^{k}modp$ and so the eavesdropper would genuinely have to calculate them all. There is no quick method.

In practice, the numbers chosen are big enough that this is practically impossible.

Thus Alice and Bob have agreed on a number, $s$, without anyone else knowing what it is even though their entire conversation could be overheard.