8
$\begingroup$

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.

$\endgroup$

marked as duplicate by Bill Dubuque elementary-number-theory Oct 3 '18 at 15:14

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

  • 1
    $\begingroup$ 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 $\endgroup$ – Xiaomi Oct 3 '18 at 12:46
  • 1
    $\begingroup$ Another nice solution is given here: math.stackexchange.com/questions/151549/… $\endgroup$ – Teddan the Terran Oct 3 '18 at 13:26
  • 1
    $\begingroup$ @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). $\endgroup$ – Mathejunior Oct 3 '18 at 13:53
12
$\begingroup$

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<m_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$.

$\endgroup$
  • $\begingroup$ That's an awesome solution! $\endgroup$ – Mathejunior Oct 3 '18 at 14:01
  • $\begingroup$ @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") $\endgroup$ – Bill Dubuque Oct 3 '18 at 15:08
1
$\begingroup$

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)}$$

$\endgroup$

Not the answer you're looking for? Browse other questions tagged or ask your own question.