A Core Discipline of Math

topOccupy Math was both pleased and startled when a recent post entitled Math is not Science! received a large number of views. The post did not manage, however, to explain very much about what math is. Mathematicians debate this quite a bit and our working definition is the very unhelpful “Math is what mathematicians do.” Bah! Humbug! In this post Occupy Math will give a demonstration of something we agree is the core of mathematics: proof.

Another popular post is How not to Teach Fractions and its follow up post Prime Numbers and Teaching Fractions. Both posts make the point that being able to factor a number into its prime parts is key to being able to do arithmetic on fractions. The prime numbers, though, have importance all through mathematics and beyond, appearing in the strangest places. Occupy Math did a post about how prime numbers are useful in the life cycle of Cicadas and in alien contact protocols. Long story short, prime numbers are a huge deal.

Enough with the greatest hits of prime numbers! Do something new!

There are an infinite number of prime numbers. How on earth do we know that? It surely is not because we made a list! Remember that a prime number is a number that can only be divided, without a remainder, by itself and one. This is if we only use positive, whole numbers. The first few primes are 2, 3, 5, 7, 11 and you can check by hand, pretty fast, that they are not divisible by a smaller number, except one. Being divisible by one is not impressive, because one divides anything.

The paragraphs below are a proof — which Occupy Math’s editor says is like juggling balls, at least mentally. Each sentence adds one ball to the stuff you’re juggling in your head and you will probably drop the balls at some point. The conclusion is in the last sentence and if you get tired out, you can understand the rest of the post by just taking that sentence on board. Occupy Math urges you to challenge yourself: when you drop the balls, pick up the first one and try again. With that pep talk, here is how we prove that the list of prime numbers goes on forever.

Suppose that there are only a finite number of primes. Start by listing them (at least in abstract — we cannot really make this list, it is just there for the sake of argument) and then compute the following number. First, take the product of all the primes in your list and then add one to the result. Call this new number C. Since C, less one, is divisible by every prime number, C cannot be divisible by any prime number: there would be a remainder of the one, inevitably, because we added in the one on purpose to set this up. If C has no divisors other than itself and one, it is prime, which would mean our list of prime numbers was incomplete.

If, on the other hand, C does factor, then one of the numbers that divides it evenly is the smallest such divisor that is still bigger than one. Call that smallest not-one divisor of C by the name d. The property of dividing evenly is transitive, so any divisor of d is also a divisor of C. Since there are no divisors of C smaller than d (except one), we see that d must have no divisors except itself and one … but this means d is prime. Since none of the primes on our list divide C evenly, but d does divide C evenly, we see again that our list of prime numbers is incomplete.

To sum up: any finite list of prime numbers is incomplete! This means that a full list must be longer than any finite number, which makes the list infinite.

primes

Wait! What?

That was a really long argument; Occupy Math apologizes if it was too long. The longest mathematical argument to date is tens of thousands of pages long, if that is any comfort. The argument Occupy Math gave, by way of demonstration, uses a technique called proof by contradiction: you start by assuming the logical opposite of what you want to prove and, from that assumption, deduce a contradiction. This contradiction demonstrates that your assumption was bad, and so proves the thing you wanted to prove in the first place. In this case we assumed we could make a complete, finite list of primes and, from that list, showed that there was another prime — meaning our original assumption of a complete finite list of primes was wrong.

The point is this: by the application of pure logic we can demonstrate beyond any hope of doubt that the list of prime numbers is endless. In fact, since it is impractical to construct infinite lists on paper or in computers, the application of logic by intellect is our only real tool for understanding infinity. This turns out to be true of many areas of mathematics, that logical proof is the only way forward. Here are some of the other facts we have learned about prime numbers and proved by logic.

  1. The fundamental theorem of arithmetic says that every whole number factors into prime numbers in only one way — neglecting the order in which the factors appear.
  2. Fermat’s little theorem says that for any whole number a and prime number p, the number ap-a must be a multiple of p. Let’s try it: two to the fifth power minus two: 25-2=32-2=30 and thirty is a multiple of five. It works!
  3. The prime number theorem says that the probability that a whole number between 1 and N will be prime is close to 1/Ln(N) (the reciprocal of the natural logarithm of N). This is a weird fact, but it does tell us about how many prime numbers there are of a given size or smaller.

There are many, many facts about or concerning prime numbers that we have figured out in the last few thousand years. There are problems about prime numbers that we are still trying to solve. Notice that 5 and 7 are primes that differ by two. We do not know if there are an infinite number of pairs of primes that differ by two. There are problems about the prime numbers we have not yet discovered. Lest you think this is all cloud-castles and abstract nonsense, prime numbers also show up in hard-core real-world applications like computer security.

book

Prime numbers, and the things they imply, are a whole field of math!

Number theory, which has three different large schools inside of it (analytic number theory, algebraic number theory, and elementary number theory) is a huge field of mathematics with both implacably abstract areas and concrete applications. One of the biggest problems right now is that we think that factoring a number into its prime factors is hard — but we cannot prove it. Since the security of financial transactions uses algorithms based on such factorization, this is a little scary. Worse, Shor’s algorithm, which needs a quantum computer to run, has been proven to be able to factor numbers into their prime parts quickly. We’re not sure we can build a big enough quantum computer for this to be a problem.

A quantum computer is a type of computer that can do huge numbers of calculations at the same time by exploiting quantum indeterminacy and then, through careful manipulation, cause only the computations that succeed to bubble out the far end of the process. We have built quantum computers, but only low-powered ones, at least so far. Anything you can compute with a quantum computer you can also compute with a regular computer, but the quantum computation is incredibly faster.

The distribution of prime numbers among the other numbers was noticed as a mystery and a wonder by the ancients. Knowledge of prime numbers is one of the oldest pieces of wisdom possessed by our species. Our knowledge of the properties of the prime numbers grows by several hundred academic papers every year — and yet modern ideas about teaching fractions and other things avoid them in many places as being “too hard”. Occupy Math thinks they are too hard only for people that have given up on the wonder in the world. Do you have topics in math you would like a post about? Please let Occupy Math know in the comments!

I hope to see you here again,
Daniel Ashlock,
University of Guelph,
Department of Mathematics and Statistics

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s