1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
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: GCD relative prime question

  1. Feb 20, 2015 #1
    1. The problem statement, all variables and given/known data
    if gcd(a,b) = 1, show that gcd(ac,b) = gcd(c,b)

    2. Relevant equations
    gcd(x,y) = xm + yn for integers n and m

    3. The attempt at a solution
    ax + by = 1
    gcd(ac,b) = d
    gcd(c,b) = g

    ac = dr
    b = ds
    c = gm
    b = gn

    I've been setting up equations and rearranging things but can't make any leeway, any tips?

    Update:
    g|c and g|b, so g|ac and hence g|d.

    d|ac and d|b. If I can show that d|c then i can conclude d|g. hence d=g. I now need help showing that d|c.
     
    Last edited: Feb 20, 2015
  2. jcsd
  3. Feb 20, 2015 #2

    RUber

    User Avatar
    Homework Helper

    If d is gcd(ac,b) then d|ac and d|b. If d >1, then d cannot divide both a and b, so d must divide c.
     
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook

Have something to add?
Draft saved Draft deleted



Loading...