\documentclass[11pt]{scrartcl}
\usepackage{evan}

\begin{document}
\title{USEMO 2020/1}
\subtitle{Evan Chen}
\author{Twitch Solves ISL}
\date{Episode 34}
\maketitle

\section*{Problem}
Which positive integers can be written in the form
\[ \frac{\opname{lcm}(x,y) + \opname{lcm}(y,z)}{\opname{lcm}(x,z)} \]
for positive integers $x$, $y$, $z$?

\section*{Video}
\href{https://www.youtube.com/watch?v=5a_XCGKiXnI}{\texttt{https://youtu.be/5a\_XCGKiXnI}}

\section*{External Link}
\url{https://aops.com/community/p18471128}

\newpage

\section*{Solution}
Let $k$ be the desired value, meaning
\[ -k \opname{lcm}(x,z) + \opname{lcm}(x,y) + \opname{lcm}(y,z) = 0. \]
Our claim is that the possible values are even integers.

Indeed, if $k$ is even,
it is enough to take $(x,y,z) = (1, k/2, 1)$.

For the converse direction we present a few approaches.

\paragraph{First approach using $\nu_2$ only.}
We are going to use the following fact:
\begin{lemma*}
  If $u$, $v$, $w$ are nonzero integers with $u+v+w=0$,
  then either
  \begin{align*}
    \nu_2(u) &> \nu_2(v) = \nu_2(w); \\
    \nu_2(v) &> \nu_2(w) = \nu_2(u); \quad\text{or} \\
    \nu_2(w) &> \nu_2(u) = \nu_2(v).
  \end{align*}
\end{lemma*}
\begin{proof}
  Let's assume WLOG that $e = \nu_2(w)$ is minimal.
  If both $\nu_2(u)$ and $\nu_2(v)$ are strictly greater than $e$,
  then $\nu_2(u+v+w) = e$ which is impossible.
  So assume WLOG again that $\nu_2(v) = \nu_2(w) = e$.
  Then
  \[ u = -(2^e \cdot \text{odd} + 2^e \cdot \text{odd})
    = -2^e \cdot \text{even}
  \]
  so $\nu_2(u) \ge e+1$.
\end{proof}

However, if we assume for contradiction that $k$ is odd, then
\begin{align*}
  \nu_2(-k \opname{lcm}(x,z)) &= \max(\nu_2(x), \nu_2(z)) \\
  \nu_2(\opname{lcm}(x,y)) &= \max(\nu_2(x), \nu_2(y)) \\
  \nu_2(\opname{lcm}(y,z)) &= \max(\nu_2(y), \nu_2(z)).
\end{align*}
In particular, the \emph{largest} two numbers among the three right-hand
sides must be equal.
So by the lemma, there is no way the three numbers
$(-k \opname{lcm}(x,z), \opname{lcm}(x,y), \opname{lcm}(y,z))$
could have sum zero.

\paragraph{Second approach using $\nu_p$ for general $p$.}
We'll prove the following much stronger claim
(which will obviously imply $k$ is even).
\begin{claim*}
  We must have $\opname{lcm}(x,z) \mid \opname{lcm}(x,y) = \opname{lcm}(y,z)$.
\end{claim*}
\begin{proof}
  Take any prime $p$ and look at three numbers $\nu_p(x)$, $\nu_p(y)$, $\nu_p(z)$.
  We'll show that
  \[ \max(\nu_p(x), \nu_p(z)) \le \max(\nu_p(x), \nu_p(y))
    = \max(\nu_p(y), \nu_p(z)). \]

  If $\nu_p(y)$ is the (non-strict) maximum, then the claim is obviously true.

  If not, by symmetry assume WLOG that $\nu_p(x)$ is largest,
  so that $\nu_p(x) > \nu_p(y)$ and $\nu_p(x) \ge \nu_p(z)$.
  However, from the given equation,
  we now have $\nu_p(\opname{lcm}(y,z)) \ge \nu_p(x)$.
  This can only occur if $\nu_p(z) = \nu_p(x)$.
  So the claim is true in this case too.
\end{proof}

\paragraph{Third approach without taking primes (by \texttt{circlethm}).}
By scaling, we may as well assume $\gcd(x,y,z) = 1$.

Let $d_{xy} = \gcd(x,y)$, etc.
Now note that $\gcd(d_{xy}, d_{xz}) = 1$, and cyclically!
This allows us to write the following decomposition:
\begin{align*}
  x &= d_{xy} d_{xz} a \\
  y &= d_{xy} d_{yz} b \\
  z &= d_{xz} d_{yz} c.
\end{align*}
We also have $\gcd(a,b) = \gcd(b,c) = \gcd(c,a) = 1$ now.

Now, we have
\begin{align*}
  \opname{lcm}(x,y) &= d_{xy} d_{xz} d_{yz} ab \\
  \opname{lcm}(y,z) &= d_{xy} d_{xz} d_{yz} bc \\
  \opname{lcm}(x,z) &= d_{xy} d_{xz} d_{yz} ac
\end{align*}
and so substituting this in to the equation gives
\[ k = b \cdot \left( \frac 1a + \frac 1c \right). \]
For $a$, $b$, $c$ coprime this can only be an integer if $a=c$, so $k = 2b$.

\begin{remark*}
  From $a=c=1$, the third approach also gets the
  nice result that $\opname{lcm}(x,y) = \opname{lcm}(y,z)$
  in the original equation.
\end{remark*}

\end{document}
