Team Selection Tests for IMO, 2018

First, suppose on the contrary that $S$ is finite, then $S=\{p_{1}, p_{2}, \ldots, p_{k}\}$ for $k=|S|$. It is easy to check that $2,3 \notin S$.

Consider number $N=(p_{1}-1)(p_{2}-1) \cdots (p_{k}-1)$ and $M=2^{N^{2}+1}-3^{N}$. For some $p \in S$, by Euler's theorem, we have
$$2^{p-1} \equiv 1 \pmod{p} \text{ and } 3^{p-1} \equiv 1 \pmod{p}.$$
Then $2^{N^{2}+1}=2 \cdot 2^{N^{2}}=2 \cdot (2^{p-1})^{\frac{N^{2}}{p-1}} \equiv 2 \pmod{p}$ and $3^{N} \equiv (3^{p-1})^{\frac{N}{p-1}} \equiv 1 \pmod{p}$. Hence, $M \equiv 2-1=1 \pmod{p}$. So by the Chinese remainder theorem, we also have $M \equiv 1 \pmod{N}$ and $M>2$ then $M$ has some prime divisor that differs from $p_{1}, p_{2}, \ldots, p_{k}$, which is a contradiction.

Thus, $S$ has infinitely many elements.

To prove the second part, just consider some prime $p$ such that there does not exist $x \in \mathbb{Z}$ such that either $x^{2} \equiv 2 \pmod{p}$ or $x^{2} \equiv 3 \pmod{p}$. Indeed, suppose that for such prime $p$, $p \in S$ then we have two cases:

- If $n$ is even then $2 \cdot 2^{n^{2}} \equiv 3^{n} \pmod{p}$, which can be written as $2 x^{2} \equiv y^{2} \pmod{p}$ for some $x, y$ coprime to $p$. Then take $x'$ such that $x x' \equiv 1 \pmod{p}$, so $2 \equiv (x' y)^{2} \pmod{p}$, contradicting that $2$ is not a quadratic residue modulo $p$.
- If $n$ is odd then we have a similar argument.

Thus, we just need to show that there are infinitely many such primes. By Euler's criterion about quadratic residues, we need
$$\left(\frac{2}{p}\right)=\left(\frac{3}{p}\right)=-1 \text{ and } \left(\frac{2}{p}\right) \equiv 2^{\frac{p-1}{2}} \pmod{p},\left(\frac{3}{p}\right) \equiv 3^{\frac{p-1}{2}} \pmod{p}.$$
So we can see that $p \equiv 3,5 \pmod{8}$ and $p \equiv 2 \pmod{3}$, which implies that we can take any prime of the form $p=24k+5$ or $p=24k+11$. Dirichlet's theorem states that the primes of the form $an+b$ for any coprime positive integers $a, b$ are infinite, so we finish our proof. $\square$