1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Homework Help: Common Multiples Proof

  1. Feb 1, 2010 #1
    1. The problem statement, all variables and given/known data
    Let a,b and m be positive integers. If m is a common multiple of a and b and m divides ab, then ab/m is a common divisor of a and b.

    2. Relevant equations
    Definition: A common multiple of a and b is any integer divisible by both a and b.
    Definition: A common divisor of a and b is any integer that divides both a and b.

    3. The attempt at a solution
    1. Let a,b,m be positive integers. suppose m is a common multiple of a and b and m divides ab.
    2. By definition m does not equal 0, a divides m and b divides m so a and b both do not equal 0.
    3. There exist integers S,D such that m=aS and m=bD
    4. From (1) m divides ab so there exists an integer F such that ab=Fm
    5. ab=Fm=aSF and bDF
    6. ab/m=aSF/aS and bDF/bD, both Give F
    7. a and b are both divisible by F so ab/m is a common divisor of a and b.

    I believe I have an error between 6 and 7 because it seems as though I am jumping to conclusions about both being divisible by F.
    Thank you
  2. jcsd
  3. Feb 1, 2010 #2
    Step 7. Why are a and b divisible by F? From the previous step ab is divisible by F but, from this, you cannot say that a and b are also divisible by F.
  4. Feb 1, 2010 #3
    Therein lies my question of what should I do to correct step 7? I am not sure what to do. It is necessary to show that F divides both a and b right?
  5. Feb 1, 2010 #4
    But that is not possible in general. Try this instead: prove that ab divides ma and mb. What could you conclude from that?
  6. Feb 1, 2010 #5
    This just tells me that b divides m and that a divides m which is what I already know. I think I am reading what you asked incorrectly.
  7. Feb 1, 2010 #6
    If ab|ma, then ma = k(ab), which implies that a = k(ab/m) (why can we say that?); what does this mean? If you could prove the same thing about b, what can you conclude?
  8. Feb 1, 2010 #7
    Oh, so this says that a is divisible by (ab/m) and for b we would have mb=d(ab) so b=d(ab/m) so b is divisible by (ab/m) too. therefore (ab/m) is a common divisor of a and b. But how do we know that ab|ma? where does that come from?
  9. Feb 1, 2010 #8
    Look at your hypothesis: m is a common multiple of a and b; a trivially divides a. So what can you say about ma and ab?
  10. Feb 1, 2010 #9
    since b|m then ab|ma and since a|m then ab|mb. This leads to a is divisible by (ab/m) because ma=k(ab) and so on. I believe I finally got it?
  11. Feb 1, 2010 #10
    Yes. Don't forget to add that ab is divisible by m by hypothesis.
  12. Feb 1, 2010 #11
    Great. Thanks for all your time and patience! I really appreciate the help.
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook