Home Companies Industry Politics Money Opinion LoungeMultimedia Science Education Sports TechnologyConsumerSpecialsMint on Sunday

The primes keep rolling on

The primes keep rolling on
Comment E-mail Print Share
First Published: Fri, Oct 14 2011. 12 03 AM IST

Updated: Fri, Oct 14 2011. 12 03 AM IST
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”) = 1x2x3x4 = 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 all are 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 4x3, 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 two slots, there are two ways to fill the third. Thus 4x3x2, or 24 ways, to fill those three. In our case, say you choose D for the third spot, which leaves you with just B for the last slot—or only one way to fill it.
Thus your answer: there are 4x3x2x1, 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 five 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 (3x7) and 10 (2x5) 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 = (1x2x3x4x5)+1 = 121. Is 121 a 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 a 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.
Once a computer scientist, Dilip D’Souza now lives in Mumbai and writes for his dinners. A Matter of Numbers will explore the joy of mathematics, with occasional forays into other sciences. Comments are welcome at dilip@livemint.com
Comment E-mail Print Share
First Published: Fri, Oct 14 2011. 12 03 AM IST