# Spring 2016, problem 10

Find all pairwise relatively prime positive integers $l, m, n$ such that $$(l+m+n)\left( \frac{1}{l}+\frac{1}{m}+\frac{1}{n}\right)$$ is an integer.

Beaker
5 years ago

Preface: Sorry I'm new and don't really understand the syntax of this system very well.

Proof First rewrite the the given expression:

(l + m + n)(lm + ln + nm)/lmn [Expression 1]

Note that this expression becomes an integer when the factors in the numerator of the expression [$(l+m+n)$ and $(lm + ln + nm)$], together or alone, contain all of the factors in the denominator l, m, and n.

#### There are five possible ways to obtain an integer from Expression 1:

Case 1. $l + m + n$ contributes all three factors l, m, and n.

That is,

$l + m + n = A(lmn)$ where A is a positive integer [Equation 1]

To satisfy this equation, $l + m + n > or = lmn$

Observe that this inequality only holds for the coprime triple $l=1, m=2, n=3$, which is a solution the the problem, and the set of triples where (without loss of generality) $l=m=1$ and $n=x$ where x is a postive integer .

Setting $l=m=1$ and $n=x$ in Equation 1 yields,

2 + x = Ax

or rewritten 2/x=(A-1).

A-1 is only allowed to be an integer when x=1 or 2 thus, $l=m=n=1$ and $l=m=1, n=2$ are also solutions to the problem.

It turns out the three solutions determined in case 1 are the only unique solutions, but we must check that the other cases do not yield additional solutions.

Case 2. $lm + ln + nm$ contributes all three factors. So,

$lm + ln + nm = B(lmn)$ where B is a postive integer [Equation 2]

rewrite as 1/l + 1/m + 1/n = B. Observe that this can only be true when $l=m=n=1$ because l, m, and n are coprime.

Case 3. $l + m + n$ contributes two factors--without loss of generality let these be l and m, and $lm + ln + nm$ contributes one factor, n.

So,

$l + m + n = C(lm)$ where C is a positive integer [Equation 3]

and

$lm + ln + nm = D(n)$ where D is a positive integer [Equation 4]

Note both equations must be true to provide solutions to the problem.

-Rewriting Equation 4 gives

lm/n + l + m = D since l, m, n are coprime n must be 1.

-Rewriting Equation 3 and setting n=1 yields,

$l + m + 1 = C(lm)$

applying the same logic as in case 1, we will obtain the same three possible solutions.

Case 4. l + m + n contributes one factor--without loss of generality let this be l, and $lm + ln + nm$ contributes two factors, m and n.

So,

$l + m + n = E(l)$ where E is a positive integer [Equation 5]

and

$lm + ln + nm = F(mn)$ where F is a positive integer [Equation 6]

-Rewritting Equation 6 gives us

l/n +l/m = F -1

observe that because n and m are coprime, n=m=1.

-Rewriting Equation 5 with n=m=1 yields

2/l = E -1

Thus $l=2$ or $l=1$.

Thus from case four we obtain two possible solutions, $n=m=l=1$ and $n=m=1,l=2$.

Case 5:Important: Case 3 and Case 4 assume that n, m, and l are prime or 1.

Thus, Case 5 must account for the possibility that any or all of l, m, and n are not prime or 1 but still coprime.

Preface b: I wish I could write this part more clearly.

let the factorization of l, m, and n be the following:

$l=a*b$

$m=c*d$

$n=e*f$

a, b, c, d, e, f are positive integers that are not necessarily prime. Let this set of integers be known as [X]. Since l, m, and n are coprime, the factors of each of these candidates are necessarily coprime with the factors of the others.

Consider that the numerator factor lm + ln + nm in Expression 1 contributes some subset of factors from [X] whose product is Y, while l + m + n contributes the remaining factors from [X] whose product is Z.

$lm + ln + nm = G(Y)$ where G is a positive integer [Equation 7]

$l + m + n = H(Z)$ where H is a positive integer [Equation 8]

