Math for Dummies part 2

This maths lesson is a little bit harder than the first one, but it is more powerful. It is also the basis for all modern cryptography. A child of 12 or 13 who is good with multiplication and division can understand it. Let's begin.

Definitions: A prime number is a whole number that is divisible only by itself and the number 1. The number 1 is not defined as being prime. A number is divisible by another number if the resulting fraction is another whole number.

Theorem: There are an infinite number of prime numbers.

Proof: Proving that there are an infinite number of something is kind of hard. Let's assume the opposite and see if we can disprove it. So if we can disprove that there are a finite (or limited) amount of prime numbers, we have shown there must be an infinite supply of prime numbers.

Given that we have assumed there is a limited supply of prime numbers, we can easily list them. So we have a list of prime numbers for which we will use alphabetic symbols instead of the actual numbers:

a, b, c, d, e, f

There could easily be more, but for the time being we just list these. Now the math gets a little tricky, but just get your pen and paper and we'll be fine.

Assuming these list of prime numbers is complete, let's find out if there could be any more numbers that fit a prime definition that isn't in this list. Let's try a trick where we multiply all the prime numbers together and then add 1 to them:

(a * b * c * d * e * f) + 1

This resulting number cannot be divisible by any previous prime number. Any previous prime number in our list would always have a remainer of 1 (that's why we add 1 in there). It also cannot be divisibly by another other smaller number -- why is that?

Notice that any number that is not prime would be divisible by some other smaller numbers. The resulting divisors would either be prime themselves or not. If not, they could be divided again. Eventually, you will be left with a bunch of divisors that are all prime! Let's try this example with the number 20:

20 is divisible by 10 and 5. Clearly 5 is prime. But 10 is not.
10 is divisible by 5 and 2. Clearly 5 and 2 are prime.

So, any number that is prime is divisible by only itself and 1. Any non-prime whole number is divisible by (eventually) a series of primes.

So, backtracking a little bit to our number again:

(a * b * c * d * e * f) + 1

This made up number is not divisible by any of a, b, c, d, e, or f, and cannot be divided by any smaller number (because those smaller numbers would be in turn divisible by a, b, c, d, e, or f). So this number we invented is another prime number!

What we have shown is that if we believe we have a comprehensive list of prime numbers (no matter how long a list), then we can always generate a larger number that is also prime!

Clearly, there are an infinite number of primes.

Did you get it?