[Solved] Prove that there are an infinite number of primes

[rabbit]

n is not divisible by any prime as directly explained in (2).  Take the following example:
2 * 3 * 5 * 7 (all primes through 10) = 210
2 !| 211
3 !| 211
5 !| 211
7 !| 211

It's a relatively simple concept man...

[Ender]

rabbit, you just proved that there can't be FOUR primes. We're proving that there can't be a FINITE number of primes. You can't say that for p1...pn; how can you say pn !| 211 when you don't know what pn is?

Anyways, here's the proof. Figure it's about time to say it. (Even though I said Sunday.)
-----------------------------------------------------------------------------------------------------------------------
This will be proven by contradiction.

Assume that there is a finite number of primes, p1p2p3...pn, which comprise set P. Consider Q := p1p2p3...pn + 1.  If Q were composite, then it would have to be divisible by some product of primes in P. This does not mean, however, that the left-hand (L | L= p1p2p3...pn) and right-hand (R | R = 1) terms have to be divisible by some prime in P. It does mean, however, that L / x + R / x must be an integer. Since L / x will always be an integer, as it contains all the primes in our set P, and R / x will never be an integer, since 1 is only divisible by 1, which is not a member of P, we will be adding an integer + a non-integer. Therefore Q is not divisible by x, and therefore Q is prime.

QED
I lost.
-----------------------------------------------------------------------------------------------------------------------
I never actually saw an "official" solution to this problem, so feel free to criticize my proof!

Edit: corrected some semantics. The proportion thing didn't achieve what I wanted it to, but the integer + non-integer thing does.

[rabbit]

MY GOD YOU'RE DUMB

That was an example showing how step 2 and step 3 naturally flow, and that you don't know what you're talking about.

[Sidoh]

MY GOD YOU'RE DUMB

That was an example showing how step 2 and step 3 naturally flow, and that you don't know what you're talking about.

No, Ender is completely right.  Just because something has "a flow" (discovered by mere intuition) does not mean that it will continue for the entire set of natural numbers.

I'm pretty sure he knows exactly what you're saying, but exactly what you're saying doesn't prove that there are an infinite number of prime numbers.  It simply suggests that it seems to be the case per a small sample of primes and an intuitive guess that such a pattern will persist.

[rabbit]

><

God dammit.  It was an intuitive thing in class.  I don't feel like proving THIS too.

[Sidoh]

><

God dammit.  It was an intuitive thing in class.  I don't feel like proving THIS too.

Just because something has a property that intuition suggests is true doesn't mean that it really is true.  If you're proving something, you're not allowed to assume anything unless you later prove that this something is true.  ;)

[Ender]

Here's another proof, which is more concise but requires knowledge of notation and stuff.
------------
We will prove this by contradiction. Assume there is a finite number of primes, p1p2p3...pn, which comprise set P. Let Q = p1p2p3...pn + 1.

Let =~ be congruence, E be "member of", and !| be not divisible by.

Q =~ 1 (mod p_k) for all k E P. Since 1 is not contained in P, 1 (mod_pk) will always return 1. We can deduce from this that Q !| any p_k, and therefore Q is prime.  This contradicts our assumption of a finite number of primes contained in P, and thus there cannot be a finite number of primes.

w^5
I lost.
------------

[Sidoh]

Ender: http://latex.sidoh.org .  Use it. :P

[Ender]

Ooh nice, a gif generator =) Thanks.