Observe that all factors that make up Y in Equation 7 will be forced to take on a value of 1 by the arguments in Cases 2, 3, and 4.

This means that the remaining factors making up Z will revert to the factors l, m, and/or n allowing us to reduce this case to Case 1, 3 or 4. This means there are no additional solutions from Case 5.

Summary Altogether we have obtained three possible solutions: $n=m=l=1$; $l=m=1,n=2$; $l=1,m=2,n=3$

Nelix
5 years ago

Edit: Thanks to NickM and pkornya for pointing out a big mistake in in my original post, where I claimed to have proved, there was only one solution. Here's the edited and hopefully correct version:

The only possible choices are (up to reordering) [$l=m=n=1$], [$l = 3, m=2, n=1$] and [$l=2, m=1, n=1$].

Proof:

Suppose, the problem conditions are satisfied by numbers $l$, $m$, and $n$. Then there exists $r \in \mathbb{N}$, such that

$(l + m + n)(\frac{1}{l} + \frac{1}{m} + \frac{1}{n}) = r$. [Eq. 1]

Multiplying this by $lmn$, and rearranging, we get:

$l^2 m + l^2 n + lm^2 + ln^2 + mn(m + n)= (r - 3) lmn$ [Eq. 2]

Now let $p$ be a prime number and let $k$ be the greatest natural number (including zero), such that $p^k$ divides $l$. From [Eq. 2] it is obvious, that $p^k$ must divide (m + n). Since $p$ was an arbitrary prime, it follows, that $m + n$ is a multiple of $l$: There exists $\lambda \in \mathbb{N}$, such that

$m + n = \lambda l$. [Eq. 4]

Similiarly, we show, that:

$n + l = \mu m$ [Eq. 5]

$l + m = \nu n$ [Eq. 6]

Adding up all equations 4 through 6, we find that

$(\lambda - 2) l + (\mu - 2) m + (\nu - 2) n = 0$. [Eq. 7]

If all of $\lambda, \mu, \nu$ are no less than 2, then [Eq. 7] can only be true, if $\lambda = \mu = \nu = 2$. In this case, plugging back into the system of equations 4 to 6 yields: $l = m = n$. Therefore, since $l, m, n$ are pairwise coprime, $l = m = n = 1$.

In the remaining cases one of $\lambda, \mu, \nu$ is 1. Without loss of generality, say $\lambda = 1$. Plugging [Eq. 4] into [Eq. 5] and [Eq. 6] then gives:

$2n = (\mu - 1) m$ [Eq. 8]

$2m = (\nu - 1) n$

So $\mu \neq 1$ and $\nu \neq 1$. Two cases: Either $m = n = 1$, then $l = 2$ and we''re done. Or (without loss of generality) $m$ has a prime factor. Then this factor has to be 2 (from [Eq. 8], since $m$ and $n$ are coprime). So $m = 2$. Since $m$ and $n$ are coprime $n = 1$.

edit: In the last paragraph I should have used the lemma that $ab=cd$ with a and c coprime implies that a divides d for clarity. So by Eq. 8 m divides 2.

Therefore $l = 3$ and we're done.

There's a mistake in this proof in the part where you claim that none of the numbers $\lambda$, $\mu$, and $\nu$ can be equal to $1$. In this case from your Equation 1, it follows not that $\frac{l}{m}+\frac{l}{l-m}$ is an integer but that $\frac{2l}{m}+\frac{2l}{l-m}$ is an integer from which you cannot conclude what you want. Indeed, one can construct (very simple) examples where one of $\lambda$, $\mu$, and $\nu$ is actually $1$.

NickM 5 years ago

${\rm{Counterexample: }}l = 1,m = 2,n = 3{\rm{ works}}$

pkornya 5 years ago

This means that the remaining factors making up Z will revert to the factors l, m, and/or n allowing us to reduce this case to Case 1, 3 or 4. This means there are no additional solutions from Case 5.

cindyssdzp7 1 month ago