Results 1 to 2 of 2

Math Help - Indirect proof of Infinate number of primes

  1. #1
    Newbie Lazarath's Avatar
    Joined
    Mar 2006
    From
    Whitby Ontario
    Posts
    3

    Indirect proof of Infinate number of primes

    IN class we derived the following expressionto express "There are an infinate number of primes" using predicates prime(x) : x is a prime and g(x, y): x > y

    There exists a "z" in N, prime(z) and [for all "x" in N , (prime(x) --> there exists a "y" in N, (prime(y) and g( y, x)))]

    I believe they want me to prove this using the contrapositive


    any hints?

    Laz
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Global Moderator

    Joined
    Nov 2005
    From
    New York City
    Posts
    10,616
    Thanks
    10
    Quote Originally Posted by Lazarath
    IN class we derived the following expressionto express "There are an infinate number of primes" using predicates prime(x) : x is a prime and g(x, y): x > y

    There exists a "z" in N, prime(z) and [for all "x" in N , (prime(x) --> there exists a "y" in N, (prime(y) and g( y, x)))]

    I believe they want me to prove this using the contrapositive


    any hints?

    Laz
    I do not know what your are asking but there is an elegant indirect proof of infinitude of primes that I know; it comes from Euclid. Assume, that there are finitely many primes, S=\{p_1,p_2,...p_n\}. Now form a number,
    N=p_1\cdot p_2\cdot ...\cdot p_n+1.
    Buy the fundamental theorem of arithmetic this number N factors into primes number and thus is divisible by a prime number. But non of these prime numbers from S divide N. Because if p_k|N then p_k|(p_1\cdot ...\cdot p_k\cdot ...\cdot p_n+1) but since p_k|p_1\cdot ...\cdot p_k\cdot ...\cdot p_n then
    p_k|1 which is not possible. Thus, there cannot be finitely many prime numbers.

    \mathbb{Q}.\mathcal{E}.D
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. indirect proof 3
    Posted in the Geometry Forum
    Replies: 3
    Last Post: February 26th 2011, 11:47 PM
  2. Indirect proof
    Posted in the Geometry Forum
    Replies: 3
    Last Post: February 25th 2011, 06:45 AM
  3. Indirect proof
    Posted in the Geometry Forum
    Replies: 2
    Last Post: February 23rd 2011, 02:22 PM
  4. direct and indirect proof
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: February 26th 2010, 09:16 PM
  5. Indirect proof
    Posted in the Geometry Forum
    Replies: 1
    Last Post: November 15th 2007, 04:34 AM

Search Tags


/mathhelpforum @mathhelpforum