Proving If GCD(a,b) = c Then c^2/ab

[FreshUC]

So here is the problem.

Prove that If the gcd(a,b) = c then c^2 divides ab

I know it looks very simple and it seems to be true, But I get the feeling I'm doing something wrong here in my proof. Would appreciate it if someone can explain if I'm on the right track or not.


~~~~~~~~~~

Proof by Contradiction:

Assume that gcd(a,b) = c and c^2 does not divide ab
Let a = 6 and b = 9. So,

gcd(6,9) = 3
ab = 54
c^2 = 9

But 54/9 = 6, so 9 divides 54 and therefore c^2 divides ab. This contradicts the assumption, so the claim "If gcd(a,b) = c then c^2/ab" is infact true.

~~~~~~~~~~~

 

[zooxanthellae]

Unfortunately, you are right to be uneasy about your proof! What you have shown is that for a = 6 and b = 9 then the statement is true. However, there remain an infinite number of unconsidered cases. What if a = 3 and b = 8? a = 444 and b = 86274?

Instead of considering specific numbers, then, we just leave a and b as arbitrary numbers. That way if we prove the statement for arbitrary numbers then we have done all cases.

So we have gcd(a,b) = c. Then c divides a and c divides b. So cx = a and cy = b. Can you see how the rest of it goes?

Hope that helps!

 

[FreshUC]

Unfortunately, you are right to be uneasy about your proof! What you have shown is that for a = 6 and b = 9 then the statement is true. However, there remain an infinite number of unconsidered cases. What if a = 3 and b = 8? a = 444 and b = 86274?

Instead of considering specific numbers, then, we just leave a and b as arbitrary numbers. That way if we prove the statement for arbitrary numbers then we have done all cases.

So we have gcd(a,b) = c. Then c divides a and c divides b. So cx = a and cy = b. Can you see how the rest of it goes?

Hope that helps!

This is very new to me. I get what you mean about how it doesn't prove it for all integers, and I do understand how a = cx and b = cy. But I'm struggling to see where to go next. could I say that a*b = cx*cy = c^2xy? And then c^2xy must be divisible by c^2?

 

[zooxanthellae]

That is how I would do it. Unless you cannot assume multiplicative commutativity, i.e. a * b = b * a (if your professor has not mentioned anything like that, chances are you can).

 

[FreshUC]

That is how I would do it. Unless you cannot assume multiplicative commutativity, i.e. a * b = b * a (if your professor has not mentioned anything like that, chances are you can).

No I don't think anything like that was mentioned. That's got to be it! Thanks so much for your help I appreciate it :)