HMIC 2024 Problem 3

Let $S$ be a set of nonnegative integers such that

• there exist two elements $a$ and $b$ in $S$ such that $a, b>1$ and $\operatorname{gcd}(a, b)=1$; and
• for any (not necessarily distinct) element $x$ and nonzero element $y$ in $S$, both $x y$ and the remainder when $x$ is divided by $y$ are in $S$.

Prove that $S$ contains every nonnegative integer.