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

[j9mom]

Homework Statement

if (a,c)=1 and (b,c)=1 prove that (ab,c)=1

Homework Equations

I know that (a,c)=1 says that au+cv=1 and bs+ct=1 prove abq+cr=1

The Attempt at a Solution

I set au+cv=bs+ct now I don't know what to do

 

[aPhilosopher]

do you know the theorem that if d|ab, then d|a or d|b?

 

[j9mom]

Yes I did learn that, but how do I use that?

 

[j9mom]

So, I should prove by contradiction. If some other number divides ab then it must divide a or b but it does not divide either so it (ab,c) must = 1

 

[Dick]

do you know the theorem that if d|ab, then d|a or d|b?

That's false. 6|(3*4) but 6 doesn't divide 3 or 4. You had better say the word 'prime' at some point.

 

[j9mom]

So if I let x equal a prime number greater than 1 I can prove by contradiction that it either divides a or b and since it doesn't there is the contradiction

 

[j9mom]

Wait... x is a prime number greater than 1 that divides c

 

[aPhilosopher]

That's false. 6|(3*4) but 6 doesn't divide 3 or 4. You had better say the word 'prime' at some point.

You're right. Thanks for the correction

 

[j9mom]

Thanks

 

[Dick]

Wait... x is a prime number greater than 1 that divides c

Slow down. Can you state your reasoning in complete sentences? (a,c)=1 means a and c have no common prime divisors. Now continue.

 

[aPhilosopher]

Wait... x is a prime number greater than 1 that divides c

you don't need to specify 'greater than 1' because 1 isn't prime.


so if d|(ab, c), then there exists some prime p such that p|ab.

 

[j9mom]

Let x = a prime number greater than 1 that divides c. Assume (ab,c)=x. Based on the theorem we know that x|a or x|b. However, based on the given that (a,c)=1 and (b,c)=1, we know that x does not divide a and x does not divide b. Hence there is a contradiction and x cannot be a prime number greater than 1. Since we know there is no prime number less than 1, x must equal 1

 

[aPhilosopher]

that doesn't look quite right. strike the first sentence and let p|x where p is prime. Go from there. It's mostly good though. The problem is that (ab, c) might not be prime.

 

[j9mom]

Did not see your next post, but that is right, so I can simplify by answer to x cannot be a prime number that divides c, so x must equal 1

 

[j9mom]

A philospher: my x equals a prime number that divides c.

 

[Dick]

Let x = a prime number greater than 1 that divides c. Assume (ab,c)=x. Based on the theorem we know that x|a or x|b. However, based on the given that (a,c)=1 and (b,c)=1, we know that x does not divide a and x does not divide b. Hence there is a contradiction and x cannot be a prime number greater than 1. Since we know there is no prime number less than 1, x must equal 1

Why are you rushing this? Think about it. You can't assume BOTH x|c AND (ab,c)=x without justifying it. Look, start from this: If (ab,c) is not 1, then let x be a prime that divides (ab,c). Go from there. SLOWLY.

 

[j9mom]

Ok, but can I leave x as a prime number that divides c but is simply a common divisor not necessarily the greatest common divisor. Then I still can say it does not divide a or b so must be 1

 

[j9mom]

Ok let me start again.

 

[aPhilosopher]

You can't assume BOTH x|c AND (ab,c)=x without justifying it.

Yes you can. By definition. What can't be assumed is that (ab, c)=x and that x is prime.

 

[j9mom]

Ok: Let x be a prime number such that divides (ab,c). Now this means that x must divide c and must divide either a or b. Now I can say here is the contradiction, we know x does not divide a or b so x cannot divide (ab,c). Therefore x must equal 1

 

[aPhilosopher]

that's the idea. looks good.

 

[aPhilosopher]

except your prof might get mad about you claiming that x = 1 since you've already assumed that it's prime. Most people exclude 1 from the list of primes.

 

[Dick]

Yes you can. By definition. What can't be assumed is that (ab, c)=x and that x is prime.

On that, you are right. Oh, I see you've both already finished. Sorry to be so slow.

 

[j9mom]

So I will just say x cannot divide (ab,c) Simce x is an arbitrary prime number then it holds for all prime numbers. Therefore (ab,c)=1

 

[Billy Bob]

Hope I'm not sidetracking you too much (ignore me if I am), but I wanted to say here's an idea for a very slick proof using your original idea.

You originally used the theorem that (m,n)=d implies mx+ny=d for some integers x, y. Even though the converse is not true in general, it is true that for the special case d=1, this is an "if and only if."

That is, (m,n)=1 if and only if mx+ny=1 for some integers x, y. If you have this theorem, then you can give a nice solution to your problem.

So, if (a,c)=1 and (b,c)=1 prove that (ab,c)=1.

You know au+cv=1 and bs+ct=1 for some integers u, v, s, and t.

Now multiply those two equations and put into the form ab(some integer) + c(big mess)=1, where big mess is an integer.