2
$\begingroup$

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

$\endgroup$
2
  • 1
    $\begingroup$ I smell a proof by induction.... $\endgroup$
    – Ty Jensen
    Dec 15, 2019 at 22:32
  • $\begingroup$ Yes, I did it exactly the same. $\endgroup$
    – nonuser
    Dec 15, 2019 at 22:45

1 Answer 1

2
$\begingroup$

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*}

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.