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 \neq \emptyset$ and hence $T \neq \emptyset$ as well. For the sake of contradiction, assume that some $p$ divides every element in $T$. Then $c^2 - d^2 \equiv 0 \pmod{p}$ for all $c, d \in S$. In other words, for each $c, d \in S$, either $d \equiv c \pmod{p}$ or $d \equiv -c \pmod{p}$. Given $c \in S$, $c^2 - c \in S$, by condition (b), so $c^2 - c \equiv c \pmod{p}$ or $c^2 - c \equiv -c \pmod{p}$. Hence,
$$c \equiv 0 \pmod{p} \text{ or } c \equiv 2 \pmod{p} \quad (*)$$
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 \pmod{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 \pmod{p}$. By (*), $\alpha \equiv 2 \pmod{p}$ and $\beta \equiv 0 \pmod{p}$. By condition (b), $\beta^2 - \alpha \in S$. Taking $c = \beta^2 - \alpha$ in (*) yields either $-2 \equiv 0 \pmod{p}$ or $-2 \equiv 2 \pmod{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 \neq \{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.

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.