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
http://mathforum.org/dr.math/
```
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
Math Forum Home || Math Library || Quick Reference || Math Forum Search