Turn on thread page Beta
 You are Here: Home

# prime number proof watch

1. prove that prime numbers go on forever
2. You Cant
3. (Original post by fubu_05)
prove that prime numbers go on forever
Suppose that they do not go on forever.

Therefore there must be a sequence of prime numbers 2,3,5....n, where n is the largest prime number.

Say x = 2.3.5...n (i.e. the product of all the prime numbers). Since x is divisble by every prime, x+1 isn't divisble by any of these primes, and so is itself prime by definition.

This is a contradiction, therefore prime numbers go on forever.

(This proof was first found by Euclid in around 8th Century BC I think)
4. (Original post by Unregistered)
You Cant
Really?
5. (Original post by fubu_05)
prove that prime numbers go on forever
Suppose the N is the largest prime number. N! + 1 will not be divisible by any of 1, 2, 3, ..., N-1, N, so it will be a prime number. but we have said that N is the largest prime number, but clearly N! + 1 is larger, so we have contradicted ourselves. therefore there is no "largest prime number", so prime numbers go on forever
6. Oh I get it! Do they ask this stuff at uni?
7. this was a P2 proof question (well, an example anyway).
8. 'Prove that root 3 is irrational' was also a P2 proof question. I thought that was hard unless you have already read the proof.
9. (Original post by mikesgt2)
'Prove that root 3 is irrational' was also a P2 proof question. I thought that was hard unless you have already read the proof.
Err does it go: Assume that 3^0.5 is rational, then it can be expressed as a fraction p/q
I don't know the rest but am fascinated by mathematical proofs, can you help me out on this?
10. Oh! Thanks a bunch mate!
11. (Original post by ZJuwelH)
Oh! Thanks a bunch mate!
Was that meant to sound sarcastic?
12. (Original post by mikesgt2)
Was that meant to sound sarcastic?
I dont think so.

(and that ^ isn't sarcasm)
13. (Original post by mikesgt2)
Was that meant to sound sarcastic?
No it was a genuine thanks. I really appreciate it!
And if I'm being sarcastic it won't be in doubt
14. (Original post by elpaw)
Suppose the N is the largest prime number. N! + 1 will not be divisible by any of 1, 2, 3, ..., N-1, N, so it will be a prime number. but we have said that N is the largest prime number, but clearly N! + 1 is larger, so we have contradicted ourselves. therefore there is no "largest prime number", so prime numbers go on forever
N! + 1 is not divisible by any of 2, 3, ..., N. It might however be divisible by a larger number.

For example, 5! + 1 = 121, which isn't divisible by 2, 3, 4 or 5 but is divisible by 11.

The trick is to consider the prime factorisation of N! + 1. That factorisation can't contain anything <= N (because N! + 1 is not divisible by any of 2, 3, ..., N). It also can't contain anything > N, because we assumed that there are no primes that big. So it can't contain anything. Contradiction. QED.
15. (Original post by Jonny W)
N! + 1 is not divisible by any of 2, 3, ..., N. It might however be divisible by a larger number.

For example, 5! + 1 = 121, which isn't divisible by 2, 3, 4 or 5 but is divisible by 11.

The trick is to consider the prime factorisation of N! + 1. That factorisation can't contain anything <= N (because N! + 1 is not divisible by any of 2, 3, ..., N). It also can't contain anything > N, because we assumed that there are no primes that big. So it can't contain anything. Contradiction. QED.
that is what i meant to say.
16. (Original post by Jonny W)
N! + 1 is not divisible by any of 2, 3, ..., N. It might however be divisible by a larger number.
But if N!+1 is divisible by a number greater than N, then since N! + 1 is not divisible by any of 2,3...N, this implies there is a prime greater than N, which is a contradiction.
17. Woah hold on, one of these proofs mentions the sum of all the primes up to N. But the other mentions N! in its place, and N! is the product of all numbers (including non-primes) up to N. Which is right???
18. (Original post by ZJuwelH)
Woah hold on, one of these proofs mentions the sum of all the primes up to N. But the other mentions N! in its place, and N! is the product of all numbers (including non-primes) up to N. Which is right???
both proofs are products, not sums. N! will include the product of all the primes up to N, multiplied by the product of the non-primes. since the non-primes are themselves products of primes, this doesn't really matter. it is just easier to write (and mathematically define) N! than to say 2.3.5.7.11.....

Turn on thread page Beta
TSR Support Team

We have a brilliant team of more than 60 Support Team members looking after discussions on The Student Room, helping to make it a fun, safe and useful place to hang out.

This forum is supported by:
Updated: October 26, 2003
Today on TSR

### Which business legend are you?

We have the answer...

Poll
Useful resources

## Articles:

Debate and current affairs forum guidelines