Team selection tests for IMO 2018

First, suppose on the contrary that $S$ is finite, then $S=\{p_1,p_2,\dots ,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(\mathrm{mod}p)\text{ and }{3}^{p-1}\equiv 1(\mathrm{mod}p).$$ Then $2^{N^2+1}=2\cdot 2^{N^2}=2\cdot (2^{p-1}{)}^{\frac{N^2}{p-1}}\equiv 2(\mathrm{mod}p)$ and $3^N\equiv (3^{p-1}{)}^{\frac{N}{p-1}}\equiv 1(\mathrm{mod}p)$. Hence, $M\equiv 2-1=1(\mathrm{mod}p)$. So by the Chinese remainder theorem, we also have $M\equiv 1(\mathrm{mod}N)$ and $M>2$ then $M$ has some prime divisor that differs from $p_1,p_2,\dots ,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(\mathrm{mod}p)$ or $x^2\equiv 3(\mathrm{mod}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(\mathrm{mod}p)$, which can be written as $2x^2\equiv y^2(\mathrm{mod}p)$ for some $x,y$ coprime to $p$. Then take $x^{\prime }$ such that $x{x}^{\prime }\equiv 1(\mathrm{mod}p)$, so $2\equiv (x^{\prime }y{)}^2(\mathrm{mod}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}}(\mathrm{mod}p),\left(\frac{3}{p}\right)\equiv 3^{\frac{p-1}{2}}(\mathrm{mod}p).$$ So we can see that $p\equiv 3,5(\mathrm{mod}8)$ and $p\equiv 2(\mathrm{mod}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$