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

\begin{document}
\title{EGMO 2024/3}
\subtitle{Evan Chen}
\author{Twitch Solves ISL}
\date{Episode 146}
\maketitle

\section*{Problem}
We call a positive integer $n$ \emph{peculiar} if,
for any positive divisor $d$ of $n$ the integer $d(d + 1)$ divides $n(n + 1)$.
Prove that for any four different peculiar positive integers $A$, $B$, $C$ and $D$,
the following holds:
\[\gcd(A, B, C, D) = 1.\]

\section*{Video}
\href{https://www.youtube.com/watch?v=EJS9br0gyqE&list=PLi6h8GM1FA6yHh4gDk_ZYezmncU1EJUmZ}{\texttt{https://youtu.be/EJS9br0gyqE}}

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

\newpage

\section*{Solution}
Note that $1$ and any prime are peculiar.
We classify all composite peculiar numbers in a series of claims.

\begin{claim*}
  A peculiar number $n$ has at most two prime factors.
\end{claim*}
\begin{proof}
  Let $p$ be the smallest prime dividing $n$, and let $\frac np = c$. Then
  \[ \frac np \cdot \left( \frac np + 1 \right) \mid n(n+1) \]
  In particular,
  \[ c + 1 \mid cp \cdot (cp+1). \]
  However,
  \[ cp \cdot (cp+1) \equiv p(p-1) \pmod{c+1}. \]
  So, since $p(p-1) \neq 0$, we get a bound
  \[ c \le p^2-p \implies n = cp \le p^3-p^2 < p^3. \]
  Hence, $n < p^3$ and $p$ is the smallest prime dividing $n$,
  $n$ can have at most one additional prime factor.
\end{proof}

\begin{claim*}
  The square of a prime is never peculiar.
\end{claim*}
\begin{proof}
  If $n = p^2$ we need $p(p+1) \mid p^2(p^2+1)$,
  or $p+1 \mid p^2+1$, which never holds as $p^2+1 \equiv 2 \pmod{p+1}$.
\end{proof}

\begin{claim*}
  If $n = pq$ is peculiar for primes $p > q$, then $p = (q+1)(q-2)+1$.
\end{claim*}
\begin{proof}
  Note that $6$ is not peculiar (as $3 \cdot 4 \nmid 6 \cdot 7$).
  Assume $n > 6$ and write the equations
  \begin{align*}
    p(p+1) \mid pq(pq+1) \iff p+1 \mid q(pq+1) &\iff p+1 \mid q(q-1) \\
    q(q+1) \mid pq(pq+1) \iff q+1 \mid p(pq+1) &\iff q+1 \mid p(p-1)
  \end{align*}
  In the second equation, since $p > q+1$, we find $\gcd(q+1, p) = 0$ so
  \[ p \equiv 1 \pmod{q+1}. \]
  So let $p = 1 + k(q+1)$.
  On the other hand, we also note that
  \[ 2 + k(q+1) = p+1 \le q(q-1) \]
  and hence $k < q-1$; that is, $k \in \{1,2,\dots,q-2\}$.

  Now, if $p+1 = 2+k(q+1)$ is divisible by $q$, it follows
  $k \equiv -2 \pmod q$ and therefore $k =q-2$ exactly.
  If it isn't, then we would have $p+1 \mid q-1$ which is impossible.
  So the claim is proved.
\end{proof}

Hence, given a fixed prime $\ell$, there are at most three peculiar numbers
divisible by $\ell$: namely
\begin{itemize}
  \ii $\ell$ itself;
  \ii $\ell \cdot \left[ (\ell+1)(\ell-2)+1 \right]$,
  if the bracketed number is indeed prime;
  \ii $\ell \cdot r$, if there is indeed a prime $r$ such that $\ell = (r+1)(r-2)+1$.
\end{itemize}
Hence given four distinct peculiar numbers, they can have no common prime factor.

\end{document}
