Chapter I. The adventure begins.

Contents: 1. Daddy, what's the biggest number?

2. What are the prime numbers, and what do they have to do with space aliens?

3. There ain't no biggest prime neither.

4. A brain like a sieve.

5. Twin primes, and proofs Sudoku style.

6. Your cellphone is crawling with prime numbers.

1. Daddy, what's the biggest number?

Anyone who's been around small children much has probably heard a

question like this one. Your first answer is probably ``actually there

isn't a biggest number'', to which the child will likely reply ``why

not?''. Well, you say, suppose you had any enormous number, like a

gazillion. If you just add one to it you get a gazillion and one, which

is even bigger. So no matter how big a number you take---the number of

stars in the sky, the number of grains of sand on the beach---you can

always add one to make it bigger.

Another way to say it (not recommended when explaining things to a little

person) is that there are infinitely many whole numbers 1,2,3,..., or

``positive integers'' as we like to call them. So it's a subtle concept,

involving as it does the notion of infinity. In any case, your

explanation to the child is a simple example of a ``proof by

contradiction''. A bit more formally, it would go like this:

I claim there is no biggest number. Proof: Suppose (in order to derive a

contradiction) that there was a biggest number. Let's call this

presumptuous number ``N''. (You could call it ``Finley'' or ``Hannah'' or

``thingamagig'', but N is short and sweet and serves to remind us that it

stands for a number.) So, Mister N, you claim to the biggest number?

Hah! I'll just add one to you to get a bigger number N+1. This

contradiction proves you are a fraud, a liar, and a menace to

society. No ``biggest number'' exists!

This might seem like making a mountain out of a molehill. But it's

always good to warm up, to stretch out your brain a bit before moving

on, so as to avoid blowing out any neurons. We'll use a more subtle

version of the same idea later to prove there is no biggest prime

number.

2. What are the prime numbers, and what do they have to do with space

aliens?

Let's think about some things you can do with numbers. You can add them,

for instance, or you can multiply them. Let's indicate multiplication

with an asterisk: 2*3=6, 3*5=15, etc. (I do this only because of the

limited symbols available on this blog page). One interesting

observation is that some numbers can be ``factored'' and others

cannot. For example 15=3*5, but there is no way to factor 7 other than

the trivial factorization 7=1*7. This state of affairs even has a nice

geometric interpretation: If you want to put 15 chocolates in a box you

can arrange them in three rows of five each:

x x x x x

x x x x x

x x x x x

But you can't do it with 7, other than by putting them all in one boring

row; no matter how you do it there are rows of different lengths, for

instance.

x x x x

x x x

So we've discovered some very special and interesting numbers, namely

those numbers that cannot be factored into smaller numbers. If we were

the first to discover these numbers we could name them whatever we like.

We could call them ``thin numbers'', ``groovy numbers'', or ``apple

fritters'' if we so desired. But we're a few millenia late to have

naming rights, so we'll stick to the standard term ``prime number'' or

simply ``prime''. While we're at it, though, it behooves us to define

our terms precisely. The description we just gave ``numbers that can't

be factored into smaller numbers'' is precise enough for our purposes,

but if taken literally it includes the number 1 as a prime. There is

nothing wrong from a logical standpoint with counting 1 as a prime, but

if you do so you'll soon discover that to say anything interesting about

primes you'll constantly have to insert disclaimers such as ``suppose p

is a prime other than 1''. Experience shows that it's better to just exclude

it by fiat. So here's our official definition:

A prime number is a number greater than 1 that cannot be factored into

smaller numbers.

You can (and should!) check that the primes less than 30 are the

following:

2,3,5,7,11,13,17,19,23,29

Except for 2, all prime numbers are odd. Why?

In one of my favorite movies, ``Contact'' (based on the book by Carl

Sagan and starring Jodie Foster), beings from beyond our galaxy send out

radio pulses in prime groups: first two, then three, then five and so

on. The point is that prime-ness is an intrinsic property of numbers,

completely independent of what symbols are used to denote them, whether

you use base ten as we do, what language you speak, and so on. The

extra-galactic reasoning therefore is that any intelligent form of life

will recognize the sequence of primes and realize that another

intelligent life-form is attempting to make contact.

Prime numbers are important because they are the building blocks for

making all whole numbers, via multiplication. If you take any such

number greater than one, you can factor it as a product of prime

numbers. For example, 30=2*3*5, 72=2*2*2*3*3.

But hold on just a doggone minute! Giving a couple of examples doesn't

prove anything. How do we know that ALL numbers admit such a

factorization into primes?

Well, suppose someone walks up to you on the street and hands you a

positive integer. Let's call this number N. If N happens to be a prime

number, then N is its own factorization (with just one factor). If it

