# A Proof involving the GCD and divisibility

1. Sep 8, 2011

### AlexChandler

1. The problem statement, all variables and given/known data

If two integers a and b are relatively prime and if each divides an integer n, prove that their product ab divides n

2. Relevant equations

1=sa+tb for some integers s and t (thm 1.35)

gcd(a,b)=1

n=aa'=bb'

3. The attempt at a solution

I have tried many many different ways to show that ab divides n, even tried a proof by induction. None of my methods seemed to be making any progress toward showing that ab divides n. Here is an example of something I tried:

Let gcd(a,b)=1 and let both a and b divide n.
Then by thm 1.35 sa+tb=1 for some integers s and t
Also we have n=aa'=bb' for some integers a' and b'
By the division algorithm, we have unique integers q,r such that ab=nq+r with r being a non-negative integer strictly less than n. Now I want to show that r=0 but haven't found a good way to do this. Clearly we must use the fact that 1=sa+tb and n=aa'=bb', but doing this does not give me that r=0 in any way that I have found.

If anybody has a hint or possibly a different strategy for this proof I would be very grateful!

2. Sep 8, 2011

### Hurkyl

Staff Emeritus
Have you considered using other characterizations of the GCD? Or even just using the properties of the GCD itself?