# How to solve this?

1. Nov 12, 2007

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

2. Nov 12, 2007

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

Last edited: Nov 12, 2007
3. Nov 13, 2007

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

Last edited: Nov 13, 2007
4. Nov 13, 2007

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

5. Nov 13, 2007

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

Last edited: Nov 13, 2007
6. Nov 14, 2007

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

Last edited: Nov 14, 2007
7. Nov 14, 2007

### sennyk

I think I've got it.

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.

Last edited: Nov 14, 2007
8. Nov 14, 2007

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

Last edited: Nov 14, 2007
9. Nov 14, 2007

### sennyk

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.

10. Nov 14, 2007

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

Last edited: Nov 14, 2007
11. Nov 14, 2007

### d_leet

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.

12. Nov 14, 2007

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

Last edited: Nov 14, 2007
13. Nov 14, 2007

### sennyk

Split factors

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

14. Nov 14, 2007

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

Last edited: Nov 14, 2007
15. Nov 14, 2007

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

Last edited: Nov 14, 2007
16. Nov 16, 2007

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

Last edited: Nov 16, 2007
17. Nov 17, 2007

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

Last edited: Nov 17, 2007
18. Nov 17, 2007

### 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$$

19. Nov 17, 2007

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

Last edited: Nov 17, 2007
20. Nov 17, 2007

### sennyk

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?

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).

Last edited: Nov 17, 2007