The fundamental theorem of arithmetic states that every integer greater than one is either is prime or the unique product of primes, ignoring the order.
Many will remember the definition from primary school. A prime is a number divisible by only two others, one and itself. All other numbers are made from two or more of these primes multiplied together. Some might even remember that one itself is not prime. But mainly, people remember the tedious process of finding prime factorizations of numbers and lowest common factors of pairs. It’s not until after a little exploration into number theory that one begins to realise the mysterious yet powerful properties of these numbers.
Prime numbers are universal. Prime numbers are compared to fundamental particles, making up all numbers and they conserve this property in any base, in any language. If we were to encounter extraterrestrials on their planet, a list of primes in an intuitive form could be the best way to establish the level of their development. (I say on their planet because if they had the means to travel to Earth they are bound to be somewhat intelligent and scientific)
There are an infinite number of primes. The best known and most easily understood proof is by Euclid and uses contradiction:
1. Assume that there are a finite number of primes
2, 3, 5, 7 … p (mathematicians often use lowercase p to represent a prime)
2. Multiply each known prime together and add one to get a new larger number q
q = 2 x 3 x 5 x 7 x … x p + 1
3. None of the known primes between 2, p is a factor of q. Each would leave a remainder of 1 on division.
4. If q is not prime then it must still be divisible by a prime larger than p. Otherwise, q is itself prime. In both these cases, there must be a prime larger than p.
5. Steps 1-4 can always be applied to the newly obtained set of prime, extending it. Hence the list is the real never ending story, in other words infinite.
The rest of “Prime Numbers and How to Find Them” will be uploaded in short segments throughout the next few weeks. I’ll be talking more about patterns in primes, the Sieve of Eratosthenes, prime spirals, use in cryptography, modern prime searches and how you can get involved, and the yet unsolved mysteries of prime numbers. Follow my twitter feed for updates on my writing and for other bits of mathematics in 140 characters or less.