Results 1 to 8 of 8

Math Help - elem.num.theo - GCD

  1. #1
    Member cassiopeia1289's Avatar
    Joined
    Aug 2007
    From
    chicago
    Posts
    101

    elem.num.theo - GCD

    OK: Given: There exists an x and y such that ax+by=2. Can you conclude that gcd(a,b)=2? If yes, why? If no, what can you say about the gcd(a,b)?

    So I know you can do it the other way around, so gcd(a,b)=2 does equal ax+by=2 - but I wasn't sure you could switch it. Even then, I would need more proof that it doesn't work. Some kind of guidance would be lovely.
    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 cassiopeia1289 View Post
    OK: Given: There exists an x and y such that ax+by=2. Can you conclude that gcd(a,b)=2? If yes, why? If no, what can you say about the gcd(a,b)?
    no.

    example, take two numbers a and b where you know the gcd is 1. so we have ma + nb = 1 for some integers m and n. now multiply that equation by 2, we get

    (2m)a + (2n)b = 2, write 2m as x and 2n as y, we have xa + yb = 2

    but we know the gcd is 1! what can you say therefore?

    So I know you can do it the other way around, so gcd(a,b)=2 does equal ax+by=2 - but I wasn't sure you could switch it. Even then, I would need more proof that it doesn't work. Some kind of guidance would be lovely.
    yes, if gcd(a,b) = 2, then you can write a linear combination of a and b equaling 2
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Moo
    Moo is offline
    A Cute Angle Moo's Avatar
    Joined
    Mar 2008
    From
    P(I'm here)=1/3, P(I'm there)=t+1/3
    Posts
    5,618
    Thanks
    6
    Hello,

    Please remember that :
    au+bv=n <=> gcd(a,b) divides n
    gcd(a,b)=n => there exist u,v such that au+bv=n

    au+bv=1 <=> gcd(a,b)=1
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Member cassiopeia1289's Avatar
    Joined
    Aug 2007
    From
    chicago
    Posts
    101
    Quote Originally Posted by Moo View Post
    au+bv=1 <=> gcd(a,b)=1
    but didn't Jhevon just prove that wasn't the case?
    I didn't think it was an if and only if case
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Moo
    Moo is offline
    A Cute Angle Moo's Avatar
    Joined
    Mar 2008
    From
    P(I'm here)=1/3, P(I'm there)=t+1/3
    Posts
    5,618
    Thanks
    6
    Quote Originally Posted by cassiopeia1289 View Post
    but didn't Jhevon just prove that wasn't the case?
    I didn't think it was an if and only if case
    It is "if and only if", if and only if it's 1.
    Follow Math Help Forum on Facebook and Google+

  6. #6
    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 cassiopeia1289 View Post
    but didn't Jhevon just prove that wasn't the case?
    I didn't think it was an if and only if case
    haha, no i didn't. i was addressing the linear combination = 2, not 1

    as Moo said, a linear combination just yields a multiple of the gcd
    Follow Math Help Forum on Facebook and Google+

  7. #7
    Member cassiopeia1289's Avatar
    Joined
    Aug 2007
    From
    chicago
    Posts
    101
    *ok, officially more confused than I started out*

    so it is true!
    since ax+by=2 <=> gcd(a,b)=2

    or does that case only work with 1 and not 2?
    Follow Math Help Forum on Facebook and Google+

  8. #8
    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 cassiopeia1289 View Post
    *ok, officially more confused than I started out*

    so it is true!
    since ax+by=2 <=> gcd(a,b)=2
    no. i started out with the gcd = 1 and showed that i could still write it as a linear combination as 2, or 3 or anything. so the linear combination yielding 2 did not imply the gcd was 2 (because we knew it was 1 in the first place). i just provided a counter-example

    or does that case only work with 1 and not 2?
    it only works for 1, nothing else
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. elem#theo - phi and odd #
    Posted in the Number Theory Forum
    Replies: 4
    Last Post: December 2nd 2008, 07:45 PM
  2. elem#theo - induction + Bertrand's
    Posted in the Number Theory Forum
    Replies: 4
    Last Post: October 23rd 2008, 05:04 PM
  3. elem.num.theo - diophantine equations
    Posted in the Number Theory Forum
    Replies: 6
    Last Post: October 9th 2008, 03:23 PM
  4. elem.num.theo - help w/proof
    Posted in the Number Theory Forum
    Replies: 3
    Last Post: September 26th 2008, 07:18 AM
  5. elem. # theo - gcd(a, a+n) divides n ...
    Posted in the Number Theory Forum
    Replies: 4
    Last Post: September 23rd 2008, 09:25 PM

Search Tags


/mathhelpforum @mathhelpforum