- #1
AlexChandler
- 283
- 0
Homework Statement
If two integers a and b are relatively prime and if each divides an integer n, prove that their product ab divides n
Homework Equations
1=sa+tb for some integers s and t (thm 1.35)
gcd(a,b)=1
n=aa'=bb'
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!