Homework Help: An LCM Problem

[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?

 

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.

 

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

 

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?

 

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

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

 

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?

 

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.

 

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 [itex]\max(n_a,n_b)[/itex] 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?

 

Thank's Dick, both for your help and your patience.