Inside and Outside the Box

The past two classes have dealt with the "division algorithm" and a variety of concepts surrounding it. For convenience I'll restate it: given any natural numbers m and n, there exist unique integers q and r with

        0 ≤ r < n

and

        m = nq + r.

The integer q is called the quotient of m by n, and r is called the remainder. This expression can be put into quotient form, by simply diving both sides by n:

        m ⁄ n = q + r ⁄ n .

We also went over a few definitions that you are responsible for. If the remainder of m by n is zero, we say that n divides m, written

        n | m.

Using this definition of "divides," you should be able to prove the following two facts: if m is any natural number, then

        m | m    and   1 | m.

That is, any number is divisible by itself and 1. If a number m has no divisors except these two, then it is called a prime number.

All of this is very ancient. The formal proof of the division algorithm can be found in Euclid (circa 300 BC), but the proof likely goes back to the Pythagoreans of two centuries prior, if not earlier. The practical use, but not the formal understanding, of the division algorithm is far, far older still.

Indeed it is present in one form or another at the very beginnings of essentially all civilizations---the practicum of mathematics appears to be a requirement for cities and trade, and the equivalent of the division algorithm is found in actuarial tables left in Sumerian cuneiform tablets, the intricate calendrics of the Maya, and taxation records of the Shang dynasty. What motivates its development, apparently, is the needs of tandem developments of economic systems (trade and taxation), legal systems (arbitration, settlement of land/goods disputes), the measurement of time, and the military.

We may take a simple example from the military. Suppose you live in a city-state whose smallest military unit is the phalanx, and that training is based around blocks of soldiers 8 deep and 12 wide (96 individuals). Conscription records indicate you have 5,012 recruits. To plan a campaign you need to arrange, ahead of time, supplies, logistics, and battlefield organization, and you need to know at any given time how many phalanges you'll have. Now, in the days before calculators or even before efficient number systems, this is actually quite serious problem! A city's administrative core would require a scribe or scholar who could answer (or show methods for how to answer) myriads of similar questions. In this case the scribe would tell you that enough soldiers are present for 52 phalanges, with 20 soldiers left over (maybe they can serve as scouts). That is, 5,012 by 96 has a quotient of 52 with a remainder of 20.

Now most cultures did not develop math beyond these practical uses, possibly because most cultures' needs extend no further, possibly because many cultures didn't have time for that development (many civilizations in the archeological past lasted 1,000 years or less), and possibly because of internal cultural proclivities---sometimes people are not interested in math for its own sake. Go figure!

I want to say something about this. The simple use of mathematics in solving other kinds of problems is what I call "in the box" thinking with regards to math. To relate this to our political system, it is a framework that you can function within, and attempt to use, as a tool, to accomplish your goals. If politics is used this way, you choose a side that suits you (left or right, Repubs or Dems), and you lobby, vote, speak, or participate in other ways. Or you can jump out of the box and think about the system, for instance you can think about what kind of system we should have instead, whether or not the current paradigm is just what we have to live with, and how we could change the system.

Likewise math can be used just to compute, calculate, and problem solve: that is, the system (math in this case) can be used. In some places and times in human history, people have left the system's confines and thought about the system. In mathematics, this originally occurred (to my knowledge) in two human cultures: during either the late Zhou dynasty or early Warring States period (records are unclear owing to the destruction of that period), and during the classical Greek enlightenment. Both periods were in the rough time frame of 500-200BC. In the Greek world, the concept of formal mathematical proof---a crowning jewel of that culture's intellectual achievement---was developed. Through the ebb and flow of cultural history (empire, fall, feudalism, enlightenment, global trade, technology), the concept of proof persisted, and remains with us, virtually unchanged, in the present day. The concept of proof is the main tool we use to understand math, as opposed to just using math.

So we want to ask about numbers. We have these special numbers, the primes, that have no divisors except the two that any number must have. In a sense, primes are natural phenomena: they have been observed by many cultures in disparate times and places. We have some examples of primes (2, 3, 5, 7, etc), but in total, how many primes are there? What is the proportion of all numbers that are prime? The second question was asked long ago but not answered with any degree of precision until the Prime Number Theorem was proved in 1896:

        The number of primes between 1 and n is approximately n / ln(n).

The answer to the first question was provided more than two millennia earlier by the Greeks themselves: there are infinitely many prime numbers. The proof is by contradiction. To begin, we assume there are just finitely many primes, and, using this assumption, derive a contradiction.

So let's start. Assume just finitely many primes exist, and that p₁, p₂,  . . . ,  p_N is the full list of all prime numbers. Then consider the number

        T = p₁ p₂ . . .  p_N + 1

formed by multiplying all the primes together, and adding 1. From here it is easy to show that the remainder of T by p₁ is 1, the remainder of T by p₂ is also 1, etc. That is, the quotient of T by any of the primes is 1. Therefore T is not divisible by any prime, and it must therefore be a new prime number. But we assumed that that  p₁, p₂,  . . . ,  p_N  was a list of ALL primes!

This impossibility means that it could not have been the case that  p₁, p₂,  . . . ,  p_N  was a list of all primes. This means is that ALL primes cannot be put into any finite list---the quantity of primes, then, must be infinite.

I mentioned that time-keeping was one of the earliest uses for math. Coming up in class, we will discuss special kinds of mathematical systems designed for exactly this kind of application.