By the Remainder Theorem we can write $Q(x)-n=(x+5)(x+2)P(x)$, where $P(x)$ is also a polynomial with integer coefficients. If we write $Q(x)=q_0+q_1 x+q_2x^2+\cdots$, $P(x)=p_0+p_1 x+p_2x^2+\cdots$, then \begin{eqnarray*} q_0-n&=&10p_0\\ q_1&=&10p_1+7p_0\\ q_i&=&10p_i+7p_{i-1}+p_{i-2} \text{ for }i\geq 2\\ \end{eqnarray*} We can work down this list to determine all $p_m$ and $q_m$ uniquely: each $q_i$ is uniquely determined by $p_0,p_1,...p_{i-1}$ and the fact that $q_i$ is an integer between 0 and 9, and then each $p_i$ is uniquely determined by $p_0,p_1,...p_{i-1}$ and $q_i$.

So if $n=0$, that polynomial is $Q(x)=0$ for all $x$?

Yes. That brings up a point- why does this process terminate? You've got uniqueness, but you haven't proved existence yet. This was on the first USAMO I took- I don't think I got anywhere on it at the time.

MithsApprentice wrote: Prove that for any integer $n$, there exists a unique polynomial $Q$ with coefficients in $\{0,1,\ldots,9\}$ such that $Q(-2) = Q(-5) = n$. Algorithm for $Q(x): =\sum\limits_{k=0}^{m}a(k)x^k \; , \; \; m\ge 2 .$ Let $n\in {\mathbb Z}$ and denote by $\lfloor \cdot \rfloor$ the floor-function ( integral part). STEP 1. Define \[ \begin{array}{|lcl|} \hline &&\\ b(0)&=& -\; \left\lfloor \ds \frac{ n }{10}\right\rfloor \\ &&\\ b(1)&=& -\; \left\lfloor \frac{7b(0)}{10}\right\rfloor \\ &&\\ \hline \end{array}\; . \] STEP 2. Find the integers $b(2) , b(3),...,b(\nu),b(\nu +1),b(\nu+2), ...$ using the rule \[ (***)\; \; \; \; \; \; \begin{array}{|c|} \hline \\ b(k)= -\; \displaystyle \left\lfloor \frac{7b(k-1)+b(k-2)}{10}\right\rfloor \; ,\; 2\le k \\ \\ \hline \end{array}\; . \] Therefore, using (***) it's possible to find the numbers $b(k) \; ,\; k\ge 2\; ,$ from the table \[ \begin{array}{||c||c|c|c|c|c|c|c|c||} \hline\hline {\mathbf k}&2&3&4&\ldots & \nu &\nu+1& \nu+2&\ldots\\ \hline {\mathbf b(k)}&b(2)&b(3)&b(4)&\ldots & b(\nu) & {\mathbf 0}& {\mathbf 0}&\ldots\\ \hline\hline \end{array}\; . \] If a certain step two consecutive are zero, e.g. $b(\nu+1)=0$ and $b(\nu+2)=0$ , then STOP and $\begin{array}{|c|} \hline m: =\nu: = \mbox{degree} [Q]\\ \hline \end{array} .\;$ A justification is that from (***) we have \[ b(\nu+3)=b(\nu+4)=\ldots =0 \; . \] STEP 3. By means of the system of numbers $\{b(0),b(1),b(2),\cdots,b(m-2)\}$ we compute numbers $\{a(0),a(1),a(2),\cdots,a(m)\}$ where \[ \left\{\begin{array}{lclcl} a(0)&=&n+10b(0)&=& n-10\left\lfloor \frac{n}{10}\right\rfloor \\ a(1) &=&7b(0)+10b(1)&=& -7\left\lfloor \frac{n}{10}\right\rfloor-10\left\lfloor \frac{7b(0)}{10}\right\rfloor \end{array}\right.\; . \] \[ \begin{array}{|lcl|} \hline a(k) &=&10b(k)+7b(k-1)+b(k-2)\\ a(m-1)&=&b(m-3)+7b(m-2)\\ a(m)&=&b(m-2)\\ \hline \end{array}\; \; ,\; \; 2 \le k\le m-2 \] Questions: 1) Find the polynomial $Q\in {\mathbb Z}[x]$ ,of minimal degree $m$ , having all coefficients in the set $\{0,1,2,...,9\}$ such that \[ P(-2)=P(-5)=2006\; . \] 2) (Unsolved) To find bounds for $m: {\mathbb Z} \to \{2,3,...\}$ , $m: =m(n) \;$ , $m$ being the minimal degree in the posted problem .

