What is the minimum number of positive integer values at which uniquely determines a polynomial with integer co-efficients? Let $p(x)$ be a polynomial with positive integer co-efficients; then what is the minimum number $k$ (depending on $p(x)$) of distinct positive integer(s) $r_1,..,r_k$ such that knowing $p(r_1),...,p(r_k)$, $p(x)$ is uniquely determined? 
My work: $p(1)$ is the sum of all the co-efficients of $p(x)$; so if say $p(x)=a_nx^n+...+a_0$, then since all the  $a_i$'s are positive, so $a_i \le p(1)$; so letting $s:=p(1)$, 
$$b=p(s+1)=a_n(s+1)^n+...+a_1(s+1)+a_0$$ is a representation of the positive ineteger $b$ in base $s+1 (>1)$ since all the $a_i$'s are positive integers and $a_i<s+1$; since representation in any base is unique, so we thus uniquely determine the co-efficients of $p(x)$ if we know $p(1)$ and $p(1+p(1))$ i.e. $k=2$, $r_1=1,r_2=1+p(1)$. Am I correct? 
 A: Very nice. You got it spot on. I'm just going to basically spell out what you have in pedantic detail, in a slightly different way, just for assurance and some rigour. Right, so equivalently what you want to show is, for all pairs of natural numbers $r, s$, that there is a unique polynomial $p$, with positive integer coefficients, such that $p(1) = s$ and $p(1 + p(1)) = r$. That is, assume such a polynomial exists, and then show that all its $a_i$ are determined. 
Firstly, let's reiterate the following that you've already stated in your question. For each $a_i$, we have:
$$a_i \leq \sum_{i=1}^n a_i = p(1) = s < s + 1 \dots (1)$$
Now, we also are given $p(1 + p(1)) = p(s + 1) = r$. Now, we show that we can uniquely determine all the $a_i$. We show by induction that each $a_i$ is uniquely determined. For $a_0$, we note that $a_0 \equiv p(s + 1)$ (mod $(s + 1)$). But by $(1)$, $a_0 < s + 1$, and there is only one term less than $s + 1$ for any congruence class, mod $s+1$. Now, assume all $a_i$ are determined up to $a_k$. We can show that $a_{k+1}$ is determined. We can stretch things a bit and assume that $a_{k+1} = 0$ if $k+1$ is greater than the degree $n$ of the polynomial; this doesn't hurt the proof at all. So since we have all $a_i$ up to $a_k$, then we can compute the "sub polynomial" as follows:
$$s(k) = a_k(s + 1)^k + a_{k - 1}(s + 1)^{k-1} + \dots + a_0$$
Subtracting from $p(s + 1)$ we get:
$$p(s + 1) - s(k) = a_n(s + 1)^n + a_{n - 1}(s + 1)^{n-1} + \dots + a_{k + 1}(s + 1)^{k + 1} = (s + 1)^{k + 1}(a_n(s + 1)^{n - k - 1} + a_{n - 1}(s + 1)^{n-k -2} + \dots + a_{k + 1})$$
Divide by $(s + 1)^{k + 1}$ and we get:
$$a_n(s + 1)^{n - k - 1} + a_{n - 1}(s + 1)^{n-k -2} + \dots + a_{k + 1}$$
From here, just employ the same trick as before using congruences to get $a_{k + 1}$ and voila, the proof is done by induction!
