# An LCM Problem

1. May 13, 2008

### e(ho0n3

[SOLVED] An LCM Problem

The problem statement, all variables and given/known data
Let a and b be positive integers and let m = lcm(a,b). If s is a multiple of both a and b, prove that s is a multiple of m.

The attempt at a solution
I want to do this without the fact that all multiples of a and b have the form n[(ab) / gcd(a,b)]. This seems impossible. Any tips?

2. May 13, 2008

### Dick

You could use unique prime factorization. Why don't you want to use n[(ab) / gcd(a,b)]?

3. May 13, 2008

### e(ho0n3

Because it's not assumed. I guess I'm stuck: to solve the problem I will either have to derive that property or the prime factorization one.

4. May 13, 2008

### Dick

So what properties of the integers DO you have that could be relevant to this? I'm guessing you at least know they are a ring. What else?

5. May 13, 2008

### Vid

You can't assume the fundamental theorem of arithmetic...?

6. May 14, 2008

### e(ho0n3

Here's what I can use:

- Well Ordering Principle
- Division Algorithm
- GCD Is a Linear Combination
- Euclid's Lemma p | ab implies p | a or p | b
- Fundamental Theorem of Arithmetic

7. May 14, 2008

### Dick

The Fundamental Theorem of Arithmetic IS unique prime factorization. Try using it.

8. May 14, 2008

### e(ho0n3

The prof. went over the proof in class. All one needs is the division algorithm. I had embarked along similar lines but failed to take the final step. Sigh...

Using FToA:

Since both m and s are multiples of a and b, there are integers x, x', y, y' such that m = ax = bx' and s = ay = by'. Factor x, x', y, y' into primes.

If x and y share no primes in common, they are relatively prime, which means that a = 1 since x = m/a and y = s/a. Similarly if x' and y' share no primes, then b = 1. Since m = lcm(a,b) = lcm(1,1), m = 1. s is a multiple of 1 and so s is a multiple of m.

If x and y share some primes, whose product I will denote z, then gcd(x,y) = z. Since x < y, z ≤ x. Suppose z < x. Then az < ax which is impossible because then az < ax = m = lcm(a,b). Therefore z = x, y is a multiple of x and consequently s is a multiple of m.

Is this correct?

9. May 14, 2008

### Dick

I think you are making it too complicated. If p is a prime and the power of p occurring in the prime factorization of a is n_a, and in that of b is n_b, then the power of p occurring in the prime factorization of lcm(a,b) is max(n_a,n_b). Can you show if s is a multiple of a and b, then the power of p occurring in the prime factorization of s is >=max(n_a,n_b)?

10. May 14, 2008

### e(ho0n3

If that is true, it's not straight-forward. Suppose $n_a = \max(n_a,n_b)$ and let lcm(a,b) = ax. If x contains p, then the lcm(a,b) will have a power of p greater than $n_a$. How do you get around this?

I suspect this has to do with the answer to my previous question.

11. May 14, 2008

### Dick

If your 'suppose' part is true then x can't contain any powers of p. Look, any multiple of a has to contain at LEAST as many factors of p as a. Ditto for b. Now lcm(a,b) is a multiple of both, so it has to contain at LEAST as many as each of a or b. Further it's the LEAST common multiple, so it shouldn't contain any more factors of p than it absolutely needs. Hence, how many does it contain?

12. May 15, 2008

### e(ho0n3

I understand. Since s ≥ m, the prime factorization of s may have more p's than that of m. What's the next step? Should I shrink s by dividing it by p, recursively for every p in the prime factorizations of both a and b until the prime factorizations of s and m have the same number of p's?

13. May 15, 2008

### Dick

Sure. Then when your are done 'shrinking' by pulling the extra prime factors out, you've shown s is a multiple of m. It's m times the extra prime factors.

14. May 15, 2008

### e(ho0n3

I'm unconvinced. How do you know, after 'shrinking' s, that s is a multiple of m? It could be that m equals ap for some prime p and s, after shrinking, equals aq for some prime q not equal to p.

15. May 15, 2008

### Dick

You have to do it for ALL prime factors of the lcm. Pick some example integers and convince yourself that EVERY prime factor of the lcm has an exponent of max(n_a,n_b) for that prime and any other common multiple has one or more extra prime factors, making it a multiple of the lcm.

16. May 15, 2008

### e(ho0n3

It just dawned on me after rereading post #9: For each prime factor p of m, if the prime factorization of s contains just as many p's as the prime factorization of m, then obviously s is a multiple of m.

There are $\max(n_a,n_b)$ prime factors p in m for otherwise I would be able to find a smaller common multiple of a and b than m, which is not possible.

And since s is a multiple of both a and b, then the prime factorization of s contains at least the same number of p's as that of m, for each prime factor p in m.

Correct?

17. May 15, 2008

### Dick

That sounds right.

18. May 15, 2008