# Prove that $a + b \geq 4k$

Let $$a, b$$ and $$k$$ be positive integers with $$k> 1$$ such that $$lcm (a, b) + gcd (a, b) = k (a + b)$$. Prove that $$a + b \geq 4k$$

Solution: Let $$a=da_0$$, $$b=db_0$$, thus $$da_0b_0+d=kd(a_0+b_0) \implies k=\frac{a_0b_0+1}{a_0+b_0}$$. Assuming to contrary, say $$k > \frac{a+b}4 \implies 4a_0b_0+4 > d(a_0^2+b_0^2+2a_0b_0) > a_0^2+b_0^2+2a_0b_0 \implies 4 > (a_0-b_0)^2$$. Thus $$|a_0-b_0| < 2$$. Considering $$a_0 \geq b_0$$, we get $$a_0$$ as one of $$b_0,b_0+1$$. As $$k$$ is an integer, $$\frac{a_0b_0+1}{a_0+b_0}$$ is an integer $$\implies a_0+b_0 \mid a_0b_0+1$$.

Case 1: $$a_0=b_0$$: $$2a_0 \mid a_0^2+1 \implies \mid 2a_0^2+2-2a_0^2 \implies \mid 2$$. Thus $$a_0=b_0=1$$, which is a contradiction as $$k>1$$.

Case 2: $$a_0=b_0+1$$: $$2b_0+1 \mid b_0^2+b_0+1 \implies \mid 2b_0^2+2b_0+2 -b_0(2b_0+1) \implies \mid b_0+2 \implies \mid 2b_0+4-2b_0-1 \implies \mid 3$$. Thus $$b_0=1 \implies a_0=2$$, which is a contradiction, as $$k>1$$.

How to prove it without contradiction? An elegant method

• I smell a proof by induction.... Dec 15, 2019 at 22:32
• Yes, I did it exactly the same. Dec 15, 2019 at 22:45

As you noted, it's enough to consider $$a$$ and $$b$$ coprime. Then, the problem is to show the implication
\begin{align*} ab + 1 \stackrel{(1)}{=} k(a+b) \Longrightarrow a+b \stackrel{(2)}{\geqslant} 4k. \end{align*} Geometrically, (1) says that $$(a,b)$$ is a lattice point on the graph of the function
\begin{align*} f_k(x) = \frac{kx-1}{x-k}, \end{align*} and (2) says that $$(a,b)$$ lies above the line $$\ell_k : x+y = 4k$$. In other words, the problem is to show that no primitive lattice point $$(a,b)$$ on the graph of $$f_k$$ can lie (strictly) below $$\ell_k$$.
By doing a straightforward computation, one finds that the intersections of $$\ell_k$$ and the graph of $$f_k$$ occur at $$x = 2k \pm 1$$, and that $$\ell_k$$ is strictly below the (relevant part of the) graph for $$x$$ outside the interval $$\left[ 2k-1, 2k+1 \right]$$. Hence the only possibility for a lattice point $$(a,b)$$ on the graph of $$f_k$$ to lie below $$\ell_k$$ is that its $$x$$-coordinate is $$2k$$. But then its $$y$$-coordinate fails to be an integer, precisely because we require $$k \geqslant 2$$. In detail,
\begin{align*} f_k(2k) = \frac{2k^2 - 1}{k} = 2k - \frac{1}{k}. \end{align*}