## October 16, 2011

### The Primes keep rolling on

Days and long nights on the road escorting 80 spirited kids around the sights of Agra and Delhi, and I'm tired even 5 days after our return. Minimal time for and access to the Web means this blog has been neglected for some time now. Let's see if I can pick up the pieces.

First, some writing that's on air.

My Mint mathematics column went live on Friday, October 14. In deference to vociferous demand, it manages to mention both Arshanapalayam and Dumbledore. There's a passing reference to Euclid thrown in, too.

See The primes keep rolling on.

Comments welcome.

And in case the link doesn't work, the text of the essay is below.

***

The primes keep rolling on

A possibly strange beast featured in my last column. No, I don't mean kitties named Aziz or Cleo. They aren't strange. What I'm referring to is the factorial. To jog your memory, the factorial of a positive number is what you get when you multiply all the numbers between 1 and itself.

Thus 4! ("four factorial") = 1 x 2 x 3 x 4 = 24.

Writing that, I can visualize eyes glazing over. Sure, I used this in the last column as an example of what recursion does well, but maybe you're wondering, why? Of what possible use is it to multiply numbers in this crazy way? Why subject us to this stuff?

Good question. We should all keep mathematicians, and those who try to write about mathematics, on their toes, especially when they try to foist evidently obscure operations on us. So yes, what is this factorial business?

Actually, it isn't that obscure.

Imagine you have four framed photographs of different relatives -- Arshanapalayam, Bob, Cherukuri and Dumbledore -- that you want to put in a row on your wall. You worry, because they are all fussy and prone to taking offence about where in the row they appear. My advice, of course, would be to fling all the photos out: equal opportunity offence. But that's not practical. Besides, it doesn't lend itself easily to mathematical intervention. So you decide that each day, you'll shuffle the positions of the photos. How many days before you must repeat an arrangement?

In other words, in how many different ways can you order the photographs on the wall?

Start with the first place. Any of the four photographs -- A, B, C or D -- can go there, meaning there are four ways of filling it. Once you've done so, let's say with C, go to the second spot. For which -- since you've used up C -- you have three frames available (A, B, D). That is, for each way of choosing a frame for the first spot, there are three ways of filling the second. Thus 4 x 3, or 12 ways of filling both the first two. Say you choose A for the second spot. You have two frames left (B, D), and either can occupy the third spot. So for each of the 12 ways of filling the first 2 slots, there are 2 ways to fill the third. Thus 4 x 3 x 2, or 24 ways, to fill those three. In our case, say you choose D for spot 3. Which leaves you with just B for the last slot -- or, only one way to fill it.

Thus your answer: there are 4 x 3 x 2 x 1, or 4!, or 24 ways to order the photographs. One of those, CADB, is what we chose above.

How many of the 24 will offend which of your relatives is also not a question that lends itself easily to mathematical intervention. But what you do have is 24 days of fresh arrangements, before you repeat.

If you had 5 framed photographs -- cousin Ekalavya joins the grumpy gang of four -- you'd have 120 arrangements.

Not much to write home about, even if it buys peace with fussy relatives? Then consider how the great Greek mathematician Euclid used factorials to prove that there is no such thing as a largest prime number.

Primes, remember, are numbers that have no factors other than 1 and themselves. For example, 3, 7, 19 and 31 are primes. Whereas 21 (3 x 7) and 10 (2 x 5) are not -- they are products of other primes.

So is there a largest such number?

Let's assume there is one. Amazingly enough, Euclid showed that this assumption undermines itself -- that there is no largest prime.

For simplicity, let's say the largest prime is 5. Consider, said Euclid, the number 5! + 1 = (1 x 2 x 3 x 4 x 5) + 1 = 121. Is 121 prime?

Well, you can't divide it by a prime less than the largest -- 5 -- because you get a remainder of 1 each time (try it). Thus either 121 is itself prime, or it is divisible by a prime larger than 5. Whichever it is, we've found a prime larger than 5. (In fact, 121 is the square of 11, a prime). And since the identical reasoning works with any prime, not just 5, this proves that there is no largest prime. Our initial assumption, that there is one, is wrong.

In other words, there is an infinite number of primes.

(As an aside, this mechanism of making an assumption and showing it is wrong is a favourite mathematical proof technique, called "reductio ad absurdum").

Such an elegant use of factorials, I always thought. Intuitive and understandable. Why can't life itself be like that? Instead, we worry about arranging and rearranging photos.