Search This Blog

20 August 2006

Guzinta Theory: Euclid Speaks to us from the Ancient Past! (aka Bob is bored)

A nifty kitchen gadget invented
by the guy who first measured the
circumference of the Earth accurately.
What's odd is that it's still
one of the fastest, most efficient
ways to find Prime Numbers on a
high-speed digital computer,
invented around 1950 AD.
2200 years: Not too shabby.

Okay, all you need to know to get through this is that a Prime Number is a whole number which can only be divided evenly by Itself and One.

Also, by definition, One is Not a Prime,
so the smallest Prime = 2.

Every positive whole number (Natural Number)
2 or larger is either Prime, or Not Prime (Composite).

Guzinta Theory is a useful math tool for this.

7 Guzinta 56 8 times

3 Guzinta 45 15 times, etc.

Euclid's "Elements"
Book IX, Proposition 20

I say: *There are infinitely many Prime Numbers.*

I will write the Primes, starting with the smallest, this way:

P(1) = 2
P(2) = 3
P(3) = 5
P(4) = 7
P(5) = 11 etc etc

For my argument, I say:

*There is a Prime P(n)
which is the Largest Prime.
There is no Prime larger than P(n) .*

I make the Product of all Primes from 2 to P(n):

P(1) x P(2) x P(3) x ... x P(n-2) x P(n-1) x P(n)

and then I add One, and call this number

Q = [ P(1) x P(2) x P(3) x ...
... x P(n-2) x P(n-1) x P(n) ] + 1

Q is obviously greater than P(n) .

Q is either Prime, or Not Prime (Composite).

If Q is Prime,
I have found a Prime Larger than P(n)
so P(n) was not the Largest Prime.

The only other possibility:
Q is Composite.

So Q must have a Prime Factor
by which Q can be evenly divided
(Remainder = 0).

Because I added One to the Product
of all Primes from 1 to P(n) ...

If I divide Q by 2, Remainder = 1.
So 2 is not a Prime Factor of Q.

If I divide Q by 3, Remainder = 1.
So 3 is not a Prime Factor of Q.

If I divide Q by 5, Remainder = 1.
So 5 is not a Prime Factor of Q.

and so on, until

If I divide Q by P(n-2), Remainder = 1.
So P(n-2) is not a Prime Factor of Q.

If I divide Q by P(n-1), Remainder = 1.
So P(n-1) is not a Prime Factor of Q.

If I divide Q by P(n), Remainder = 1.
So P(n) is not a Prime Factor of Q.

So the smallest Prime Factor of Q
must be Greater Than P(n) .
So P(n) was not the Largest Prime.

Whether Q is Prime or Composite,
I can always find a Prime Number larger than P(n).

So *there are infinitely many Prime Numbers.*

Which is what I set out to prove!


jamesjolson said...

Yes, but what are VLPN's good for? (Very Large Prime Numbers)

Bob Merkin said...

oh man what a GREAT question!

Greeks well before Euclid had already found Prime Numbers to be things of great interest ... but they gave the world an ironclad guarantee:

Prime Numbers are good for NOTHING! Small ones, big ones ... they have no practical use or value. And so it will always be.

This ironclad guarantee of No Practical Use Whatsoever very naturally led the greatest mathematicians in every subsequent generation -- Euler, Fermat, Gauss, Riemann, etc. -- to spend HUGE amounts of their lives studying the curious behavior and propery of Prime Numbers.

Well ... they lied.

Around 1970 2 American guys figured out a way to use a pair of Very Large Primes as the key to making Secret Codes which are just about Unbreakable. With a pair of Very Large Primes, it would take a snoop using the world's most powerful supercomputer decades, maybe a century before the snoop could crack the Secret Code.

Now large primes are the system used for all computer cryptography -- the stuff that lets you use your credit card to buy halvah over the Internet so nobody can eavesdrop of your electronic communication.

Also government agencies like the NSA use big prime codes, and spend huge amounts of time and research to try to break prime-pair codes. (NSA I think is the world's largest employer of mathematicians.)

So with superpower spooks involved, it's just possible that since the invention of this kind of code, people have been selling Very Large Prime Numbers for Big Bucks -- and maybe even by now, somebody's been MURDERED over very large prime numbers.

I also know an application for prime numbers to minimize unwanted noise and crosstalk in a big cable of communication wires.

Other than that, they're not good for anything. They're just Infinitely Fascinating. The most difficult Unsolved Problem in all mathematics, the Extended Riemann Hypothesis, is all about the behavior of Prime Numbers.

Jim Olson said...

(I knew that, I was just poking you to see what your answer would's the professor in me...)