Turn on thread page Beta
    • Thread Starter
    Offline

    0
    ReputationRep:
    prove that prime numbers go on forever

    You Cant
    Offline

    0
    ReputationRep:
    (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)
    Offline

    0
    ReputationRep:
    (Original post by Unregistered)
    You Cant
    Really?
    Offline

    15
    ReputationRep:
    (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
    Offline

    18
    ReputationRep:
    Oh I get it! Do they ask this stuff at uni?
    Offline

    14
    ReputationRep:
    this was a P2 proof question (well, an example anyway).
    Offline

    0
    ReputationRep:
    'Prove that root 3 is irrational' was also a P2 proof question. I thought that was hard unless you have already read the proof.
    Offline

    18
    ReputationRep:
    (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?
    Offline

    0
    ReputationRep:
    http://mathforum.org/library/drmath/view/52619.html
    Offline

    18
    ReputationRep:
    Oh! Thanks a bunch mate!
    Offline

    0
    ReputationRep:
    (Original post by ZJuwelH)
    Oh! Thanks a bunch mate!
    Was that meant to sound sarcastic?
    Offline

    15
    ReputationRep:
    (Original post by mikesgt2)
    Was that meant to sound sarcastic?
    I dont think so.

    (and that ^ isn't sarcasm)
    Offline

    18
    ReputationRep:
    (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
    Offline

    8
    ReputationRep:
    (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.
    Offline

    15
    ReputationRep:
    (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.
    Offline

    0
    ReputationRep:
    (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.
    Offline

    18
    ReputationRep:
    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???
    Offline

    15
    ReputationRep:
    (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.....
 
 
 
Poll
Black Friday: Yay or Nay?
Useful resources

The Student Room, Get Revising and Marked by Teachers are trading names of The Student Room Group Ltd.

Register Number: 04666380 (England and Wales), VAT No. 806 8067 22 Registered Office: International House, Queens Road, Brighton, BN1 3XE

Write a reply...
Reply
Hide
Reputation gems: You get these gems as you gain rep from other members for making good contributions and giving helpful advice.