## Primal Soup

Number theory really began with Euclid, around 300BC, in books 7 through 9 of his masterwork, *The Elements*. It is here that we find the original definitions of odd and even numbers, prime and composite numbers, perfect numbers (numbers which are the sum of their factors, e.g. 6 = 3 + 2 + 1), and more. But the greatest achievements of all were his proofs that composite numbers are the products of primes, that this factorization is unique, and that there are an infinity of primes. Most introductory algebra or number theory classes cover these three great proofs, but they are worth revisiting for those who may have forgotten.

Before doing so, it is worth revisiting Euclid’s clever algorithm for calculating the greatest common divisor (GCD) of two numbers. We made use of this when solving the Monkey and Coconuts puzzle.

We divide the smaller number into the larger and keep track of the remainder. Then we divide that remainder into the smaller number to get a second remainder, then divide the second remainder into the first remainder to get a third remainder, and so on. Eventually we get a remainder of zero; the remainder just before this is the GCD. If this happens to be one, we say the numbers are coprime. For example, consider 64 and 10:

- 64 = 10 x 6 + 4
- 10 = 4 x 2 + 2
- 4 = 2 x 2 + 0

So the GCD is 2.

For another example, consider 77 and 65:

- 77 = 65 x 1 + 12
- 65 = 12 x 5 + 5
- 12 = 5 x 2 + 2
- 5 = 2 x 2 + 1
- 2 = 1 x 2 + 0

So the GCD is 1 and the numbers are coprime.

In the proofs below we make use of a special case of Bézout’s identity, which states that if two numbers and have a GCD, then there exists some and such that. In our case we care about the situation where and are coprime, so that there exists some and such that. We aren’t proving that here but it is exactly equivalent to solving the Diophantine equations we solved for the Monkey and Coconuts problem (where and where the number of coconuts at the start and end).

**Proof that Composite Numbers have Prime Factors**

Let be a composite number. Then by definition must be divisible by some smaller number. If is prime we are done; if is not prime it is must be divisible by some smaller number, and so on. Continuing in this way, we find:

This sequence must terminate with a prime number in the last position before 1; if not, that is, if each successive number is still composite, then the series is infinite, but we cannot have an infinite series of decreasing whole numbers.

**Prime Factorization Theorem (aka the Unique Factorization Theorem aka the Fundamental Theorem of Arithmetic)**

There are two steps: first we show that if a prime divides a composite, then must divide at least one of or. Assume does not divide – then the GCD (greatest common divisor) of and must be 1, as is prime. By Bézout’s identity, there must be some integers and satisfying. Multiplying both sides by gives, and both terms on the left hand side are products of, thus must be a product of.

Now for the main proof. Let be the smallest natural number that can be written as a product of prime numbers in more than one way (ignoring ordering, of course). Let one factorization be and another be. The previous result proves that divides either or. Because both and must have unique prime factorizations, must equal some. If we then remove and we have two different factorizations of a number which is smaller than, which contradicts our assumption that is the smallest such number.

**Proof of the Infinitude of the Primes**

Assume the set of primes is finite, given by. Consider the number . This is not divisible by any of the primes in the set; it always leaves a remainder of 1. Therefore it is either itself prime or has other prime divisors not in the set, and so the set is incomplete.

Further reading: William Dunham’s Journey through Genius: The Great Theorems of Mathematics has two chapters on Euclid’s elements and covers much of this material (although he omits the proofs apart from the last one). Proofs from THE BOOK has about six different proofs of the infinitude of the primes, each using a different branch of mathematics, from algebra to set theory to topology. To dust off my rusty memory of these proofs I had to pull out my well-thumbed college textbook Rings, Fields and Groups: An Introduction to Abstract Algebra, but while it is a great text I wouldn’t recommend it to those faint of heart!

## Archimedes counts the sand

In a previous post I described the Babylonian/Sumerian sexagesimal (base 60) counting system. Unlike this system, most cultures adopted a base 10 counting system due to the natural inclination to count with the fingers (leading to the term *digits*). Less common were quinary (base 5) systems, but vigesimal (base 20) were not unusual – for example, this was widespread in native American culture, including (with a novel variation) the Mayans. Duodecimal (base 12) has also played a role; we still have remnants in the groupings of dozens and gross.

Once the numbers in the base group are exceeded, we need to group to represent larger numbers – for example in decimal we have units, tens, tens of tens (hundreds), and so on. The Mayans used a novel variation where the second grouping only went up to 18, although after this the groupings reverted to base 20 again. This means the second order group represents numbers up to 360 rather than 400, and may relate to the Mayan calendar of 18 months of 20 days plus 5 extra days.

