1. Not finding help here? Sign up for a free 30min 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!

An LCM Problem

  1. May 13, 2008 #1
    [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. jcsd
  3. May 13, 2008 #2

    Dick

    User Avatar
    Science Advisor
    Homework Helper

    You could use unique prime factorization. Why don't you want to use n[(ab) / gcd(a,b)]?
     
  4. May 13, 2008 #3
    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.
     
  5. May 13, 2008 #4

    Dick

    User Avatar
    Science Advisor
    Homework Helper

    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?
     
  6. May 13, 2008 #5

    Vid

    User Avatar

    You can't assume the fundamental theorem of arithmetic...? o_O
     
  7. May 14, 2008 #6
    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
     
  8. May 14, 2008 #7

    Dick

    User Avatar
    Science Advisor
    Homework Helper

    The Fundamental Theorem of Arithmetic IS unique prime factorization. Try using it.
     
  9. May 14, 2008 #8
    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?
     
  10. May 14, 2008 #9

    Dick

    User Avatar
    Science Advisor
    Homework Helper

    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)?
     
  11. May 14, 2008 #10
    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.
     
  12. May 14, 2008 #11

    Dick

    User Avatar
    Science Advisor
    Homework Helper

    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?
     
  13. May 15, 2008 #12
    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?
     
  14. May 15, 2008 #13

    Dick

    User Avatar
    Science Advisor
    Homework Helper

    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.
     
  15. May 15, 2008 #14
    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.
     
  16. May 15, 2008 #15

    Dick

    User Avatar
    Science Advisor
    Homework Helper

    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.
     
  17. May 15, 2008 #16
    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?
     
  18. May 15, 2008 #17

    Dick

    User Avatar
    Science Advisor
    Homework Helper

    That sounds right.
     
  19. May 15, 2008 #18
    Thank's Dick, both for your help and your patience.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?



Similar Discussions: An LCM Problem
  1. GCD and LCM (Replies: 2)

  2. Lcm proof (Replies: 5)

  3. LCM is associative (Replies: 4)

Loading...