Proving s is a Multiple of m in LCM Problem

[e(ho0n3]

[SOLVED] An LCM Problem

Homework Statement
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?

 

[Dick]

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

 

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

 

[Dick]

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.

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?

 

[Vid]

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

 

[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

 

[Dick]

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 Fundamental Theorem of Arithmetic IS unique prime factorization. Try using it.

 

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

 

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

 

[e(ho0n3]

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).

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?

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

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

 

[Dick]

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.

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?

 

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

 

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

 

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

 

[Dick]

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.

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.

 

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

 

[Dick]

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?

That sounds right.

 

[e(ho0n3]

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