Blogs, Mathematical Reasoning, Proofs

All those primes

Irreducible and Prime Numbers

The natural numbers (or counting numbers) is the set of numbers that comes most naturally to people.  We start off with one object, then if we put one object together with another object, we have two objects.  If we continue adding one more, we end up with any natural number we want.  Thus, the set is generated, under addition, by the single element, one.

While the natural numbers under addition are straight forward, somewhere along the line, someone decided they wanted to look at this thing called multiplication.  Well, we just add the same thing over and over and we get some new natural number, that seems easy enough.  However, if we try to generate the set of natural numbers using only multiplication, we arrive at a much more complicated problem than that of generating the natural numbers under addition.

Looking at the natural numbers under addition, we can say that a number is irreducible (or cannot be reduced) if it cannot be written as the sum of two other natural numbers.  Note that since every number can be written as n=(n-1)+1, hence the only irreducible natural number is one, since 0 is not a natural number.  Note that, if n-1 is not 1, we can then reduce this number.  We can continue to do this until n=(1+1+1…+1), where we have n ones.  That is we can reduce any number into a sum consisting only of the number one.

If we change this definition to work for multiplication, we would say that a number p is irreducible if p cannot be written as the product of natural numbers.  In other words, if p=a*b, then a=p and b=1, or a=1 and b=p.

When we looked at the natural numbers, I want to point that did not include 0 in the set, because it doesn’t help to create any new numbers.  That is, if we add 0, we just end up where we start.  For the same reason, we could exclude 1 from the set of natural numbers if we were only interested in multiplication.  That is, 1 times anything gets you where you started.  However, instead of ignoring 1 completely (or 0 with addition) we would call it an identity element and make an added assumptions that an identity element is when determining if numbers are irreducible.  That is, while 1=0+1, 1 is not equal to the sum of any numbers if we do not include 0 in the set, hence we call 1 irreducible.  Similarly, p is irreducible for multiplication if p cannot be written as the product a*b if we do not allow for the use of the identity 1.  Since we are not using the identity, we would furthermore not consider the identity to be an irreducible or reducible number.

Now that we’ve defined irreducible, I should point out that such irreducible natural numbers for multiplication are called prime numbers.  Here, if we have a reducible number, we can rewrite as a product of two natural numbers, both greater 1.  If the terms are reducible, we can do this again.  Each time, the terms of the product will get smaller, unless we arrive at a prime number.  Since, if we start with a natural number n, we can’t get smaller than 1, every natural number can then be written as the product of these prime numbers.  In this way, we would consider the prime numbers as the set of numbers that generate the natural numbers for multiplication.

How many primes are there?

The question that then comes to mind is, how many prime natural numbers are there?  Well let’s start by listing some: 2,3,5,7,11,13,17,19,23… While we could keep going, it is clear that there is more than one prime, so finding a generating set for multiplication will be much more difficult than just stating that 1 is good enough.  Then we could ask, could we find all these elements?  That is, are there a finite number of such elements?  If there aren’t can we provide a pattern for determining what they would be in general?

In order to answer these questions, I want to point out that the act of finding large primes is an ongoing problem.  We are still looking for larger and larger primes, because knowing such primes is helpful in many applied setting.  One such area is cryptography.  Here we can decode a message using a numeral equivalency for the symbols, than apply some invertible operation to get out a new set.  Then person that receives the message can then apply the inverse operation and get the original out.  The use of primes comes in, because if we use the integers mod p for some prime p, then we can use matrix multiplication over this field and have an invertible mapping.  If someone wants to decode the message they would then both have to find the prime p we are using and the inverse matrix.  Hence, if you know a prime that no one else knows, this gives them no way to decode your message unless you give them the key.

Therefore, I should point out, that we do not have a nice way for determining what each next prime will be.  Therefore, we only know a finite number of primes, so there is no way for us to create a list of infinitely many primes.  If we wanted to prove that the set of primes is infinite directly, this is exactly what we would have to do.  Therefore, this is something that the mathematical community does not know how to do at this point.  On the other hand, the fact that we only know finitely many primes, does not necessarily mean that there are only finitely many primes.  Hence, we need to try something else to see if we can determine if the set of primes is finite or not.

Can there be only finitely many primes?

We haven’t provided an answer for this yet in this post, so let’s assume that there are only finitely many primes.  What does this mean?  We then have

  • Since there are only a finite number of primes, we can say there are exactly k primes and we can list them out.
  • Let the primes be p1,p2,…,pk be all of the primes.
  • Since there are k primes, then p=p1*p2**pk is a natural number.
  • Note that pi divides p for all prime pi, therefore,pi does not divide p+1.
    • If the prime did divide p+1, then we would have 1/p is an integer, but the only way this is possible for a natural number is if p=1.
  • Hence, p+1 cannot be written as the product of primes, and therefore must be prime.
  • However, this contradicts are assumption that we had listed all primes since p+1 is greater than all listed numbers.
  • Hence, there must be infinitely many prime numbers.


Wow, after all that, I spent almost the entire post explaining what question we were asking and showing that it would be extremely difficult to answer the question.  It seemed like there was no hope, but then after an argument using only 7 statements, we’ve proven that there must be infinitely many primes.  This is one of the reasons I enjoy this proof so much, it takes longer to set up the question than it does to provide an answer.  Furthermore, this is an extremely important result.  It tells us that the set of natural numbers is not generated by some fixed set of primes under multiplication.  Rather, we need infinitely many such primes in order to create the infinite natural numbers.

I hope you enjoyed this proof as much as I do.  If you did, please like the post or comment what you thought below.  There are more proofs to come, so make sure to follow the blog so that you know when these posts are made.

4 thoughts on “All those primes”

We'd love to hear your thoughts!

This site uses Akismet to reduce spam. Learn how your comment data is processed.