Results 1 to 8 of 8

Math Help - Infinite Primes Proof

  1. #1
    Newbie Yankee77's Avatar
    Joined
    Mar 2005
    Posts
    3

    Infinite Primes Proof

    I have heard that Euclid wrote a proof demonstrating that there are infinite prime numbers. Is it true?
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Newbie Matrix's Avatar
    Joined
    Mar 2005
    Posts
    10
    Euclid proved that there are infinitely many prime numbers. This is one of the first proofs known which uses the method of contradiction to establish a result. Euclid also gives a proof of the Fundamental Theorem of Arithmetic: Every integer can be written as a product of primes in an essentially unique way.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Newbie Artriste's Avatar
    Joined
    Apr 2005
    Posts
    5

    Euclid's infinite primes

    Assume there are a finite number, n, of primes, the largest being pn. Consider the number that is the product of these, plus one: N = p1...pn+1. By construction, N is not divisible by any of the pi. Hence it is either prime itself, or divisible by another prime greater than pn, contradicting the assumption.

    2 + 1 = 3, is prime
    2*3 + 1 = 7, is prime
    2*3*5 + 1 = 31, is prime
    2*3*5*7 + 1 = 211, is prime
    2*3*5*7*11 + 1 = 2311, is prime
    2*3*5*7*11*13 + 1 = 30031 = 59*509
    2*3*5*7*11*13*17 + 1 = 510511 = 19*97*277
    2*3*5*7*11*13*17*19 + 1 = 9699691 = 347*27953
    2*3*5*7*11*13*17*19*23 + 1 = 223092871 = 317*703763
    2*3*5*7*11*13*17*19*23*29 + 1 = 6469693231 = 331*571*34231
    2*3*5*7*11*13*17*19*23*29*31 + 1 = 200560490131, is prime

    As you can see Euclids logic does produce primes at first but not always. It is a brilliant peice of logic however it does not prove the infinitude of primes.

    -Artriste
    Follow Math Help Forum on Facebook and Google+

  4. #4
    hpe
    hpe is offline
    Member hpe's Avatar
    Joined
    Apr 2005
    Posts
    158

    Exclamation Inifinitely many primes

    @ Artriste -

    Euclid proved that you can never run out of primes, so there must be infinitely many of them. To be sure, he didn't actually give a formula to produce all possible primes, but that's not necessary to show that there are infinitely many.


    Challenge - are there infinitely many primes in the arithmetic progression 3, 7, 11, 15, 19, 23, 27, 31, ... ? Why / why not?
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Junior Member theprof's Avatar
    Joined
    Apr 2005
    From
    Torino - Italy
    Posts
    26
    I have heard that Euclid wrote a proof demonstrating that there are infinite prime numbers. Is it true?

    Yes it is.
    He proved that if you write down all known primes, you can always get a greater one, that is: "prime numbers are infinite."

    Proof
    Suppose 2,3,5,7,11 are the only primes you know.
    You write a bigger number in this way:

    N=2x3x5x7x11+1

    This number is not a multiple of 2, 3, 5, 7 or 11 because performing division you always have remainder one. Therefore:
    a. N is prime itself;
    b. N is a multiple of a prime grater than 11.

    In both cases you have the proof that exists a prime number grater than the greatest you suppesed to have found, so they are infinite.

    bye
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Newbie Artriste's Avatar
    Joined
    Apr 2005
    Posts
    5

    I give up

    Quote Originally Posted by hpe

    Challenge - are there infinitely many primes in the arithmetic progression 3, 7, 11, 15, 19, 23, 27, 31, ... ? Why / why not?
    I would guess that the answer is yes. But you have stumped me. Care to enlighten us hpe?
    Follow Math Help Forum on Facebook and Google+

  7. #7
    Junior Member theprof's Avatar
    Joined
    Apr 2005
    From
    Torino - Italy
    Posts
    26
    Quote Originally Posted by hpe
    @ Artriste -
    Challenge - are there infinitely many primes in the arithmetic progression 3, 7, 11, 15, 19, 23, 27, 31, ... ? Why / why not?
    the aritmetic sequence of terms 3,7,11,15,... can be writtenas 3+4n (n=0,1,2,3...) and GCD(3,4) = 1. So contains infinitely many primes because of Dirichlet Theorem.
    http://mathworld.wolfram.com/DirichletsTheorem.html

    bye
    Follow Math Help Forum on Facebook and Google+

  8. #8
    hpe
    hpe is offline
    Member hpe's Avatar
    Joined
    Apr 2005
    Posts
    158

    Inifinitely many primes

    Hi theprof -

    I had an elementary proof in mind for the fact that yes, there are infinitely many primes in the set {3,7,11,15,...}.

    So, here goes:

    Suppose there are only finitely many such primes, say a, b, ..., p, q. They are all of the form 4n+3, that is, they leave a remainder of 3 when divided by 4. The first one is a=3, the last one ... who knows.

    Multiply them all together and call the product x, i.e. x = abcd....pq.

    Now consider - as an aside - what happens when you multiply two odd numbers together:

    If they are both of the form 4n+3, say 4n+3 and 4m+3, the product is (4n+3)(4m+3) = 16mn + 12m + 12n + 9 = 4(4mn + 3m + 3n + 2) + 1. So the product is of the form 4k+1.

    If they are both of the form 4n+1, say 4n+1 and 4m+1, the product is (4n+1)(4m+1) = 16mn + 4m + 4n + 1 = 4(4mn + m + n) + 1. So the product is also of the form 4k+1.

    If one is of the form 4n+3, and the other of the form 4m+1, the product is (4n+3)(4m+1) = 16mn + 12m + 4n + 3 = 4(4mn + 3m + n) + 3. So in this case the product is of the form 4k+3.

    Back to the product x. All factors are of the form 4n+3 with different n, so there are two cases:
    • If the number of factors is even, then abcd...pq = (ab)(cd)...(pq). Each parenthesis term is of the form 4n+1, so the whole product is of the form 4N+1, with a humongous number N.

    • If the number of factors is odd, then abcd...pq = (ab)(cd)...p)q. Each parenthesis term is of the form 4n+1, and there is one extra factor of the form 4n+3. So the the whole product is of the form 4M+3, with a gigantic number M.

    In the first case, consider the value y=x+2.

    This number cannot be evenly divisible by any prime number of the form 4n+3, i.e. by a, b, c, ..., p, q, since it will leave a remainder of 2 when divided by any of them. So all its prime factors must be of the other flavor, namely of the form 4n+1. However, y = x+2 = 4N+3, and when you multiply factors of the form 4n+1 together, you can never get a result of the form 4N+3. So y doesn't have any prime factors at all - which is absurd.


    In the second case (an odd number of factors), consider the value y=3x+2.
    This number cannot be evenly divisible by any prime number of the form 4n+3, i.e. by a, b, c, ..., p, q, since it will leave a remainder of 2 when divided by any of them. So all its prime factors must be of the other flavor, namely of the form 4n+1. However, y = 3x+2 = 3(4M+3)+2 = 12M + 11 = 4(3M+2) + 3 = 4K+3, and as before, when you multiply factors of the form 4n+1 together, you can never get a result of the form 4K+3. So y doesn't have any prime factors at all - which is equally absurd.

    If you believe that there are only finitely many prime numbers of the form 4n+3, you are forced to absurd conclusions - which proves there must be infinitely many of them
    Last edited by hpe; April 11th 2005 at 06:02 PM.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Infinite Primes Proof is complete ?
    Posted in the Number Theory Forum
    Replies: 3
    Last Post: November 2nd 2009, 05:49 AM
  2. infinite primes
    Posted in the Number Theory Forum
    Replies: 8
    Last Post: January 30th 2009, 10:42 AM
  3. infinite primes?
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: October 13th 2007, 05:42 PM
  4. Primes in an Infinite Sequence
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: March 27th 2007, 01:25 AM
  5. my last question-infinite number of primes
    Posted in the Number Theory Forum
    Replies: 15
    Last Post: December 28th 2006, 11:12 AM

Search Tags


/mathhelpforum @mathhelpforum