isn't prime, then N can be factored into two smaller numbers N=a*b. If a

and b are primes, then we have our factorization. If not, then they in

turn can be factored into smaller numbers. If we continue this process,

it has to stop after a finite number of steps, because positive integers

(just good old whole numbers, remember) can't keep getting smaller

forever. When the process stops, we have written N as a product of

smaller numbers, none of which can be factored further and so are primes

by definition. Here ends the (convincing, I hope) explanation.

Let's illustrate with a specific example. Say you started with

N=60. There are multiple ways you might do the first step, but probably

the most obvious would be 60=6*10. Neither 6 nor 10 is prime, so we

factor them further: 6=2*3, 10=2*5. We luck out and are done after two

steps: 60=2*3*2*5 is our prime factorization. However, and this is a

crucial point, an example does not constitute a proof. A proof is a

convincing argument that works in ALL cases under consideration. It

should hold up in a court of law under rigorous cross-examination. The

person-on-the-street argument given above is an example of a proof. In

a textbook you might see something like this:

Theorem. Every number greater than 1 can be factored into primes.

Proof: (Insert here a cleaned-up, more precisely worded version of the

version above.)

There's nothing wrong with this style, but some people are put off

and/or intimidated by the words ``Theorem'' and ``Proof''. So if you

prefer, rewrite it as follows:

Cool Fact: Every number greater than 1 can be factored into primes.

Here's why it's true, dude: Suppose someone walks up to you on the

street...etc.

Also important to note is that we didn't START by writing down Theorem:

blah blah blah Proof: blah blah blah. We started with a question. We

found an answer and convincingly demonstrated its truth. The more formal

``theorem'' and ``proof'' come later, after the smoke has cleared and

the dust has settled. The reason that we mathematicians often write out

our proofs very pedantically, dotting every i and crossing every t, is

that the deeper the mathematics, the easier it is to make subtle

mistakes. Very careful reasoning is required. But that's not the form in

which the proof is discovered.

Note also the following corollary of the theorem.

Corollary: If N is bigger than 1, then there is at least one prime that

divides N.

(By ``divides N'' I mean the same thing as ``is a factor of N''. In

mathematics, as in other languages, there are often different words for

the same thing.)

In mathematics a ``corollary'' of a theorem is a second theorem (cool

fact!) that follows easily from the first. What constitutes ``easily''

is of course a matter of opinion, but in the present case it's like,

totally easy: The theorem says N can be factored into primes, and any of

these prime factors will divide it.

3. There ain't no biggest prime neither.

What's the biggest prime? This would be good to know, as then we'd have

a finite list of the primes, the basic building blocks for all numbers.

Well, there ain't no such thing. The Greek mathematician Euclid (who

lived around 300 BC and is most famous for his work in geometry), found

a clever argument to prove that there are infinitely many primes. His

proof is by contradiction. Such a proof really is like a

cross-examination. Imagine that Mr. P is on trial for mathematical

fraud, having sold stock based on his claim to be the largest prime

number. The defense has called him as a witness, and Euclid, the

prosecuting attorney, now proceeds to the cross-examination.

Euclid: Mr. P, you claim to be the largest prime, is that correct?

P (with a disgusted look): Yes.

Euclid: I see. (He pauses, shuffling a few papers.) Now Mr. P, suppose I

multiply together the first few primes---let's say 2,3 and 5, and then

add 1. Is this number divisible by 2, 3, or 5?

Defense: Objection, your honor! Irrelevant!

Judge: Overruled. I'll give you some leeway, Mr. Euclid, but this better

be leading somewhere. The witness may answer the question.

P (sarcastically, as though talking to a child): Well, 2 times 3 times 5

is 30, and if I add one I get 31. That isn't divisible by 2, 3 or 5. If

that was too fast for you I can go over it again.

Euclid: All right, but isn't it true that you really didn't need to do

the multiplication at all? I mean, if you multiply 2,3 and 5 together,

then without even writing down the answer you know that adding 1 will

produce a number whose remainder, after division by 2,3 or 5, is 1.

Defense: Objection! I fail to see what this has to do with---

Judge: Sit down, counselor! I'll allow it, but I warn you, Mr. Euclid,

that my patience is wearing thin.

P: Well yeah, sure. I could take 2,3,5,7,11, multiply them together,

add 1 and know in advance that if I divide any of those five primes into the

new number the remainder will be 1. That's how remainders work. But

maybe they didn't cover that when you went to school.

