\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/uj93tNL8f7M}}
\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}