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

[Ender]

AND DO NOT LOOK IT UP AND THEN POST IT.  Or else you're lame, among other things.

Hint:
Try proving it by contradiction. Assume a finite number of primes, p1p2p3...pn.
Then consider the number Q := p1p2p3...pn + 1.

EDIT: I'm posting the answer next Sunday.

[Newby]

[size=0pt]Q = 2 + 1
Q = 3

Q = 3*2 + 1
Q = 7

Q = 5*3*2 + 1
Q = 30 + 1
Q = 31

Going off of your assumption, if you multiply all the primes together, you can factor them down to the primes. If you add one, you can't. You will have a remainder of one left over. It isn't prime, and it isn't divisible by any prime numbers. So it can't exist, according to our assumption. Thus, the assumption is false, and there are an infinite number of prime numbers.[/size]I didn't have to look it up. I've seen it proven before. I just figured out how the reasoning works, though, so I learned something! =P

[Sidoh]

Since every natural number can be written as a factorization of prime numbers and is an infinite set, there has to be a continuing, increasing set of primes to allow for this.  If there were a finite number of primes that ended (for example) somewhere around , writing as factorization of prime numbers such that would be impossible.

Edit: Thinking about that a bit longer led me to realize that doesn't necessarily make sense, but since Newby already ruined the fun... :P

[Ender]

Yeah, that doesn't make sense.

[Sidoh]

Yeah, that doesn't make sense.

Well excuse me if I haven't seen the proof before. :P

[Ender]

Didn't mean that meanly, just wanted to state that the problem was still unsolved, but I probably did come across as mean =\.

This proof is doable, but it takes some epiphanies and some incorrect proofs to ponder before you get it. I thought I had it one day, then explained it to my grandpa the next day, and when explaining it to him I realized it was wrong. So then I thought about it again, and that's when I got the epiphany.

Note: The hint really helps, use it, you're expected to =p. After you've solved it with the hint, then you can do it another way without a hint.

[Sidoh]

Didn't mean that meanly, just wanted to state that the problem was still unsolved, but I probably did come across as mean =\.

This proof is doable, but it takes some epiphanies and some incorrect proofs to ponder before you get it. I thought I had it one day, then explained it to my grandpa the next day, and when explaining it to him I realized it was wrong. So then I thought about it again, and that's when I got the epiphany.

Note: The hint really helps, use it, you're expected to =p. After you've solved it with the hint, then you can do it another way without a hint.

Quote Newby's post.  I'm pretty sure he answered it.

[Ender]

No, he saw it proven before. Figuring out the reasoning is good, but the question is to derive the reasoning. Still unsolved! =P Anyways, for you literary sticklers: if you didn't prove it yourself, then don't post the proof.

[Newby]

Well, I had the general idea of what to do, and your post was that general idea. So I just knew it was possible, so I worked at it. :)

(By I had seen it proven before, I know there was a solution. I didn't understand the reasoning or many of the words at the time, and it was over a year ago so eh?)

All I knew was to prove the opposite (finite #) to be incorrect, and your formula.

[Sidoh]

Well, I had the general idea of what to do, and your post was that general idea. So I just knew it was possible, so I worked at it. :)

(By I had seen it proven before, I know there was a solution. I didn't understand the reasoning or many of the words at the time, and it was over a year ago so eh?)

All I knew was to prove the opposite (finite #) to be incorrect, and your formula.

You'd still seen it before. :P

[rabbit]

I proved this last year in number theory, but I don't even have time to finish reading the boards.  I'll edit later!!!

[Sidoh]

I proved this last year in number theory, but I don't even have time to finish reading the boards.  I'll edit later!!!

I think we all would have given a number theory class. :'(

[rabbit]

That doesn't make sense!

Anyway, we did it by contradiction:
1. There are a finite number of primes.
2. Multiply all the primes together, and add 1, call it n.
3. Since n is not divisible by any prime, and since all composite numbers are divisible by prime numbers, this number is not composite.
4. Since it is not composite, it must be prime.
5. n is not prime because if it was, multiplying all primes and adding 1 would yield a larger number than n.  Thus, n cannot exist.

We did another method with FLT (I think, it was definitely one of Fermat's, not sure if it was his LT), but I don't feel like trying to explain it.

[Sidoh]

That doesn't make sense!

The implication was: "given [the opportunity to take] a number theory class."

:P

[Ender]

3. Since [Q] is not divisible by any prime...

Sorry to get knitty-gritty on you, but proofs are like that. Step 3 is the crux of the proof. yet you didn't explain it! Prove that Q is not divisible by any prime. You also seem to have some superfluous steps in there. Written proofs are better too, but anyways, the flow of it is "Q is not divisible by any prime because... therefore Q is prime, and since Q > pn, there must be an infinite number of primes."

Oh, and hint: It takes more explanation than you would think.