How Can You Prove (ab,c) = 1 Given (a,c) and (b,c) Are Both 1?

[Undoubtedly0]

Homework Statement

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!

 

[micromass]

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?

 

[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?

 

[micromass]

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

 

[Undoubtedly0]

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

 

[micromass]

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

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

 

[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?

 

[micromass]

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?

Yes, this is already correct.

 

[Undoubtedly0]

Yes, this is already correct.

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

 

[micromass]

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

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

 

[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?

 

[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.