Results 1 to 4 of 4

Math Help - pairwise relatively prime

  1. #1
    Super Member
    Joined
    Apr 2009
    Posts
    677

    pairwise relatively prime

    This question is based on Goldbach's Proof of the Infinitude of Primes
    Goldbach's Proof of the Infinitude of Primes (1730)


    Let
    a1 = a
    a2 = a1+b
    a3 = a1a2 + b
    a4 = a1a2a3 + b
    ..
    ..

    Prove that the above seq is paiwise prime (given HCF(a,b) = 1)

    My attempt
    If the assertion is not true then their exist a smallest number 'n' for which a_n is not relatively with some a_m (m>n)

    Thus there exist a prime p such that
    p|a_m
    and p|a_n

    => p|a_m - a_n
    => p|a1a2a3....a_(n-1) [a_n....a_(m-1) - 1]
    Now p can't divide [a_n....a_(m-1) - 1] (as p|a_n)

    Thus p|a1a2a3....a_(n-1)
    => p|ai where i < n

    Hence 'n' is not the smallest. Hence Proved

    I have two questions

    1. Can someone please review this proof for me?
    2. Can someone suggest a proof without using induction?
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor undefined's Avatar
    Joined
    Mar 2010
    From
    Chicago
    Posts
    2,340
    Awards
    1
    Quote Originally Posted by aman_cc View Post
    This question is based on Goldbach's Proof of the Infinitude of Primes
    Goldbach's Proof of the Infinitude of Primes (1730)


    Let
    a1 = a
    a2 = a1+b
    a3 = a1a2 + b
    a4 = a1a2a3 + b
    ..
    ..

    Prove that the above seq is paiwise prime (given HCF(a,b) = 1)

    My attempt
    If the assertion is not true then their exist a smallest number 'n' for which a_n is not relatively with some a_m (m>n)

    Thus there exist a prime p such that
    p|a_m
    and p|a_n

    => p|a_m - a_n
    => p|a1a2a3....a_(n-1) [a_n....a_(m-1) - 1]
    Now p can't divide [a_n....a_(m-1) - 1] (as p|a_n)

    Thus p|a1a2a3....a_(n-1)
    => p|ai where i < n

    Hence 'n' is not the smallest. Hence Proved

    I have two questions

    1. Can someone please review this proof for me?
    2. Can someone suggest a proof without using induction?
    1. You forgot to include the case n=1. Also I'm wondering if special consideration should be made for the case a=1, since it could lead to a contradiction of the form p|1. But otherwise I agree with your proof.

    2. Your proof did not use induction, but rather well ordering of the naturals.
    Last edited by undefined; June 10th 2010 at 08:46 AM. Reason: wording
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Super Member
    Joined
    Apr 2009
    Posts
    677
    Quote Originally Posted by undefined View Post
    1. You forgot to include the case n=1. Also I'm wondering if special consideration should be made for the case a=1, since it could lead to an earlier contradiction of the form p|1. But otherwise I agree with your proof.

    2. Your proof did not use induction, but rather well ordering of the naturals.
    n=1 ; I omitted it as I thought it is trivial to prove that. Sorry for that.

    a =1; as far as i can think i dont think we need any special treatment.

    regarding your point 2 - i consider induction and well ordering as one and the same, so i am still looking at another way to prove this. thanks
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor undefined's Avatar
    Joined
    Mar 2010
    From
    Chicago
    Posts
    2,340
    Awards
    1
    Quote Originally Posted by aman_cc View Post
    n=1 ; I omitted it as I thought it is trivial to prove that. Sorry for that.

    a =1; as far as i can think i dont think we need any special treatment.

    regarding your point 2 - i consider induction and well ordering as one and the same, so i am still looking at another way to prove this. thanks
    Well we could use a proof just like the one on the page you linked to, but then we'd have to prove that gcd(a_i, b)=1 for all i. My instinct is to use induction for that... can't think of anything that doesn't.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Vertices pairwise in grid graph
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: December 13th 2009, 07:41 AM
  2. Pairwise non-isomorphic formality
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: November 29th 2009, 06:05 AM
  3. Pairwise Independence vs Idependence help
    Posted in the Advanced Statistics Forum
    Replies: 1
    Last Post: September 15th 2009, 02:50 PM
  4. pairwise prime
    Posted in the Number Theory Forum
    Replies: 5
    Last Post: September 6th 2008, 05:21 PM
  5. pairwise relatively prime integers
    Posted in the Number Theory Forum
    Replies: 4
    Last Post: July 17th 2006, 10:10 AM

Search Tags


/mathhelpforum @mathhelpforum