Results 1 to 4 of 4

Math Help - pairwise relatively prime

  1. #1
    Super Member
    Joined
    Apr 2009
    Posts
    678
    Thanks
    1

    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 09:46 AM. Reason: wording
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Super Member
    Joined
    Apr 2009
    Posts
    678
    Thanks
    1
    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, 08:41 AM
  2. Pairwise non-isomorphic formality
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: November 29th 2009, 07:05 AM
  3. Pairwise Independence vs Idependence help
    Posted in the Advanced Statistics Forum
    Replies: 1
    Last Post: September 15th 2009, 03:50 PM
  4. pairwise prime
    Posted in the Number Theory Forum
    Replies: 5
    Last Post: September 6th 2008, 06:21 PM
  5. pairwise relatively prime integers
    Posted in the Number Theory Forum
    Replies: 4
    Last Post: July 17th 2006, 11:10 AM

Search Tags


/mathhelpforum @mathhelpforum