Show that infinitely many positive integer pairs $(m,n)$ exist s.t $\frac{m+1}{n}+\frac{n+1}{m} \in \mathbb{N}$ [duplicate]

Show that infinitely many positive integer pairs $(m,n)$ exist such that $\frac{m+1}{n}+\frac{n+1}{m} \in \mathbb{N}$.

I couldn't solve it but I did make an observation which might or might not be helpful. WLOG assume that $m < n$ (since the term is symmetric wrt $m,n$ along with the fact that ignoring the $m=n$ case wouldn't create any trouble). Write $n=mq+r$ for some $r\in \{[0,m-1]\cap \mathbb{N}\}$. Now, the question boils down to showing $\frac{m+1}{n}+\frac{r+1}{m} \in \mathbb{N}$. Note that each of the summand is $\leq 1$. Since the equality case wouldn't be helpful in generating infinitely many pairs of $(m,n)$, we can safely say that the sum is equal to $1$.

Now I don't know how to proceed from here.

marked as duplicate by Bill Dubuque elementary-number-theory StackExchange.ready(function() { if (StackExchange.options.isMobile) return; $('.dupe-hammer-message-hover:not(.hover-bound)').each(function() { var$hover = $(this).addClass('hover-bound'),$msg = $hover.siblings('.dupe-hammer-message');$hover.hover( function() { $hover.showInfoMessage('', { messageElement:$msg.clone().show(), transient: false, position: { my: 'bottom left', at: 'top center', offsetTop: -7 }, dismissable: false, relativeToBody: true }); }, function() { StackExchange.helpers.removeMessages(); } ); }); }); Oct 3 '18 at 15:14

• I wonder if, given an $m,n$ that satisfies this, you can construct another $m^*,n^*$ strictly greater than $m,n$ that does. Then, by showing one $m,n$ that satisfies it, it follows that infinitely many would – Xiaomi Oct 3 '18 at 12:46
• Another nice solution is given here: math.stackexchange.com/questions/151549/… – Teddan the Terran Oct 3 '18 at 13:26
• @TeddantheTerran I wish I had searched the problem before but I do really like the solutions here (they aren't exactly similar to the ones there). – Mathejunior Oct 3 '18 at 13:53

I shall find all pairs $$(m,n)$$ of positive integers such that $$\frac{m+1}{n}+\frac{n+1}{m}\in\mathbb{N}.$$ Let $$k$$ be such a positive integer for which $$\dfrac{m+1}{n}+\dfrac{n+1}{m}=k\tag{1}$$ for some $$m,n\in\mathbb{N}$$. Note that $$t=m$$ is a solution to $$t^2-(kn-1)t+(n^2+n)=0.$$ However, there is another root $$t=kn-1-m=\dfrac{n^2+n}{m}$$, which is an integer as $$kn-1-m\in\mathbb{Z}$$, and which is positive since $$\dfrac{n^2+n}{m}>0$$. Thus, if $$(m,n)$$ is a positive integer solution to (1), then $$(n,kn-1-m)=\left(n,\dfrac{n^2+n}{m}\right)$$ is also a positive integer solution.

Now, suppose that $$(m_0,n_0)$$ is a solution to (1) such that $$m_0\geq n_0$$ and $$m_0+n_0$$ is smallest possible. If $$m_0>n_0$$, we see that $$\left(n_0,\dfrac{n_0^2+n_0}{m_0}\right)$$ is also a solution, but $$n_0+\frac{n_0^2+n_0}{m_0}=n_0+n_0\left(\frac{n_0+1}{m_0}\right)\leq n_0+n_0 This contradicts the minimality of $$m_0+n_0$$, and so $$m_0=n_0$$ must hold. Thus, $$k=\frac{m_0+1}{m_0}+\frac{m_0+1}{m_0}=2+\frac{2}{m_0}\,.$$ That is, $$(m_0,n_0)=(1,1)$$ (which gives $$k=4$$), or $$(m_0,n_0)=(2,2)$$ (which gives $$k=3$$).

In the first case, $$m_0=n_0=1$$ and $$k=4$$. Define a sequence $$(a_0,a_1,a_2,\ldots)$$ by taking $$a_0=1$$, $$a_1=1$$, and $$a_{r}=4a_{r-1}-a_{r-2}-1$$ for $$r=2,3,4,\ldots$$. It follows that all solutions $$(m,n)$$ with $$k=4$$ such that $$m\leq n$$ are of the form $$(a_{r},a_{r+1})$$ for some $$r=0,1,2,\ldots$$. For example, $$a_2=2$$, $$a_3=6$$, $$a_4=21$$, and $$a_5=77$$.

In the second case, $$m_0=n_0=2$$ and $$k=3$$. Define a sequence $$(b_0,b_1,b_2,\ldots)$$ by taking $$b_0=2$$, $$b_1=2$$, and $$b_r=3b_{r-1}-b_{r-2}-1$$ for $$r=2,3,4,\ldots$$. It follows that all solutions $$(m,n)$$ with $$k=3$$ such that $$m\leq n$$ are of the form $$(b_{r},b_{r+1})$$ for some $$r=0,1,2,\ldots$$. For example, $$b_2=3$$, $$b_3=6$$, $$b_4=14$$, and $$b_5=35$$.

• That's an awesome solution! – Mathejunior Oct 3 '18 at 14:01
• @Mathejunior As I mentioned in my answer in the linked duplicate, this method is a special case of exploiting well-known symmetry groups of conics - see this answer for further discussion on this (and so-called "Vieta jumping") – Bill Dubuque Oct 3 '18 at 15:08

Equation: $$\frac{m+1}{n}+\frac{n+1}{m}=a$$ You can solve using the Pell equation: $$p^2-(a^2-4)s^2=1$$ Then the solutions are:

$$n=2(p-(a+2)s)s$$

$$m=-2(p+(a+2)s)s$$

And more solutions:

$$n=\frac{2p(p+(a-2)s)}{a-2}$$

$$m=\frac{2p(p-(a-2)s)}{a-2}$$

You can also write the solution formula if the coefficient is such that the equation $$p^2-(a^2-4)s^2=4$$ and taking advantage of his decisions. Then the formula has the form:

$$n=\frac{p-(a-2)s+2}{2(a-2)}$$

$$m=\frac{p+(a-2)s+2}{2(a-2)}$$