# Abstract Algebra: GCD proof

1. Sep 26, 2011

### Undoubtedly0

1. The problem statement, all variables and given/known data

If (a,c) = 1 and (b,c) = 1, prove that (ab,c) = 1. Note that (x,y) refers to the greatest common divisor between x and y.

2. The attempt at a solution

There is a theorem that says since (a,c) = 1, there exist integers u and v such that au + cv = 1. Likewise, there also exist integers p and q such that bp + cq = 1. How though, could that be tied to the proof's conclusion, that there exist integers m and n such that (ab)m + cn = 1? Thanks all!

2. Sep 26, 2011

### micromass

Staff Emeritus
OK, let's do this from the definitions. Let p be a prime such that p divides ab and c. Can you reach a contradiction?

3. Sep 26, 2011

### Undoubtedly0

Maybe, if p divides ab and c, then there is an x and y such that px = ab and py = c. Now substituting into au + cv = 1 gives (px/b)u + (py)v = p(xu/b + yv) = 1. If (xu/b + yv) is an integer, is this a contradiction?

4. Sep 26, 2011

### micromass

Staff Emeritus
If p divides ab, can you show that p divides either a or b?

5. Sep 26, 2011

### Undoubtedly0

I think so; if px = ab, then p(x/b) = a, meaning p divides a?

6. Sep 26, 2011

### micromass

Staff Emeritus
Not necessarily as you don't know that x/b is an integer.

7. Sep 26, 2011

### Undoubtedly0

Ah! Okay, if py = c, then since au + cv = 1, substituting gives au + (py)v = au + p(yv) = 1, which means (a,p) = 1. It could be done similarly to show (b,p) = 1. Is this correct?

8. Sep 26, 2011

### micromass

Staff Emeritus

9. Sep 26, 2011

### Undoubtedly0

Sorry, what do you mean? Do you mean to say that this is the end of the proof?

10. Sep 26, 2011

### micromass

Staff Emeritus
No, I'm saying that what you done is correct.

11. Sep 26, 2011

### Undoubtedly0

Okay, so I assume from there it must be true that p cannot divide ab, thus a contradiction. But how would you suggest writing this out in a rigorous manner?

12. Oct 3, 2011

### Undoubtedly0

Ah, this works:

ax + cy = 1 (1)

bw + cz = 1 (2)

Multiplying (2) by 'a' gives

abw + cz = a (3)

and substituting (3) into (1) gives

(abw + cz)x + cy = ab(w) + c(azx + y) = 1

meaning (ab,c) = 1.