GCD Number Theory Problem

  • #1
784
11

Homework Statement


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

Homework Equations


None

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.
 

Answers and Replies

  • #2
RUber
Homework Helper
1,687
344
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.
 

Related Threads on GCD Number Theory Problem

  • Last Post
Replies
4
Views
3K
  • Last Post
Replies
2
Views
475
  • Last Post
Replies
14
Views
2K
  • Last Post
Replies
1
Views
2K
  • Last Post
Replies
2
Views
3K
Replies
2
Views
3K
  • Last Post
Replies
1
Views
1K
  • Last Post
Replies
4
Views
40K
  • Last Post
Replies
1
Views
1K
Replies
5
Views
556
Top