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

Ender · « **on:** October 22, 2006, 08:21:32 pm »

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 · « **Reply #1 on:** October 22, 2006, 08:48:19 pm »

[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 · « **Reply #2 on:** October 22, 2006, 08:53:27 pm »

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

Ender · « **Reply #3 on:** October 22, 2006, 09:08:25 pm »

Yeah, that doesn't make sense.

Sidoh · « **Reply #4 on:** October 22, 2006, 09:10:39 pm »

Quote from: Ender on October 22, 2006, 09:08:25 pm

Yeah, that doesn't make sense.

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

Ender · « **Reply #5 on:** October 22, 2006, 09:45:24 pm »

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 · « **Reply #6 on:** October 22, 2006, 09:47:59 pm »

Quote from: Ender on October 22, 2006, 09:45:24 pm

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 · « **Reply #7 on:** October 22, 2006, 10:07:32 pm »

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 · « **Reply #8 on:** October 22, 2006, 10:37:25 pm »

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 · « **Reply #9 on:** October 22, 2006, 10:45:02 pm »

Quote from: Newby on October 22, 2006, 10:37:25 pm

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.

rabbit · « **Reply #10 on:** October 23, 2006, 08:27:40 am »

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 · « **Reply #11 on:** October 23, 2006, 12:24:27 pm »

Quote from: rabbit on October 23, 2006, 08:27:40 am

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 · « **Reply #12 on:** October 23, 2006, 06:25:44 pm »

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 · « **Reply #13 on:** October 23, 2006, 06:31:17 pm »

Quote from: rabbit on October 23, 2006, 06:25:44 pm

That doesn't make sense!

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

Ender · « **Reply #14 on:** October 23, 2006, 07:32:21 pm »

Quote from: rabbit on October 23, 2006, 06:25:44 pm

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.

rabbit · « **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...

Ender · « **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.

rabbit · « **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.

Sidoh · « **Reply #18 on:** October 24, 2006, 10:59:05 pm »

Quote from: rabbit 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.

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 · « **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.

Sidoh · « **Reply #20 on:** October 25, 2006, 11:07:57 am »

Quote from: rabbit 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.

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 · « **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.
------------

Sidoh · « **Reply #22 on:** October 25, 2006, 02:29:11 pm »

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

Ender · « **Reply #23 on:** November 22, 2006, 03:13:25 pm »

Ooh nice, a gif generator =) Thanks.

News:

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