Proving Infinitely Many Pairs of Positive Integers for Sum Equation

[Sam_]

Show that there are infinitely many pairs of positive integers (m, n) such that

(m + 1) / n + (n + 1) / m

is a positive integer.

 

[sennyk]

The first thing I would do is to find a few values for m and n that do work (via inspection). Then I'd try to find a relationship between those values. Once you can find n in terms of m (or vice versa), then you can show that the expression must be an integer, given that the inputs are integers.

Never mind my suggestion. It is much easier said than done. This is extremely difficult.

 

[robert Ihnot]

Firstly, by (m,n), I take it he means (m,n) =1, which is to say, they are relatively prime.
A trivial solution is m=n=1.

Given (m+1)/n + (n+1)/m =I, we have the modular equation m^2+m+n^2+n ==0 Mod mn

From this, m,n being relatively prime, we get n^2+n ==0 Mod m, reducing to n+1 ==0 Mod m, and similarly for n.

At this point we can-arbitrarily-assume that n is the larger, while we have:

$$m\geq n+1; n\geq m+1$$

Thus we take n=m+1. The equation now is m+1/(m+1) + (m+2)/m = I, which gives that m divides 2. Thus m=1 n=2, or m=2; n=3.

So all solutions are 2/2 + 3/1 =4; and 3/3 +4/2=3. Which is not infinite solutions for (m,n)=1.

 

[sennyk]

There is also one more solution

(2, 2) is a valid solution. I keep thinking that there are more solutions, but I can't find any by inspection. I have found the following solutions, (1, 1), (1, 2), (2, 1), (2, 2), (2, 3), (3, 2). I can't find any others, but I can't seem to prove that either.

 

[robert Ihnot]

sennyk: (2, 2) is a valid solution.

It is true I overlooked (2,2), thinking only of relatively prime solutions. As far as which one, m or n, is larger, that was purely arbitrary, so either (both) way(s) is correct.

 

[sennyk]

I'm not sure that your proof covers it all

Wouldn't you have to prove that ((m+1) mod n)/n + (n+1)/m cannot be equal to 1? (assuming that m > n + 1).

 

[sennyk]

I think I've got it.

Wouldn't you have to prove that [(m+1) mod n]/n + (n+1)/m cannot be equal to 1? (assuming that m > n + 1).

I think that I have proven that this doesn't have infinite solutions. I think I have proven that it only has 6 unique solutions.

(m + 1)mod n will be a constant between 0 and n - 1. We'll just call that "a".
Let's restrict m & n to both be > 3, because we have found all solution less than 4.

a/n + (n + 1)/m = 1 If this is possible (for a positive integer a, m, and n) then we can have infinite solutions.

ma + n(n + 1) = mn
n(n + 1) - mn = -ma
n(n + 1 - m) = -ma
n + 1 - m = -ma/n
m - (n + 1) = ma/n We will use this as a basis for the rest

since a is not a multiple of n, m must be a multiple of n

let m = cn

cn - (n + 1) = ca

cn - ca = n + 1
c(n - a) = n + 1
c = (n + 1)/(n - a)

now we just have to find the values of a that will allow (n + 1)/(n - a) to be an integer.
a can be n - 1, n - 2, ... 0

since n > 3, (we can find (analytically) all solutions where n is 1, 2, or 3), we can show that the expression
(n+1)/(n-a) is less than 2 and greater than 1, therefore, there are not infinite solutions.

we know that a < n, therefore
lim n->infinity (n+1)/(n-a) = 1
for n = 4 we have 5/(4 - a), for values of a that are not equal to n - 1, this will never be an integer.

Now we're left with proving that a cannot be = n - 1, for n in the domain of [4, infinity).

We know that m is a multiple of n. We know that m > n + 1; the original equation was
(m + 1)/n + (n + 1)/m

(cn + 1)/n + (n + 1)/(cn)

We are only interested in the first term. We can show that the first term cannot have a remainder of n - 1, n > 3.
(cn + 1)/n = c + 1/n. Since m is a multiple of n, the remainder cannot be n - 1, n > 3. It is always 1.

Thus there are no solutions when n > 4 or m for that matter.

Does this proof make sense? Someone with a pure math background, please check my work. This problem is very very very interesting.

 

[robert Ihnot]

sennyk:Wouldn't you have to prove that [(m+1) mod n]/n + (n+1)/m cannot be equal to 1? (assuming that m > n + 1).

Actually the equation was (m+1)/n + (n+1)/m = I, where "I" represents integer. Furthermore you use those brackets[..] suggestive of Greatest Integer In, but anyway, i do now see what you mean, but you are just starting over on the problem.

