# Homework Help: Common Multiples Proof

1. Feb 1, 2010

### scottstapp

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. Feb 1, 2010

### JSuarez

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.

3. Feb 1, 2010

### scottstapp

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?

4. Feb 1, 2010

### JSuarez

But that is not possible in general. Try this instead: prove that ab divides ma and mb. What could you conclude from that?

5. Feb 1, 2010

### scottstapp

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.

6. Feb 1, 2010

### JSuarez

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?

7. Feb 1, 2010

### scottstapp

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?

8. Feb 1, 2010

### JSuarez

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?

9. Feb 1, 2010

### scottstapp

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?

10. Feb 1, 2010

### JSuarez

Yes. Don't forget to add that ab is divisible by m by hypothesis.

11. Feb 1, 2010

### scottstapp

Great. Thanks for all your time and patience! I really appreciate the help.