$S=\mathbb{Z}$ which can be proved using induction on $n$ and writing $2^{v_2(n)+\phi(\frac{n}{2^v_2(n)})}-2^{v_2(n)}$ in base $n$

My favorite ISL 2019 problem (among the ones i've solved) uwu. Hint I paid for the entire polynomial, I'm gonna use the entire polynomial The answer is $\mathbb{Z}$ only, which clearly works. Let $S$ be one such rootiful set. Initially we add all integers of the form $2^a - 2^b$ for positive integers $a, b$. We try to show that all other integers must follow. Let $P(a_0, a_1, \cdots, a_n) = a_0+a_1x+\cdots+a_nx^n$ for conciseness. Clearly $1$ is in the set; this can be seen by taking $P(2^1 - 2^2, 2^2 - 2^1) = P(-2, 2) = 2x-2$ which has root $x = 1$. Claim: $k \in S \Longrightarrow -k \in S$. Proof: $P(k, 1) = x + k$ has root $x = -k$. $\square$ Thus we just have to show all of $\mathbb{N}$ are in $S$. Let $k$ be the smallest positive integer not in $S$. Write $k = 2^e \cdot m$, where $e$ is a maximal positive integer (and thus $m$ is odd). Note that $m > 1$; it's easy to see that all powers of $2$ are already in $S$. Consider the integer $M = 2^{e + \phi(m) + 1} - 2^{e + 1} = 2^{e+1} \cdot (2^{\phi(m)} - 1)$, which is divisible by $m$ (Euler's theorem) and $2^e$ (by looking at $\nu_2$'s). Thus $M$ is divisible by $k$. We rewrite $M = \overline{b_n\cdots b_4b_3b_2b_10}_k$ in base k. Then consider the polynomial $$P(-M, b_1, b_2, \cdots, b_n)$$Clearly $-M = 2^{e + 1} - 2^{e + \phi(m) + 1} \Longrightarrow -M \in S$, and all the $b_i$ are nonnegative integers less than $k$ (which are in $S$ by hypothesis), so all integer roots of this polynomial are in $S$. But then it's easy to see that $k$ is a root of the entire thing, so $k \in S$. Thus we can get all of $S$. Yay! :DD

Wonderful problem indeed. $\textbf{Claim .}$ $S=\mathbb{Z}$ . $\textbf{Proof .}$ Assume the contrary that some integers from $\mathbb{Z}$ don't appear in $S$ and choose the one with the smallest absolute value among them , say it's $k$ . By our choice , all numbers up to $k-1$ are in $S$ . Take $a\neq b$ s.t. \[2^a\equiv 2^b\pmod{k}\]Writing $2^a-2^b$ in base $k$ \[2^a-2^b=a_0+a_{1}k+\dots+a_{n}k^n\]for some $0\leq{a_0,\dots,a_n}\leq{k-1}$ . Then it's clear that $k\mid{a_0}$ for all $k\in{\mathbb{N}}\implies{a_0=0}$ . So if we let \[P(x)=a_{n}x^n+\dots+a_{1}x+(2^b-2^a)\]we get $P(k)=0$ , and since all the coefficients of $P(x)$ are in $S$ , we have $k\in{S}$ , contradiction. $\blacksquare$ $\textbf{Edit :}$ I forgot to mention why $-k\in{S}$ that's because $1\in{S}$ (easy to see) and $k\in{S}$ , thus $-k$ as a root of the polynomial $x+k$ is in $S$.

Comment: Great problem, but not really number theory. It's necessary that $S=\mathbb{Z}$. First, we do some bash to prove the following claim. Claim: We have $0,1,-1\in S$ and $a\in S\implies -a\in S$ for any $a$. Proof. Obviously, $0\in S$. Note that $2,4\in S$ by condition. Hence we use $2x+4$ to get $-2\in S$. Then we use $2x-2$ and $2x+2$ to get that $1,-1\in S$. To prove the second statement, just use $x+a$. $\blacksquare$ Now we get more serious and induct on any positive integer $n$ to show that $n\in S$. We have done the base case. For inductive step, take $a,b$ such that $n\mid 2^a-2^b$ (possible with pigeonhole). By induction, $0,1,\hdots,n-1\in S$ hence we do the base $n$ representation $2^a-2^b = a_1n+a_2n^2+\hdots+a_kn^k$ to get the required polynomial.

This is a really cute problem ! We claim that $S=\mathbb Z$. Note that this clearly works. We start with some basic observations. Note that $0,2 \in S$. Also $1\in S$ as it is the root of $2x-2=0$. Note that this means that if $n\in S \implies -n \in S$. This is because $-n$ is a root of $x+n=0$. Hence we will only care about positive integers henceforth.

$n$ has a multiple of the form $2^a-2^b$. Let this multiple be $m$. Write $m$ in base $n$, so we have : $$m = \sum_{i=1}^{k} m_i \cdot n^i \implies \sum_{i=1}^{k} m_i \cdot n^i -m =0$$ Suppose $P(x) = \sum_{i=1}^{k}m_i \cdot x^i$. Note that the above expression says that $P(n)=0$, where all the coefficients of $P(x)$ are in $S$ (all the $m_i$'s are less than $n$ so they are in $S$ by strong induction. Also $m$ is defined to be in $S$. )Hence $n\in S$ and we are done by induction.

The answer is $S = \mathbb{Z}$. Let $c$ be an integer. Fix $n$ and consider sequences of positive integers $a_0, a_1, \ldots, a_n$ with $1 \leq a_i \leq n$ for all $0 \leq i \leq n$. There are $n^{n+1}$ such sequences. Notice that: $$|2^{a_0} + 2^{a_1}c + \cdots 2^{a_n}c^n| \leq 2^n \cdot (|1| + |c| + \cdots + |c|^n) = O((2c)^{n+1})$$Since $(2c)^{n+1} = o(n^{n+1})$ for sufficiently large $n$ there exist two sequences $a_0, a_1, \ldots, a_n$ and $b_0, b_1, \ldots, b_n$ such that: $$2^{a_0} + 2^{a_1}c + \cdots 2^{a_n}c^n = 2^{b_0} + 2^{b_1}c + \cdots 2^{b_n}c^n$$which means $c$ is in $S$. Remark: This solution was motivated by USA TST 2011 9. Alternative solution: Observe $0 \in S$. Take $n = 1, a_1 = a_0 = 0$. Then since every integer is a root of the zero polynomial we are done. The statement should require the $a_i$ to not all be $0$...

Define $S[x]$ is the set of all polynomial with all of coefficient belong to $S$ $0=2^{1}-2^{1}\in S$ $2x-2\in S[x]\Rightarrow 1\in S$ $\forall\ s\in S,\ x+s\in S[x]\Rightarrow -s\in S$ $\forall\ n\in\mathbb{N},\ 2^{n}=2^{n+1}-2^{n}\in S$ $\forall\ n=2^{p}q\in\mathbb{N},2\nmid q\ \exists\ s\text{ s.t. }n\ |\ N=2^p(2^s-1)$ $\Rightarrow N=\sum_{k=1}^{K}a_{k}n^{k},0\leq a_{k}<n$ using induction w.r.t n, $\sum_{k=1}^{K}a_{k}x^{k}-N\in S[x]\Rightarrow n\in S$ $\therefore\ S=\mathbb{Z}$

We claim that every integer belongs to the set S. First of all, if a is a positive integer belonging to S then x + a has root -a so -a also belongs to S so we need to show that all non-negative integers belong to S. 0 definitely belongs to S. 2 also belongs to S since 2 = 2^2-2. Now, 2x-2=0 has root 1 so 1 also belongs to S. Now, let k be the smallest natural that doesn't appear in S. We know that given any pair of integer m,n the powers of m become periodic after awhile or they become cyclic. Proof : Suppose not. Then they should never hit the same modulo again since if it does, it must become cyclic. But the set Z_p is finite which completes a contradiction. Hence, there exists a, b such that k divides 2^a - 2^b and in fact cycle(k) divides a - b but we'll not keep this fact in mind as it is not important. Now since k divides 2^a-2^b, 2^a-2^b can be written as a_0+a_1k^1...... so on. But this means that the equation a_0 + a_1x^1...... - 2^a + 2^b = 0 has a root which belongs to S and it complete our proof by contradiction.

This is a nice problem with some Number Theory. Our Claim is S=Z Our Proof is: Assume that Z doesn't appear in S and choose the one with the smallest absolute value among them, say its k. By our choice, all numbers up to k-1 are in S. Now we can take that A is not equal to B. We can write 2^a-2^b in base k 2^a-2^ba(0)+a(1)(k)+...+a(n)k^n) for some 0<=a(0).....,a(n)<=k-1. Then it's clear that k divides a(0) for all k is an element of N which makes a(0)=0. Now we can let P(x)=ax(n)+....+a(1)x+(2^b-2^a). We now get that P(k)=0 and cause all of the coefficients in the polynomial P(x) are in S we have k is an element of S. Hence this is a contradiction and we are done. My other sol even though it has practically been posted couldn't think of any other ones. Same as post 5 acknowledges to them.

InternetPerson10 wrote: We say that a set $S$ of integers is rootiful if, for any positive integer $n$ and any $a_0, a_1, \cdots, a_n \in S$, all integer roots of the polynomial $a_0+a_1x+\cdots+a_nx^n$ are also in $S$. Find all rootiful sets of integers that contain all numbers of the form $2^a - 2^b$ for positive integers $a$ and $b$. nice problem but too bad that a simillar problem has been there. . the problem i am refering to is . . if $S$ is a set of integers such that it contains $0,2n$ with $n>2$ and the integer root of any polynomial with coefficient from the set $S$ is also in $S$ then prove $2,-2 \in S$. . we will use the idea from the above problem . first we will prove that all the integers are in $S$ clearly every power of $2$ is in $S$ and from $2x +(2 -8)$ gives $3 \in S$ . let $k$ be the minimal integer not in $S$ . now we need a $2^a -2^b$ being divisible by $k$ let $Ord_k 2=r$ and $r|a-b$ so lets write $2^a -2^b$ in the base $k$ as $a_1k +...+a_nk^{n}$ now clearly the polynomial $p(x)=a_n x^n+...+a_1x -2^a +2^b$ has the root $k$ and we are done . the problem i mentioned also solves with using a base $2$ representation

A02 wrote: Notice this statement is true for any sets T and S such that $S = \{x - y | x, y \in T\}$ where the $ith$ smallest element of $T$ is bounded above exponentially. Are you sure we even need this? Let $T=\{t_1,t_2,\dots,\}$ be any infinite set of integers. Fix $c$ which we want to show to be in $S$. Then allowing only $t_1,\dots,t_N$ as coefficients of the polynomial (where $N$ is some parameter not necessarily equal to $n$) we have $N^{n+1}$ possible polynomials but all values are bounded by \[(n+1)t_N \cdot c^n.\]So we win unless \[(n+1)t_N \cdot c^n>N^{n+1}.\]But fixing $N>c$ this is a contradiction for $n \to \infty$, regardless the size of $t_N$.

Much better than N2. I claim that our answer is $\mathbb{Z}$. Clearly this works; all integer roots of a polynomial are integers. Now FTSoC let $T$ be the set of integers $\not \in S$. Pick the number $m \in T$ for which $|m|$ is minimized. By assumption all numbers $m'$ with $|m'| < |m|$ are in $S$. Now, we are able to choose some $b_1 > b_2$ for which $m \mid 2^{b_1} - 2^{b_2}$ as they clearly always exist for all $m$; make $b_1$ large enough to kill the even factors of $m$ and we can kill the odd factors of $m$ by Euler's Totient. Now, write in base $|m|$,\[2^{b_1} - 2^{b_2} = c_{\ell}\ldots c_1c_0 \textbf{}_{|m|} = c_0 + c_1|m| + \ldots + c_{\ell}|m|^{\ell}.\]where all $c_i$ are in $[0, |m| - 1]$. Since $|m|$ divides $2^{b_1} - 2^{b_2}$, we must have $|m| \mid c_0 \implies c_0 = 0$. Consider the polynomial\[P(x) = c_{\ell}x^{\ell} + \ldots + c_1 - (2^{b_1} - 2^{b_2})\]where $|m|$ is clearly a root and all coefficients are clearly in $S$; note that this is true for the constant coefficient since it is in the form $2^a - 2^b$. Hence, $|m| \in S$ as well, a contradiction to our initial assumption. $\blacksquare$

We attempt to present a terse but complete solution. Note that $1,0,-1\in S$. By the polynomial $x+k$, note $k\in S\implies -k\in S$, and vice versa, so it suffices to show all nonnegative integers are in $S$, which we do with induction. To show $k\in S$, pick $k\mid 2^a-2^b$ with $a\ne b$ (by Pigeonhole, say), then consider the base $k$ expansion $\overline{a_na_{n-1}\dots a_1}_k$ of $2^a-2^b$ and consider the polynomial $a_nx^n+a_{n-1}x^{n-1}+\cdots+a_1x-2^a+2^b$ to finish.

Cute but sort of easy. We can prove the result by induction on the positives to show that all the positive numbers are in $S$, then show that if all the positive integers are in $S$, then all the negative numbers are also in $S$. It's also easy to see that $0 = 2^{1} - 2^{1} \in S$. Our base case is to show that $1$ is in $S$. This is true by $2x - 2 = 0$. For our inductive step, assume $1,2,\ldots n-1$ are in $S$, we show that $n$ is in $S$. Observe that there exists some $a,b$ such that $n | M = 2^{a} - 2^{b} < 0$ (this is true by pigeonhole principle on the residues class of $\mod n$). If $-M = \overline{b_{t}b_{t-1}\ldots b_{0}}_{n}$, we take the polynomial $x^{t}b_{t} + x^{t-1}b_{t-1} + \ldots x_{1}b_{1} + M$. All of $b_{0}, b_{1}, \ldots b_{n} \in S$ by our inductive hypothesis, and since $\overline{b_{t}b_{t-1}\ldots b_{0}}_{n} = -M$, we have $n^{t}b_{t} + \ldots nb_{0} = -M$, which also means $n$ is a root of that polynomial. Thus, $n\in S$, which completes our induction, so all positive numbers are in $S$. If all positive numbers are in $S$, then all negative numbers are also in $S$. To see this, for any $n > 0$, take the polynomial $x + n$, so $-n$ must also be in $S$. We conclude that $S = \mathbb{Z}$

InternetPerson10 wrote: We say that a set $S$ of integers is rootiful if, for any positive integer $n$ and any $a_0, a_1, \cdots, a_n \in S$, all integer roots of the polynomial $a_0+a_1x+\cdots+a_nx^n$ are also in $S$. Find all rootiful sets of integers that contain all numbers of the form $2^a - 2^b$ for positive integers $a$ and $b$. The answer is all integers. Firstly, define $L=\{2^n-1:n \in \mathbb{N}\}=\{1,3,7,15,31,\dots\}.$ Then the set of integers of the form $2^a-2^b$ with $a>b$ is precisely $L \cup 2L \cup 2^2L \cup \dots,$ so that $k \in L$ implies $2^{\alpha}k \in L.$ Observe that if $n \in S,$ then $-n$ is a root of $n+x=0,$ and hence $-n \in S.$ So we only need to show positive integers are in $S,$ which we do by induction. Let $m$ be the smallest positive number not in $S.$ Write $m=2^{\alpha}n$ with $n$ odd. Define $N=2^{\alpha+\varphi(n)}-2^{\alpha},$ so that $m \mid N$ and $N \in S.$ Consider the base $m$ representation of $N/m:$ $$\frac{N}{m}=a_0+a_1m+\dots+a_km^k.$$For any $i,$ $0 \le a_i<m,$ and hence $a_i \in S$ by the induction hypothesis. Now $m$ is a root of $$P(x)=-N+a_0x+a_1x^2+\dots+a_kx^{k+1},$$and hence $m \in S,$ completing the induction. $\square$

Tintarn wrote: A02 wrote: Notice this statement is true for any sets T and S such that $S = \{x - y | x, y \in T\}$ where the $ith$ smallest element of $T$ is bounded above exponentially. Are you sure we even need this? Let $T=\{t_1,t_2,\dots,\}$ be any infinite set of integers. Fix $c$ which we want to show to be in $S$. Then allowing only $t_1,\dots,t_N$ as coefficients of the polynomial (where $N$ is some parameter not necessarily equal to $n$) we have $N^{n+1}$ possible polynomials but all values are bounded by \[(n+1)t_N \cdot c^n.\]So we win unless \[(n+1)t_N \cdot c^n>N^{n+1}.\]But fixing $N>c$ this is a contradiction for $n \to \infty$, regardless the size of $t_N$. Good point, I'll edit my post.

A lot of people seemed to give a great deal of praise to this problem. I found it good, but slightly underwhelming. Still probably the best in the 2019 shortlist I've solved so far, aside from maybe 2019 C3. The answer is $S=\mathbb{Z}$, which obviously works. Let $P(a_0,a_1,\ldots,a_n)$ denote the polynomial $a_0+a_1x+\cdots+a_nx^n$. We prove the following lemma: Lemma: If $a \in S$, then $-a \in S$. Proof: First observe that $2=2^2-2^1 \in S$, and $-2=2^1-2^2 \in S$. Now from $P(2,-2)$, we get that $1 \in S$. Suppose $a \in S$. Then from $P(a,1)$ we get $-a \in S$. $\blacksquare$ Also observe that $0=2^1-2^1 \in S$. I will now show that $\mathbb{Z^+} \subseteq S$. Suppose otherwise, for the sake of contradiction. Then let $k$ be the least positive integer not in $S$; clearly $k \geq 2$. Then pick $a>b$ such that $k \mid 2^a-2^b$, which clearly exist. Denote $2^a-2^b$ as $N$ for convenience. We now write $N$ in base $k>1$; let $$N=(\overline{b_mb_{m-1}\cdots b_1b_0})_k.$$Since $k \mid N$ we have $b_0=0$. Further, as $0\leq b_i<k$ for all $1 \leq i \leq m$, we have $b_i \in S$ for all $1 \leq i \leq m$ due to the minimality of $k$. Now consider $P(-N,b_1,b_2,\ldots,b_m)$, which works since $N \in S \implies -N \in S$. Since $b_0=0$, $k$ is a root of this polynomial, hence $k \in S$—contradiction. Therefore no such $k$ exists, so every positive integer is in $S$. From our lemma, this implies that every negative integer is in $S$ as well. We previously proved $0 \in S$, so we're done. $\blacksquare$

$S = \mathbb Z.$ Note $0,$ $1$ are in $S,$ and if $s\in S,$ the polynomial $s + x$ asserts $-s \in S$ too. Thus it remains to prove $\mathbb N_{>0} \subset S.$ We prove this by induction. Suppose $1,\dots, k-1 \in S.$ Note there must exist some pair $a,b$ such that $2^a \equiv 2^b \pmod k$ for bounding reasons. As a result, all $x$ satisfying the following must be in $S$ as well: $$2^a-2^b = a_1x + \cdots + a_n x^n,$$Considering the unique base $k$ representation of $2^a - 2^b$ implies $k\in S$. $\blacksquare$

InternetPerson10 wrote: We say that a set $S$ of integers is rootiful if, for any positive integer $n$ and any $a_0, a_1, \cdots, a_n \in S$, all integer roots of the polynomial $a_0+a_1x+\cdots+a_nx^n$ are also in $S$. Find all rootiful sets of integers that contain all numbers of the form $2^a - 2^b$ for positive integers $a$ and $b$. This one is lit First of all, note that \(k\in S\) implies \(-k\in S\) because \(x+k=0\) has the root \(x=-k\) and so \(1\in S\) (\(kx-k=0\)). Now, we will show that all \(\mathbb{N}\) elements belong to \(S\) which will prove that \(S\) and \(\mathbb{Z}\) coincide. We prove this by induction with the base case clear, let this work for all \(1\) to \(k-1\), then for \(k\), choose \(a\neq b\) so that \(k\mid 2^a-2^b\) and writing \(2^a-2^b\) in base \(k\) gives \[2^a-2^b=a_0+a_1k+\hdots+a_nk^n\]and since all \(a_i<k\), they are in \(S\). Moreover \(a_0=0\), so \[(2^b-2^a)+a_1k+\hdots+a_nk^n=0\]But since \(k\) is a root of this equation, we get that \(k\in S\) too, completing the inductive step and hence the proof.

The answer is $\boxed{S= \mathbb{Z}}$, or equivalently $S$ is the set of all integers. It's easy to check that this indeed satisfies the problem conditions. We now show this is the only one that does. Let $f(a_0,a_1,\ldots, a_n)$ denote the polynomial $a_0+a_1x + \cdots + a_nx^n$. We have $2^3 - 2^2 = 4\in S$, $2^2 - 2^1=2\in S$, and $2^2 -2^2 = 0\in S$. $f(4,2): 2x+4 = 0\implies -2\in S$. $f(2,2): 2x+2=0\implies -1\in S$. $f(-2,2): 2x-2=0\implies 1\in S$. For any positive integer $m\in S$, $P(m,1): x+m$, so $-m\in S$ also. Thus, it suffices to prove that all positive integers are in $S$. Suppose not. Let $k$ be the smallest positive integer not in $S$. Now choose positive integers $a\ne b$ such that $k\mid 2^a - 2^b$ (this is possible by pigeonhole as there are infinitely many powers of $2$). Let \[2^a - 2^b = b_1 k + b_2 k^2 +\cdots + b_n x^n, \]where $0\le b_1, b_2, \ldots, b_n\le k-1$. This is possible because of the base $k$ representation of $2^a - 2^b$. We have $-(2^a - 2^b) = 2^b - 2^a\in S$, and all the $b_i$ are in $S$ because $0\le b_1, b_2, \ldots, b_k\le k-1$. $f(2^b - 2^a, b_1, b_2,\ldots, b_n): 2^b - 2^a + b_1 x + b_2 x^2 + \cdots + b_nx^n$. Note $k$ is a root of this polynomial, so $k\in S$, contradiction. So all positive integers are in $S$, now by the condition that $m\in S\implies -m\in S$, we have that all integers are in $S$.

We claim $S = \mathbb{Z}$ is the only rootiful set. Let $S$ be a rootiful set. Note that $2 = 2^2 - 2^1 \in S$, $-2 = 2^1 - 2^2 \in S$ and $0 = 2^1 - 2^1 \in S$. Taking roots of $2x - 2$ yields $1 \in S$. Also, $z \in S$ iff $-z \in S$. Assume for sake of contradiction that $S \neq \mathbb{Z}$. By the Well-Ordering Principle, there exists a smallest positive integer $k$ not in $S$. Evidently, $k \geq 2$. Write $k = 2^rs$ where $s$ is odd. Observe that $k \mid 2^{r + \phi(s)} - 2^r$. We can write $2^{r + \phi(s)} - 2^r$ in base $k$: \[2^{r + \phi(s)} - 2^r = a_1k + a_2k^2 + \cdots + a_nk^n,\]where $0 \leq a_n, a_{n-1}, \dots, a_1 \leq k - 1$. By minimality of $k$, $a_1, a_2, \cdots, a_n \in S$. Note that $2^{r + \phi(s)} - 2^r$ and $k$ is a root of \[a_nk^n + \cdots + a_1k + (2^r - 2^{r + \phi(s)}) = 0,\]and thus $k \in S$. Contradiction. Therefore $S = \mathbb{Z}$.

The only such set is $S=\mathbb{Z}$. First, we can see that $0$ and $1$ are in $S$. Next, if $a$ is in $S$, then $-a$ is in $S$ as it is a root of $a+x$. Hence it suffices to show that all positive integers are in $S$. Now suppose otherwise, and let $m$ be the smallest positive integer not in $S$ (clearly $m>1$). Write $m=2^k \cdot q$ where $q$ is odd. Since $q$ is odd, $q \hspace{0.3em} | \hspace{0.3em} 2^{\phi(q)}-1 \implies m \hspace{0.3em} | \hspace{0.3em} 2^{\phi(q)+k} - 2^k$. Let $M=2^{\phi(q)+k} - 2^k$. Then $M$ and $-M$ are in $S$. Now, let $M=a_rm^r+a_{r-1}m^{r-1}+\cdots+a_1m$ be the base-$m$ expansion of $M$. Consider the polynomial \[a_rm^r+a_{r-1}m^{r-1}+\cdots+a_1m-M\]Since $a_1,a_2, \cdots a_r$ are between $0$ and $m-1$ so they are in $S$ by assumption. Therefore $m$ is in $S$ as it is a root of that polynomial, contradiction! Thus, $S=\mathbb{Z}$ and we are done.

This is an awesome problem! Claim1: $1\in S$. Claim2: $a\in S\implies -a\in S$. $S=\mathbb{Z}$! Note that $m$ is the first positive integer that is not in $S$, so all integers from 0 to $m-1$ are in $S$. We will use a number like $K$ of the form $2^c-2^b$.Write $K$ in base $m$, so we have $a_0, a_1, \cdots, a_n $ such that for every i from 1to n we have: 0\leq $a_i$ < $m$. $a_0+a_1m+\cdots+a_n m^n$=$K$ If $a_0$ be zero we are done! Take $p(x)=a_n x^n+...+a_1x -2^c +2^b$ , so obviously $m$ is a root of $p(x)$ and because $a_i$ and $2^c-2^b$ sre in $S$ so $m \in S$. So we just need to find $c$ and $b$ such that $a_0$ be zero and it happen when: $m\mid 2^c-2^b=k$ Take $c=b+varphi(m)$ and a big enough $b$.Done.

The only set is $S = \mathbb{Z}$, which clearly works. First note that $2 = 2^2 - 2^1$, $-2 = 2^1 - 2^2$, and $0 = 2^1 - 2^1$ are in $S$. Then the polynomial $2x-2$ gives $1 \in S$. Furthermore, if $a \in S$, then $x+a$ has root $-a$, so $-a \in S$. Also, if $a \in S$ is even, then $2x-a$ has root $\frac{a}{2}$, so $\frac{a}{2} \in S$. As a result, by dividing by 2 if needed, $2^a - 2^b \in S$ for all nonnegative integers $a$, $b$. Now we will prove that all positive integers $x$ are in $S$, by strong induction on $x$. Assume $x \ge 3$ and that $0, 1, \dots, x-1 \in S$. Then let $x = 2^p \cdot q$ where $p$ is a nonnegative integer and $q$ is odd. Then let \[K = 2^p(2^{\phi(q)} - 1) = 2^{p + \phi(q)} - 2^p.\]Note that $K \in S$, and $x \mid K$ by Euler's theorem. Represent $K$ in base $x$ as \[K = d_1x + d_2x^2 + \dots + d_kx^k,\]or $-K + d_1x + d_2x^2 + \dots + d_kx^k = 0$, where $0 \le d_i < x$ for all $1 \le i \le k$. Therefore a polynomial with coefficients in $S$ has an integer root $x$, so $x \in S$, as desired. Then all nonpositive integers are in $S$ as well, and we are done.

Note that $-2$ and $2\in S$ therefore taking polynomials $2x+2$ and $2x-2$, $-1$ and $1\in S$. Now, if $k\in S$ then $x+k$ means $-k\in S$ so we only need to show for the nonnegative integers. Note that $2x$ implies $0\in S$. Suppose $0$, $1$, $\dots$, $k-1\in S$ then let $k\mid 2^a-2^b$ and $2^a-2^b=a_nk^n+a_{n-1}k^{n-1}+\dots + a_1k$ where $a_n$, $a_{n-1}$, $a_{n-2}$, $\dots$, $a_1$ are between $0$ and $k-1$ inclusive. Then, $k$ is a root of \[a_nk^n+a_{n-1}k^{n-1}+\dots + a_1k+(2^b-2^a)\]so we are done.

The answer is $\boxed{\mathbb{Z}}$ only, which obviously works. We will prove that every rootiful set of integers contains every integer. Let $T$ be the set of numbers of the form $2^a-2^b$ for positive integers $a$ and $b$ and let $S$ be our rootiful set. Note that $T\subseteq S$, $0\in T$, $-2\in T$, $2\in T$, and $1\in S$ because of $2-2x$. Now, if $k\in S$, then the polynomial $k+1x$ gives us $-k\in S$. Lemma 1. For every positive integer $k$, there is a positive multiple of $k$ in $T$. Proof. Consider the set of all $2^a$ for positive integers $a$. By pigeonhole, two different elements of this set must have the same residue mod $k$, so we can just take their positive difference. We now prove by strong induction that every positive integer $k\in S$. Since $2^1-2^1=0\in S$, by the previous claim, this will finish. We already proved base case $k=1$ above. For the inductive hypothesis, suppose that $1$, $2$, $\dots$, $k-1$ are all in $S$. Now choose an element $t\in T$ such that $k\mid t$, possible by lemma 1. Since $t\in T$, $t\in S$ so $-t\in S$. Let $t$ in base $k$ be $\left(d_nd_{n-1}\dots d_2d_1d_0\right)_{(k)}$. Since $k\mid t$, $d_0=0$. So the polynomial \[d_n x^n+d_{n-1}x^{n-1}+\dots+d_2x^2+d_1x-t\]has $k$ as an integer root, so $k\in S$, completing our induction. $\blacksquare$

Take $S$ minimal for which this holds. Then, call the degree of a number $s \in S$ to be $1$ more than the inf of the max of the degree of coefficients over all polynomials. Set the degree of $2^a - 2^b$ to be $0$. Claim: If $x \in S$ then $-x \in S, 2x \in S$. Proof. Induct on degree. Base case follows by considering $2^a - 2^b$ and $2^b - 2^a$, and $2^a - 2^b$ and $2^{a+1} - 2^{b+1}$. $\blacksquare$ Claim: If $1$ through $k$ are in $S$, then $k+1$ in $S$. Proof. Take $k \mid 2^K - 2^N \in S$. Then if $2^K - 2^N = \overline{a_na_{n-1}\dots a_10}_{k+1}$, it follows that taking $a_0 = 2^N - 2^K$ finishes. $\blacksquare$

Let $k$ be the minimal positive integer not in $S$. Pick $k\mid a_0=2^a-2^b$ which is always possible by Euler. Then, consider $P(x)=-k+a_1x+a_2x^2+\dots+a_nx^{n}$ where $k=\overline{a_na_{n-1}\dots a_0}_n$. Then, $k$ is a root of $P$, finishing since $x+k$ implies $-k \in S$

I claim that $S = \mathbb{Z}$. Note that $0,1 \in S$ by taking $(2^a - 2^b)x = 0$, $(2^a - 2^b)x + 2^b - 2^a = 0$ Claim: If $k \in S \implies -k \in S$. Proof: Take $x + k = 0$. Now we just have to show that all the positive integers are in $S$. To do this, we induct on $n$ where we have already shown base case $n = 1$. Take $N = 2^{\nu_2(n)+\varphi({\frac{n}{2^\nu_2(n)}})} - 2^{\nu_2(n)}$. Note that $n \mid N$. Now let $\overline{a_ma_{m-1} \dots a_1a_0}$ be the representation of $\frac{N}{n}$ in base $n$. Now take polynomial $a_mx^{m+1} + a_{m-1}x + \dots +a_1x^2 + a_0x - N = 0$. Since, $a_i < n$, we get that $n\in S$ and we are done.

Hint: base $n$ representation. We show that $S=\mathbb Z$. Note that $a=b$ gives $0\in S$, and $a=2,b=1$ gives $2\in S$. So, $2x+2=0$ has $x=-1$ which means $-1\in S$. Take $a=1,b=2$ to get $-2\in S$. So, $2x-2=0$ gives $x=1\in S$. So, for any $n\in S$, we have $x+n=0$ which means $-n\in S$. So, we only need to show that $\mathbb{N}=S$. We induct on $n$. Base case $n=2$ is done above. Now, for $n>1$, consider $\{2^2-2,2^3-2,\ldots,2^{n+1}-2\}$. If none of them are divisible by $n$, then $2^a-2\equiv 2^b-2\pmod{n}$ for some $a\ne b$ by pigeonhole principle. Hence, $n\mid 2^a-2^b$. Finally, note that we may write \[2^a-2^b=c_0+c_1n+c_2n^2+\cdots+c_kn^k\]where $0\leq c_i < n$ and $c_0=0$. So, the polynomial \[(2^b-2^a)+c_1x+c_2x^2+\cdots+c_kx^k=0\]gives the required root. The induction is complete. $\blacksquare$

Solved with GoodMorning

The answer is all integers. Note that since $-2$ and $2$ are both in the set, $1$ also is, and obviously $0$ is. Furthermore, taking $a_0=a_1$ gives $-1$ in the set. Since we have $-1$, we see that $n$ is in the set if and only if $-n$ is. We claim that all positive integers must be in the set. We will use induction. Since $0,1,2$ are in the set, we will show that for $k\geq 3$, $0$ through $k-1$ being in the set implies $k$ also is. The idea is that $$(k-1)k^{n-1}+(k-1)k^{n-2}\dots +(k-1)k+(k)1=k^n.$$However, unfortunately we cannot use this directly since we do not know that the constant coefficent of $k$ is in the set (the $x^n$ coefficient being $-1$ is fine since that is in the set). Thus, if there is some multiple of $k$ already in the set, by picking large enough $n$, we can have the constant coefficent "borrow" from all the other ones and reach said multiple of $k$. As long as $n$ is sufficiently large, by base $k$ this can be done so that all other coefficents are still from $0$ to $k-1$ inclusive, so by induction hypothetsis we are done. However, since $2^a\pmod{k}$ is eventually periodic, there exist large multiples of $k$ that are in the set, hence done. Remark: The idea is essentially to "propagate out" from the set we are originally given. It is not too hard to see that it's quite easy to fill in the gaps between the numbers, suggesting that the answer is all integers. The main motivation for looking at a specific number in order to induct is that, it's very hard to think about the roots of a polynomial from the perspective of the coefficients, but it's much easier to fix the input and then try to construct the coefficients, which is essentially what we are doing here. The induction hypothesis is "barely not enough", since if all lower coefficients are as high as possible $(k-1)$, we are still one short. However, this is where the given elements come in, as we are now able to pick out a large constant coefficent.

The answer is $S =\mathbb Z$ only. In particular, I will show by induction that every $n \in \mathbb N$ is a member of $S$, from where it follows that $S = \mathbb Z$ (just flip signs of odd-degree terms in the argument). Now, verify that $n=1, 2$ are members of $S$ for the base case. To show the inductive step, notice that there are always positive integers $a, b$ such that $n \mid 2^a - 2^b$. To see this, let $n = 2^{\nu_2(n)}k$, from where we can let $b = \nu_2(n)$ and $a = b+\varphi(k)$. Let $\ell = 2^a - 2^b$ and $k = \left \lceil \log_n (2^a - 2^b) \right \rceil$. Define sequences $\{a_i\}$ and $\{b_i\}$ recursively as follows: we have $a_k = 1$, $b_k = n^k$, and for each $i \leq k-1$, $a_i$ is the largest nonnegative integer such that \[b_i = b_{i+1} - n^i a_i \geq \ell.\]Claim. $a_i < n$ for each $i$. Proof. Assume that $i$ is the maximal index with $a_i \geq n$, so \[\ell \leq b_{i+1}-n^i a_i \leq b_{i+1} - n^{i+1}\]implying $b_{i+1} \geq n^{i+1} + \ell$. But then \[b_{i+2} - (a_{i+1} + 1) n^{i+1} = b_{i+1} - n^{i+1} \geq \ell\]which contradicts maximality of $a_{i+1}$. $\blacksquare$ In particular, the above shows that $b_i < n^i + \ell$ for each $i$. Now consider the polynomial \[P(x) = x^k - a_{k-1} x^{k-1} - a_{k-2} x^{k-2} - \cdots - a_1 x - \ell.\]Observe that the coefficients of this polynomial are $1, a_{k-1}, \dots, a_1, \ell$, all of which are in $S$ by the inductive hypothesis. Furthermore, recursively, we see that $b_{k-i}$ constitutes the first $i + 1$ terms of $P(n)$. In particular, $b_1 = P(n) + \ell$ is less than $n + \ell$, thus it is precisely $\ell$. It follows that $P(n) = 0$, and by definition we have $n \in S$, as needed. Remark: There's nothing special about $2^a - 2^b$. As long as we pick a starting set $S$ such that every $n \in N$ as a multiple in $S$, the argument works the same way.