# Thread: Number Theory - LCM Problem

1. ## Number Theory - LCM Problem

Find all triples $\displaystyle (a,b,c)$ of integers such that $\displaystyle \text{LCM}(a,b,c) = a+b+c$. Note: permutations of $\displaystyle (a,b,c)$ such as $\displaystyle (a,c,b), (b,a,c), (b,c,a), (c,a,b)$ and $\displaystyle (c,b,a)$ need only be represented once by $\displaystyle (a,b,c)$.

2. ## 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. $\displaystyle \text{LCM}(a,b,c) = \text{LCM}(|a|,|b|,|c|)$
2. $\displaystyle \text{LCM}(a,b,c) = 0$ if at least one of $\displaystyle 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).

3. ## 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.

4. ## Re: Number Theory - LCM Problem

Originally Posted by Hartlw
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

$\displaystyle LCM(0,0,0) = 0 = 0+0+0$, true
$\displaystyle 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:

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

Hence, any solution where $\displaystyle a,b,c$ are all positive must be a multiple of some solution $\displaystyle (a',b',c')$ where all three are pairwise coprime. But then $\displaystyle \text{LCM}(a',b',c') = a'+b'+c' = a'b'c'$. Since $\displaystyle a\le b\le c$, it must be that $\displaystyle a'\le b'\le c'$. Since these numbers are pairwise coprime, we can only have equality if $\displaystyle a'=b'=1$ or $\displaystyle a'=b'=c'=1$. Since $\displaystyle \text{LCM}(1,1,c) = c \neq 1+1+c = c+2$, it cannot be that $\displaystyle a'=b'=1$. Hence, $\displaystyle a' < b' < c'$, so $\displaystyle a'+b'+c' < 3c'$. Then $\displaystyle a'b'c' = a'+b'+c' < 3c' \Rightarrow a'b' < 3$. Since $\displaystyle a'b' \neq 1$, it must be $\displaystyle a'b' = 2$, so $\displaystyle a'=1,b'=2$. Then $\displaystyle 2c' = 1+2+c'$ implies $\displaystyle c'=3$. Hence, the only solution with all three numbers positive and coprime is $\displaystyle (1,2,3)$, so the set of all solutions with all three numbers positive is $\displaystyle \{(m,2m,3m)\mid m\in \mathbb{Z}, m>0\}$. Since $\displaystyle (0,0,0)$ is a solution, we can include $\displaystyle m=0$.

5. ## 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?

6. ## Re: Number Theory - LCM Problem

Originally Posted by Hartlw
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 $\displaystyle \text{LCM}(1,0,0)=0 \neq 1$. This is because zero does NOT divide 1, but 1 DOES divide zero. So, $\displaystyle a$ is NOT a multiple of $\displaystyle 0$ unless $\displaystyle a=0$. The set of all multiples of zero is $\displaystyle \{m\cdot 0\mid m\in \mathbb{Z}\} = \{0\}$. Additionally, I added a proof for when $\displaystyle 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.

7. ## 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·2·3 = 1+2+3
LCM(m1,m2,m3) = m(1·2·3) = m1+m2+m3

LCM(-1,1,n) = (-1)(1)(n) = -1+1+n (n and –n are CM’s)
LCM(-m,m,mn) = m(-1)(1)(n) = -m+m+mn

I couldn’t come up with conditions for abc to be LCM, or uniqueness. I think it’s in “spoiler,” I’ll 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’t see any point in “seeing” 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?

8. ## 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 $\displaystyle q$ be a prime power (a positive prime number taken to some positive integral power). Let $\displaystyle M$ be an $\displaystyle r \times r$ invertible matrix over $\displaystyle \Bbb{F}_q$. Let $\displaystyle n$ be the smallest nonnegative integer such that $\displaystyle M^n$ is the identity matrix. If $\displaystyle n>0$ and $\displaystyle M$ is irreducible, then $\displaystyle n$ divides $\displaystyle q^r-1$, but $\displaystyle n$ does not divide $\displaystyle q^k-1$ for any $\displaystyle 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 $\displaystyle M$ is an $\displaystyle r\times r$ invertible matrix over $\displaystyle \Bbb{F}_q$ with multiplicative order $\displaystyle n$ such that $\displaystyle n$ divides $\displaystyle q^r-1$ but it does not divide $\displaystyle q^k-1$ for any $\displaystyle k<r$, is it possible that $\displaystyle M$ is reducible? It turns out that this can occur.

How do you construct an invertible matrix $\displaystyle 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, $\displaystyle M$ is an $\displaystyle r\times r$ matrix where $\displaystyle r=a+b+c$. Now how can we make it so that the order of $\displaystyle M$ divides $\displaystyle q^r - 1$, but does not divide $\displaystyle q^k - 1$ for $\displaystyle k < r$? Well the order of $\displaystyle M$ is the LCM of the orders of the blocks on the diagonal. We know from the theorem that the blocks have orders dividing $\displaystyle q^a - 1$, $\displaystyle q^b - 1$, and $\displaystyle q^c - 1$ respectively, and no lower powers. Now if $\displaystyle m$ is the multiplicative order of the block of rank $\displaystyle a$, then $\displaystyle m$ divides $\displaystyle q^a - 1$ and $\displaystyle a$ is the smallest such power, then $\displaystyle m$ can only divide $\displaystyle q^t - 1$ where $\displaystyle t$ is a multiple of $\displaystyle a$. So this will only work for triples $\displaystyle a,b,c$ so that $\displaystyle a+b+c = \text{LCM}(a,b,c)$.

I found it an enjoyable challenge for a few hours to find all possible integers $\displaystyle a,b,c$ such that $\displaystyle \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 $\displaystyle (a,b,c,d)$ so that $\displaystyle \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.

9. ## 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.