The larger groupings have names that are often quite recent introductions to language; while the term *hundred* can be traced back to a root meaning *ten times (ten)*, the word *thousand* has no clear relation to the roots of Indo-European languages and is likely quite a late construction, seemingly from an early Germanic term meaning *great hundred*. An exception was the Hindus who seemed attracted to large numbers; there is a story from the life of the Buddha which mentions numbers up to. The Greeks typically stopped at *myriad* (ten thousand), and for a long time the Roman number system stopped at 100,000; the term for a *million* appeared around 1400AD in Italy. Numbers larger than a million have appeared so recently in European language that there is no common agreement – a *billion* in Europe is while in America it is (called a *milliard* in Europe), and things get worse for trillion and quadrillion.

One of the first known efforts to systematize the number system to encompass large numbers is Archimedes’ *The Sand Reckoning*, a treatise addressed to his relative King Gelo of Syracuse, in which Archimedes constructs a systematic method for representing arbitrarily large numbers while addressing the problem of estimating the number of grains of sand in the universe. In his preface, he stated “There are some, King Gelo, who think that the number of the sand is infinite in multitude; and I mean by the sand not only that which exists about Syracuse and the rest of Sicily but also that which is found in every region whether inhabited or uninhabited.” Archimedes went on to use myriads raised to the the power of myriads, successively, to represent the very large numbers he needed for his calculations. In the process of doing this Archimedes discovered and proved the law of exponents:

Archimedes had to estimate the size of the universe. He assumed a heliocentric model, with the earth revolving around the sun, the sun at the center, and the stars at the periphery. By his estimates the universe was about two light years across. Given we now know the next closest star to our sun is about 4 lights years away this was quite impressive for the time!

## More on Diophantus and Fermat

In a previous post I wrote about how Fermat scribbled his famous “last theorem” in the margin of Diophantus’ *Arithmetica*. This is called Fermat’s last theorem not because it was the last thing Fermat wrote but because of all the incomplete theorem’s we know were left by Fermat it was the last to be proved, taking about 350 years.

The section of the book where Fermat wrote his comment was on finding *Pythagorean triples*: square numbers whose sums also form squares. Such numbers can be the sides of Pythagorean (right-angled) triangles, the most well know being 3-4-5.

The *Arithmetica* was a book of computational methods rather than theoretical mathematics. In modern terms we would call it a book of numerical algorithms. Much of the material was not invented by Diophantus but was collected by him. This includes his method for finding Pythagorean triples, which was as follows. Take any two whole numbers and. Then the following three numbers are the sides of a Pythagorean triangle:

Furthermore, any such triple can be multiplied by a constant to get another triple (e.g. the triple 3-4-5 can be multiplied by 3 to get the triple 9-12-15, etc).

Fermat’s theorem asserts that while there are an infinite number of Pythagorean triples, there are no solutions in whole numbers for higher powers. Fermat did leave a proof for the fourth power. Euler proved the theorem for the third power. Dirichlet proved the theorem for fifth and 14th powers. Lame and Kummer managed to prove the theorem for all powers up to 100 except for 37, 59 and 67. By 1980, the theorem had been proven for all powers up to 125,000!

It took some modern developments in elliptic functions to proceed further. Elliptic functions are functions in two unknowns where one unknown is squared and the other cubed (e.g. ). It was found that if Fermat was wrong, and there is a solution for some power higher than two, then that solution describes a very unusual elliptic curve, so unusual it seems unlikely it could exist.

In 1986 Kenneth Ribet showed that such an elliptic curve would violate the 1955 Taniyama-Shimura conjecture, which claims that every elliptic curve is associated with a modular function. While the Taniyama-Shimura conjecture was not itself proven this did provide a link between two fields of mathematics, and it was this conjecture that was ultimately proven by Andrew Wiles and a former student in 1993 and 1994, thus finally proving Fermat correct.

If Fermat really did have a proof, though, then there is a much simpler proof still waiting to be found…

## The Wandering Ant

Imagine an infinite grid filled where each square is initially either black or white. On this grid is an ant, which can face either north, south, east or west. The ant moves over the grid according to the following rules:

- it it lands on a black cell it turns left 90 degrees; if it lands on a white cell it turns right 90 degrees
- in each case the cell it just left changes color to its opposite (white to black or vice-versa)

