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
    9
    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, 10:47 PM
  2. Indirect proof
    Posted in the Geometry Forum
    Replies: 3
    Last Post: February 25th 2011, 05:45 AM
  3. Indirect proof
    Posted in the Geometry Forum
    Replies: 2
    Last Post: February 23rd 2011, 01:22 PM
  4. direct and indirect proof
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: February 26th 2010, 08:16 PM
  5. Indirect proof
    Posted in the Geometry Forum
    Replies: 1
    Last Post: November 15th 2007, 03:34 AM

Search Tags


/mathhelpforum @mathhelpforum