Find all positive integers $k$ for which the equation: $$ \text{lcm}(m,n)-\text{gcd}(m,n)=k(m-n)$$has no solution in integers positive $(m,n)$ with $m\neq n$.
Problem
Source: Netherlands Team Selection Test 2016 Day 1-Problem 3
Tags: number theory, least common multiple
22.09.2016 12:09
For $k=1$ we can choose $m=6,n=3$ For $k=2a+1$ we can choose $m=2a^2-1,n=2a-1$ For $k=2a,a\geq 2$ , we can choose $m=4a^2-2a-1,n=2a-1$ For $k=2$ there are not such $m,n$
27.09.2016 18:21
Looked more difficult than it actually was. Let $m=dx$ and $n=dy$ with $\gcd(x,y)=1$ and thus $x \neq y$. Then the given equation is equivalent to \[ dxy-d=k(dx-dy) \iff x(y-k)=1-ky. \]Assume there is a solution $(x,y)$ for $k=2$, then the above equation will be $x(y-2)=1-2y$. As $x,y \geq 1$, it is evident that the right hand side is negative. Thus the left hand side is negative as well. That leaves us with the possibility $y=1$. But $y=1$ yields $x=1$. That gives $x=y$ which is a contradiction. It is easy to construct a solution for all other $k$. For $k=1$ take for example $m=6$ and $n=3$ as the above post, in general, one could take $(m,n)=(dx,d)$. For $k>2$ take \[ (x,y) = \left(k^2-k-1,k-1 \right). \]By the Euclidean Algorithm, we can see $\gcd \left(k^2-k-1,k-1 \right)=\gcd(-1,k-1)=1$ and confirming that that pair is a solution for all $k>2$ is easy. It is easy to see that $x \neq y$. Therefore, we are done and the only solution is $k=2$.
17.01.2018 15:33
Solution $lcm(m,n)gcd(m,n)=mn$ $gcd(m,n)=d$ $m=dx,n=dy$ $lcm(m,n)=dxy$ $d(xy–1)=kd(x–y) $ $\implies (xy–1)=k(x–y) $ $k=\frac{xy–1}{x–y}$ $k>2$ $gcd(xy–1,x–y) =1$ for $k>2$ It can be factorised $k=1$ works $k>2$ doesn't Example $xy–1=2(x–y) $ work$ k=2$ $(2+x)(y–2)=–3$ Has no solution$ (x, y) $ in $Z^+$