Let $c_k=|b_k|$. It is obviosly that $c_k\le \frac 45 c_{k-1}<cb_{k-1}$. Therefore $c_m=0$ for $m>\frac{ln(n)}{ln(1.25)}$.

Rust wrote: Let $c_k=|b_k$. It is obviosly that $c_k\le \frac 45 c_{k-1}<cb_{k-1}$. Therefore $c_m=0$ for $m>\frac{ln(n)}{ln(1.25)}$. Nice, but a question ! What means $c_k=|b_k$ ? It's $c_k=|b_k|$ ? It's possible to find an upper bound for $m$ ?

I'm very interested in this exercise, & i'm searching for a solution with continued fraction...it seems to me the value have the particularity that division by 2 and/or 5 doesn't make a infinite periodic reminder different by 0

From mo around the world 1997-98 book:

Assumption: $\displaystyle{Q(x) = \sum_{i=0}^m a_i x^i,\; (a_i\in\{0,1,2,3,4,5,6,7,8,9\},\quad m_0 = n = n_0)}$ Algorithm : $\begin{cases}m_i & \overset{0\le r<2}{\equiv} r\pmod{2}\\n_i & \overset{0\le s<5}{\equiv} s\pmod{5}\end{cases} \implies a_i = \begin{cases} s, & r - s\equiv 0\pmod{2}\\ s +5, & r-s \equiv 1\pmod{2} \end{cases}$                    $m_{i+1} = (m_i - a_i)/(-2),\quad n_{i+1} = (n_i -a_i)/(-5)$ Examples:  (1) $m_0 = n_0 = n = -10$        $\begin{array}{lll}a_0 = 0, & m_1 = 5, & n_1 = 2\\ a_1 = 7, & m_2 = 1, & n_2 = 1\\ a_2 = 1, & m_3 = 0, & n_3 = 0\\ a_3 = 0, & m_4 = 0, & n_4 = 0\\ \cdots\end{array}$        $Q(x) = x^2 + 7x$     (2) $m_0 = n_0 = n = 18$        $\begin{array}{lll}a_0 = 8, & m_1 = -5, & n_1 = -2\\ a_1 = 3, & m_2 = 4, & n_2 = 1\\ a_2 = 6, & m_3 = 1, & n_3 = 1\\ a_3 = 1, & m_4 = 0, & n_4 = 0\\ a_4 = 0, & m_5 = 0, & n_5 = 0\\ \cdots\end{array}$        $Q(x) = x^3 + 6x^2 +3x + 8$    (3) $m_0 = n_0 = n = 23$        $\begin{array}{lll}a_0 = 3, & m_1 = -10, & n_1 = -4\\ a_1 = 6, & m_2 = 8, & n_2 = 2\\ a_2 = 2, & m_3 = -3, & n_3 = 0\\ a_3 = 5, & m_4 = 4, & n_4 = 1\\ a_4 = 6, & m_5 = 1, & n_5 = 1\\ a_5 = 1, & m_6 = 0, & n_6 = 0\\ a_6 = 0, & m_7 = 0, & n_7 = 0\\ \cdots\end{array}$        $Q(x) = x^5 + 6x^4 + 5x^3 +2x^2 +6x +3$

