Consider two coprime integers $p{}$ and $q{}$ which are greater than $1{}$ and differ from each other by more than $1{}$. Prove that there exists a positive integer $n{}$ such that \[\text{lcm}(p+n, q+n)<\text{lcm}(p,q).\]
Problem
Source: 44th International Tournament of Towns, Senior A-Level P2, Fall 2022
Tags: number theory, Tournament of Towns
grupyorum
16.02.2023 18:55
Let $q-p\ge 2$. Let $k$ be the smallest positive integer for which $kq-(k+1)p>0$. Note that $(k-1)q-kp\le -1$ (as $q-p>1$) and thus $kq-(k+1)p\le q-p-1$. So, we get $k(q-p)\le q-1$. Now, taking $n=kq-(k+1)p$, we find that \[ [p+n,q+n] = \frac{(p+n)(q+n)}{{\rm gcd}(p+n,q+n)} = k(k+1)(q-p). \]Now using $(k-1)q-kp\le -1$, we find that $kp\ge (k-1)q+1 \ge (k-1)(p+2)+1 \implies p\ge 2k-1$. So, if $k\ge 2$, we are done immediately. Finally, if $k=1$ then we have $k(k+1)(q-p) = 2q-2p<2q\le pq$ as $p\ge 2$. This completes the proof.
laikhanhhoang_3011
16.02.2023 19:07
Define $p=q+k, k \geq 2$ and $t \geq 1$ is the smallest positive integer such that: $t(p-q) > q.$
$$\Rightarrow (t-1)(p-q) \leq q$$$\bullet$ If $(t-1)(p-q)=q \leftrightarrow (t-1)p=tq,$
$\, \,$ then $q \mid (t-1)p;t-1 \mid tq$ and $p \mid tq; t \mid (t-1)p.$
$\, \,$ $ \, \rightarrow q \mid t-1; t-1 \mid q$ and $p \mid t; t \mid p.$ So $p=t, q=t-1 \rightarrow p-q=1,$ adsurb.
So $(t-1)(p-q) \leq q-1 \rightarrow t-1 \leq \frac{q-1}{p-q}, (1).$
Choose $n=t(p-q)-q.$ We need to prove: $$t(t+1)(p-q) \leq pq(p-q) \leftrightarrow t(t+1) \leq pq$$From $(1),$ we need to prove: $$(p-1)(2p-q-1) \leq pq(p-q)^2 \leftrightarrow (q+k-1)(q+2k-1) \leq (q+k)qk^2$$$$\leftrightarrow (q+k-1)^2 +k(q+k-1) \leq (qk)^2 + k.qk^2$$But $q+k-1 \leq qk$ and $q+k-1 \leq qk^2,$ the ineq is absolutely true.
Q.E.D
RemarK: Get sniped by a same solution, but anyway ...
VicKmath7
16.02.2023 20:29
Let WLOG $q>p$. We want $\frac {(p+n)(q+n)} {\gcd(p+n, q-p)} <pq$. Choose $n$ so that $k=q-p \mid p+n$ (and $n<k$ since we choose $n$ modulo $k$), so we want $kpq>pq+p+q+n$. Indeed, this is true as $kpq \geq (n+1)pq>pq+p+q+n \iff npq>p+q+n \iff n(pq-1)>p+q$, which is obvious.
ThisNameIsNotAvailable
23.02.2023 18:07
Let $n=kp-(k+1)q>0$, then $k>t=\frac{q}{p-q}$. It suffices to prove there exists such positive integer $k$ satisfying $$\frac{k(k+1)(p-q)^2}{(p-q)(k,k+1)}<pq\iff k(k+1)<\frac{pq}{p-q}.$$If $p>\frac{3}{2}q$, choose $k=2$ (Note that $pq\geq 2\dot 5=10$). Otherwise $q<p<\frac{3}{2}q$, we need to prove $$\frac{-1+\sqrt{1+4pt}}{2}\geq t+1\iff pt\geq (t+1)(t+2)\iff q\geq \frac{2p-q}{p-q},$$which is true since $2p<3q$ and $p-q\geq 2$.