How to solve this?

  • Thread starter Sam_
  • Start date
  • #1
15
0
Show that there are infinitely many pairs of positive integers (m, n) such that

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

is a positive integer.
 

Answers and Replies

  • #2
73
0
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:
  • #3
1,056
0
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:

[tex] m\geq n+1; n\geq m+1[/tex]

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:
  • #4
73
0
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
1,056
0
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:
  • #6
73
0
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:
  • #7
73
0
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.
 
Last edited:
  • #8
1,056
0
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:
  • #9
73
0
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.
 
  • #10
73
0
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:
  • #11
1,074
1
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.
 
  • #12
1,056
0
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:
  • #13
73
0
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
 
  • #14
1,056
0
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:
  • #15
1,056
0
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:
  • #16
73
0
Here goes...

[tex]m \in N^*[/tex]

[tex]n \in N^*[/tex]

[tex]\frac{m+1}{n}+\frac{n+1}{m} \in N^*[/tex]

case m = n:

[tex]\frac{n+1}{n}+\frac{n+1}{n} \in N^*[/tex]

[tex]1+\frac{1}{n}+1+\frac{1}{n} \in N^*[/tex]

[tex]2+\frac{2}{n} \in Z[/tex]

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

[tex]\frac{n+1+1}{n}+\frac{n+1}{n+1} \in N^*[/tex]

[tex]1+\frac{2}{n}+1 \in N^*[/tex]

[tex]2+\frac{2}{n} \in N^*[/tex]

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

[tex]a= (m + 1) mod(n)[/tex]

[tex]\frac{a}{n} + \frac{n+1}{m} = 1[/tex]

[tex]ma + n(n+1) = mn[/tex]

[tex]n(n+1) = mn - ma[/tex]

[tex]n(n+1) = mn - ma[/tex]

[tex]\frac{n(n+1)}{n-a} = m[/tex]

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

[tex] m = cn [/tex]

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

[tex] \frac{1}{n} + \frac{n+1}{cn} = 1 [/tex]

[tex] c + n + 1 = cn [/tex]

[tex] n + 1 = cn - c [/tex]

[tex] \frac{n + 1}{n - 1} = c [/tex]

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.

[tex]\frac{dc}{dn}=\frac{-2}{(n-1)^2}[/tex]

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

[tex]\displaystyle\lim_{n\to\infty}\frac{n+1}{n-1}=1[/tex]

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:
  • #17
1,056
0
[tex]\frac{n(n+1)}{n-a} = m[/tex] 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 [tex]\frac{n(n+1)}{(k+1)n-(m+1)}=m.[/tex]

So what do we get out of that? I don't know. Do we know how those factors divide up?
 
Last edited:
  • #18
73
0
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.

[tex]\frac{a}{n} + \frac{n+1}{m} = 1[/tex]
 
  • #19
1,056
0
You are saying that [tex]\frac{n(n+1)}{(k+1)n-(m+1)}=m.[/tex] 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:
  • #20
73
0
You are saying that [tex]\frac{n(n+1)}{(k+1)n-(m+1)}=m.[/tex] 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).
 
Last edited:
  • #21
73
0
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,

[tex]m=\frac{n(n+1)}{n-a}[/tex] is working well; however, I'm not sure how to continue to prove that there are infinite solutions for m > n + 1.
 
Last edited:
  • #22
1,056
0
Great Work! That gives us a case where m and n have a common element, but one does not divide the other!
 
  • #23
73
0
Maybe continue by letting m = n + t? Another solution (90, 35)
 
  • #24
73
0
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)
 
  • #25
73
0
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)
 

Related Threads on How to solve this?

  • Last Post
Replies
5
Views
11K
  • Last Post
Replies
1
Views
2K
  • Last Post
Replies
1
Views
2K
  • Last Post
Replies
3
Views
1K
  • Last Post
Replies
3
Views
658
  • Last Post
Replies
9
Views
2K
  • Last Post
Replies
2
Views
1K
  • Last Post
Replies
2
Views
1K
  • Last Post
Replies
3
Views
2K
  • Last Post
Replies
1
Views
1K
Top