Results 1 to 4 of 4

Math Help - Proof involving GCD

  1. #1
    Junior Member
    Joined
    May 2010
    Posts
    36

    Proof involving GCD

    Hello, I'm having a bit of trouble with the following problem; I'm not sure about how to prove this statement. I'm not even sure on how to begin:

    Let a,b ∈ Z. Prove that gcd(a,b)=gcd(2a−3b,a−2b).

    I would greatly appreciate any help/tips to get me started.


    Thanks!
    Follow Math Help Forum on Facebook and Google+

  2. #2
    is up to his old tricks again! Jhevon's Avatar
    Joined
    Feb 2007
    From
    New York, USA
    Posts
    11,663
    Thanks
    3
    Quote Originally Posted by spoc21 View Post
    Hello, I'm having a bit of trouble with the following problem; I'm not sure about how to prove this statement. I'm not even sure on how to begin:

    Let a,b ∈ Z. Prove that gcd(a,b)=gcd(2a−3b,a−2b).

    I would greatly appreciate any help/tips to get me started.


    Thanks!
    let \displaystyle \gcd (a,b) = d_1 and \displaystyle \gcd (2a - 3b, a - 2b) = d_2

    Then, for some \displaystyle m,n,x,y \in \mathbb Z, we have:

    \displaystyle d_1 = ma + nb and \displaystyle d_2 = x(2a - 3b) + y(a - 2b), and these are the smallest linear combinations.

    But this means \displaystyle d_2 = (2x + y)a + (-3x - 2y)b, and so \displaystyle d_2 is also a linear combination of \displaystyle a and \displaystyle b. This means that this linear combination is a multiple of \displaystyle d_1 (*) and hence, \displaystyle d_2 = k d_1 for some \displaystyle k \in \mathbb Z \implies d_1 \mid d_2.

    The proof is complete if you can show that \displaystyle d_2 \mid d_1. How can you do this?


    (*) this should have been proven in your class or text at some point.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Junior Member
    Joined
    May 2010
    Posts
    36
    Quote Originally Posted by Jhevon View Post
    \displaystyle k \in \mathbb Z \implies d_1 \mid d_2.

    The proof is complete if you can show that \displaystyle d_2 \mid d_1. How can you do this?
    Thanks for the reply. Is this d_1 \mid d_2 or d_2 \mid d_1

    I'm assuming that to \displaystyle d_2 \mid d_1, we would do the follwoing:

    \displaystyle  d_2 = d_1 k
    Therefore, we get:

    \displaystyle k = d_2 \mid d_1

    Do you think this is a correct approach?
    Follow Math Help Forum on Facebook and Google+

  4. #4
    is up to his old tricks again! Jhevon's Avatar
    Joined
    Feb 2007
    From
    New York, USA
    Posts
    11,663
    Thanks
    3
    Quote Originally Posted by spoc21 View Post
    Thanks for the reply. Is this d_1 \mid d_2 or d_2 \mid d_1

    I'm assuming that to \displaystyle d_2 \mid d_1, we would do the follwoing:

    \displaystyle  d_2 = d_1 k
    Therefore, we get:

    \displaystyle k = d_2 \mid d_1

    Do you think this is a correct approach?
    um, no. first, you can't assume what you want to prove. that's called begging the question.

    and what you did after that makes no sense especially your last statement. what i think you were trying to say, doesn't follow from the statement you had before that.

    go back to basics. what do you know about gcd. what relationship does \displaystyle d_2 have with \displaystyle (2a - 3b) and \displaystyle (a - 2b)?
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Proof involving mods
    Posted in the Number Theory Forum
    Replies: 6
    Last Post: March 12th 2010, 07:35 AM
  2. Proof involving e
    Posted in the Calculus Forum
    Replies: 1
    Last Post: March 2nd 2010, 03:44 PM
  3. Proof involving inequalities
    Posted in the Advanced Algebra Forum
    Replies: 4
    Last Post: December 22nd 2009, 08:06 PM
  4. Proof involving GCD
    Posted in the Discrete Math Forum
    Replies: 11
    Last Post: December 5th 2009, 04:36 PM
  5. Proof of a limit involving [x]
    Posted in the Calculus Forum
    Replies: 4
    Last Post: April 5th 2009, 01:48 AM

Search Tags


/mathhelpforum @mathhelpforum