1. ## Divisability Theorem

Hello!
Using integers a, b and c...

I am trying to prove that if a and b are relativly prime (their gcd is 1), and if a divides c, and b divides c, then ab must divide c.

I started tooling with linear combinations and multipules but I couldn't seem to get the result (that some integer multipule of ab is equal to c)

Thanks! Sorry about my brutal spelling.

2. Originally Posted by matt.qmar
Hello!
Using integers a, b and c...

I am trying to prove that if a and b are relativly prime (their gcd is 1), and if a divides c, and b divides c, then ab must divide c.

I started tooling with linear combinations and multipules but I couldn't seem to get the result (that some integer multipule of ab is equal to c)

Thanks! Sorry about my brutal spelling.
You can use that a and b have no prime factors in common. So all the prime powers that divide a divide c, and all the prime powers that divide b divide c, and the prime powers of ab are precisely the union of those of a and those of b.

3. Hey, thanks!

It does make sense, however, we now have each of these prime factors dividing c, but we can't say their product divides c, because that is what we are trying to prove, isn't it?

4. Originally Posted by matt.qmar
Hey, thanks!

It does make sense, however, we now have each of these prime factors dividing c, but we can't say their product divides c, because that is what we are trying to prove, isn't it?
x divides y if and only if all the prime powers of x divide y.

5. of course! thanks alot.

6. Originally Posted by matt.qmar
of course! thanks alot.
I'm actually wondering now whether this is a circular argument since the theorem of post #4 is pretty similar to what you're trying to prove. I'll have to think on it some more when I have more time.

7. Well I'm still a little unclear on which theorems we can or can't make use of (if theorem A is used to prove theorem B, it wouldn't make sense to use B to prove A), but possibly another way is to use

$\displaystyle \gcd(a,b)=\frac{a\cdot b}{\text{lcm}(a,b)}$

And the fact that every multiple of ab is divisible by lcm(a,b). Probably would have to hit the books and see a proper development from axioms to give the best response, but maybe you have all you need by now.

8. (a,b) = 1

=> there exist integers x,y such that xa + yb = 1
=> xac + ybc = c
divide the above by ab on RHS and LHS, the result follows