The Math Forum

Ask Dr. Math - Questions and Answers from our Archives
Associated Topics || Dr. Math Home || Search Dr. Math

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 
Associated Topics:
High School Number Theory

Search the Dr. Math Library:

Find items containing (put spaces between keywords):
Click only once for faster results:

[ Choose "whole words" when searching for a word like age.]

all keywords, in any order at least one, that exact phrase
parts of words whole words

Submit your own question to Dr. Math

[Privacy Policy] [Terms of Use]

Math Forum Home || Math Library || Quick Reference || Math Forum Search

Ask Dr. MathTM
© 1994- The Math Forum at NCTM. All rights reserved.