Find all posible pairs of positive integers $x,y$ such that $$\text{lcm}(x,y+3001)=\text{lcm}(y,x+3001)$$
Problem
Source: Bolivian Cono Sur TST 2021 Day 1 P2
Tags: number theory, least common multiple, LCM, Bolivia, Cono Sur TST, TST
18.11.2021 06:21
I claim the only family of pairs is $(x,y)=(n,n)$, where $n\in\mathbb{N}$ is arbitrary. Notation. In what follows, let $[a,b]\triangleq {\rm lcm}(a,b)$ and $(a,b)\triangleq {\rm gcd}(a,b)$. We recall the useful fact that $[a,b](a,b)=ab$, and thus $[a,b]\mid ab$. First, I'll replace $3001$ by any arbitrary prime $p$, and prove the general version. If $x=1$, then $y+p = [y,p+1]$. Noting that $y\mid [y,p+1]$, we have $y\mid y+p$. Thus $y\in\{1,p\}$. If $y=p$, then $2p=[p,p+1]=p(p+1)$, which is absurd. Hence, $y=1$; and $(x,y)=(1,1)$ indeed works. Assume in the remainder $x,y\ne 1$. We have $x\mid [x,y+p] =[y,x+p]\mid y(x+p)$. As a result, $x\mid y(x+p)$. Case 1. $p\nmid x,y$. In this case, $(x,x+p)=(y,y+p)=1$; and thus we are left with $x\mid y$ and $y\mid x$. As a result, $x=y$, which indeed works. Case 2. $p\mid x,y$. Setting $x=pa$ and $y=pb$, we are left with $[a,b+1]=[b,a+1]$. Now, let $q\mid a$ be a prime. Then $q\mid [b,a+1]$; and thus either $q\mid b$ or $q\mid a+1$. Clearly $q\nmid a+1$, and thus $q\mid b$. This, in turn, yields $q\nmid b+1$. Hence, $v_q([a,b+1])=v_q(a) = v_q([b,a+1])=v_q(b)$. Repeating this for all prime factors, we find $x=y$. Case 3. $p\mid x$ and $p\nmid y$. (which includes, by symmetry, $p\mid y$ and $p\nmid x$). Set $x=px_1$. We then have $px_1\mid [y,px_1+p]\mid yp(x_1+1)$. As a result, $x_1\mid y$. Likewise, $y\mid x(y+p)$. Now, $(y,y+p)=1$ since $p\nmid y$, yielding $y\mid px_1$. Once again, as $(y,p)=1$, it follows $y\mid x_1$, and thus $y=x_1$. This yields $x=px_1$ and $y=x_1$ for some $x_1$. In this case, we are left with $[px_1,x_1+p]=[x_1,px_1+p]$, that is \[ \frac{x_1+p}{(px_1,x_1+p)} = \frac{x_1+1}{(x_1,px_1+p)}. \]Now if $p\nmid x_1$, then $(px_1,x_1+p)=(x_1,x_1+p)=(x_1,px_1+p)=1$, yielding $x_1+p=x_1+1$, a clear contradiction. From here, we are left with $p\mid x_1$, set $x_1=pk$. After some messy algebra, we arrive at \[ p(k+1) = (pk+1)(pk,k+1). \]From here, $p\mid k+1$. Set $k+1=p\ell$. Then $(pk,p\ell)=p$ as $(k,\ell)=1$ (since $\ell\mid k+1$). This yields $k+1=pk+1$, which is absurd.