Problem: Let $S$ be a set of integers with the following properties:
\begin{itemize}
\ii $\{ 1, 2, \dots, 2025 \} \subseteq S$.
\ii If $a, b \in S$ and $\gcd(a, b) = 1$, then $ab \in S$.
\ii If $s + 1$ is composite for some $s \in S$, then all positive divisors of $s + 1$ are in $S$.
\end{itemize}
Prove that $S$ contains all positive integers.

\end{enumerate}

Solution: We prove by induction on $N$ that $S$ contains $\{1, \dots, N\}$
with the base cases being $N = 1, \dots, 2025$ already given.

For the inductive step, to show $N+1 \in S$:
\begin{itemize}
  \ii If $N+1$ is composite we're already done from the third bullet.

  \ii Otherwise, assume $N+1 = p \ge 2025$ is an (odd) prime number.
  We say a number is \emph{good} if the prime powers in its prime factorization
  are all less than $p$.
  Hence by the second bullet (repeatedly), good numbers are in $S$.
  Now our proof is split into three cases:

  \begin{description}
  \ii[Case 1.]
    Suppose neither $p-1$ nor $p+1$ is a power of $2$ (but both are still even).
    We claim that the number \[ s \coloneq p^2-1 = (p-1)(p+1) \] is good.
    Indeed, one of the numbers has only a single factor of $2$,
    and the other by hypothesis is not a power of $2$ (but still even).
    So the largest power of $2$ dividing $p^2-1$ is certainly less than $p$.
    And every other prime power divides at most one of $p-1$ and $p+1$.

    Hence $s \coloneq p^2-1$ is good. As $s+1 = p^2$, Case 1 is done.

    \ii[Case 2.]
    Suppose $p+1$ is a power of $2$; that is $p = 2^q-1$.
    Since $p > 2025$, we assume $q \ge 11$ is odd.
    First we contend that the number
    \[ s' \coloneq 2^{q+1} - 1 =
        \left( 2^{(q+1)/2}-1 \right) \left( 2^{(q+1)/2}+1 \right) \]
    is good.
    Indeed, this follows from the two factors being coprime and both less than $p$.
    Hence $s'+1 = 2^{q+1}$ is in $S$.

    Thus, we again have
    \[ s \coloneq p^2-1 = (p-1)(p+1) \in S \]
    as we did in the previous case, because the largest power of $2$ dividing $p^2-1$
    will be exactly $2^{q+1}$ which is known to be in $S$.
    And since $s+1=p^2$, Case 2 is done.

    \ii[Case 3.]
    Finally suppose $p-1$ is a power of $2$; that is $p = 2^{2^e}+1$ is a Fermat prime.
    Then in particular, $p \equiv 2 \pmod 3$.
    Now observe that
    \[ s \coloneq 2p-1 \equiv 0 \pmod 3 \]
    and moreover $2p-1$ is not a power of $3$
    (it would imply $2^{2^e+1} + 1 = 3^k$, which is impossible for $k \ge 3$
    by Zsigmondy/Mihailescu/etc.).
    So $s$ is good, and since $s+1 = 2p$, Case 3 is done.
  \end{description}
  Having finished all the cases, we conclude $p \in S$ and the induction is done.
\end{itemize}

\begin{remark*}
  In fact just $2025 \in S$ is sufficient as a base case;
  however this requires a bit more work to check.
  Here is how:
  \begin{itemize}
    \ii From $2025 \in S$ we get $2026 = 2 \cdot 1013$, so $2,1013 \in S$.
    \ii From $1013+1 = 1014 = 2 \cdot 3 \cdot 13^2$ we get $3,13 \in S$.
    \ii From $3+1 = 4$ we get $4 \in S$.
    \ii $3 \cdot 13 + 1 = 40 = 2^3 \cdot 5$ we get $5 \in S$.
    \ii Once $\{1,2,\dots,5\} \subseteq S$,
    the induction above actually works fine;
    that is, $N \le 5$ are sufficient as base cases
    for the earlier cases to finish the rest of the problem.
    (Case 2 works once $q \ge 3$, and Case 3 works once $e \ge 2$.)
  \end{itemize}
  However, $\{1,2,3,4\} \subseteq S$ is not sufficient;
  for example $S = \{1,2,3,4,6,12\}$ satisfies all the problem conditions.
\end{remark*}