1

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\}$.

Batominovski
  • 49,629
Hhhhhhhhhhh
  • 141
  • 7

1 Answers1

2

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.)

Batominovski
  • 49,629
  • Actually I suspected it to be using some algebraic number theory but your solution is really nice – Hhhhhhhhhhh Jul 13 '20 at 16:34
  • 1
    It is well known that a polynomial which has no rational roots but has root modulo p for each prime then degree of the polynomial must be atleast 5 which is proven by chebotarev density theorem – Hhhhhhhhhhh Jul 14 '20 at 04:11
  • @Hhhhhhhhhhh This is me, Batominovski. I am writing from my office's computer, and I couldn't figure out my password. Would you mind providing a proof of the claim in your comment above (perhaps as an answer, or as a part of your question)? This claim is not known to me. –  Jul 14 '20 at 11:55
  • @batominovski the proof is quite hard and hence it's just a difficult known result which uses chebotarev density theorem – Hhhhhhhhhhh Jul 14 '20 at 15:10
  • @Hhhhhhhhhhh Could you please give me some references? –  Jul 14 '20 at 15:11
  • It is a komal prob and while seeing the sol in pftb they mentioned this fact they have mentioned this fact on page 213 – Hhhhhhhhhhh Jul 14 '20 at 15:13
  • @Hhhhhhhhhhh I didn't understand that. What is a komal prob, and what is pftb? Also, on Page 213 of which book? – Batominovski Jul 14 '20 at 16:39
  • 1
    Search problems from the book on Google and see page 213 – Hhhhhhhhhhh Jul 14 '20 at 17:38