You write:
"m - (n + 1) = ma/n We will use this as a basis for the rest."

And, "since a is not a multiple of n, m must be a multiple of n,"

a, you say, is equal to (m+1) modulo n. well, what if a+1 = n? (Which is pretty much the kind of cases we have been looking at.) Anyway, if m is a multiple of n that definitively changes the problem to something easier, but we have another problem, n might have factors split between a and m.

 

[sennyk]

sennyk:Wouldn't you have to prove that [(m+1) mod n]/n + (n+1)/m cannot be equal to 1? (assuming that m > n + 1).

Actually the equation was (m+1)/n + (n+1)/m = I, where "I" represents integer. Furthermore you use those brackets[..] suggestive of Greatest Integer In, but anyway, I can't see how you got such an equation.

The brackets don't mean the floor or any step function.

If m > n + 1, that means that (n + 1)/m is less than 1, so the remainder of (m + 1)/n plus (n + 1)/m must be equal to 1 if the entire expression evaluates to an integer.

 

[sennyk]

While refining my proof, I found other solutions (2, 6), (3, 6), (6, 2), (6, 3).

I have the full proof. There are only 10 solutions to this, not an infinite number. I'll latex it some time tonight when I get home.

 

[d_leet]

Firstly, by (m,n), I take it he means (m,n) =1, which is to say, they are relatively prime.

Why do you take it to mean that, he never says anything that implies that at all. He talks about pairs of integers (m,n) so (m,n) is nothing more than a pair of numbers.

 

[robert Ihnot]

Why do you take it to mean that, he never says anything that implies that at all. He talks about pairs of integers (m,n) so (m,n) is nothing more than a pair of numbers.

O.K., that's right. I just thought he could have written m,n and generally when they write (m,n) they mean the common factor(?), or maybe they mean points on a graph, or maybe not.

Anyway, I think I solved it for (m,n)=1. I thought I got somewhere using that restriction.

 

[sennyk]

Split factors

n might have factors split between a and m.

I take that into account in my revised proof; If my algebra didn't fail me, I can show that m must be a multiple of n.

Ken

 

[robert Ihnot]

sennyk: I take that into account in my revised proof; If my algebra didn't fail me, I can show that m must be a multiple of n.

If so, that's an important improvement.

Also, while its great you found more solutions, you have to clear up this point as well: "since n > 3, (we can find (analytically) all solutions where n is 1, 2, or 3), we can show that the expression..." Are you attempting to use the fact that n>3 ?

 

[robert Ihnot]

Now as far as the case of a and the multiple ma giving (ma+1)/a + (a+1)/ma , we can reduce this to:

1/a + (a+1)/ma =(m+a+1)/ma. If we restrict this such that m>3, a>3, then we have to solve, m+a+1 equal to ma, or greater multiple of ma. So at the least this is m+a+1 = ma, or a+1 =m(a-1). If a was 4, this gives 5=3m or greater, but m exceeds 3. Similarly for greater values of a, so those cases are taken care of.

But this does not take care of the case where n=ca, m=cb, (a,b)=1, and c is a common factor greater than 1.

 

[sennyk]

Here goes...

$$m \in N^*$$

$$n \in N^*$$

$$\frac{m+1}{n}+\frac{n+1}{m} \in N^*$$

case m = n:

$$\frac{n+1}{n}+\frac{n+1}{n} \in N^*$$

$$1+\frac{1}{n}+1+\frac{1}{n} \in N^*$$

$$2+\frac{2}{n} \in Z$$

From this, n can only be 1 or 2.
Therefore, the only solutions for m = n are (1, 1), and (2, 2)

case m = n + 1

$$\frac{n+1+1}{n}+\frac{n+1}{n+1} \in N^*$$

$$1+\frac{2}{n}+1 \in N^*$$

$$2+\frac{2}{n} \in N^*$$

From this, n can only be 1 or 2.
Therefore, the only solutions for m = n + 1 are (2, 1) and (3, 2).
And the only solutions for n = m + 1 are (1, 2) and (2, 3).

case m > n + 1

$$a= (m + 1) mod(n)$$

$$\frac{a}{n} + \frac{n+1}{m} = 1$$

$$ma + n(n+1) = mn$$

$$n(n+1) = mn - ma$$

$$n(n+1) = mn - ma$$

$$\frac{n(n+1)}{n-a} = m$$

This tells us that m has to be a multiple of n.

$$m = cn$$

If m is a multiple of n, then a has to be 1.

$$\frac{1}{n} + \frac{n+1}{cn} = 1$$

$$c + n + 1 = cn$$

$$n + 1 = cn - c$$

