Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Hard? least common multiple problem

  1. Sep 10, 2008 #1
    I'm trying to prove or disprove the following:

    Let a_1, ..., a_n be natural numbers such that the least common multiple of EVERY n-1 of them is equal to lcm(a_1, ..., a_n) = m. Is it true that a_i = m for some i?

    The method I've tried so far is to build systems of equations using the information known to prove it in the positive, but it gets very messy. I've also had no luck finding a counter example.

    n=2 is easy (it's true), but the method doesn't generalize.

    Thanks in advance.
  2. jcsd
  3. Sep 10, 2008 #2
    Try it for a few more n's and do you see a pattern?
  4. Sep 10, 2008 #3
    Consider n=3: (a,b,c), and let's try to find a counterexample. Let d=gcd(a,b), e=gcd(b,c), f=gcd(a,c). Clearly we must have d,e,f>1 or one would be the lcm of the other two. Let's assume that (d,e,f)=1 for simplicity. The simplest way to construct a triple would be (df,de,ef). Then:
    lcm(df,de)=lcm(de,ef)=lcm(df,ef)=lcm(df,ef,de)=def=m > a,b,c. Or a more concrete example: (6,10,15) then the lcm = 30.
  5. Sep 11, 2008 #4
    Many thanks. Yes, silly of me not to spot this sooner. Actually I'm trying to solve a more general problem and this would have been a sufficient condition if it were true. My post in the algebra section has the details.
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?

Similar Discussions: Hard? least common multiple problem
  1. Hard Sequence problem (Replies: 4)

  2. Least Common Multiple (Replies: 4)