Running a computer simulation of this system, which was invented by Christopher Langton in 1986, shows that after a while the ant gets stuck in a cycle of 104 moves which move it two squares diagonally, after which point it continues building this diagonal “highway”. It is speculated that this will always occur (in which case we say that this sequence is an *attractor* for the system), regardless of the initial state of the grid, but so far no-one has been able to prove it (or the opposite).

The diagram to the left shows what happens with an initial white grid after 11,000 moves. The ant is the red pixel near the bottom right. Note the diagonal highway moving down and to the right.

In 2000 it was shown that Boolean circuits (AND, OR, NOT) could be created with the ant, and so the ant system is a universal computer or Turing machine.

Some interesting extensions can be made to this system. For example, more than two colors can be used, or more than one ant can be used (as long as there are rules for what happens when they collide). Rules can be added to make the ants reproduce. One of the simplest but most interesting changes is to give the ant a color, and have the rules of the system be extended to include changing the color of the ant, as well as being dependent on the color of the ant (e.g. we could have the turn rules behave as above if the ant is white but be reversed if the ant is black). Such ants that have state are called *turmites*, and can generate some very interesting patterns (originally these were named tur-mites by A.K. Dewdney but Rudy Rucker shortened the name and his version has stuck).

Further reading: Professor Stewart’s Cabinet of Mathematical Curiosities has a short chapter where I first learned about Langton’s Ant, and Stephen Wolfram discusses them briefly in a section on Turing machines in his opus A New Kind of Science.

## The Mathematics of Toilet Rolls

In the late 1980s I was contracted to write some software for a company that produced video-based educational systems. They had video cassette machines that had been modified to interface with a PC, which could send instructions to the VCRs such as play, stop, fast forward, and rewind. The educational programs consisted of short recorded segments which typically ended with a question, and based on the answer the user provided they wanted to continue play at different portions of the tape. The software they wanted me to write was meant to be able to be given a current position (i.e. play time) and advance to a new position. For example I might be told that they are at minute 8 currently and want to resume play at minute 12.

Without going into all the detail, I can tell you this was a Very Hard Problem. There was no way to tell where you were on the tape without actually playing, and if you are familiar with VCRs (which are rapidly going the way of the dinosaur) you may be aware that engaging the play head takes a few seconds. There were variations in motor speed, tape stretching, and all sorts of other variables to take into account. The approach I used was to try to calculate the “optimal” fast forward time, shorten that a bit, and then narrow down to the exact position with a modified binary search (or, to put it more crudely, “trial and error”).

We got the system to work although it was a pretty crude affair but before anything shipped new VCRs came out that recorded “time code” on the tape and had much more precise electronics essentially supporting just this functionality we had duct-taped together, and so it was all for naught (and not long after CD-ROMs came and made it all redundant anyway).

I don’t remember all the math that I worked out for this system, but it is easy enough to recall the basic parameters. There was the diameter of the empty plastic spools, the diameter of a full spool, and the playing time of the tape (typically 120 minutes), which was a linear function of the length (assuming an unstretched tape :-))

While playback happened at a constant speed, as the tape ran through an independent roller mechanism unaffected by the spool state, fast-forwarding and rewinding happened at a variable rate, as it was controlled by the motors driving the spool, and the spool diameters changed.

All in all, a nasty business, and we are better off without tape! But there is still a common household item with some similar characteristics, namely the toilet roll. So, here are some problems surrounding toilet rolls to think about. To save you having to measure your toilet rolls here are some typical measurements from mine (Charmin 2 ply from Costco) – spool diameter 45mm, roll diameter 120mm, 250 x 101mm sheets = 25250mm length.

- how thick is each sheet of paper? (and thus, how many times does it go around the spool?)
- what would the diameter of a roll be that went all the way around the earth (assuming the earth’s diameter is 12,756.32km)?
- what if it went around the earth but 1m higher than in the example before? How long would the roll be? (you may recognize this as a familiar puzzle involving rope but I thought I’d sneak it in here!)

(BTW no less a figure than Donald Knuth has considered toilet paper worthy of investigation, as evidenced here).

If we call the paper thickness, the radius of the spool and the radius of the roll (spool plus paper), then it should be obvious that the number of winds is:

If we approximate the roll as a number of concentric circles rather than a spiral, then the innermost roll has length, and the next roll has length, and so on; each successive roll is longer than the prior one, and the final roll has length.