Euclid (continuing to ignore P's sarcasm): So if you're the biggest

prime, there is a finite list of ALL primes and we can multiply them all

together. Call this number N. Then N+1 is not divisible by any of the

aforementioned primes, because if you divide by any prime on the list

you'll get a remainder of 1.

P: Right. So what?

Euclid: I call the attention of the court to the earlier testimony of

expert witness Herr Professor Doctor Mitchell, who testified that for

any number bigger than 1, there is SOME prime that divides it. So there

is a prime---I'll call it q, if it please the court---such that q

divides N+1. In other words, the remainder after division by q is 0, not

1. So this prime q is not on the list, it is bigger than you, and your

claim is a lie!

(Pandemonium erupts in the court. Mr. P is found guilty and sentenced to

a year of watching Dragnet re-runs.)

More formally, say for publication in the Proceedings of the North

Kirkland Philosophical Society, one might write things out like so:

Theorem. There are infinitely many primes.

Proof: Suppose (in order to reach a contradiction) that the theorem is

false, i.e. that there are only finitely many primes. Multiply them all

together (this is possibile because there are only finitely many); call

the resulting number N. Then dividing any of the primes into N+1

produces a remainder of 1, so no prime divides N+1. But since N+1 is

greater than 1, there IS a prime that divides. We have therefore arrived

at a contradiction, proving that the theorem is true.

4. A brain like a sieve.

When I was a boy, my father used to say I had a ``brain like a sieve'',

a reference to the absent-mindedness that apparently was already

evident. Even sieves can be put to good use, however.

To expand our above list of primes more efficiently, we can use a method

picturesquely known as the ``Sieve of Eratosthenes''. Eratosthenes (276

BC-195BC) was a Greek man of many talents---mathematician, poet,

``Father of Geography''. The Wikipedia article on him includes an

color-coded animation of the sieve being used to find all primes less

than 121. But let's see how you might discover this method yourself to

find all primes below 121. Start by writing down all the numbers from 2

to 120. Or at least imagine that you've done so; as you'll see, there

are many shortcuts to speed up the process.

1. Cross out all even numbers greater than 2 on your list, since these

have 2 as a factor and so can't be prime. This is superty-duperty easy,

as Kaia would say, because in our customary base 10 a number is even if

and only if its last digit is even. But hey, even without knowing this,

you could just start at 4 and cross out every other number 4,6,8,....

2. Cross out all numbers with 3 as a factor, other than 3 itself. So you

cross out 6, 9, 12, 15,...ah, but actually all the even ones 6, 12, 18

are already gone.

3. Skip to the next number that hasn't yet been crossed out. It has to

be a prime (why?), in this instance 5. Cross out all multiples of 5,

which is very easy in base 10 because they are the numbers whose last

digit is 0 or 5 (why?). All such multiples that also multiples of 2 or 3

have already been crossed out, speeding up the process further.

4. Repeat step 3. The next number not already crossed out is 7, which

indeed is prime as claimed. Proceed as before to cross out all multiples

of 7 (there won't be many left).

5. Repeat step 3. The next number not already crossed out is 11...but

wait a minute, we're already done! There's no need for Step 5! We know

without even looking that every multiple of 11 has already been crossed

out. Do you see why? (Hint: 121=11*11.) If you can answer this then you

see why we can stop the process at Step 4. All remaining numbers on the

list are primes!!

For future reference, here's the list of all primes below 121:

2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97,101,103,

107, 109, 113.

5. Twin primes, proofs Sudoku style, and other diversions.

If you ponder the above list of primes, you notice some things about the

way they're ``distributed''. For example, every now and then one

encounters ``twin primes'', meaning two consecutive odd numbers that are

both prime, such as 3,5 and 29,31. Taking our cue from Euclid, we ask:

Are there infinitely many such pairs of twin primes? No one knows! This

is an example of an unsolved problem in mathematics. If you can answer

it you will be famous, and probably will rake in some big bucks too.

Okay, what about ``triplet primes'', meaning three consecutive odd

numbers that are prime, such as 3,5,7? Staring at the list above, you'll

see that 3,5,7 are the only triplet primes below 121. It's a fun problem

to prove that these are the ONLY triplet primes. I'll give some hints

after a digression on Sudoku (which you can skip if you're not familiar

with the game).

When you play Sudoku, you are doing mathematical proofs. The proofs in

question could be styled ``proofs by contradiction'' or ``proofs by

process of elimination''. In the simplest case it works something like

this: Maybe you have a row with only three squares remaining to be

filled in, so that you know that one of the squares has to be, let's

say, a 3,5 or 8. But that square already has a 3 in its column, and an 8

in its 3 by 3 block. So by process of elimination you have PROVED that

it has to be a 5. Sudoku is pure mathematics!

Now, back to the triplet prime problem. Usually I don't like to give

hints, because they interfere with your creativity. This is true at all

levels of mathematics. But since we're just getting started, and you

might still be uncertain about what a ``proof'' is, I'll make some

suggestions. First of all, experiment with small numbers to get an idea

of what's going on. Examples don't constitute a proof, but they can

SUGGEST a proof. For instance, 5,7,9 aren't triplet primes because 9

isn't prime; it's divisible by 3. Nor does 13, 15, 17 work, as 15 isn't

prime (it's divisible by 3). Or try 27, 29, 31. Nope; 27 is divisible by

3. In fact it appears that in every case, one number in the triplet

is divisible by 3. This suggests proceeding as follows: We need names

for our triplets; let's call the smallest one n. Then the other two are

n+2 and n+4. Try proving that one of the numbers n,n+2,n+4 has to be

divisible by 3 and therefore can't be prime (except in the special case

n=3). Here's where ``Sudoku style'', or process of elimination, comes

in. If n or n+2 is divisible by 3 we can quit; our theorem is proved. So

suppose that n and n+2 are NOT divisible by 3 and prove that this forces

n+4 to be divisible by 3. Further hints available on request!

Here's another interesting question, at the opposite extreme from twin

primes. How big can the gaps between consecutive primes be? If you look

at the list of primes below 121 given above, you'll see that for a long

time there is no gap bigger than 6, e.g. 23 and 29, and then we suddenly

get a gap of 8 from 89 to 97. In fact the gaps can be arbitrarily large.

Once you have the right creative idea, the proof of this fact is

surprisingly ``easy''. But of the course that little idea is the catch!

Here it is: Let's use the traditional, centuries-old notation n! to mean

the product of all the numbers from 1 to n. Thus

3! =1*2*3=6

4! =1*2*3*4=24

5!= 1*2*3*4*5=120

and so on. I don't know who first came up with the exclamation point

notation, but it was long ago. You could just as well use a heart, a

smiley-face, or a skull-and-crossbones, but n! is the standard (to be

read as ``n factorial''). Now consider the following list of

consecutive numbers:

n!+2, n!+3, n! +4,...,n!+n.

Here the ellipses ... are a standard way of saying ``keep going in this

way until you get to n!+n''. Then no number in this list is prime. Do

you see why? Prove this to yourself! There are n-1 numbers on the list,

so the gap between the biggest prime less than n!+2 and the next prime

is at least n-1. Since n can be any number here---a thousand, a million,

a gazillion, whatever---this proves that there can be arbitrarily large

gaps between consecutive primes.

The distribution of primes has been intensively studied, and is

currently a very active area of research. The biggest unsolved problem

in this area, often regarded as the biggest unsolved problem in

mathematics, is the ``Riemann hypothesis''. It was first conjectured by

the brilliant German mathematician Bernhard Riemann (1826-1866). The Clay

Research Institute has offered a million dollars for its solution.

(Unfortunately, I can't explain it here; you'd need a solid background

in undergraduate mathematics.)

6. Your cellphone is crawling with prime numbers.

In his 1940 essay ``A mathematician's apology'' (the word ``apology'' is

used in the sense of justification), the prominent British mathematician

G.H. Hardy (1877-1947) claimed that number theory would never have any

practical applications. Number theory was his field, and he regarded the

lack of applications as a good thing, as then it could never be applied

to war. Within a generation or two he was proved spectacularly wrong, as

number theory---this includes the prime numbers we've been

discussing---is absolutely crucial for our current technology: the

internet, CD's, DVD's, cellphones, anything to do with computers and

data transmission. There is an ``elliptic curve'' in your cellphone, for

example, and it is crawling with prime numbers.

The main applications that I'm aware of (and I've only scratched the

surface) have to with (1) encryption, and (2) error-correcting

codes. Secure data transmission---of your bank information or your

credit card number, of military secrets---requires that it be

encrypted. An ingenious way of doing this using prime numbers was

invented about thirty years after Hardy's statement that number theory

would never be applied. Later a colleague of mine in the UW Math

department, Neil Koblitz, invented a new approach based on mathematical

objects called ``elliptic curves''; this too involves much number

theory. You literally have an elliptic curve in your cellphone.

Setting aside security, there is still the issue of accuracy. All data

transmission is subject to error. Minor mistakes could erase your bank

account, turn CD's and DVD's into gibberish, and cause a spacecraft to

land in Hoboken instead of on Mars. To prevent this, sophisticated

schemes have been developed that allow the machine receiving the signal

to not only recognize transmission errors, but also correct them in

real-time. These ``error-correcting codes'' are of mathematical origin,

and again involve primes and other aspects of number theory.

As I said at the outset, it's not my goal to talk about applications.

But there are millions of applications out there. If you want to learn

more, try searching ``public-key cryptography'', ``elliptic curve

cryptography'' and ``error-correcting codes''. I can't promise that it

will be easy reading, however.

## No comments:

## Post a Comment