Answer: no. Suppose otherwise. Let $S = \{s_1, s_2, \cdots , s_{n + 1}\}$ and write $g(x) = g_1(x) + g_2(x)$ where $g_1$ contains all terms of $g$ with degree $\le n$ and $g_2$ contains all terms of $g$ with degree $> n.$ By replacing $f$ with $f - g_1$ and $g$ with $g - g_1$, we may assume that $g$ contains no terms of degree $< n.$ We will refer to this as the degree assumption. Since $f \not\in \mathbb{Z}[x]$ by assumption, we may choose an integer $a > 1$ such that $af \in \mathbb{Z}[x]$ and the content of $af$ is $1.$ Let $p$ be a prime divisor of $a$, and write $h = (a / p)g.$ Consider the polynomial $R(x) = af(x) - ph(x).$ By the degree assumption, the terms of $R$ with degree $\le n$ are identical to the terms of $af$, and the terms of $R$ with degree $> n$ are identical to $ph.$ Meanwhile, since every element of $S$ is a zero of $R$, we may write \[R(x) = \left(x - s_1\right) \cdots \left(x - s_{n + 1}\right)k(x) \quad (\star)\]for some polynomial $k \in \mathbb{Q}[x].$ By examining the terms of $R$ with degree $\le n$, the degree assumption implies that $\text{cont}(R) \mid \text{cont}(af) = 1.$ Therefore $\text{cont}(R) = 1$ as well. Hence, Gauss' Lemma yields $\text{cont}(k) = 1$, i.e. $k$ is a monic polynomial with integer coefficients. Now, we claim that all coefficients of $k$ are congruent to $0$ modulo $p.$ Indeed, suppose otherwise, and let $bx^m$ be the leading coefficient of $k$, with $b \not\equiv 0 \pmod{p}.$ According to the degree assumption, the coefficient of $x^{n + m + 1}$ in $R$ is congruent to $0$ modulo $p.$ However, according to $(\star)$, the coefficient of $x^{n + m + 1}$ in $R$ is $b$, contradiction. Therefore, $k \equiv 0 \pmod{p}$ as a polynomial. It follows that \[0 \equiv R \equiv af - ph \equiv af \pmod{p}.\]However, as $\text{cont}(af) = 1$, we cannot have $af \equiv 0 \pmod{p}.$ Thus, we have arrived at a contradiction, and the proof is complete. $\square$

But $g$ doesn't necessarily have degree $n$.

Assume for sake of contradiction that this is possible. Suppose $mf(x)\in \mathbb{Z}[x]$, and let $f_1(x)=mf(x)$. Then there is some prime $p$ such that $p\mid m$ but $p\nmid f_1(x)$, so let $mg(x)=pg_1(x)$. Then $f_1(x)-pg_1(x)$ vanishes on $S$, so $(x-t_1)\cdots (x-t_{n+1})\mid f_1-pg_1(x)$ polynomially. Reducing to $\mathbb{F}_p[x]$, $f_1$, a nonzero polynomial, is divisible by $(x-t_1)\cdots (x-t_{n+1})$, which is also a nonzero polynomial. But the second has a larger degree than the first, so this is a contradiction.

NewAlbionAcademy wrote: But $g$ doesn't necessarily have degree $n$. Fixed using division algorithm

suli wrote: Answer: no. Indeed, let $S = \{ x_1, x_2, \dots, x_n, x_{n+1} \}$. Use division algorithm to write $g(x) = (x - x_1)(x - x_2) \dots (x - x_{n+1}) h(x) + r(x)$, where $r(x)$ is of degree $n$ or smaller. Then $f(x) - r(x) = a(x - x_1)(x - x_2) \dots (x - x_{n+1})$ and because $f - r$ is at most degree $n$ and the RHS is of degree $n+1$ or is $0$, $f - r$ must be zero and so $f = r$, which cannot happen because $r$ also has integer coefficients. Why is $r$ an integer polynomial?

pi37 wrote: Reducing to $\mathbb{F}_p[x]$, $f_1$, a nonzero polynomial, is divisible by $(x-t_1)\cdots (x-t_{n+1})$, which is also a nonzero polynomial. But the second has a larger degree than the first, so this is a contradiction. Would you clarify this more ? And isn't $f_1$ zero on $\mathbb{F}_p[x]$ (since $p|m|f_1|$)

