Set Theory and GCD and Divisibility

Date: 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/