Because each successive roll is longer by a constant amount, we have an arithmetic sequence. Recall that the sum of an arithmetic sequence is given by, where is the number of terms, is the first term, and is the last term. So the length of the entire roll is given by:

Thus my toilet paper is about 0.38 mm thick – quite luxurious!

For the second problem it is reasonable to assume, to give us the simpler formula:

or:

or:

where is the earth’s diameter. So for my paper this would be about 70 meters. If I had a cheaper brand of one ply paper this might be considerably less.

I’ll leave the last question as an exercise but it should be fairly clear that the difference in in this case is quite small and so the extra radius needed for the toilet roll is very small.

## Babylonian numbers in 60 seconds

My 5 year old daughter wanted to heat something up in the microwave. I suggested she use a minute, and she asked me how to enter that. I said enter 1, 0, 0, Start. “But when mom tells me to do a minute she says 6, 0, Start”, she responded. I wasn’t sure how to explain to her that 1:00 minute is the same as 60 seconds; microwaves are confusing enough to her as is.

So why are there are 60 seconds in a minute? Why not 100? The answer lies about 4000 years ago, in some of the earliest known mathematics, of Sumeria and Babylon. The Sumerians and later the Babylonians used a *sexagesimal* (base 60) number system for their astronomy (although they used decimals for day-to-day applications). They had no way to represent non-whole numbers other than as fractions, and 60 was a convenient base as it has a large number of factors; in particular it can represent 1/2, 1/3, 1/4, 1/5, and 1/6 all with whole numerators. In fact sexagesimal notation can be used to exactly represent any fraction in which the denominator has prime factors of 2, 3, and/or 5 (as these are the prime factors of 60), with a finite number of symbols.

Interestingly, both cultures did not have 60 distinct symbols but still used base 10 representation for numbers in the range 0..59, with narrow vertical wedges for 0..9 and thicker horizontal “corner” signs for 0..5 tens:

However, numbers were encoded as base 60 using place notation. For example, decimal 63.3 would be written as 1, 3 . 18.

As there was no symbol for zero interpreting these numbers sometimes had to be done in context; often a space was used although various other symbols were introduced later, like slanting wedges. As far as we know these symbols didn’t represent “zero” as we understand it – that came later – but just represented a “void” position.

Sumeria was invaded by the Akkadians around 2350BC, who adopted the Sumerian system but introduced new symbols for hundreds and thousands.

This system was an improvement over the earlier Egyptian notation, which was base 10 but, apart from a few special cases, was limited to fractions with one as the numerator (i.e. reciprocals only).

## Monkeying Around

After a huge storm blew up, the ship foundered. Dawn’s light found just six survivors washed up on a desert island – five men and one monkey. The men spent the day gathering all the food they could find – which was just a pile of coconuts. After a dinner of coconut milk and flesh, the exhausted men decided to they would divide the remaining coconuts up the following day, before splitting up and exploring the remainder of the island.

During the night one man woke up and started worrying about whether there would be a disagreement in the morning over the coconuts. He decided to take his share, and divided the coconuts equally into five. There was one left over which he gave to the monkey, then he took his share and hid them away, before going back to sleep.

A little later the next man woke up, and had the same fear. He too divided the coconuts into five, and had one left over that he gave to the monkey, before hiding his share and going back to sleep. And so the night went on, with each man waking up, dividing the remaining coconuts in five, hiding one share and giving the one extra to the monkey.

In the morning, the men awoke and divided the remaining coconuts, which came out to five equal shares. No-one said anything about the missing coconuts as each thought he had been the first to hide a share and was thus the best off.

How many coconuts were there in the beginning?

It is not difficult to express this problem as a set of equations; what makes the equations hard to solve is that the solutions must be integers. Such equations are called Diophantine equations, after the 3rd century AD’s Diophantus of Alexandria, who was the first known algebraist to examine equations limited to rational number solutions. We know little of Diophantus himself other than the following puzzle left after his death:

- his childhood lasted 1/6 of his life
- he grew a beard after another 1/12
- after 1/7 more he married
- 5 years later he had a son
- the son lived to half Diophantus’ age
- and Diophantus died 4 years later

From this we can determine how long Diophantus lived, how long his boyhood lasted, what age he grew a beard, what age he got married, when he had a son, and how long his son lived.

