Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Greatest Common Divisor

  1. Jan 2, 2010 #1
    If there are integers s,t with as+bt=6, this implies that gcd(a,b)=6, right?

    And if gcd(a,b)=6, does this necessarily mean that a and b are not relatively prime since their gcd is not 1? (I have read that two integers a and b are relatively prime if gcd(a,b)=1).
     
  2. jcsd
  3. Jan 2, 2010 #2
    No. It simply implies that gcd(a,b) divides 6. For instance take a=4, b =6, then gcd(a,b) = 2 but:
    [tex]0a+1b = 6[/tex]

    Yes, 6 divides them both so they have a common factor besides 1 (2,3,6 are all common factors). That gcd(a,b)=1 is actually a pretty common definition of integers being relatively prime.

    By the way if you wanted to use this argument to prove that a and b are not relatively prime, then unfortunately that doesn't work. Consider for instance:
    a = 2, b= 3
    which are definitely relatively prime as they are both prime, but:
    [tex]6b+(-6)a = 6[/tex]
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook




Similar Discussions: Greatest Common Divisor
  1. Integral Divisors (Replies: 2)

  2. Greatest Number (Replies: 5)

  3. Greatest common divisor (Replies: 11)

Loading...