GCD Number Theory Problem

  • #1

Homework Statement

if 1 = gcd(a,b), show that gcd(ac,b) = gcd(c,b)

Homework Equations


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 each other.
  • #2
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.