Diophantus’ great work, The Arithmetica, is a text on computational arithmetic rather than theoretical mathematics, closer to the mathematics of Egypt, Babylon and India than to Greece. Diophantus promised 13 books in his introduction but only ten are known, with four only being discovered recently in an Arabic manuscript found in Iran. The earliest commentaries on The Arithmetica were written by Hypatia, the first known Western female mathematician, who was brutally murdered by a mob of Christian fanatics in 415 AD as they burned Alexandria’s great library to the ground and destroyed much of the world’s repository of classical knowledge.

Many people are familiar with Fermat’s famous “Last Theorem”; it was in the margins of a copy of Diophantus’ Arithmetica (Book 2, problem 8 ), in which Diophantus describes how to find solutions to for a given value of, that Fermat wrote his famous note asserting that there are no solutions to equations of this form for any powers higher than two, and that “For this I have discovered a truly wonderful proof, but the margin is too small to contain it.”

Going back to the coconuts, if we call the initial number of coconuts and the number hidden away by each man as respectively, and the number of coconuts each sailor got on the next day as, we get this set of equations:

We can use successive substitutions to reduce this to a single equation in two unknowns. The first sailor took coconuts, and left coconuts. The second sailor then took coconuts and left coconuts. Continuing in this way we can find that the number of coconuts left by the third, fourth and fifth sailors were,, and respectively. Therefore:

or:

Normally, for real numbers, we would need two equations in two unknowns, but because we know the solutions must be integers the possible answers are more constrained. Equations of the form:

are known as linear Diophantine equations; in our case, and, and we have:

If and have a common denominator, then clearly for the equation to have integer solutions must also be a multiple of this common denominator.; if it is not, then there are no integer solutions. So we can simplify a linear Diophantine equation by dividing the coefficients of x and y, and the constant, by their greatest common denominator (GCD). The coefficients are then relatively prime, the gcd is 1 and no further simplification can be done.

Assuming we can simplify to the point where we have co-prime coefficients and still have an integer constant, we will have solutions – in fact, an infinity of them. This is quite easy to show. Assume we do have two solutions, and. Then:

and so:

So the difference between two solutions for must satisfy:

If is the GCD of and, then we can divide both and on the right hand side by to get a coprime numerator and denominator:

Because and are coprime, the smallest that can expand the right hand side out to an integer value is:

And similarly:

So we have an infinite number of solutions of the form:

The problem usually comes down to finding the smallest pair of positive integers that satisfy the equation.

To solve a linear Diophantine equation such as the one above, we can apply Euclid’s method for finding the GCD of the coefficients (which will be 1, as our coefficients are coprime, but we are interested in the steps anyway):

Note how the coefficients on the left of the right hand side match those in the continued fraction:

We can invert the steps to get a solution. Starting at the bottom:

We keep expanding this, working backwards, and substituting the equations we have derived above for the remainders:

So we have determined that and is a solution of. This is all very well but how do we adjust this for the fact that the value we actually care about is 8404, not 1? Simple! We just have to multiply each side by 8404 to get a solution to our original equation, namely and .

We know from earlier that the general solution of our equation has the form:

It’s easy to see we have our first positive solution at, namely and . So there were 3121 coconuts originally, and on the last division each sailor got 204 coconuts.

A variant of this problem has there being a single coconut left on the final day as well. In this case there is a very clever trick that can be used, which uses the fact that if we add four coconuts to the original pile it is evenly divisible by 5. If we allow the use of *negative* coconuts it is easy to see that –4 is a solution. In this case, the first sailor divides the pile into 5 negative coconuts, gives one positive coconut to the monkey, and returns four negative coconuts to the pile, so there are once again –4 coconuts! Each sailor repeats the same process, always leaving –4 coconuts. To get to the first positive solution we just need to observe that since we divide the pile into 5 six times, each successive solution must be larger than the last, so the first solution is 15621.

This variant appeared in a short story by Ben Ames Williams that ran in the Saturday Evening Post in October 1926. Williams did not include the answer, and the Post’s offices were flooded with letters, to the point where the editor sent Williams a wire: “For the love of Mike, how many coconuts? Hell popping around here”. Williams continued to receive letters requesting the answer for the next twenty years!

Further reading:

I first heard this problem, and learnt the method of continuous fractions, as a high school student when doing an extra-curricular math class at the University of the Witwatersrand’s Schmerenbeck Center (so long ago Diophantus may still have been alive). Martin Gardner’s Colossal Book of Mathematics discusses this problem in the first chapter, along with some unorthodox and general solutions. Steven Hawking’s book God created the Integers includes annotated excerpts from The Arithmetica, and some biographical material. Clifford Pickover’s The Math Book includes a chapter on Hypatia.