A finite set $S$ containing no perfect powers such that, for any prime $p$, $x^n\equiv s\pmod{p}$ has a solution $(x,s)\in\mathbb{Z}\times S$

Question

Let $n$ be a positive integer. Prove that there exists a finite set $S$ of positive integers greater than $1$ with the following properties:

1. No element of $S$ may be expressed as $a^b$ with $a,b>1$.
2. For any prime $p$ there exists $s \in S$ and $x \in \mathbb{Z}$ such that $x^n \equiv s \ (\text{mod} \ p)$.

Note that the fact that cardinality of the set $S$ is greater than $1$ is a nontrivial problem in itself which requires Chebotarev density theorem, so any ideas?

For context, the case $n=2$ can be satisfied by $S=\{2,3,6\}$.

Answer 1

Let $p_1,p_2,p_3,\ldots$ be an enumeration of the prime natural numbers. Take $S$ to be the set of integers of the form $$p_ip_{i+1}\cdots p_{j-1}p_j\,,$$ where $i$ and $j$ are integers such that such that $1\leq i\leq j\leq n$. For example, if we use the enumeration of primes so that $p_1<p_2<p_3<\ldots$, then for $n=3$, $$S=\{2,3,5,2\cdot 3,3\cdot 5,2\cdot 3\cdot 5\}\,.$$

Let $r$ be an arbitrary positive integer. If $r\leq n$, then the congruence $x^n\equiv s\pmod{p_r}$ has a solution $(x,s)\in\mathbb{Z}\times S$ by taking $x:=0$ and $s:=p_r$. From now on, we suppose that $r>n$.

Suppose that $g_r$ is a generator of the multiplicative group $(\mathbb{Z}/p_r\mathbb{Z})^\times$. Suppose that $t_j$ is an integer such that $0\leq t_j <p_r-1$ and $p_j\equiv g_r^{t_j} \pmod{p_r}$, for each $j=1,2,\ldots,n$. It is an easy combinatorics exercise using the Pigeonhole Principle to show that there exist indices $i$ and $j$ such that $1\leq i\leq j \leq n$ and $n$ divides $t_{i}+t_{i+1}+\ldots+t_{j-1}+t_j$. Thus, by choosing an integer $x$ such that $$x\equiv g_r^{\left(\frac{t_{i}+t_{i+1}+\ldots+t_{j-1}+t_j}{n}\right)}\pmod{p_r}$$ and choosing $s\in S$ to be $p_{i}p_{i+1}\cdots p_{j-1}p_j$, we have $x^n\equiv s\pmod{p_r}$.

Remark. From the proof above, we see that $|S|=\dfrac{n(n+1)}{2}$. What is the smallest possible cardinality of such a set $S$? Can we find such a set $S$ with fewer than $\dfrac{n(n+1)}{2}$ elements? For $n=2$, it is clear that $|S|\geq 2$, but I have not yet found a way to show that $|S|\geq 3$.

Related Question. Does there exist a finite set $S$ of positive integers greater than $1$ such that, for any prime natural number $p$ and for any positive integer $n$, the congruence $x^n\equiv s\pmod{p}$ has a solution $(x,s)\in \mathbb{Z}\times S$? (The answer is no, per Carl Schildkraut's answer here.)