This is sort of the mo sol, except I avoided the intricate stuff by reducing it to a casework bash. We prove both uniqueness and existence by providing a construction: By the remainder theorem, it follows that Q(x) = $(x^2+7x+10)(r_k \cdot x^k + r_{k-1} \cdot x^{k-1} + \dots + r_1 \cdot x^1 - r_0) + 10r_0+c$, where $r_i \in (0, 1, 2, \dots 9), \forall i \geq 1, c \in (0, 1, 2, \dots 9)$ and $r_0$ is an integer. Since n = $10r_0 + c$, $r_0\ and\ c$ are uniquely determined. Specifically, c is the residue of n mod 10, and $r_0 = \frac{n-c}{10}$. We now prove that each $r_i$ is uniquely determined. $\textbf{Lemma One}$: Each $r_i$ is uniquely determined from $r_0$. We have that $r_i = -\lfloor\frac{7r_{i-1} + r_{i-2}}{10}\rfloor$. Using the base cases of $r_{-1} = 0$ and $r_0$ to be defined as before, it follows that each $r_i$ is uniquely determined by induction. The procedure terminates when $r_k$ = 1 or 2, since any other value would make the coefficient of the $x^{k+1}$ term or $x^{k+2}$ term not among the ten digits specified in the problem statement. Any following $r_i$ would have to equal zero (by the procedure given above), which proves uniqueness. Now we want to prove existence, or that repeating this procedure actually gives a finite polynomial. For this, we need another lemma: $\textbf{Lemma Two}$ The above procedure eventually yields $r_k$ = 1, 2 or a special case for all n. For this, we note that $\mid r_i \mid < \mid r_{i-1} \mid$, with exceptions at $(r_{i-1}, r_{i-2}) = (-6,-9), (-6,-8), (-5,-9), (-5,-8), (-5,-7), \dots (3, 9) $. This follows from looking at the recursion formula for $r_i$. For these special cases, we can test by hand that the polynomial terminates using the recursion. For all other cases, trivial bounding suffices. Since $\mid r_i \mid$ is monotonocally decreasing (with a few exceptions which we can compute and show that it terminates), $\mid r_i \mid$ eventually reaches one of our special cases, one or two. If $r_i$ is positive and not one of our special cases, it equals one or two and we're done. If it's negative one or negative two, we can just test these by hand and we're done. And we have already shown the special cases. So the process terminates, hence proving existence.

If we let \[ Q(x) = \sum_{k \ge 0} a_k x^k \]then $a_k$ is uniquely determined by $n \pmod{2^k}$ and $n \pmod{5^k}$. Indeed, we can extract the coefficients of $Q$ exactly by the following algorithm: Define $b_0 = c_0 = n$. For $i \ge 0$, let $a_i$ be the unique digit satisfying $a_i \equiv b_i \pmod 2$, $a_i \equiv c_i \pmod 5$. Then, define \[ b_{i+1} = \frac{b_i - a_i}{-2}, \qquad c_{i+1} = \frac{c_i - a_i}{-5}. \] The proof is automatic by Chinese remainder theorem, so this shows uniqueness already. The tricky part is to show that all $a_i$ are eventually zero (i.e.\ the ``existence'' step is nontrivial because a polynomial may only have finitely many nonzero terms). In fact, we will prove the following claim: Claim: Suppose $b_0$ and $c_0$ are any integers such that \[ b_0 \equiv c_0 \pmod 3.\]Then defining $b_i$ and $c_i$ as above, we have $b_i \equiv c_i \pmod 3$ for all $i$, and $b_N = c_N = 0$ for large enough $N$. Proof. Dropping the subscripts for ease of notation, we are looking at the map \[ (b, c) \mapsto \left( \frac{b-a}{-2}, \frac{c-a}{-5} \right) \]for some $0 \le a \le 9$ (a function in $b$ and $c$). The $b \equiv c \pmod 3$ is clearly preserved. Also, examining the size, If $|c| > 2$, we have $\left\lvert \frac{c-a}{-5} \right\rvert \le \frac{|c|+9}{5} < |c|$. Thus, we eventually reach a pair with $|c| \le 2$. Similarly, if $|b| > 9$, we have $\left\lvert \frac{b-a}{-2} \right\rvert \le \frac{|b|+9}{2} < |b|$, so we eventually reach a pair with $|b| \le 9$. this leaves us with $5 \cdot 19 = 95$ ordered pairs to check (though only about one third have $b \equiv c \pmod 3$). This can be done by the following code: import functools @functools.lru_cache() def f(x0, y0): if x0 == 0 and y0 == 0: return 0 if x0 % 2 == (y0 % 5) % 2: d = y0 % 5 else: d = (y0 % 5) + 5   x1 = (x0 - d) // (-2) y1 = (y0 - d) // (-5)   return 1 + f(x1, y1)   for x in range(-9, 10): for y in range(-2, 3): if (x % 3 == y % 3): print(f"({x:2d}, {y:2d}) finished in {f(x,y)} moves") Running the program, we see it terminates, hence we are done. $\blacksquare$

