Prove that there exists a polynomial p(x) with coefficients belonging to the set {-1, 0, 1} such that p(3) = n, for some positive integer n

Question

Prove that there exists a polynomial p(x) with coefficients belonging to the set {-1, 0, 1} such that p(3) = n, for some positive integer n.

I started off my proof by noticing that n = either 3k or 3k±1 and that $p(x) = a_0+a_1x+a_2x^2+\cdots+a_nx^n$. It follows that $p(3) = a_0+3a_1+3^2a_2+\cdots+3^na_n$. Thus $p(3) = a_0+3(a_1+3a_2+\cdots+3^{n-1}a_n)$. We know that $a_0= -1,0 \text{ or }1$. Thus there exists a polynomial p(x) such that p(3)=3k, or 3k±1 = n. q.e.d.

Any help would be greatly appreciated. This is also my first time asking a question on this website so I apologize for my sloppy MathJAX skills.

Answer 1

There are $3^{n+1}$ strings $(a_0,a_1,...,a_n)$ which consists of entries in $\{-1,0,1\}$ and each string corresponds to a unique integer in the interval $[-(\frac{3^{n+1}-1}{2}),\frac{3^{n+1}-1}{2}]$ through the map $(a_0,a_1,...,a_n) \rightarrow \sum _{j=0}^n 3^ja_j$.

Hence every integer in the interval $[-(\frac{3^{n+1}-1}{2}),\frac{3^{n+1}-1}{2}]$ is attainable; letting $n \rightarrow \infty$ we have the result.

Answer 2

Hint: try using the expression of an integer $n$ in base 3. How would you write this expression algebraically?

EDIT: Here's how one might proceed with a solution. First, a claim:

Claim: any positive integer $n$ can be expressed uniquely in base $b$ for a positive integer $b > 1$. i.e. $n = a_0 + a_1b + \cdots + a_kb^k$ for $0 \leq a_i \leq b-1$.

Granting the claim for now, we can choose $b = 3$ and write: $$ n = a_0 + 3a_1 + 3^2a_2 + \cdots + 3^ka_3 $$ for $a_i \in \{0,1,2\}$. Now suppose $a_i = 2$. Then $3^i\cdot 2 = 3^i(3 - 1) = 3^{i+1} - 3^i$.

Thus $$n = \sum_i3^ia_i + \sum_j3^{j+1} - 3^j$$ for $i$ ranging over the terms with $a_i \not= 2$ and $j$ over the terms with $a_j = 2$. Hence $p(3) = n$ for $$ p(x) = \sum_i a_ix^i + \sum_jx^{j+1} - x^j $$ for $i$ and $j$ over the same ranges as above. This $p$ has the desired properties.

To prove the claim then, one could use the Euclidean algorithm, the basic fact for which says that for a positive integer $n$ and some positive integer $q < n$, one can find a unique pair of non-negative integers $b$ and $r$ such that $0 \leq r < q$ and $$ n = bq + r $$ Letting $q$ be the largest power $3^k$ will yield $b = a_k$ and then one can replace $n$ by $r$ and proceed by induction.

Answer 3

In the radix $\,3\,$ rep of $\,n\,$ replace digits $\,2\,$ by $\,-1\,$ via $\,(2)3^k = (3\!-\!1)3^k = 3^{k+1}-3^k,\,$ i.e. replace the digit $\,2\,$ by $-1$ then carry a $1$, doing least significant digits first so carries don't destroy prior work, e.g.

$$\begin{align} &\ \ \ \ \ \ \ 1,\ \ \ 1,\ \ \ \color{#c00}2 = 14 = 3^2 + 3 + 2\\ \to\ \ &\ \ \ \ \ \ \ 1,\ \ \ 2,\color{#0a0}{-1}\ \ \ \text{by replace $\,\color{#c00}2\,$ by $\,\color{#0a0}{-1}\,$ then carry $1$}\\ \to\ \ &\ \ \ \ \ \ \ 2,-1,-1\\ \to\ \ &1,-1,-1,-1\\ =\ \ &\! 27\!-\!9 - 3 - 1 = 14\end{align}$$

Remark $ $ More directly we can can show the existence of such a radix rep in the usual way, by iterating the division algorithm, but using least magnitude remainders in $\{-1,0,1\}.\,$ See also this related question on uniqueness of such reps.