$$\frac{n + 1}{n - 1} = c$$

For n = 1; c is undefined.
For n = 2; c is 3; m is 6.
For n = 3; c is 2; m is 6.

Now we can prove that no other c's are integers.
For n = 4; c is 5/3 < 2.

$$\frac{dc}{dn}=\frac{-2}{(n-1)^2}$$

That derivative is always negative on the interval [4, infinity). Thus c is always decreasing.

$$\displaystyle\lim_{n\to\infty}\frac{n+1}{n-1}=1$$

Therefore, there are no other c's that are integers on the interval [4, infinity).

Thus the only answers for m > n + 1 are (6, 2) and (6, 3).
And the only answer for n > m + 1 are (2, 6) and (3, 6).

Finally, we have proven that the only solutions are (1,1), (1, 2), (2, 1), (2, 2), (2, 3), (2, 6), (3, 2), (3, 6), (6, 2) and (6, 3).

What do you think? Is this proof enough?

 

[robert Ihnot]

$$\frac{n(n+1)}{n-a} = m$$ That's O.K., but this whole matter looks like slight of hand in order to confuse. Now we have an a in here, what is a? Well it's a=m-kn+1.

So we change that equation to $$\frac{n(n+1)}{(k+1)n-(m+1)}=m.$$

So what do we get out of that? I don't know. Do we know how those factors divide up?

 

[sennyk]

Well, ...

When m > n + 1, then the second fraction is less than 1. "a" is the remainder of (m+1)/n. That's how I come up with the following equation.

$$\frac{a}{n} + \frac{n+1}{m} = 1$$

 

[robert Ihnot]

You are saying that $$\frac{n(n+1)}{(k+1)n-(m+1)}=m.$$ tells us that m has to be a multiple of n.

You are saying that the denominator has no common factor with n, well we can continue to subtract off n from the denominator and are left with -(m+1), which you say has no common factor with n. However we are back to square 1 with nothing shown.

Certainly we know about (m+1)/n + (n+1)/m =k+1 where m =kn, but by reducing the sum to 1 does not change anything. TAke (2,6), 6=3*2, as you have shown:
7/2+3/6 = 4. If you want to reduce it 7 =(3x2) +1, and we get 1/2+3/6=1. But this does not mean that every solution is of that form.

 

[sennyk]

You are saying that $$\frac{n(n+1)}{(k+1)n-(m+1)}=m.$$ tells us that m has to be a multiple of n.

You are saying that the denominator has no common factor with n, well we can continue to subtract off n from the denominator and are left with -(m+1), which you say has no common factor with n. However we are back to square 1 with nothing shown.

I don't come up with that denominator. How are you getting that?

My denominator is (n - a), where a is the remainder of (m+1)/n, m > n + 1. The domain of a is (0, 1, ..., n - 1). If a is zero, then m = n + 1, which is outside of our initial condition anyway. So the denominator will never be a multiple of n. It could be a factor of n. Are you saying that (n - a) could be a factor of n and not n + 1?

Certainly we know about (m+1)/n + (n+1)/m =k+1 where m =kn, but by reducing the sum to 1 does not change anything. TAke (2,6), 6=3*2, as you have shown:
7/2+3/6 = 4. If you want to reduce it 7 =(3x2) +1, and we get 1/2+3/6=1. But this does not mean that every solution is of that form.

I'm saying that every solution is of the form m = kn when m > n +1.I've taken care of the case of m = n, m = n + 1, and m > n + 1. The case of m < n is taken care of by swapping m with n and repeating the analysis. Thus I've handled the entire interval [1, infinity).

 

[sennyk]

You are correct. This only proves the solutions for m = kn. I just found another solution by letting a = n/2. I do think there are infinite solutions now. I think by letting a = n/t, that will yield infinite solutions. My new solutions found are (14, 6), (6, 21).

The equation,

$$m=\frac{n(n+1)}{n-a}$$ is working well; however, I'm not sure how to continue to prove that there are infinite solutions for m > n + 1.

 

[robert Ihnot]

Great Work! That gives us a case where m and n have a common element, but one does not divide the other!

 

[sennyk]

Maybe continue by letting m = n + t? Another solution (90, 35)

 

[sennyk]

Pattern

I've noticed a pattern. It seems like there is some sort of recursive relationship.

(1, 2)
(2, 3)
(3, 6)
(6, 21)
(21, 77)
(77, 286)

 

[sennyk]

I have a theory. I think that there are infinite solutions where the expression (m+1)/n+(n+1)/m = 4.

