1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

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

  1. Mar 18, 2012 #1
    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.

    ~~~~~~~~~~~
     
  2. jcsd
  3. Mar 18, 2012 #2
    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!
     
    Last edited: Mar 18, 2012
  4. Mar 18, 2012 #3
    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?
     
  5. Mar 18, 2012 #4
    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).
     
  6. Mar 18, 2012 #5
    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 :)
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook