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