Author Topic: [Solved] Prove that there are an infinite number of primes  (Read 7341 times)

0 Members and 1 Guest are viewing this topic.

Offline rabbit

  • x86
  • Hero Member
  • *****
  • Posts: 8092
  • I speak for the entire clan (except Joe)
    • View Profile
Re: Prove that there are an infinite number of primes
« Reply #15 on: October 23, 2006, 11:14:08 pm »
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...

Offline Ender

  • Moderator
  • Hero Member
  • *****
  • Posts: 2390
    • View Profile
Re: Prove that there are an infinite number of primes
« Reply #16 on: October 24, 2006, 07:28:57 pm »
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.
« Last Edit: October 25, 2006, 02:17:08 pm by Ender »

Offline rabbit

  • x86
  • Hero Member
  • *****
  • Posts: 8092
  • I speak for the entire clan (except Joe)
    • View Profile
Re: Prove that there are an infinite number of primes
« Reply #17 on: October 24, 2006, 08:44:14 pm »
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.

Offline Sidoh

  • Moderator
  • Hero Member
  • *****
  • Posts: 17634
  • MHNATY ~~~~~
    • View Profile
    • sidoh
Re: Prove that there are an infinite number of primes
« Reply #18 on: October 24, 2006, 10:59:05 pm »
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.
« Last Edit: October 24, 2006, 11:00:56 pm by Sidoh »

Offline rabbit

  • x86
  • Hero Member
  • *****
  • Posts: 8092
  • I speak for the entire clan (except Joe)
    • View Profile
Re: Prove that there are an infinite number of primes
« Reply #19 on: October 25, 2006, 07:18:50 am »
><

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

Offline Sidoh

  • Moderator
  • Hero Member
  • *****
  • Posts: 17634
  • MHNATY ~~~~~
    • View Profile
    • sidoh
Re: Prove that there are an infinite number of primes
« Reply #20 on: October 25, 2006, 11:07:57 am »
><

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.  ;)

Offline Ender

  • Moderator
  • Hero Member
  • *****
  • Posts: 2390
    • View Profile
Re: Prove that there are an infinite number of primes
« Reply #21 on: October 25, 2006, 02:26:34 pm »
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.
------------
« Last Edit: November 11, 2006, 07:31:55 pm by Ender »

Offline Sidoh

  • Moderator
  • Hero Member
  • *****
  • Posts: 17634
  • MHNATY ~~~~~
    • View Profile
    • sidoh
Re: Prove that there are an infinite number of primes
« Reply #22 on: October 25, 2006, 02:29:11 pm »
Ender: http://latex.sidoh.org .  Use it. :P

« Last Edit: October 25, 2006, 02:31:58 pm by Sidoh »

Offline Ender

  • Moderator
  • Hero Member
  • *****
  • Posts: 2390
    • View Profile
Re: Prove that there are an infinite number of primes
« Reply #23 on: November 22, 2006, 03:13:25 pm »
Ooh nice, a gif generator =) Thanks.