# GCD Number Theory Problem

1. Jan 7, 2015

### PsychonautQQ

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

2. Relevant equations
None

3. The attempt at a solution
My attempt at a solution:

Let d = gcd(ac,b),
Let g = gcd(c,b),
I want to show that g|d and that d|g. I then went on to make a bunch of circular writing and get nowhere... I set up things like:

1 = ax + by
d = acw + bz --> 1 = (ac/d)w + (b/d)z
g = cn + bm --> 1 = (c/d)n + (b/d)m

Is my approach here a solid method? I can't think of any other way to show that gcd(ac,b) = gcd(c,b) besides assigning each of them a value and showing that they divide eachother.

2. Jan 7, 2015

### RUber

That seems to be a reliable method.
I prefer to work with factor sets:
Let A be the unique prime factor set of a, B be the unique prime factor set of b, and C be the unique prime factor set of c.
$A\cap B =\{1\}$
$AC=A \cup C$
$AC\cap B= (A \cup C) \cap B = (A\cap B) \cup (C \cap B) = 1 \cup (C \cap B)$
A similar argument should apply with repeated prime factors and combinations to find the gcd.