We will use notations from the above solution. One can show that:

Moreover, $b_i \equiv c_i \pmod{3}$ is a invariant. So we can just work out these small cases for $(b_i,c_i)$ by hand, as follows: [asy][asy] /* Geogebra to Asymptote conversion, documentation at artofproblemsolving.com/Wiki go to User:Azjps/geogebra */ import graph; size(6cm); real labelscalefactor = 0.5; /* changes label-to-point distance */ pen dps = linewidth(0.7) + fontsize(10); defaultpen(dps); /* default pen style */ pen dotstyle = black; /* point style */ real xmin = -10.26, xmax = 12.7, ymin = -1.73, ymax = 11.47; /* image dimensions */ pen wrwrwr = rgb(0.3803921568627451,0.3803921568627451,0.3803921568627451); /* draw figures */ draw((-3,3)--(-1,1), linewidth(0.8) + wrwrwr,EndArrow(6)); draw((-1,3)--(-1,1), linewidth(0.8) + wrwrwr,EndArrow(6)); draw((1,3)--(-1,1), linewidth(0.8) + wrwrwr,EndArrow(6)); draw((-1,5)--(-1,3), linewidth(0.8) + wrwrwr,EndArrow(6)); draw((-3.98,4.85)--(-1,3), linewidth(0.8) + wrwrwr,EndArrow(6)); draw((0.3,4.77)--(-1,3), linewidth(0.8) + wrwrwr,EndArrow(6)); draw((2,4)--(-1,3), linewidth(0.8) + wrwrwr,EndArrow(6)); draw((-4,7)--(-3.98,4.85), linewidth(0.8) + wrwrwr,EndArrow(6)); draw((-2,7)--(-1,5), linewidth(0.8) + wrwrwr,EndArrow(6)); draw((0.26,6.99)--(-1,5), linewidth(0.8) + wrwrwr,EndArrow(6)); /* dots and labels */ dot((-1,1),dotstyle); label("$(0,0)$", (-1.18,0.45), NE * labelscalefactor); dot((-3,3),dotstyle); label("$(2,2)$", (-3.9,2.29), NE * labelscalefactor); dot((-1,3),dotstyle); label("$(1,1)$", (-1.06,2.47), NE * labelscalefactor); dot((1,3),dotstyle); label("$(-1,-1)$", (0.9,2.27), NE * labelscalefactor); dot((-1,5),dotstyle); label("$(4,1)$", (-2.1,4.73), NE * labelscalefactor); dot((0.3,4.77),dotstyle); label("$(3,0)$", (0.28,4.75), NE * labelscalefactor); dot((2,4),dotstyle); label("$(2,-1)$", (1.68,4.21), NE * labelscalefactor); dot((-3.98,4.85),dotstyle); label("$(5,2)$", (-4.98,4.55), NE * labelscalefactor); dot((-2,7),dotstyle); label("$(-1,2)$", (-2.62,7.23), NE * labelscalefactor); dot((-4,7),dotstyle); label("$(-1,-1)$", (-4.86,7.29), NE * labelscalefactor); dot((0.26,6.99),dotstyle); label("$(-2,1)$", (0.34,7.19), NE * labelscalefactor); clip((xmin,ymin)--(xmin,ymax)--(xmax,ymax)--(xmax,ymin)--cycle); /* end of picture */ [/asy][/asy]

Sketch: Let $Q(x)=a_nx^n+\cdots$. More generally if $Q(-2)=a,Q(-5)=b$, and $a \equiv b \pmod{3}$, then there is a unique $Q$. We can find $Q$ as follows: pick $k \in \{0,\ldots,9\}$ such that $a \equiv k \pmod{2}$ and $b \equiv k \pmod{5}$, which is unique and exists by CRT. Then set $a_0=k$ and transition from $(a,b) \to (\tfrac{a-k}{-2},\tfrac{b-k}{-5})$, which preserves $a \equiv b \pmod{3}$. Uniqueness comes from the fact that $a_0=k$ is in fact necessary, so it suffices to show that this process terminates. This can be done by bounding $a$ and $b$ such that something like $|a+b|$ won't decrease from this operation (since otherwise we just apply it and induct down) and then just manually checking them