Results 1 to 8 of 8

Math Help - Divisability Theorem

  1. #1
    Member
    Joined
    Oct 2009
    Posts
    128

    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.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor undefined's Avatar
    Joined
    Mar 2010
    From
    Chicago
    Posts
    2,340
    Awards
    1
    Quote Originally Posted by matt.qmar View Post
    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.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Member
    Joined
    Oct 2009
    Posts
    128
    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?
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor undefined's Avatar
    Joined
    Mar 2010
    From
    Chicago
    Posts
    2,340
    Awards
    1
    Quote Originally Posted by matt.qmar View Post
    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.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Member
    Joined
    Oct 2009
    Posts
    128
    of course! thanks alot.
    Follow Math Help Forum on Facebook and Google+

  6. #6
    MHF Contributor undefined's Avatar
    Joined
    Mar 2010
    From
    Chicago
    Posts
    2,340
    Awards
    1
    Quote Originally Posted by matt.qmar View Post
    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.
    Follow Math Help Forum on Facebook and Google+

  7. #7
    MHF Contributor undefined's Avatar
    Joined
    Mar 2010
    From
    Chicago
    Posts
    2,340
    Awards
    1
    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.
    Follow Math Help Forum on Facebook and Google+

  8. #8
    Super Member
    Joined
    Apr 2009
    Posts
    678
    Thanks
    1
    (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
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Replies: 4
    Last Post: January 10th 2011, 09:51 AM
  2. Replies: 3
    Last Post: May 14th 2010, 11:04 PM
  3. Replies: 2
    Last Post: April 3rd 2010, 05:41 PM
  4. Replies: 0
    Last Post: November 13th 2009, 06:41 AM
  5. Prime Divisability
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: October 1st 2008, 07:41 PM

Search Tags


/mathhelpforum @mathhelpforum