1. Not finding help here? Sign up for a free 30min 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!

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.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?
Draft saved Draft deleted



Similar Discussions: GCD relative prime question
  1. GCD and Relative Primes (Replies: 15)

  2. Relatively prime (Replies: 11)

Loading...