As we mentioned in the first chapter, general questions concerning whole numbers, rather than merely mechanical computations, can be extremely difficult to answer. Indeed this higher (as opposed to basic) arithmetic is one of the most difficult and fascinating branches of mathematics, and has been extensively studied by many of the greatest mathematicians. These mathematicians often spent an enormous amount of time and energy checking their conjectures with specific numbers and sifting through mountains of experimental data. (Mathematics is an experimental science after all. It differs from other experimental sciences, however, because often the amount of experimental evidence prior to the proof of a result might be very slim, and after the proof experimental evidence is strictly irrelevant, although psychologically reassuring.) Anyway, the computational feats of mathematicians of old are often extremely impressive, bearing in mind that they only had paper and pencil (or papyrus and stylus or whatever) to hand. What an advantage we have! Indeed what might Gauss have achieved with his own micro? Let us start our investigations. The emphasis throughout this chapter will be on the building blocks of arithmetic: the prime numbers.

Prime numbers

Recall that a natural number x is prime if it is only divisible by 1 and itself (in other words cannot be written as a product of natural numbers a and b unless a or b is 1). It is fairly clear that any number can be factored as a product of prime numbers and the resulting factorization is unique up to the order of the factors.