Set Theory and GCD and DivisibilityDate: 01/27/2003 at 16:17:43 From: Kanishka Subject: Set theory and GCD and divisibility If 1 <= a <= n and 1 <= b <= n and ab <= n, and if a divides n and b divides n, does that mean that ab divides n given that GCD(a,b) = 1 ? I can prove this using numbers but cannot do so using variables. I mean I have no general proof of the same. Date: 01/27/2003 at 16:33:20 From: Doctor Wilkinson Subject: Re: Set theory and GCD and divisibility Hi, Kanishka. The trick in many GCD problems is to use the fact that the GCD(a,b) can be expressed in the form xa + yb, where x and y are integers. So here you have integers x and y such that xa + yb = 1 If you multiply this equation by n, you get nxa + nyb = n Now I claim that both terms on the left hand side of this equation are divisible by ab. Can you see why? - Doctor Wilkinson, The Math Forum http://mathforum.org/dr.math/ |
Search the Dr. Math Library: |
[Privacy Policy] [Terms of Use]
Ask Dr. Math^{TM}
© 1994-2013 The Math Forum
http://mathforum.org/dr.math/