Dukejukem wrote: suli wrote: Answer: no. Indeed, let $S = \{ x_1, x_2, \dots, x_n, x_{n+1} \}$. Use division algorithm to write $g(x) = (x - x_1)(x - x_2) \dots (x - x_{n+1}) h(x) + r(x)$, where $r(x)$ is of degree $n$ or smaller. Then $f(x) - r(x) = a(x - x_1)(x - x_2) \dots (x - x_{n+1})$ and because $f - r$ is at most degree $n$ and the RHS is of degree $n+1$ or is $0$, $f - r$ must be zero and so $f = r$, which cannot happen because $r$ also has integer coefficients. Why is $r$ an integer polynomial? This is obvious because $(x - x_1)(x - x_2) \dots (x - x_{n+1})$ is a monic polynomial with integer coefficients and $g$ is a polynomial with integer coefficients. Stop fighting over the correctness of my solution, please.

suli wrote: This is obvious because $(x - x_1)(x - x_2) \dots (x - x_{n+1})$ is a monic polynomial with integer coefficients and $g$ is a polynomial with integer coefficients. Stop fighting over the correctness of my solution, please. This reasoning wasn't entirely clear to me, and wasn't stated in the above post, so I was asking for clarification on the solution. I wouldn't describe this as "fighting over the correctness of my solution."

It's not a problem of fighting over correctness. It's just I have been asked to clarify things several times and I have gotten a bit frustrated.

dothef1 wrote: pi37 wrote: Reducing to $\mathbb{F}_p[x]$, $f_1$, a nonzero polynomial, is divisible by $(x-t_1)\cdots (x-t_{n+1})$, which is also a nonzero polynomial. But the second has a larger degree than the first, so this is a contradiction. Would you clarify this more ? And isn't $f_1$ zero on $\mathbb{F}_p[x]$ (since $p|m|f_1|$)

Remember that $f$ is in $\mathbb{Q}[x]$, not $\mathbb{Z}[x]$, so we chose $p$ such that $p\nmid f_1(x)$. Since $f_1(x)-pg_1(x)=h(x)(x-t_1)\cdots (x-t_{n+1})$ for some polynomial $h\in \mathbb{Z}[x]$, if we reduce all of the coefficients of the polynomials mod $p$, we just get $\overline{f_1(x)}=\overline{h(x)} \overline{(x-t_1)\cdots (x-t_{n+1})}$, where the bar denotes the polynomial's reduction mod $p$. But $\overline{f_1(x)}$ has degree $n$, and the RHS has degree at least $n+1$, unless $\overline{h(x)}$ is $0$. So this tells us that $\overline{f_1(x)}=0$ in $\mathbb{F}_p[x]$, and so $f_1$ has all coefficients divisible by $p$.

suli wrote:

pi37 wrote: Reducing to $\mathbb{F}_p[x]$, $f_1$, a nonzero polynomial, is divisible by $(x-t_1)\cdots (x-t_{n+1})$, which is also a nonzero polynomial. But the second has a larger degree than the first, so this is a contradiction. This might be a silly question, but does this logic of lower degree polynomial indivisible by a higher degree polynomial work for $\mathbb{F}_p[x]$? Take for example $x^p+1 \mid x+1$ in $\mathbb{F}_p[x]$, which is true by FLT since they become the same polynomial. (Note: the second polynomial might have other larger degree terms which which are divisible by $p$). Can someone please confirm? I am confused

It is only about coefficient

Ahh I get it now... Thanks!

Solution: We use induction. The base case is $deg=0$ (it is possible, the statement just doesn't give us $n=0$ but screw it) Now, notice that $\dfrac{g(x)-g(y)}{x-y}=\dfrac{f(x)-f(y)}{x-y}$, for all $x,y \in S$. But notice that now we may just fix $y$ and interpretate $g'(x)=g(x)-g(y)/x-y$ and $f'(x)=f(x)-f(y)/x-y$ as $x$ variables polynomials of $deg= n-1$ and reduce the number of variables in exactly one. Notice $g$ continues to have integer coefficients and $f$ has rational ones, with one still non-integer. Also, $f,g$ exist iff $f',g'$ also do. But clearly they don't because of the induction hypotesis. $\blacksquare$