Euclid's theorem and some questions

[Amaton]

My take on the original proof by Euclid, which shows that there are infinitely many prime numbers. A good introductory proof I believe...

 

Let [math]L[/math] be a finite and arbitrary list of distinct prime numbers: [math]L=p_1,p_2,p_3...p_n[/math]

Let [math]P[/math] be the product of all elements in [math]L[/math]: [math]P=p_1\times p_2\times p_3\times ...\times p_n[/math]

Let [math]q=P+1[/math]

 

We will call [math]L[/math] "incomplete" if it does not contain all prime numbers.

 

Now, nothing definitively says that [math]q[/math] is prime or composite. So we will analyze the two cases:

 

(1) [math]q[/math] is prime.

(2) [math]q[/math] is composite.

 

(1) is true, where [math]q[/math] is prime, and [math]q[/math] is certainly not in [math]L[/math]: so there exists a prime number that is not in [math]L[/math]. Therefore, (1) implies [math]L[/math] is incomplete.

 

If (2) is true, where [math]q[/math] is composite, then there exists some prime number [math]K[/math] which divides [math]q[/math]. Now, we assume two possibilities: either [math]K[/math] is in [math]L[/math], or [math]K[/math] is not in [math]L[/math], each of which will be analyzed.

>> (2.A) [math]K[/math] is not in [math]L[/math]. Thus, whenever (2.a) is true, by implication, [math]L[/math] is incomplete.

 

>> (2.B) [math]K[/math] is in [math]L[/math], which means [math]K[/math] is an element in the list. This means that [math]K[/math] not only divides [math]q[/math], but it also divides [math]P[/math], since all elements in [math]L[/math] are prime factors of [math]P[/math]. If [math]K[/math] divides both, then it also divides their difference [math]q-P=1[/math]. However, no prime number exists which divides [math]1[/math]. Since the latter statement is a direct implication of (2.B) and is an absurdity, (2.B) is an impossibility.

 

Now it is shown that (2.B) is impossible. No other cases exist for (2) other than (2.A)... Therefore, (2) implies [math]L[/math] is incomplete.

 

 

There are no other possibilities other than [math]q[/math] being either prime or composite, both of which determine L to be incomplete. Thus, L is always incomplete.

 

Now questions regarding the nature and methodology of the proof...

 

What demonstrations are involved in this? I'd like to think: proof by exhaustion (whole) and proof by absurdity (2.B). Can case 2B also be shown as a proof by contradiction, where it implies K is not in L (a direct contradiction of the assumption)?

 

BTW, I'm a student. When I first encountered this theorem, this was my first real exposure to an elementary proof and I found it beautiful. I wanted to paraphrase it so that things would be a little more obvious to non-mathematicians. Although I wonder if it seems unnecessarily thorough. Thoughts?

Edited January 25, 2013 by Amaton

[mathematic]

 

Although I wonder if it seems unnecessarily thorough.

 

I agree.

[mora]

I wanted to paraphrase it so that things would be a little more obvious to non-mathematicians.

Why? Most 'non-mathematicians' people don't even remember what a prime number is, and they don't need to. Don't waste your time.

[Amaton]

Why? Most 'non-mathematicians' people don't even remember what a prime number is, and they don't need to. Don't waste your time.

 

Oh, I don't even expect the majority of ordinary people to understand this, let alone have the slightest interest in it.

 

But at least motivated high school students... who should get more exposure to the proofing context of mathematics. The only exposure I get is in dealing with simple inductive series (yawn). Also, there are lots of people interested in popularized mathematics. YouTube has several popular videos covering topics like prime numbers, transfinite cardinals, and modern geometry (etc.)

 

Euclid's theorem is another nice topic of interest, and I thought it'd be cool to study its proofs (however beyond-me some of the more recent methods are).