<s>[INST] L.C.M. and H.C.F. problem Let $a$ and $b$ be natural numbers with $ab>2$. Suppose that the sum of their highest common factor and least common multiple is divisible by $a+b$. Prove that the quotient is at most $\frac{a+b}4$. When is this quotient exactly equal to $\frac{a+b}4$.
 [/INST] Let $g=\gcd(a,b)$ and $a=gA$, $b=gB$. Then, $\mathrm{lcm}(a,b)=gAB$ and we have
$$\frac{\mathrm{lcm}(a,b)+\gcd(a,b)}{a+b} = \frac{AB+1}{A+B}$$
Without loss of generality, we can assume $A\geq B$. Let's start with two simple cases:


*

*$A=B$; which implies $A=B=1$ (and $a=b=g$) due to $\gcd(A,B)=1$. The quotient is equal to $1$ and $\frac{a+b}{4}=\frac{g}{2}$. Since $ab\geq 2$, the desired inequality is proven in this case and equality happens only for $g=2$, corresponding to $(a,b)=(2,2)$.

*$A=B+1$; so the quotient reduces to $$\frac{B^2 + B + 1}{2B+1}$$
But this can be integer only if $\frac{B+2}{2B+1}$ is an integer; which happens only for $B=1$. Thus, $(A,B)=(2,1)$ and $(a,b)=(2g,g)$ and the quotient is equal to $1$. The inequality $ab>2$ implies $g\geq 2$, so the inequality $\frac{a+b}{4}\geq 1$ is always strict.

*$A\geq B+2$. Then, we have
$$\begin{eqnarray}
2 & \leq & A-B \\
4 & \leq & (A-B)^2 \\
4(AB+1) & \leq & (A+B)^2 \\
\frac{AB+1}{A+B} & \leq & \frac{A+B}{4} \leq g\frac{A+B}{4} = \frac{a+b}{4}\\
\end{eqnarray}$$
Clearly, the equality can happen only for $A=B+2$ and $g=1$. This corresponds to pairs of consecutive odd numbers, $(a,b)=(2n-1,2n+1)$ for any positive integer $n$.

</s>