India — Team Selection Test, 2012

If $S$ is singleton, then the statement is vacuously true. Hence $S = \{p\}$, $p$ a prime.

Suppose $S$ contains two elements. One of these must be odd primes and hence $2$ is in $S$. Moreover $p-1$ must be a power of $2$. Hence $p$ is Fermat prime.

Suppose $|S| \ge 3$. Here we consider two cases: $|S| < \infty$ and $S$ is an infinite set.

If $|S| < \infty$, let $S = \{p_1(=2), p_2, \dots, p_r\}$, with $r \ge 3$. Since $|S| \ge 3$, there is a prime of the form $3k+1$ or $3k+2$ in $S$. Observe $(3k+1)-1=3k$ and $2(3k+2)-1=6k+3$ both have $3$ as a prime factor. Hence $3 \in S$. Now
$$(2 \cdot p_3 \cdots p_r) - 1 = 3^k \text{ and } (3p_3 \cdots p_r) - 1 = 2^l,$$
for some $k > 0$ and $l > 0$. Hence we get
$$3(3^k + 1) = 2(2^l + 1).$$
This gives $2^{l+1} - 3^{k+1} = 1$. The only possibility is $l+1=2$ and $k+1=1$. This forces $k=0$, a contradiction. Hence $3 \le |S| < \infty$ is not possible.

Finally assume $S$ is an infinite set. Suppose there exists a prime $p$ not in $S$. Take $S = \{p_1(=2), p_2, \dots\}$

Consider $p_1 - 1, p_1p_2 - 1, \dots, p_1p_2 \dots p_p - 1$ modulo $p$. Since $p$ is not in $S$, none of them is equal to $0$. By pigeonhole principle, we can find $j < k$ such that
$$p_1p_2 \cdots p_j - 1 \equiv p_1p_2 \cdots p_j p_{j+1} \cdots p_k - 1 \pmod{p}.$$
Hence $p$ divides $p_1p_2 \cdots p_j(p_{j+1} \cdots p_k - 1)$. But this contradicts the choice of $p$ that it is not in $S$. Hence $S$ is the set of all primes now.