All of these solutions equal 4.
(1, 2)
(2, 6)
(6, 21)
(21, 77)
(77, 286)
(286, 1066)
(1066, 3977)
(3977, 14841)
(14841, 55386)
(55386, 206702)

 

[sennyk]

(m+1)/n+(n+1)/m=3 also has an infinite number of solutions. I believe that is it.

 

[Ben Niehoff]

I have it. Suppose

$$\frac{m+1}n + \frac{n+1}m = Z$$

where Z is some integer. Then

$$m^2 + m + n(n+1) = Zmn$$

$$m^2 - (Zn - 1)m + n(n+1) = 0$$

This has two roots

$$m^2 - (m_1 + m_2)m + m_1m_2 = 0$$

Therefore, we have

$$m_1 + m_2 = Zn - 1$$

But we know that

$$Z = \frac{m_1+1}n + \frac{n+1}{m_1}$$

$$Zn = m_1 + 1 + \frac{n(n+1)}{m_1}$$

and so

$$m_1 + m_2 = Zn - 1 = m_1 + \frac{n(n+1)}{m_1}$$

which yields

$$m_2 = \frac{n(n+1)}{m_1}$$

Now we just have to prove this is an integer. First, we know:

$$\frac{m_1+1}n + \frac{n+1}{m_1} = Z$$

$$m_1(m_1+1) + n(n+1) = Zm_1n$$

$$n(n+1) = Zm_1n - m_1(m_1+1)$$

$$\frac{n(n+1)}{m_1} = Z - m_1 - 1$$

which is an integer. QED

Edit: This doesn't technically prove that there are infinitely many solutions, because I haven't proved that m_2 is always greater than m_1...hmm...

 

[Ben Niehoff]

Suppose Z is a positive integer (if m and n are positive, this is always the case). Then suppose that m_1 < n. Then if Z > 2,

$$Zn - m_1 - 1 > Zn - n - 1 = (Z-1)n - 1 > n > m_1$$

Now all we need is at least one case for Z > 2 and m < n, which Sennyk has already shown.

QED

 

[sennyk]

Relationship between solutions

I've found the recursive relationship between the solutions.

case $$\frac{m+1}{n}+\frac{n+1}{m}=4$$

$$n_0=1, m_0=1$$
$$n_1=1, m_1=2$$
$$n_k=m_k_-_1, m_k=\frac{n_k(n_k+1)}{m_k_-_2}$$

case $$\frac{m+1}{n}+\frac{n+1}{m}=3$$

$$n_0=2, m_0=2$$
$$n_1=2, m_1=3$$
$$n_k=m_k_-_1, m_k=\frac{n_k(n_k+1)}{m_k_-_2}$$

Maybe a proof by induction would work?

 

[Ben Niehoff]

Yeah, my above two posts give a proof by induction. That recursive relation shows up in the proof.

Part of the proof involves proving that

$$m_k = \frac{n_{k-1}(n_{k-1} + 1)}{m_{k-2}}$$

is always an integer. Finally, one also has to prove that

$$m_k > m_{k-2}$$

or else the attempt at "induction" might actually loop back on itself.

 

[sennyk]

I have it. Suppose

$$m^2 - (Zn - 1)m + n(n+1) = 0$$

This has two roots

$$m^2 - (m_1 + m_2) + m_1m_2 = 0$$

I'm not seeing how you make this leap. Please explain.

 

[Ben Niehoff]

I'm not seeing how you make this leap. Please explain.

Whoops, there's a typo. It should be:

$$m^2 - (m_1 + m_2)m + m_1m_2 = 0$$

It's directly from the fundamental theorem of algebra. If a second-degree polynomial has roots r_1 and r_2, then

$$\begin{array}{rcl}(x - r_1)(x - r_2) & = & 0 \\ x^2 - r_1x - r_2x + r_1r_2 &=& 0 \\ x^2 - (r_1 + r_2)x + r_1r_2 &=& 0\end{array}$$

 

[robert Ihnot]

sennyk, while he did make a typo, you have got to look at symmetric functions as they apply to the roots of a polynominal.

Take the equation X^3-1 = 0. This equation has three roots x=1, $$X=\frac{-1\pm\sqrt-3}{2}$$

Question: What is the sum of the three roots and what is their product?

Answer: In the equation X^3-bX^2+cX-d, the sum of the roots equals -b, and the product of the roots equals -d. Since b=0 the sum of the roots is 0 and since -d =1 the product of the roots is 1.

We get the above form from multiplying out (x-r)(x-s)(x-t), where r,s,t represent the three roots.

 

[sennyk]

The typo completely threw me off. I know how to find the roots of a polynomial. I'm not a complete amateur. :)

 

[robert Ihnot]

O.K., sorry