Polynomial with integer coefficients: given values at point find minimal value for a point A polynomial $P(x)$ with integer coefficients satisfies the following: $P(5) = 25, P(7) = 49, P(9) = 81$. How do I find the minimal possible value of $|P(10)|$.
 A: We can write $p(x)=q(x)(x-5)(x-7)(x-9)+x^2$.
Now $p(10)=q(10)(10-5)(10-7)(10-9)+100=q(10) \cdot 5 \cdot 3 \cdot 1 +100=15 \cdot q(10)+100$
So we want $q(10)$ to be "as close as possible" to $-\frac{100}{15}=-6,67..$, i.e. we want $q(10)=-7$ and then $|p(10)|=|-15 \cdot 7 +100|=|-105+100|=5$. So for example take $q(x)=x-17$ and then we get the minimal value for $|p(10)|=5$.
EDIT: unicity of form for representing $p(x)$
Suppose $g(x) \neq x^2$ such that $g(5)=25, g(7)=49, g(9)=81$. Then $g(x)-x^2$ has  at least three roots, namely $5,7,9$ so $g(x)-x^2=r(x)(x-5)(x-7)(x-9)$ or in other words $g(x)=r(x)(x-5)(x-7)(x-9)+x^2$. Now we have two different representations for $p(x)$, i.e. $p(x)=q(x)(x-5)(x-7)(x-9)+x^2$ and $p(x)=h(x)(x-5)(x-7)(x-9)+g(x)$ , but we can substitute $g(x)=r(x)(x-5)(x-7)(x-9)+x^2$ inside the first representation for $p(x)$ and get 
$$p(x)=h(x)(x-5)(x-7)(x-9)+r(x)(x-5)(x-7)(x-9)+x^2=\\=[h(x)+r(x)](x-5)(x-7)(x-9)+x^2=q(x)(x-5)(x-7)(x-9)+x^2$$
where $q(x)=r(x)+h(x)$. So we can assume WLOG the representation $p(x)=q(x)(x-5)(x-7)(x-9)+x^2$.
A: Here's the theory (prove it!) behind the problem:

For a polynomial $P(x)$ with integer coefficients, if $ a_i, a_j \in \mathbb{N}$, then $ a_i-a_j \mid P(a_i) - P(a_j)$.   
Given (finitely many) values $a_i , b_i$ such that $a_i - a_j \mid b_i - b_j$ hold over all pairs, then there exists a polynomial $P(x)$ with integer coefficients such that $P(a_i) = b_i$ if and only if the interpolating polynomial has integer coefficients.

So $10 - 5 \mid P(10) - 25$, $10-7 \mid P(10) - 49$, $10-9 \mid P(10) - 81$.
So we require $ P(10) \equiv 0 \pmod{5}, P(10) \equiv 1 \pmod{3}$.
This gives $P(10) \equiv 25 \pmod{30}$.   
Hence, the minimum possible value of $|P(10)| = |-5| = 5$.
Thankfully, the interpolating polynomial has integer coefficients (check it), so this is truly the minimum. 

Proof:
First claim: $ a_i^n - a_j^n = (a_i-a_j) (a_i^{n-1}+a_i^{n-2}a_j+\ldots+a_j^{n-1})$.
So $(a_i - a_j)$ is a factor of $\sum p_k (a_i ^k - a_j ^k)$.   
Second claim: 
Given $2n$ values that satisfy the conditions, let the interpolating polynomial be $I(x)$.
If the interpolating polynomial has non-integer coefficients, 
let $P(x) = Q(x) \prod(x-a_i) + I(x)$ with $\deg(P) \geq n, \deg(I) \leq n-1$.
Let $k$ be the largest degree of $Q(x)$ that has a non-integer coefficient, then the coefficient of $x^{k+n}$ will be a non-integer, so no polynomial with integer coefficients exist.
Conversely,if the interpolating polynomial has integer coefficients, we are done.   
