(adsbygoogle = window.adsbygoogle || []).push({}); 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!

**Physics Forums | Science Articles, Homework Help, Discussion**

Dismiss Notice

Join Physics Forums Today!

The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

# Homework Help: A Proof involving the GCD and divisibility

**Physics Forums | Science Articles, Homework Help, Discussion**