Results 1 to 9 of 9
Like Tree3Thanks
  • 1 Post By SlipEternal
  • 1 Post By SlipEternal
  • 1 Post By SlipEternal

Math Help - Number Theory - LCM Problem

  1. #1
    MHF Contributor
    Joined
    Nov 2010
    Posts
    1,845
    Thanks
    715

    Number Theory - LCM Problem

    Find all triples (a,b,c) of integers such that \text{LCM}(a,b,c) = a+b+c. Note: permutations of (a,b,c) such as (a,c,b), (b,a,c), (b,c,a), (c,a,b) and (c,b,a) need only be represented once by (a,b,c).
    Last edited by SlipEternal; June 3rd 2014 at 08:34 AM.
    Thanks from topsquark
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    Joined
    Nov 2010
    Posts
    1,845
    Thanks
    715

    Re: Number Theory - LCM Problem

    By the way, in case anyone is not sure how to handle LCM when one or more of the integers are not positive, assume the following:

    1. \text{LCM}(a,b,c) = \text{LCM}(|a|,|b|,|c|)
    2. \text{LCM}(a,b,c) = 0 if at least one of a,b,c is zero.

    Otherwise, LCM is well-understood for positive integers.

    (Also, please post answers in spoilers so as not to give it away for anyone else who may want to work on it).
    Last edited by SlipEternal; June 3rd 2014 at 09:41 AM.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Banned
    Joined
    Aug 2010
    Posts
    961
    Thanks
    98

    Re: Number Theory - LCM Problem

    LCM(a,b,c) = a+b+c
    From the definitions:
    e is a CM of a,b,c if r,s,t exist such that e=ra=sb=st
    (a+b+c)le, solve for a,b,c. Can't do.

    However, by inspection (a,b,c) = (a,0,0) satisfies LCM(a,b,c) = a+b+c

    EDIT What's a spoiler? Anyhow, this is probably not the only answer.
    Last edited by Hartlw; June 3rd 2014 at 01:53 PM.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor
    Joined
    Nov 2010
    Posts
    1,845
    Thanks
    715

    Re: Number Theory - LCM Problem

    Quote Originally Posted by Hartlw View Post
    LCM(a,b,c) = a+b+c
    From the definitions:
    e is a CM of a,b,c if r,s,t exist such that e=ra=sb=st
    (a+b+c)le, solve for a,b,c. Can't do.

    However, by inspection (a,b,c) = (a,0,0) satisfies LCM(a,b,c) = a+b+c

    EDIT What's a spoiler? Anyhow, this is probably not the only answer.
    I'm not quite sure what you mean

    LCM(0,0,0) = 0 = 0+0+0, true
    LCM(a,0,0) = 0 \neq a+0+0 in general

    Example: LCM(1,0,0) - Wolfram|Alpha

    So, I'm not sure what you mean...

    As for a spoiler, that is text that is put in [spoiler][/spoiler] tags. For example, here is the solution:

    Spoiler:
    Any solutions is either in the following set, or is some permutation of an element in this set:

    \{(m,2m,3m) \mid m\in \mathbb{Z}, m\ge 0\}\cup \{(-m,m,mn) \mid m,n\in \mathbb{Z}, m>0, n\ge 0\}

    It is a little tricky to prove that these are the only solutions, though.

    Here is a sketch of a proof that if 0<a\le b\le c, where \text{LCM}(a,b,c) = a+b+c, then (a,b,c) = (a,2a,3a):
    Suppose 0 < a \le b \le c and \text{LCM}(a,b,c) = a+b+c. Then suppose m divides any two of the numbers. Without loss of generality, assume m | a and m | b. Then since a | \text{LCM}(a,b,c), we know m | \text{LCM}(a,b,c). But then since m divides both a,b, we have some integer j such that a+b = mj. Then m | \text{LCM}(a,b,c) = a+b+c = mj+c implies m | c. Hence, if a number divides two of the numbers, it must also divide the third.

    Hence, any solution where a,b,c are all positive must be a multiple of some solution (a',b',c') where all three are pairwise coprime. But then \text{LCM}(a',b',c') = a'+b'+c' = a'b'c'. Since a\le b\le c, it must be that a'\le b'\le c'. Since these numbers are pairwise coprime, we can only have equality if a'=b'=1 or a'=b'=c'=1. Since \text{LCM}(1,1,c) = c \neq 1+1+c = c+2, it cannot be that a'=b'=1. Hence, a' < b' < c', so a'+b'+c' < 3c'. Then a'b'c' = a'+b'+c' < 3c' \Rightarrow a'b' < 3. Since a'b' \neq 1, it must be a'b' = 2, so a'=1,b'=2. Then 2c' = 1+2+c' implies c'=3. Hence, the only solution with all three numbers positive and coprime is (1,2,3), so the set of all solutions with all three numbers positive is \{(m,2m,3m)\mid m\in \mathbb{Z}, m>0\}. Since (0,0,0) is a solution, we can include m=0.
    Last edited by SlipEternal; June 3rd 2014 at 03:09 PM.
    Thanks from topsquark
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Banned
    Joined
    Aug 2010
    Posts
    961
    Thanks
    98

    Re: Number Theory - LCM Problem

    LCM(a,0,0)=a = a+b+c which divides all CM of (a,0,0).

    As for the "spoiler," Personally, I find an underived answer totally uninteresting and annoying. What's the point? What do you learn other than that somebody either derived it or "saw" it?
    Follow Math Help Forum on Facebook and Google+

  6. #6
    MHF Contributor
    Joined
    Nov 2010
    Posts
    1,845
    Thanks
    715

    Re: Number Theory - LCM Problem

    Quote Originally Posted by Hartlw View Post
    LCM(a,0,0)=a = a+b+c which divides all CM of (a,0,0).

    As for the "spoiler," Personally, I find an underived answer totally uninteresting and annoying. What's the point? What do you learn other than that somebody either derived it or "saw" it?
    You clearly did not read post #2 nor did you click on the link to Wolframalpha where it shows \text{LCM}(1,0,0)=0 \neq 1. This is because zero does NOT divide 1, but 1 DOES divide zero. So, a is NOT a multiple of 0 unless a=0. The set of all multiples of zero is \{m\cdot 0\mid m\in \mathbb{Z}\} = \{0\}. Additionally, I added a proof for when a,b,c are all positive (check the spoiler above). I posted this problem in the Math Challenge Problems forum, so even though I gave the solution in a spoiler tag in case someone wanted to see the answer, one should expect the challenge to be deriving the solution for his/herself. If you find underived answers "totally uninteresting and annoying", then this may not be the forum for you.
    Last edited by SlipEternal; June 3rd 2014 at 03:13 PM.
    Follow Math Help Forum on Facebook and Google+

  7. #7
    Banned
    Joined
    Aug 2010
    Posts
    961
    Thanks
    98

    Re: Number Theory - LCM problem

    ref: Number Theory - LCM Problem

    Wasn't able to reply to thread so I'm doing it this way.

    a is not a CM of (a,0,0). Don't know what I was thinking. Sorry

    abc is a Common Multiple, CM, of (a,b,c).
    If abc is LCM and a+b+c = abc, then a+b+c is LCM.

    Examples:
    LCM(1,2,3) =1򈭿 = 1+2+3
    LCM(m1,m2,m3) = m(1򈭿) = m1+m2+m3

    LCM(-1,1,n) = (-1)(1)(n) = -1+1+n (n and 杗 are CM抯)
    LCM(-m,m,mn) = m(-1)(1)(n) = -m+m+mn

    I couldn抰 come up with conditions for abc to be LCM, or uniqueness. I think it抯 in 搒poiler, I抣l have to give it another try. When is CM abc LCM is an interesting question and would make the post worthwhile (educational). Personally, I don抰 see any point in 搒eeing an answer out of the clear blue sky. Not my idea of fun.

    For example: solve x^3+y^3 +z^3 =54371. Wasted a few hours? OK. The answer is:
    (x,y,z)=37,15,7
    How did I get it? I calculated 373 + 153 + 73.

    Do you really think someone else figured out the OP cold?
    Follow Math Help Forum on Facebook and Google+

  8. #8
    MHF Contributor
    Joined
    Nov 2010
    Posts
    1,845
    Thanks
    715

    Re: Number Theory - LCM Problem

    In case anyone is interested, the motivation behind this problem came from Linear Algebra. Specifically, it came from looking for counterexamples to the converse of the following theorem:

    Theorem: Let q be a prime power (a positive prime number taken to some positive integral power). Let M be an r \times r invertible matrix over \Bbb{F}_q. Let n be the smallest nonnegative integer such that M^n is the identity matrix. If n>0 and M is irreducible, then n divides q^r-1, but n does not divide q^k-1 for any k<r.

    The theorem has been around for a long time, so I'm sure you can find its proof somewhere. It is actually a really cool proof. But I digress.

    If M is an r\times r invertible matrix over \Bbb{F}_q with multiplicative order n such that n divides q^r-1 but it does not divide q^k-1 for any k<r, is it possible that M is reducible? It turns out that this can occur.

    How do you construct an invertible matrix M that is reducible? Well the natural way is to put blocks of invertible matrices going down the diagonal (in fact all matrices can be put into this form, as this is the rational canonical form). Suppose we just look at reducible matrices that decompose into 3 irreducible blocks down the diagonal. Suppose the dimensions of the blocks are a,b, and c. So, M is an r\times r matrix where r=a+b+c. Now how can we make it so that the order of M divides q^r - 1, but does not divide q^k - 1 for k < r? Well the order of M is the LCM of the orders of the blocks on the diagonal. We know from the theorem that the blocks have orders dividing q^a - 1, q^b - 1, and q^c - 1 respectively, and no lower powers. Now if m is the multiplicative order of the block of rank a, then m divides q^a - 1 and a is the smallest such power, then m can only divide q^t - 1 where t is a multiple of a. So this will only work for triples a,b,c so that a+b+c = \text{LCM}(a,b,c).

    I found it an enjoyable challenge for a few hours to find all possible integers a,b,c such that \text{LCM}(a,b,c)=a+b+c, so I thought it would make a good Math Challenge Problem for others on the forum. When I first posted it, the actual motivation behind the problem seemed like it would take longer to explain than the problem itself, and really did not offer anything towards solving it, which is why I omitted it originally. Since others have commented that the problem seems to be pointless, I decided to share its origin.

    For anyone who does find this interesting, finding all 4-tuples (a,b,c,d) so that \text{LCM}(a,b,c,d) = a+b+c+d, is a fairly intractable problem. Looking for solutions over the positive integers, I can show that for any tuple with greater than 3 elements, if the LCM equals its sum, then it cannot be that they are all pairwise coprime. So, at least 2 of the integers must share a common factor (greater than 1). Beyond that, I have been unable to really reduce the problem to something simpler than testing it case-by-case.
    Last edited by SlipEternal; June 4th 2014 at 08:23 AM.
    Thanks from topsquark
    Follow Math Help Forum on Facebook and Google+

  9. #9
    Banned
    Joined
    Aug 2010
    Posts
    961
    Thanks
    98

    Re: Number Theory - LCM problem

    With regard to last post of referenced thread (Number Theory - LCM Problem), which I can't access,

    I personally had no problem with the question, just the clear-blue-sky "solution." To the extent that an intelligible solution is possble, I believe it is given in OP of this extended thread.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Number theory
    Posted in the Algebra Forum
    Replies: 1
    Last Post: September 26th 2012, 11:52 PM
  2. Using group theory to prove results in number theory
    Posted in the Math Philosophy Forum
    Replies: 6
    Last Post: May 12th 2012, 01:34 AM
  3. Textbooks on Galois Theory and Algebraic Number Theory
    Posted in the Advanced Algebra Forum
    Replies: 3
    Last Post: July 8th 2011, 06:09 PM
  4. Replies: 2
    Last Post: December 18th 2008, 05:28 PM
  5. Number theory, prime number
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: September 17th 2006, 08:11 PM

Search Tags


/mathhelpforum @mathhelpforum