**Table of Contents**

Number theory is one of the oldest branches of pure mathematics. Of course, it concerns questions about numbers, usually meaning integers or rational numbers. It has many applications in security. For example, the famous public-key cryptosystem RSA is based on some number theoretical results. Next we will go through some fundamental topics.

Pierre de Fermat wasn't a professional mathematician. He was actually a lawyer and government official. But he is absolutely one of the most important figures in the history of mathematics. Many people know the story of his last theorem, Fermat wrote his Last Theorem in the margin of his copy of the Arithmetica:

It is impossible to separate a cube into two cubes, or a fourth power into two fourth powers, or in general, any power higher than the second into two like powers. I have discovered a truly marvellous proof of this, which this margin is too narrow to contain.

And it took more than three hundred years for such a proof to emerge. The quest for a proof of this theorem resulted in the development of several branches of mathematics. The eventual proof of the theorem is more than a hundred pages long.

Fermat's little theorem may be less well known to the general public but is more important in cryptography. It is very simple:

For any prime number

n, and for any numbera, 0 <a<n,a≡ 1 mod^{n-1}n.

One application of Fermat's little theorem is primality test, i.e. to tell whether a number is prime or composite. For example, given

n = 31987937737479355332620068643713101490952335301

Is *n* a prime number? Of course you can try to
factor *n*. If you can find any factor of
*n*, then you can conclude *n* is
a composite number. Otherwise it is a prime number. But we know there is
no efficient factorisation algorithm, so it may take you some time. Or
you can pick a number between 2 and *n*-1, for
example let us pick 2, and compute 2^{n-1} mod
*n*, the result is
1281265953551359064133601216247151836053160074. This can be done quite
fast using the square-and-multiply
algorithm. Then we can immediately conclude that
*n* is a composite number. This is because if
*n* were a prime number, then
2^{n-1} would be congruent to 1 modulo
*n* based on Fermat's little theorem. But now the
result is not 1, therefore *n* must be a composite
number.

Let's try again with another number n = 3778118040573702001. This
time 2^{n-1} ≡ 1 mod *n*. Can
we say *n* is a prime number? NO! Fermat’s little
theorem works in only one direction: there is no "only if" in the
theorem. That's means
*a** ^{n-1}*
≡ 1 mod

3

^{n-1}≡ 1 mod*n*

5

^{n-1}≡ 1 mod*n*

7

^{n-1}≡ 1 mod*n*11

^{n-1}≡ 3434652764157910911 mod*n*

So 3778118040573702001 is a composite number! Since Fermat's
little theorem won't tell us a number is a prime, what we can do is to
pick multiple numbers and try then one by one. If one of them failed the
test, then we know *n* is not a prime; if all numbers
passed the test, than we have some confident that *n*
is probably a prime number.

But how many test do we have to do before we are confident enough?
Unfortunately, it is hard to say. Let's call a number
*a* a witness (for the compositeness of
*n*) if
*a** ^{n-1}*
≢ 1 mod

In most cases there are more than 50% numbers which are witnesses,
so the Fermat primality test goes well. But there are some special
composite numbers called Carmichael numbers which have much less
witnesses. For example, 3778118040573702001 only about 12% numbers as
witnesses; 994788345601, only 0.07%. If *n* happens
to be a Carmichael number, then the Fermat primality test may falsely
report that *n* is a prime number. Although
Carmichael numbers are rare, there are infinitely many of them. That's
why in practice we usually don't use Fermat primality test. Instead,
some sophisticated variants are used. For example, Miller-Rabin
primality test and Solovay-Strassen
primality test. Miller-Rabin guarantees that for all composite
numbers (including Carmichael numbers), the error rate is below 25%.
Solovay-Strassen guarantees that the error rate is below 50%. That's
means if a number passes the Miller-Rabin test 10 times, then the
probability of it being a prime number is 1-
0.25^{10} = 0.999999. Those tests only produce a
probabilistic result. If *n* is not found to be a
composite number, then it can be declared *probably
prime*. If you are uncomfortable with this, there are also
deterministic primality test algorithms. For example, the AKS
primality test, which is also based on Fermat's little
theorem.

**Useful Links**