Determine all such pairs pf positive integers $(a, b)$ such that $a + b + (gcd (a, b))^ 2 = lcm (a, b) = 2 \cdot lcm(a -1, b)$, where $lcm (a, b)$ denotes the smallest common multiple, and $gcd (a, b)$ denotes the greatest common divisor of numbers $a, b$.
Problem
Source: Czech-Polish-Slovak Junior Match 2015, Team p4 CPSJ
Tags: LCM, GCD, number theory
socrates
20.03.2020 20:42
Nice problem!
Richangles
20.03.2020 20:46
Any solution?
kaede
20.03.2020 21:08
Let $ ( a,b) =( ds,dt)$ where $ d=\gcd( a,b)$ and $ ( s,t) \in \mathbb{N}^{2}$.
From $ a+b+d^{2} =\text{lcm}( a,b)$, we have $ d=st-s-t\ \cdots ( \heartsuit )$.
From $ \text{lcm}( a,b) =2\cdot \text{lcm}( a-1,b)$, we have $ dst=2\cdot \text{lcm}( ds-1,dt)$.
It follows that $ st=2\cdot \text{lcm}( ds-1,t)$.
Since $ \gcd( t( ds-1) ,s) =1$, we must have $ s\in \{1,2\}$.
Assume that $ s=1$, then we have $ d=-1$ from $ ( \heartsuit )$, impossible.
So we must have $ s=2$.
So we have $ t=\text{lcm}( 2d-1,t)$ and $ d=t-2$.
Since $ t=\text{lcm}( 2d-1,t)$, we have $ 2d-1\mid t$.
It follows that $ 2d-1\mid d+2$, which implise $ d\in \{1,3\}$.
Hence the answer is $ \boxed{( a,b) =( 2,3) ,( 6,15)}$.
naman12
20.03.2020 21:13
Let $a=dk$ and $b=d\ell$. Then we get
\[dk+d\ell+d^2=dk\ell\]or
\[k+\ell+d=k\ell\]Thus we can write
\[(a,b)=(k^2\ell-k^2-k\ell,k\ell^2-\ell^2-k\ell)\]Now, note that at least one of $a,b$ are even. Thus, $2\mid k$ or $2\mid\ell$. However, as $k,\ell$ are relatively prime, we have only one of $k,\ell$ can be divisible by $2$. Now, note that $d$ must be odd, so $a$ and $b$ have different parities. If $b$ is even, we get that
\[v_2(\text{lcm}(a-1,b))\geq v_2(b)=v_2(\text{lcm}(a,b))\]so we can not have the last said equality. Thus $b$ is odd and $a$ is even. Thus $k$ is even and $\ell$ is odd.
Now, we also notice that as $a-1\mid\text{lcm}(a,b)$ and $\gcd(a,a-1)=1$, $a-1\mid b$. Thus we notice that $\text{lcm}(a,b)=2b$, so $a,a-1\mid 2b$. Thus in particular $a(a-1)\mid 2b$, or
\[k(k^2\ell-k^2-k\ell-1)\mid 2\ell\]We can look back in our equation for $d$
\[d=k\ell-k-\ell\]to see $\ell\geq 3$ and $k\geq 2$. If $k\geq 4$, we have that
\[(k^2-k)\ell-(k^2+1)\leq\dfrac{1}{2}\ell\]impossible. Thus $k=2$, giving $2\ell-5\mid\ell$. Thus, we get $\ell=1,3$ so thus
\[(a,b)=(2,3),(6,15)\]