Results 1 to 7 of 7

Math Help - GCD and the Euclidean Algorithm

  1. #1
    Newbie
    Joined
    Nov 2009
    Posts
    23

    GCD and the Euclidean Algorithm

    What can you conclude about gcd(a,b) if there are integers s,t with as+bt=6?
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Senior Member Shanks's Avatar
    Joined
    Nov 2009
    From
    BeiJing
    Posts
    374
    we can conclude that gcd(a,b) is a divisor of 6.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Member
    Joined
    Apr 2008
    Posts
    191
    Also you can conclude that a and b are NOT relatively prime since their gcd is 6. Because two integers a and b are relatively prime if gcd(a,b)=1.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor Drexel28's Avatar
    Joined
    Nov 2009
    From
    Berkeley, California
    Posts
    4,563
    Thanks
    21
    Quote Originally Posted by kturf View Post
    What can you conclude about gcd(a,b) if there are integers s,t with as+bt=6?
    To expand upon Shanks's explanations it can be proven that the equation ax+by=c (a linear Diophantine equation) is solvable precisely when c=m\cdot (a,b) for some m\in\mathbb{Z}. It follows that \frac{6}{(a,b)}\in\mathbb{Z}\implies (a,b)\mid 6.

    Unfortunately though, Roam's observation is slightly wrong. If he considers x+2y=6 which has solution x=3\cdot6,y=-2\cdot6 (there is a reason why I didn't simplify).
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Member
    Joined
    Apr 2008
    Posts
    191
    Quote Originally Posted by Drexel28 View Post
    To expand upon Shanks's explanations it can be proven that the equation ax+by=c (a linear Diophantine equation) is solvable precisely when c=m\cdot (a,b) for some m\in\mathbb{Z}. It follows that \frac{6}{(a,b)}\in\mathbb{Z}\implies (a,b)\mid 6.

    Unfortunately though, Roam's observation is slightly wrong. If he considers x+2y=6 which has solution x=3\cdot6,y=-2\cdot6 (there is a reason why I didn't simplify).
    Thanks for spotting my mistake; I had that backwards. "as+bt=6" simply implies that gcd(a,b) divides 6. For instance if you take a=4, b =6, then gcd(a,b) = 2 but 0a+1b = 6.

    On the other hand, if gcd(a,b)=6, then 6 divides them both so they have a common factor besides 1 (2,3,6 are all common factors). "gcd(a,b)=1" is a pretty common definition of integers being relatively prime.
    And yes, if you wanted to use this argument to prove that a and b are not relatively prime, then that doesn't work. Consider for instance: a = 2, b= 3, which are definitely relatively prime as they are both prime, but 6b+(-6)a = 6.
    Follow Math Help Forum on Facebook and Google+

  6. #6
    MHF Contributor Drexel28's Avatar
    Joined
    Nov 2009
    From
    Berkeley, California
    Posts
    4,563
    Thanks
    21
    Quote Originally Posted by Roam View Post
    Thanks for spotting my mistake; I had that backwards. "as+bt=6" simply implies that gcd(a,b) divides 6. For instance if you take a=4, b =6, then gcd(a,b) = 2 but 0a+1b = 6.

    On the other hand, if gcd(a,b)=6, then 6 divides them both so they have a common factor besides 1 (2,3,6 are all common factors). "gcd(a,b)=1" is a pretty common definition of integers being relatively prime.
    And yes, if you wanted to use this argument to prove that a and b are not relatively prime, then that doesn't work. Consider for instance: a = 2, b= 3, which are definitely relatively prime as they are both prime, but 6b+(-6)a = 6.
    If you look closely your last example is precisely the example I used!
    Follow Math Help Forum on Facebook and Google+

  7. #7
    Senior Member Shanks's Avatar
    Joined
    Nov 2009
    From
    BeiJing
    Posts
    374
    In fact, gcd(a,b) is the smallest positive integer of the form as+bt,where s and t are integers.
    further more, all numbers of the form as+bt is in the multiple table of gcd(a,b).

    I hope this would help you.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Euclidean Algorithm
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: September 30th 2010, 11:46 AM
  2. Euclidean Algorithm
    Posted in the Number Theory Forum
    Replies: 3
    Last Post: September 14th 2010, 07:53 AM
  3. [SOLVED] Euclidean Algorithm
    Posted in the Number Theory Forum
    Replies: 5
    Last Post: September 5th 2010, 07:45 PM
  4. Euclidean algorithm
    Posted in the Number Theory Forum
    Replies: 4
    Last Post: August 8th 2009, 09:28 AM
  5. Euclidean Algorithm
    Posted in the Discrete Math Forum
    Replies: 4
    Last Post: May 13th 2007, 08:20 AM

Search Tags


/mathhelpforum @mathhelpforum