Romania — NMO Selection Tests for the Balkan and International Mathematical Olympiads

Clearly, $S$ is closed under multiplication and division: if $r$ and $s$ are members of $S$, so are $rs$ and $r/s$.

If $a$ is a positive integer, and $p \neq 5$ is a prime factor of $a^2 + a - 1$, then $p \equiv \pm 1 \pmod 5$. To prove this, notice that $(2a + 1)^2 \equiv 5 \pmod p$, so $5$ is a quadratic residue modulo $p$. By quadratic reciprocity, $p$ is a quadratic residue modulo $5$, so $p \equiv \pm 1 \pmod 5$. Notice also that $S$ contains $5$, for $5 = 2^2 + 2 - 1$.

We now show by induction that $S$ contains all primes congruent to $\pm 1 \pmod 5$. Since there are infinitely many such, the conclusion follows. To begin, notice that $11$ and $19$ both are in $S$: $11 = 3^2 + 3 - 1$, and $19 = 4^2 + 4 - 1$.

Consider now a prime $q \equiv \pm 1 \pmod 5$, and assume that $S$ contains all primes $p < q, p \equiv \pm 1 \pmod 5$. Since $q$ is a quadratic residue modulo $5$, quadratic reciprocity shows that $5$ is a quadratic residue modulo $q$, so there exists $a$ in $\{1, 2, \dots, q - 1\}$ such that $a^2 + a - 1 = mq$ for some positive integer $m$. Notice that $a^2 + a - 1 \le (q - 1)^2 + (q - 1) - 1 = q^2 - q - 1 < q^2$, to deduce that $m < q$. If $m = 1$, then $q = a^2 + a - 1$ which is a member of $S$. If $m > 1$, and $p$ is a prime factor of $m$, then

$p$ is also a prime factor of $a^2 + a - 1$, so $p = 5$ or $p \equiv \pm 1 \pmod 5$. In either case, $p$ is a member of $S$, so $m$ is a member, for $S$ is closed under multiplication. Since $q = (a^2 + a - 1)/m$, and $S$ is closed under division, it follows that $q$ is indeed a member of $S$. This completes the proof.