Question 37
Let $S$ be a set of nonnegative integers such that
- there exist two elements $a$ and $b$ in $S$ such that $a, b \gt 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.
- there exist two elements $a$ and $b$ in $S$ such that $a, b \gt 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.