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

Homework Help: Number Theory. If d=gcd(a,b) then

  1. Sep 5, 2012 #1
    1. The problem statement, all variables and given/known data
    If d=gcd(a,b) show that gcd((a/d),(b/d))=1

    2. Relevant equations

    3. The attempt at a solution
    Basically, I know that I need to show that 1 is a linear combination of a/d and b/d. I'm not exactly sure how to go about this. Dividing by d gives (d/d)=1=gcd(a/d,b/d) if that's correct, does that get me anywhere?
  2. jcsd
  3. Sep 5, 2012 #2


    User Avatar
    Science Advisor
    Homework Helper
    Gold Member

    If d = gcd(a,b), then what does that imply about linear combinations of a and b?
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook