Help on this divisibility Problem

Question

Find all positive integers m and n such that:

$$ m+n\mid mn+1 $$

we have according to the condition $$ m+n\mid (m+1)(n+1) $$ any ideas??

Answer 1

If $m=2k-1,n=2k+1$ then $m+n=4k$ which divides $mn+1=4k^2.$ So there are infinitely many solutions, but these are likely not all of them. :-)

ADDED: To get them all based on a fixed $n$, consider that $$\frac{mn+1}{m+n}=n-\frac{n^2-1}{m+n}.$$ One is now free to choose $m$ independently from the fixed $n$ so long as $m+n$ is a divisor $d$ of $n^2-1$. For each such $d$ we have $m=d-n$ and (to ensure $n>0$) we only need to make sure we choose divisors $d$ of $n^2-1$ which exceed $n$.

For example for $n=13$ we have $n^2-1=2^3\cdot 3 \cdot 7$ and one of the divisors is $56$ which gives the pair $(56-13,13)=(43,13)$ where the ratio is $10$.

Answer 2

Let $m=ak+1$, $n=bk-1$, where $(a,b)=1$. (This decomposition is unique; just take $k=(m-1,n+1)$.) Then if $q(m+n)=mn+1$, we have $q(a+b)=abk+b-a$, so $abk\equiv a-b\pmod{a+b}$, and $k$ is a modular division in $\Bbb Z_{a+b}$. The converse is also true; given a solution to the division in $\Bbb Z_{a+b}$, we have $q(a+b)=abk+b-a$ and hence $q(m+n)=mn+1$. Thus this characterizes all solutions to $m+n\mid mn+1$. (Note that we have treated $m,n$ asymmetrically; either approach will yield the set of all solutions.)

I claim that $ab$ is invertible in $\Bbb Z_{a+b}$ for each relatively prime $a,b$, yielding the solution set described above, where $k=[ab]^{-1}(a-b)+j(a+b)$ and $[ab]^{-1}$ is some "canonical" inverse to $ab$ in $\Bbb Z_{a+b}$ and $j\in\Bbb Z$. So suppose $p$ is a prime with $p\mid ab$ and $p\mid a+b$. Then $p\mid a$ or $p\mid b$ (since $(a,b)=1$), so $p\mid a+b-a=b$ or $p\mid a+b-b=a$, and in either case $p\mid (a,b)=1$, a contradiction. Thus $(ab,a+b)=1$, and $ab$ is invertible. To summarize:

\begin{align} m&=a[ab]^{-1}_{a+b}(a-b)+ka(a+b)+1\\ n&=b[ab]^{-1}_{a+b}(a-b)+kb(a+b)-1 \end{align}

where $k\in\Bbb Z$, $a,b\in\Bbb N$, $(a,b)=1$ characterizes all solutions. (You may need to clip $k$ to be greater than some negative bound if you only want positive solutions for $m,n$, or you can solve the division problem $\frac{a-b}{ab}$ directly in $\Bbb Z_{a+b}$ instead of using $(a-b)\cdot[ab]^{-1}_{a+b}$, which will introduce extra multiples of $a+b$; in this case $k\in\Bbb N_0$ will suffice.)