Loading [MathJax]/jax/output/CommonHTML/jax.js

Spring 2016, problem 10

Find all pairwise relatively prime positive integers l,m,n such that (l+m+n)(1l+1m+1n) is an integer.

Comments

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=ab

m=cd

n=ef

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 rN, such that

(l+m+n)(1l+1m+1n)=r. [Eq. 1]

Multiplying this by lmn, and rearranging, we get:

l2m+l2n+lm2+ln2+mn(m+n)=(r3)lmn [Eq. 2]

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

m+n=λl. [Eq. 4]

Similiarly, we show, that:

n+l=μm [Eq. 5]

l+m=νn [Eq. 6]

Adding up all equations 4 through 6, we find that

(λ2)l+(μ2)m+(ν2)n=0. [Eq. 7]

If all of λ,μ,ν are no less than 2, then [Eq. 7] can only be true, if λ=μ=ν=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 λ,μ,ν is 1. Without loss of generality, say λ=1. Plugging [Eq. 4] into [Eq. 5] and [Eq. 6] then gives:

2n=(μ1)m [Eq. 8]

2m=(ν1)n

So μ1 and ν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 λ, μ, and ν can be equal to 1. In this case from your Equation 1, it follows not that lm+llm is an integer but that 2lm+2llm is an integer from which you cannot conclude what you want. Indeed, one can construct (very simple) examples where one of λ, μ, and ν is actually 1.

NickM 5 years ago

Counterexample:l=1,m=2,n=3works

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