USA IMO

In the solution below we use the expression $S$ is stable under $x\mapsto f(x)$ to mean that if $t$ belongs to $S$, then $f(t)$ also belongs to $S$. If $c,d\in S$, then by condition (b), $S$ is stable under $x\mapsto c^2-x$ and $x\mapsto d^2-x$. Hence, it is stable under $x\mapsto c^2-(d^2-x)=x+(c^2-d^2)$. Similarly, $S$ is stable under $x\mapsto x+(d^2-c^2)$. Hence, $S$ is stable under $x\mapsto x+n$ and $x\mapsto x-n$, whenever $n$ is an integer linear combination of finitely many numbers in $T=\{c^2-d^2\mid c,d\in S\}$.

By condition (a), $S\ne \varnothing$ and hence $T\ne \varnothing$ as well. For the sake of contradiction, assume that some $p$ divides every element in $T$. Then $c^2-d^2\equiv 0(\mathrm{mod}p)$ for all $c,d\in S$. In other words, for each $c,d\in S$, either $d\equiv c(\mathrm{mod}p)$ or $d\equiv -c(\mathrm{mod}p)$. Given $c\in S$, $c^2-c\in S$, by condition (b), so $c^2-c\equiv c(\mathrm{mod}p)$ or $c^2-c\equiv -c(\mathrm{mod}p)$. Hence, $$c\equiv 0(\mathrm{mod}p)\text{ or }c\equiv 2(\mathrm{mod}p)(\ast )$$ for each $c\in S$. By condition (a), there exist some $a$ and $b$ in $S$ such that $\gcd (a,b)=1$, that is, at least one of $a$ or $b$ cannot be divisible by $p$. Denote such an element of $S$ by $\alpha$; thus, $\alpha \not\equiv 0(\mathrm{mod}p)$. Similarly, by condition (a), $\gcd (a-2,b-2)=1$, so $p$ cannot divide both $a-2$ and $b-2$. Thus, there is an element of $S$, call it $\beta$, such that $\beta \not\equiv 2(\mathrm{mod}p)$. By (), $\alpha \equiv 2(\mathrm{mod}p)$ and $\beta \equiv 0(\mathrm{mod}p)$. By condition (b), ${\beta }^2-\alpha \in S$. Taking $c={\beta }^2-\alpha$ in () yields either $-2\equiv 0(\mathrm{mod}p)$ or $-2\equiv 2(\mathrm{mod}p)$, so $p=2$. Now (*) says that all elements of $S$ are even, contradicting condition (a). Hence, our assumption is false and no prime divides every element in $T$.

It follows that $T\ne \{0\}$. Let $x$ be an arbitrary nonzero element of $T$. For each prime divisor of $x$, there exists an element in $T$ which is not divisible by that prime. The set $A$ consisting of $x$ and each of these elements is finite. By construction, $\text{gcd}\{y\mid y\in A\}=1$, and $1$ can be written as an integer linear combination of finitely many elements in $A$ and hence in $T$. Therefore, $S$ is stable under $x\mapsto x+1$ and $x\mapsto x-1$. Because $S$ is nonempty, it follows that $S$ is the set of all integers.

---

Alternative solution.

Define $T$, $a$, and $b$ as in the first solution. We present another proof that no prime divides every element in $T$. Suppose, for sake of contradiction, that such a prime $p$ does exist. By condition (b), $a^2-a,b^2-b\in S$. Therefore, $p$ divides $a^2-b^2$, $x_1=(a^2-a{)}^2-a^2$, and $x_2=(b^2-b{)}^2-b^2$. Because $\text{gcd}(a,b)=1$, both $\text{gcd}(a^2-b^2,a^3)$ and $\text{gcd}(a^2-b^2,b^3)$ equal 1, so $p$ does not divide $a^3$ or $b^3$. But $p$ does divide $x_1=a^3(a-2)$ and $x_2=b^3(b-2)$, so it must divide $a-2$ and $b-2$. Because $\text{gcd}(a-2,b-2)=1$ by condition (a), this implies $p\mid 1$, a contradiction. Therefore our original assumption was false, and no such $p$ exists.