This problem was used in a Romanian TST

This problem was also used at MOP, and I posted it on my blog. I might as well re-post it here.

mathocean97 wrote: This problem was also used at MOP, and I posted it on my blog. I might as well re-post it here.

Great solution! It's a very natural and intuitive approach. (I started on the same path but got stuck. :-( ) I don't think there is a different way to solve it (usually, there would be induction, but it doesn't seem to work out).

Here is another solution. $|pf+g|=|f||p + \frac{g}{f}|$, but $|f|=0$ has finite solutions, and $\frac{g}{f} \rightarrow 0$ when $|x| \rightarrow 0$, so the absolute value of all roots of $pf+g=0$ are bounded by some constant $M$ independent of $p$. Now let the highest degree term of $f$ be $a x^n$. Assume that $p>a$. By Gauss Lemma, $pf+g$ can be factored into two integer polynomials as one of the following. $pf+g = pa x^n + ... = (b x + b_0)(pc x^{n-1} + ... ) $ or $pf+g = pa x^n + ... = (pb x + b_0)(c x^{n-1} + ... ) $, where $a = bc$. Now, because the roots of $pf + g$ has bounded absolute value $M$, using Vieta's formula, you can show that each coefficients of polynomials (with constant degree) having those as roots divided by the highest degree coefficient is bounded by something like $2^n max (M^n , 1) $ where $n$ is the degree. $b, c$ can only take finite values, so the factor where the highest-degree term coefficient does not contain $p$ can only take finite values. So, whether it is the first case or the second case, there are two primes where the factor without $p$ coincides, now subtract them to get something like $(p_1 - p_2 ) f = ($linear term$) ($something$)$. So, $f$ has a rational root.

Yay compactness! Assume without loss of generality that $f$ is monic by scaling. To be explicit, if $c$ is the leading coefficient of $f$, then we may replace $f$ and $g$ by $c^{\deg f - 1} f(x/c)$ and $c^{\deg f - 1} g(x/c)$, respectively. Consider a sequence $x_n$ of rational numbers and $p_n$ of increasing prime numbers such that \[ 0 = p_n f(x_n) + g(x_n) = f(x_n) + \frac{1}{p_n} g(x_n). \qquad (\star) \]It's easy to check that $x_n$ must be bounded by some $M$. By compactness of $[-M,M]$ some subsequence of $(x_n)$ converges to some $x$; so let's just assume without loss of generality (by discarding all other $x_n$) that $x_n \to x$. Furthermore, $0 = f(x_n) + \tfrac{1}{p_n} g(x_n) \to f(x)$ hence $x$ is a root of $f$. (Another way to phrase this is to consider the function $g/f$; since it is outputting $1/p_i$, the subsequence goes to $0$.) Therefore it suffices to show that this limit $x$ is rational. We will actually show it must be an integer (now that $f$ is monic). We have two cases. If $x_n$ is an integer infinitely often, then $x$ must be as well, and done. Otherwise, discard all the integral $x_n$ and consider the remaining sequence. By the Rational Root Theorem on the first half of $(\star)$, $x_n = \tfrac{k_n}{p_n}$ for some $p_n \nmid k_n$. The idea is that this will cause issues with powers of $p$ in the denominator now except in special situations. To write it out, \[ 0 = p_n^{d+1} f(\tfrac{k_n}{p_n}) + p_n^{d} g(\tfrac{k_n}{p_n}) \]where $d = \deg g$. From this form we can deduce $d+1 = \deg f$ and then that $0 \equiv k_n^{d+1} + ck_n^d \pmod{p_n}$, where $c$ is the leading coefficient of $g$. Consequently $k_n \equiv -c \pmod{p_n}$ for all $n$. Then \[ x_n + \frac{c}{p_n} \in {\mathbb Z} \qquad \forall n. \]Since $c$ is fixed, this forces $x_n$ to converge to an integer (as $p_n$ grows large).

Let $p_1<p_2<...$ be primes and let $r_1,r_2,...$ be rationals such that $p_if(r_i)+g(r_i)=0$ for all $i$. Let $f(x)=a_nx^n+...+a_0$ and let $g(x)=b_mx^m+...+b_0$. WLOG $p_i$ is coprime to all coefficients of both polynomials for all $i$. Let $r_i=\frac{x_i}{y_i}$ so that $(x_i,y_i)=1$. By rational Root Theorem, $y_i | p_ia_n$ always. So, there exists a divisor $d$ of $a_n$ such that $y_i = d$ or $y_i = dp_i$. WLOG, this divisor $d$ is constant for all $i$. Now, suppose $y_i=dp_i$ and take $p_if\left( \displaystyle\frac{x_i}{dp_i} \right)+g\left( \displaystyle\frac{x_i}{dp_i} \right) =0$ Multiplying by $p_i^n$ and taking mod $p_i^2$, we see that $n=m+1$ and that $p_i | x+c$, where $c=\frac{b_md}{a_n}$ is a constant. (Note that $n=m+1$ can only be guaranteed if $y_i=dp_i$ for some $i$. We might have $y_i=d$ for all $i$). Now, notice that $f(r_i)+\frac{g(r_i)}{p_i} = 0$. Since $m<n$, this means $r_i$ must be bounded. This is because if $h(x)=f(x)+g(x)$, for big $x$ this resembles $f(x)$ since $m<n$, and $p_i > 1$ always. So we can safely assume there exist $a,b$ such that $r_i \in (a,b)$ for all $i$. Notice that as $i$ gets big, then $\frac{g(r_i)}{p_i}$ goes to $0$ (since $g(r_i)$ is bounded since $r_i$ is bounded, and $p_i$ grows indefinitely). Therefore as $i$ gets big, $f(r_i)$ must get arbitrarily close to $0$. Let $R_1,...,R_V$ be all the roots of $f$ inside interval $(a,b)$. Because there are infinitely many primes, we may assume $lim_{i \to \infty} r_i = R$ for some $R$ that is a root of $f$ in $(a,b)$. Recall that for all $i$ either $y_i=d$ or $y_i=p_id$ and $p_i | x+c$. Since rationals of the form $\frac{M}{d}$ cannot get arbitrarily close to $R$, we may assume $y_i=p_id$ for all $i$. So, for all $i$ there exists $k_i$ such that $x_i = \displaystyle\frac{p_ik_i-b_md}{a_n}$ From this, $r_i = \displaystyle\frac{k_i}{da_n} - \displaystyle\frac{b_m}{p_ia_n}$ The second term gets arbitrarily close to $0$ as $i$ gets big. Therefore the first term must get arbitrarily close to $R$ as $i$ gets big. Since it has a fixed denominator, we must have that there exists a $k$ such that $R = \frac{k}{da_n}$ and so $R$ is rational. So we are done!

Is something wrong with this? Let $p_1<p_2<...$ be primes and let $r_1,r_2,...$ be rationals such that $p_if(r_i)+g(r_i)=0$ for all $i$. Then, $-p_i=\frac{g(r_i)}{f(r_i)}$ i.e. $p_i=\frac{|g(r_i)|}{|f(r_i)|}$. Since $f$ and $g$ are polynomials with $\deg f>\deg g$, the $r_i$'s must be bounded above and below ($f$ grows much faster than $g$ when the domain goes to $\infty$ and $-\infty$, so it is impossible for $\frac{|g(r_i)|}{|f(r_i)|}$ to go to infinity as $p_i$ does). Let the maximum of $|g(r_i)|$ be $M$ and the minimum of $|f(r_i)|$ be $m$ for $i= 1, 2, ...$. Maximum and minimum exist because the $r_i$'s are bounded above and below and polynomials are continuous. Suppose $m$ does not equal to 0. Then, $p_i=\frac{|g(r_i)|}{|f(r_i)|} \leq \frac{M}{m}$, a contradiction for primes $p_i > \frac{M}{m}$. Hence, $m=0$, so there exists $i$ such that $|f(r_i)|=0$ i.e. $f$ has a rational root.

Could someone tell me if this is right? Thank you very much!

No, the above is quite inaccurate. This is because $g(x_n)$ can approach zero.

I believe this works. Perhaps not much different from what other posters have done, but adding anyway. lyukhson wrote: Let $f$ and $g$ be two nonzero polynomials with integer coefficients and $\deg f>\deg g$. Suppose that for infinitely many primes $p$ the polynomial $pf+g$ has a rational root. Prove that $f$ has a rational root. Call this sequence of primes as $(p_k)_{k \ge 1}$. Now let $f(x)=a_nx^n+\dots+a_0$ and $g(x)=b_mx^m+\dots+b_0$; let $z_k=\left(\frac{x_k}{y_k}\right)$ with $\gcd(x_k, y_k)=1$ for all $k$; be the sequence of rational roots. Note that $x_k \mid p_na_0+b_0$ while $y_k \mid p_na_n$. For any $k$ if $g(z_k)=0$ then $f(z_k)=0$ and we're done. So $g(z_k) \ne 0$ for all $n \ge 1$. Now $$0=|p_kf(z_k)+g(z_k)| \ge p_k|f(z_k)|-|g(z_k)| \implies \frac{|g(z_k)|}{|f(z_k)|} \ge p_k$$so the sequence $|z_k|$ must be bounded (since $\text{deg} \, f> \text{deg} \, g$) by a constant $M>0$. Now, by compactness, it is well-known that any bounded sequence of real numbers has a convergent sub-sequence. Pick a sequence $(z_{n_k})_{k \ge 1}$ which converges to the limit $\ell$ for some sub-sequence $(n_k)_{k \ge 1}$. Case 1. If an infinite subsequence of $(z_{n_k})$ exists with $\gcd(p_k, y_k)=1$ for all the respective indices. Let $(z_{k_i})_{i \ge 1} $ be the sequence; then both $(x_{k_i})$ and $(y_{k_i})$ are bounded. Consequently, some rational root $r$ shows up infinitely many times; hence $f(r)=0$. Case 2. If an infinite subsequence $(z_{\ell_i})_{i \ge 1}$ exists with $p_{\ell_i} \mid y_{\ell_i}$ for all $i \ge 1$. Now we pick sequences $(c_i), (d_i)$ with $x_{\ell_i}d_i=p_{\ell_i}a_0+b_0 $ and $y_{\ell_i}=p_{\ell_i}c_i$ for all $i \ge 1$ with $c_i \mid a_n$. Again we may pick an infinite subsequence with $c_i=c$ is constant; so let's assume that right-off the bat. By convergence, we see $\tfrac{x_{\ell_i}}{y_{\ell_i}} \rightarrow \tfrac{a_0}{d_ic}$ so in fact $d_i$ must converge as well to a limit $d$. Consequently, we see that $\ell$ is also a rational number $\tfrac{a_0}{cd}$ hence taking limits gives $\tfrac{|f(\ell)|}{|g(\ell)|}>p_{\ell_k}$ which fails when $k \rightarrow \infty$; unless $f(\ell)=0$. In any case, $f$ must have a rational root!

This seems to be at least a little bit different from the other solutions. If you find an error, please point it out. The structure of this solution is not very pretty: we constantly do proof by contradiction until we have exhausted all of the cases. Let $f(x) = f_nx^n + \ldots + f_0$, and $g(x) = g_nx^n + \ldots + g_0$, where $g_i = 0$ for all $i > \deg g$. Let $H_p(x) = pf(x) + g(x)$. Write $H_p(x) = c_nx^n + \ldots + c_0$, where $c_i = pf_i + g_i$ for all $i$. Lemma 1. If there exists a rational number $y$ such that $H_p(y) = H_q(y) = 0$ for two distinct primes $p$, $q$, then we are done. Proof. $0 = H_p(y) - H_q(y) = (p - q)f(y)$. Let $\frac{a}{b}$ be a root of $H_p$, where $\gcd(a, b) = 1$. By the rational root theorem $b$ must divide $c_n = pf_n$, and $a$ must divide $c_0 = pf_0 + g_0$. Note that $$p = -\frac{g(\frac{a}{b})}{f(\frac{a}{b})}$$ (assuming that $f(\frac{a}{b}) \neq 0$, otherwise we are done). We note that $\frac{a}{b}$ must be bounded, as for large values of $\frac{a}{b}$ the absolute value of the right hand side of the above equation is approximately $0$. Now, if $b$ is infinitely often not divisible by $p$, we are done, as then $b$ divides $f_n$, and $a$ is bounded to some interval -> lemma 1 finishes the job. We will now on only care about the cases when $b$ is divisible by $p$. We now go back to the equation $$0 = c_na^n + c_{n-1}a^{n-1}b + \ldots + c_1ab^{n-1} + c_0b^n$$ $p^2$ divides all except the first two terms of the sum, so $p^2$ must divide $c_na^n + c_{n-1}a^{n-1}b$. Write $b = pd$. We now have $$c_na^n + c_{n-1}a^{n-1}b = a^{n-1}(c_na + c_{n-1}b) = a^{n-1}(pf_na + p^2f_{n-1}d + pg_{n-1}d)$$ So $p$ must divide $f_na + g_{n-1}d$. However, we note that $d$ is bounded (since $pd = b | pf_n$). Also, $a$ divides $pf_0 + g_0$. This means that there is some constant $C$ such that the absolute value of $f_na + g_{n-1}d$ is at most $Cp$. Thus, there exists some $k$ such that $f_na + g_{n-1}d = kp$ for infinitely many $p$. From here we can solve for $d$ and thus $b$: we get $$b = \frac{kp^2 - f_npa}{g_{n-1}}$$ We will now prove that there exists a constant $D > 0$ such that $|b| > p^2D$ for infinitely many $p$. Using the above formula for $b$, we have to prove that $$\Big|\frac{kp - f_na}{g_{n-1}}\Big| > pD$$ for some $D$, that is, $|kp - f_na| > pD'$ for some constant $D'$. But we know that $a | pf_0 + g_0$, so we can write $a = \frac{pf_0 + g_0}{t}$ for some integer $t$ which depends on $a$. If there are infinitely many $t$ such that $\frac{f_0}{t}$ is not equal to $k$, the lemma is proven, as $\frac{f_0}{t}$ can't get arbitrarily close to $k$, because $t$ and $k$ are integers. But if there are infinitely many $t$ such that $\frac{f_0}{t} = k$, we have $$kp - f_na = \frac{g_0k}{f_0}$$ a constant independent of $p$. Plugging this in to the formula for $b$ we get that $b$ is of the form $mp$, for some constant $m$. We also have $a = kp + \frac{g_0k}{f_0}$. This means that the fraction $\frac{a}{b}$ will get arbitrarily close to some constant as $p$ increases. Thus, the value of $$\frac{g(\frac{a}{b})}{f(\frac{a}{b})}$$ will be very close to some constant. This contradicts the fact that $p = -\frac{g(\frac{a}{b})}{f(\frac{a}{b})}$. Now, $b$ is about the size of $p^2D$ for some constant $D$. But this is a contradiction, as $b$ must divide $pf_n$. So, we are done.

Very similar to above solutions. This solution has two parts, part 1 being number theory, and part 2 being the analysis. The number theory portion is relatively natural, but for me, the analysis portion took quite a while to see. Preliminary notations: Let $n=\deg f$, $m=\deg g$, and write \begin{align*} f(x) &= a_nx^n + a_{n-1}x^{n-1}+\cdots+a_0 \\ g(x) &= b_mx^m + b_{m-1}x^{-1}+\cdots+b_0. \end{align*}Also let $r_p$ be the rational root of $pf+g$. Part 1: We assume WLOG that $p$ is sufficiently larger than all the $a_i,b_i$. Firstly, if $-d=\nu_p(r_p)\le -2$, then we can write $r_p=z/p^d$ where $p\nmid z$. The equation $pf(r_p)+g(r_p)=0$ multiplied by $p^{nd-1}$ is \begin{align*} &a_nz^n + p^da_{n-1}z^{n-1}+\cdots+p^{nd}a_0 \\ +& p^{nd-1-m}b_mz^m + p^{nd-1-m+1}b_{m-1}z^{m-1}+\cdots+p^{nd-1-m+m}b_0 = 0. \end{align*}We see that $nd-1-m\ge 2n-m-1=n+(n-m-1)\ge n\ge m+1\ge 1$, so taking mod $p$ tells us that $a_nz^n\equiv 0\pmod{p}$, which can't happen. Therefore, this case is impossible. Suppose $\nu_p(r_p)=-1$. Then, we have that $r_p=y_p/p$ for some $p\nmid y_p$ (note $y_p$ is defined only if $\nu_p(r_p)=-1$). The equation $pf(y_p/p)+g(y_p/p)=0$ multiplied by $p^{n-1}$ is \begin{align*} &a_ny_p^n + pa_{n-1}y_p^{n-1}+\cdots+p^na_0 \\ +& p^{n-1-m}b_my_p^m + p^{n-1-m+1}b_{m-1}y_p^{m-1}+\cdots+p^{n-1-m+m}b_0 = 0. \end{align*}If we have $n-1>m$, then taking mod $p$ reveals that $a_n y_p^n\equiv 0\pmod{p}$, which can't be since $a_n\ll p$ and $p\nmid y_p$. Thus, $n-1=m$. Then, mod $p$ tells us $a_ny_p\equiv -b_{n-1}\pmod{p}$, so $y_p\equiv -b_{n-1}/a_n\pmod{p}$. All in all, either all the $r_p$ are integral, or $n-1=m$ and $y_p\equiv -b_{n-1}/a_n\pmod{p}$. Part 2: Note that $h(r_p):=-f(r_p)/g(r_p)=1/p$. We see that $h(N)=(-a_n/b_{n-1})N+O(1)$ for large $|N|$, so since $h(r_p)$ is bounded, we must also have that the $r_p$ are bounded. Therefore, $r_p\in[-M,M]$ for some $M>0$. Now by compactness of $[-M,M]$, some subsequnce of $p$s has $r_p$ convering, call it $p_1<p_2<p_3<\cdots$, and suppose that then $r_p\to r$. Furthermore, there is some resiude class mod $a_n$ such that the sequence hits it infinitely many times (pigeon-hole), so WLOG, assume they all have the same residue class. Note that since $h$ is continuous, we have that $h(r_{p_i})\to h(r)$, so $1/p_i\to h(r)$, so $h(r)=0$. It remains to show that $r$ is rational. If $r_{p_i}$ is an integer infinitely often, then $r$ is an integer so we're done. Otherwise, its an integer only finitely many times, so WLOG its always non-integral. Therefore, we have that $r_p=y_p/p$ and $y_p\equiv -b_{n-1}/a_n\pmod{p}$. However, since all the $p$ are the same mod $a_n$, we have that $1/a_n\equiv (p+C)/a_n\pmod{p}$ for some constant $C$ and $a_n\mid p+C$. Thus, $y_p=k_pp-\frac{b_{n-1}}{a_n}(p+C)$ for some integer $k_p$, so \[r_p = (k_p-b_{n-1}/a_n) - \frac{1}{p}\frac{b_{n-1}}{a_n}C.\]Therefore, the limit of $r_p$ is the limit of $k_p-\ell$ for some rational constant $\ell$, and $k_p$ is always integral, so we see that $r_p\to k-\ell$ for some integer $k$. Thus, $r=k-\ell\in\mathbb{Q}$, as desired.

This works I guess. Not sure though.

@Kayak: In the opening lines of my solution I assumed WLOG that $f$ was monic.

We will show the following slightly stronger claim: Either $f$ has a rational root or $f, g$ have a common root. We'll also solve the problem for the version where $f,g$ have rational coefficients by clearing the appropriate denominators. Indeed, if $f,g$ have a common root $\alpha$, then $h = \gcd(f,g)$ (over $\mathbb Q$) is divisible by the minimal polynomial of $\alpha$ over $\mathbb Q$, so $pf+g = h(pf_0 + g_0)$. Either the rational root of $pf+g$ is a divisor of $h$ infinitely many times or it is a divisor of $pf_0+g_0$ infinitely many times. In the latter case we proceed by induction since $\deg f$ has decreased; else we are done since $h\mid f$ has a rational root. So this implies the problem. Suppose $f(0) \neq 0$ and let $A = \{\alpha\colon f(\alpha) = 0, \alpha\in \mathbb R\}$. We note that $P = f^2/g^2$ also has zeroes at $\alpha$. Furthermore, for sufficiently small $\delta > 0$, we can find $\varepsilon$ such that $P(x) < \delta\implies |x-\alpha| < \varepsilon$ for some $\alpha\in A$. Here we have used $\deg f \geq \deg g$ to guarantee that the limits of $P$ as $x\to\pm\infty$ are $\infty$. When $p$ is sufficiently large so that $2/p^2$ is such a $\delta$ we let $e_p$ be the associated $\varepsilon$ value. Let $S_p = \bigcup_{\alpha} \{x\colon |x-\alpha| < e_p\}$, then since $P(q) = 1/p^2$, we have $q\in S_p$. Also, take $p$ sufficiently large so that $S_p$ does not contain any roots of $g$; this can be done since $e_p\to 0$ as $p\to \infty$ and $\alpha$ is never a root of $g$. In particular this guarantees that $P$ is continuous on $f^2/g^2$. We will henceforth assume that $p$ is sufficiently large so as to satisfy these properties; there are still infinitely many $p$. Call $p$ murine if $pf+g$ has a rational root. Now, we let $a, b$ be the constant terms of $f,g$, and $c$ the leading coefficient of $f$. Then, any rational root of $pf+g$ is of the form $m/n$ for $m\mid pf+g$, $n\mid pc$. Also, note that no rational can be the root of $pf+g$ for two different $p$-values, since this would make it a root of $f$ and $g$. Since $S_p \subset S_q$ for $p < q$ and $S_p$ individually are bounded, the union of $S_p$ over murine $p$ is also bounded; in particular, this means for each $c'\mid c$ there are only finitely many murine $p$ so that the root is of the form $x/c'$. In particular, for infinitely many $p$ the root must be of the form $m/(pn)$ for $m\mid ap+b$, $n\mid c$. Then, our root is of the form \[ (ap+b)/(pc'x), \]for $x\mid ap+b$. This is equal to \[ \frac{a}{c'x} + \frac{b}{pc'x}, \]which is within $1/p$ of $\frac{a}{c'x}$. So, if we let $f_p = e_p+ \frac 1p$ and let $R_p$ be the set of numbers within $f_p$ of some $\alpha$, then note that $\frac{a}{c'x}\in R_p$. Then, note that $R_p$ does not intersect some neighborhood of $0$ for $p$ sufficiently large or else $0$ is a root of $p$. Call $p$ tasty if $p$ is murine, has root of the form $(ap+b)/(pc'x)$, and $R_p$ doesn't intersect some neighborhood of $0$. But then this means that $x$ must be bounded. So, some triple $(a,c',x)$ occurs infinitely many times, in whcih case $\frac{a}{c'x}\in R_p$ for arbitrarily large $p$, which implies that $\alpha = \frac{a}{c'x}$ for some $\alpha$ and we are done. $\blacksquare$

Solved with eisirrational, goodbear, Th3Numb3rThr33. I claim the roots of $pf+g$ lie on $[-R,R]$ for some constant $R$. Since $\deg f>\deg g$, there is an $R$ such that for all $|x|>R$, we have $|g(x)/f(x)|<1$. Hence for such $x$ and all primes $p$, \[|pf(x)+g(x)|\ge|f(x)|\left(p-\left\lvert\frac{g(x)}{f(x)}\right\rvert\right)>0\]so the roots of $pf+g$ lie in $[-R,R]$. By Gauss' lemma $pf+g$ is the product of two polynomials $h_p$ and $j_p$, with the leading coefficient of $h_p$ dividing that of $f$, and $1\in\{\deg h_p,\deg j_p\}$. There are finitely many possible leading coefficients and degrees, so assume infinitely many $h_p$ have the same degree and leading coefficient. There are finitely many possible set of roots of $h_p$ by Rational Root theorem, so there are finitely many possible $h_p$. Thus for some $h$, we have $h=h_p$ infinitely often. But if $h=h_p=h_q$, then $h$ divides $pf-g$ and $qf-g$, so $h$ divides $(p-q)f$. Since $\deg h=1$ or $\deg h=\deg f-1$, $f$ has a rational root, as desired.

@TheUltimate123, Why there are finitely many possible roots oh $h_p$? I agree that there are finitely many rational roots but how do you get anything about non-rational roots?

Worked with nukelauncher. Let $f(x)=a_nx^n+\cdots+a_0$ and $g(x)=b_mx^m+\cdots+b_0$. Call the primes $p$ for which $pf+g$ has a rational root valid. For each valid $p$, let $pf+g$ have rational root $r_p$, and let $r_p=u_p/v_p$ for some coprime $u_p,v_p \in \mathbb{Z}$. Lemma: Over all valid $p$, we have $|r_p|$ is bounded above. Proof: Since $\deg g < \deg f$, clearly there exists a constant C such that $|x|\ge C \implies |g(x)/f(x)|<0.01$. But since $pf(r_p)+g(r_p)=0$, hence $|g(r_p)/f(r_p)|=p>0.01$, so we must have $|r_p|<C$. $\blacksquare$ By the Rational Root Theorem, $v_p\mid pa_n$ and $u_p\mid pa_0+b_0$. Therefore, from the former, each valid $p$ satisfies exactly one of $p\mid v_p$ (call such primes peasants), or $v_p\mid a_n$ (call such primes rebels). Claim: Infinitely many valid primes $p$ are peasants. Proof: Suppose finitely many valid $p$ are peasants. Let $S$ be the set of all valid rebels $p$. Over all $p\in S$, there are finitely many possible values for $v_p$, since $v_p\mid a_n$. For each such possible value of $v_p$, there are finitely many possible values for $u_p$, since $|u_p/v_p|$ is bounded above. In turn, there are finitely many possible values for $u_p/v_p=r_p$, over all $p\in S$. Since all but finitely many of the valid $p$ are in $S$, there are finitely many possible values of $r_p$ over all valid $p$. Hence there are finitely many possible values for $-\tfrac{g(r_p)}{f(r_p)}$. But $p=-\tfrac{g(r_p)}{f(r_p)}$, contradicting the infinitude of valid $p$. $\blacksquare$ Consider a sufficiently large peasant prime $p$ much larger than all the $a_i$'s and $b_i$'s. Since $r_p=u_p/v_p$, we have \[ (pf+g)(r_p) = \sum_{i=0}^n pa_i\left(\frac{u_p}{v_p}\right)^i + \sum_{j=0}^m b_j\left(\frac{u_p}{v_p}\right)^j = 0 , \]so multiplying through by $v_p^n$ gives \[ \sum_{i=0}^n pa_i\cdot u_p^i v_p^{n-i} + \sum_{j=0}^m b_j\cdot u_p^jv_p^{n-j} = 0. \qquad (\heartsuit) \]Take $(\heartsuit) \mod p^2$. Since $p\mid v_p$, the former term above reduces to $pa_nu_p^n \mod p^2$, and the latter term reduces to $b_m\cdot u_p^mv_p^{n-m} \mod p^2$. Case 1: $n\ge m+2$. Then $b_m\cdot u_p^mv_p^{n-m} \equiv 0 \pmod{p^2}$. So actually $pa_nu_p^n \equiv 0 \pmod{p^2}$, i.e. $a_nu_p^n \equiv 0 \pmod p$. We know $p>a_n$ and $\gcd(u_p,v_p)=1$, so this is impossible. Case 2: $n=m+1$. Then $(\heartsuit)$ becomes \[ pa_nu_p^n + b_{n-1}u_p^{n-1} v_p \equiv 0 \pmod{p^2}, \]so since $p\nmid u_p$, we divide and reduce to \[ a_nu_p + b_{n-1}\left(\tfrac{v_p}{p}\right) \equiv 0 \pmod{p}.\]Let $d_p:=v_p/p$. Then by the above, $u_p/d_p\equiv b_{n-1}/a_n\pmod{p}$, so $u_p/d_p\equiv C \pmod{p}$ for some constant integer $C$. Hence $\tfrac{u_p}{d_p} - C = p\cdot \tfrac{\text{some integer}}{d_p}$. But $v_p\mid pa_n$ by RRT, so $d_p\mid a_n$, so also \[ \frac{u_p}{d_p} - C = p\cdot \frac{\text{some integer}}{a_n}, \quad \text{i.e.}\quad \frac{u_p}{d_p} = C + \frac{pZ_p}{a_n}\]for some $Z_p\in \mathbb{Z}$. But $r_p = u_p/v_p = \tfrac{1}{p}\tfrac{u_p}{d_p}$, so \[ r_p = \frac{C}{p} + \frac{Z_p}{a_n}. \]The issue is we currently have no control over $Z_p$. But remember that $|r_p|$ is bounded! Hence there exists some $Z\in \mathbb{Z}$ which is equal to $Z_p$ for infinitely many $p$. For these $p$, we have $r_p = C/p + Z/a_n$. Now, taking $p$ arbitrarily large makes $r_p\to Z/a_n$, a fixed rational. We have $p=-\tfrac{g(r_p)}{f(r_p)}$. Since $r_p \to Z/a_n$, but $f$ has no rational roots, we have $f(Z/a_n)\not =0$, so \[ -\frac{g(r_p)}{f(r_p)} \to -\frac{g(Z/a_n)}{f(Z/a_n)},\]a fixed number. This is a contradiction upon making $p$ arbitrarily large.

TheUltimate123 wrote: Solved with eisirrational, goodbear, Th3Numb3rThr33. I claim the roots of $pf+g$ lie on $[-R,R]$ for some constant $R$. Since $\deg f>\deg g$, there is an $R$ such that for all $|x|>R$, we have $|g(x)/f(x)|<1$. Hence for such $x$ and all primes $p$, \[|pf(x)+g(x)|\ge|f(x)|\left(p-\left\lvert\frac{g(x)}{f(x)}\right\rvert\right)>0\]so the roots of $pf+g$ lie in $[-R,R]$. By Gauss' lemma $pf+g$ is the product of two polynomials $h_p$ and $j_p$, with the leading coefficient of $h_p$ dividing that of $f$, and $1\in\{\deg h_p,\deg j_p\}$. There are finitely many possible leading coefficients and degrees, so assume infinitely many $h_p$ have the same degree and leading coefficient. There are finitely many possible set of roots of $h_p$ by Rational Root theorem, so there are finitely many possible $h_p$. Thus for some $h$, we have $h=h_p$ infinitely often. But if $h=h_p=h_q$, then $h$ divides $pf-g$ and $qf-g$, so $h$ divides $(p-q)f$. Since $\deg h=1$ or $\deg h=\deg f-1$, $f$ has a rational root, as desired. This is being referenced to which Gauss Lemma?

@above I believe that the Gauss Lemma referenced above is the one concerning the connection between irreducibility in $\mathbb{Z}[x]$ and $\mathbb{Q}[x]$. Could somebody explain how one is able to assume that $f$ is monic, this was done in a few solutions and I am missing why one is able to do this. My solution is quite similar to that of #6 and #15. When solving the problem I ended up proving the Rational Root Theorem through the proof of Gauss' Lemma but later noticed that I was simply using said Theorem, so this part is omitted from the following solution.

Solved with rama1728. Define a sequence of increasing prime numbers $p_1, p_2, \dots $ and rational numbers $x_1,x_2, \dots$ where $$f(x_i) + \frac{1}{p_i} g(x_i) = 0$$for all $i.$ Define the integer polynomial $h_i = p_i f + g.$ Obviously, the roots of all the $h_i$ are bounded in magnitude. By Gauss's Lemma, each $h_i$ can be represented as the product of an integer polynomial with degree $1,$ and an integer polynomial with degree $\deg f - 1.$ One of these has a leading coefficient dividing the leading coefficient of $f,$ since $p$ is prime. Call this polynomial $j_i.$ By PHP, we can find infinitely many $j_i$ with equal degree and leading coefficient. These polynomials have equal degree, equal leading coefficient, and roots that are bounded in magnitude. By RRT, there are only finitely many numbers that can be the root of such a polynomial, and thus finitely many such polynomials that exist. So by PHP, we can find an integer polynomial $j$ of degree $1$ or $\deg f-1$ dividing at least two of the $h_i,$ and thus dividing $f$ as well. Either $j$ or $f/j$ yields a rational root of $f.$ $\blacksquare$

Can someone check this? I am not entirely sure it is correct.

I think this is somewhat different from the previous solutions. Let the infinite sequence of primes in the statement be $S_p$, call any sequence good if it is a subsequence of rational roots corresponding to $S_p$. Let $p = \frac{-g}{f}$, since $\deg f > \deg g$ there exists an interval $I = [A,B]$ such that $|f| \geq |g|$ in ${\mathbb R} \setminus I$. Now, because $g,f$ are continuous functions then so is $\frac{-g}{f}$, but as $\frac{-g}{f} \to \infty$ there exists some good increasing rational sequence $\left\{\frac{r_i}{s_i}\right\} \to L$ in $I$ with $f(L) = 0$, and which corresponds to some sequence of primes $\{p_i\} \to \infty$. Henceforth, only care about this sequence. Let the leading coefficient of $pf$ and the constant coefficient of $pf+g$ be $pa_n$ and $pa_0 + b_0$ respectively, then by the rational root theorem \[ r_i \mid pa_0 + b_0, s_i \mid pa_n \]Claim: $p \mid s_i \ \forall \ i \geq N$ for some $N$. Proof. If not then, since $s_i \leq a_n$, then $\frac{r_i}{s_i}$ which eventually gets big because two elements of this sequence cannot be the same. $\blacksquare$ A well known theorem says that all subsequences of a converging sequence also converge to the same real number. Claim: Either $r_i= \mathcal{O}(pa_0 + b_0) = \mathcal{O}(p)$ or $L=0$. Proof. Forget about the first $N$ terms. Let $s_i = ps'_i$. Note that the sequence $1 \geq \frac{r_i}{p_ia_0 + b_0}$ is underbounded by 0. This means there is an infimum of this sequence. If this infimum is positive then $r_i = O(p)$, otherwise it is 0, which means there exists a subsequence $\left\{\frac{r_{N_i}}{p_{N_i}a_0 + b_0}\right\}_{i \geq 1} \to 0$. But since $s'_i \leq a_n$ we get that, $r_i/s_i$ \[ \frac{\frac{r_{N_i}}{a_0 p_{N_i} + b_0}}{s'_{N_i}}\leq \frac{r_{N_i}}{p_{N_i}s'_{N_i}} \leq (a_0+1)\frac{\frac{r_{N_i}}{a_0p_{N_i} + b_0}}{s'_{N_i}} \]goes to 0. Thus by the aforementioned theorem $L=0$, so we are done. It is easy to finish from here. Indeed, note that since $r_i = \mathcal{O}(pa_0 + b_0)$ there exist positive constants $C_1,C_2$ such that $C_1 \leq \frac{r_i}{pa_0 + b_0} \leq C_2$, let $k_i = \frac{pa_0+b_0}{r_i}$, so $\frac{1}{C_2}\leq k_i \leq \frac{1}{C_1}$, so \[ \frac{r_i}{s_i} = \frac{r_i}{ps'_i} = \frac{a_0 + \frac{b_0}{p}}{k_i \cdot s'_i} \]Now, as $k_i \cdot s'_i$ can only take finitely many values, by infinite PHP there exists atleast one value that repeats infinitely many times, let it be $\alpha$, so by the theorem $L = \frac{a_0}{\alpha}$ which is rational and we are done.

Suppose the contrary. Let $f(x) = f_0+f_1x+...+f_nx^n$ and $g(x) = g_0+g_x+...+g_mx^m$, $f_n\ne 0 \ne g_m$. Swaping $f,g$ by $f_n^{n-1}f(x/f_n)$ and $f_n^{n-1} g(x/f_n)$, suppose wlog $f_n=1$. Let $r_i$ be a sequence of rational numbers and $p_i$ a (wlog increasing) sequence of primes such that \[(p_if+g)(r_i) = 0.\]\[\implies p_i = -\frac{g(r_i)}{f(r_i)}\]a contradiction for large $r_i$, so this sequence is bounded. Since by the rational root theorem its denominators are either $1$ or $p_i$, the latter must occour for infinitely many $i$. Suppose wlog it happens for all $i$. \[\implies r_i = \frac{z_i}{p_i} \forall i\]with $z_i\in \mathbb Z$, $(z_i,p_i)=1$. We now claim $n=m+1$. Suppose $n\ge m+2$. Then, multiplying by $p^{n-1}$ and taking $\pmod{p_i}$ \[z_i^{n}\equiv LHS \equiv 0 \pmod {p_i}\]a contradiction. Therefore, again multiplying by $p^{n-1}$ and taking $\pmod{p_i}$, \[z_i^n+g_{n-1}z_i^{n-1}\equiv 0 \pmod{p_i}\]\[\therefore p_i \mid z_i+g_{n-1}\]\[\implies k_i = r_i+\frac{g_{n-1}}{p_i}\in \mathbb Z\]Since $r_i$ is bounded, it has a convergent subsequence. Suppose wlog then that $r_i$ converges to $r$. The above equation implies $r\in \mathbb Z$. However, \[f(r_i) = -\frac{g(r_i)}{p_i}\to 0 \ as\ i\to \infty\]\[\implies f(r) = 0 \ \ \ \blacksquare\]

Let $Q(x)$ denote the polynomial $pf(x)+g(x)$. Let $p_i$ denote the $i$th prime and $x_i$ be any rational root Claim: The absolute values of the rational roots of $Q(x)$ are bounded Proof: $$p_if(x_i) +g(x_i) =0$$$$p_i= -\frac{g(x_i)}{f(x_i)}$$ but note $ \deg f> \deg g $ Which implies that for large enough $|x_i|$, $|f(x_i)|>|g(x_i)|$ Which would imply that $|p|<1$ which is absurd WLOG suppose that $f(x)$ is a monic polynomial. $$f(x)=x^f+a_{f-1}x^{f-1}.....+a_0$$$$g(x)=b_{g}x^g+b_{g-1}x^{g-1}.....+b_0$$Let $x_i= \frac {m_i}{n_i}$, where $\gcd (m_i,n_i)=1$ Claim: $n_i=p_i$ or $1$ for infinitely many values of $i$ Proof: Considering the rational root theorem, $$n_i|p_i$$Which means that $n_i$ is $1$ or $p$ or both for infinitely many values Case 1: $n_i=p_i$ for infinitely many values of $i$ Claim: $\deg f = \deg g+1$ Proof: Note that $$\min { V_p(px_i^ja_j)}= \min {V_{p_i}(x_i^kb_k)}$$$$V_{p_i}(p_i(\frac{m_i}{p_i}^f)=V_{p_i}(b_g(\frac{m_i}{p_i}^g)$$ Since we are considering large $p_i$, $p_i >> b_g$ Hence, $\deg {f}-1=\deg g$ Claim: $x_i+ \frac{b_g}{p_i}$ is an integer Proof: Consider $p_i^{g_i}(p_if(x_i)+g(x_i))=0$ Note that it follows from the divisibility condition that $$m_i^f+b_gm_i^g \equiv 0 (\mod p_i)$$$$m_i +b_g \equiv 0 ( \mod p_i) $$ This means that $ \frac{m_i}{p_i} + \frac{b_g}{p_i}$ is an integer So $x_i+ \frac{b_g}{p_i}=\frac{m_i}{p_i} + \frac{b_g}{p_i}$ is an integer Note that from our first claim, we know that $x_i$ is bounded. Next, note that as $p_i$ increases, $x_i$ must monotonically increase/decrease due to the condition that $f(x_i)+\frac{g(x_i)}{p_i}=0$ This means that $x_i$ is a converging sequence Say $x_i$ converges to some value $x$ Also, note that for infinitely large $p_i$, $x_i + \frac{b_g}{p_i} -> x_i=x$ Which implies that $x$ is an integer But $$f(x)=-\frac{g(x)}{p_i}=0$$since $x$ is the convergent value when $p_i$ becomes infinitely large. Therefore, $x$, which is an integer, is a root of $f(x)$ Case 2: $n_i=1$ for infinitely many $i$ This implies that there are infinitely many distinct integer solutions to $x_i$, which implies $x_i$ is unbounded, which is absurd

Claim. For some constant $D$ roots of all polynomials $pf+g$ lie in $[-D;D].$ Proof. Since $\deg f>\deg g$ one may take $D$ such that $|g(x)/f(x)|<1$ for all $|x|>D.$ Then $$|pf(x)+g(x)|=|f(x)|(p-|g(x)/f(x)|)>0\text{ } \Box$$ By Gauss' lemma $pf+g$ can be represented as the product of two polynomials with degrees $1,f-1$ - since $p$ is prime one of them (denote it by $h_p$) has leading coefficient dividing the leading coefficient of $f.$ Thus all $h_p$ may have finitely many leading coefficients and degrees, and infinitely many of them coincide at both parameters. By Rational Root theorem set of roots of $h_p$ is finite and therefore for some polynomial $h=h_{p}=h_{q}$ and primes $p\neq q$ we have $h|((pf+g)-(qf+g))=(p-q)f.$ But either $h$ or $f/h$ is linear implying the conclusion.

Let $\deg f=n>m=\deg g$ and let $f(x)=a_nx^n+\cdots+a_0$, $g(x)=b_mx^m+\cdots+b_0$; also, for convenience, extend the sequence $(b_i)$ to $n$, so the last few terms should be zeroes. Let $p_1,p_2,\ldots$ be the primes such that $p_if+g$ has a rational root, and let this rational root be $x_i/y_i$, where $x_i \perp y_i$ and $y_i>0$. Then by the rational root theorem, $y_i \mid p_ia_n$. Since $\deg f>\deg g$, there exists some constant $M>0$ such that any real root of $pf+g$ will fall in the interval $[-M,M]$. If there are infinitely many $i$ such that $y_i \mid a_n$, then by Pigeonhole and this size constraint some rational root must actually appear twice, so by subtraction it's a root of $f$ and we're done. Therefore suppose that there are finitely many such $i$. Thus for all sufficiently large $i$ we can write $y_i=p_iz_i$, where $z_i \mid a_n$. Now take $i$ so that $p_i$ is large, hence $p_i>\max\{|a_n|,\ldots,|a_0|,|b_m|,\ldots,|b_0|\}$, and consider $p_if(\tfrac{x_i}{p_iz_i})+g(\tfrac{x_i}{p_iz_i})$. Take this expression "modulo $p_i^{2-n(1+\nu_{p_i}(z_i))}$", which is $$p_ia_n\left(\frac{x_i}{p_iz_i}\right)^n+b_{n-1}\left(\frac{x_i}{p_iz_i}\right)^{n-1}.$$This expression should also be congruent to zero, and since $p_i$ is large the first summand is not zero, so the second shouldn't be either. This implies that $b_{n-1} \neq 0$, i.e. $m=n-1$, and additionally $\nu_p(z_i)=0$. Multiplying through by $p_i^{n-1}$, this actually implies that $$a_n\left(\frac{x_i}{z_i}\right)^n+b_{n-1}\left(\frac{x_i}{z_i}\right)^{n-1} \equiv 0 \pmod{p} \implies x_i \equiv -\frac{z_ib_{n-1}}{a_n} \pmod{p}.$$By infinite pigeonhole, some value of $z_i$ should appear infinitely many times. For these $i$, we have that the integer $x_i$ is congruent to some fixed value $r$ modulo $p$, i.e. for these $i$ the rational root of $p_if+g$ is of the form $$\frac{r+k_ip_i}{z_ip_i}=\frac{r}{z_ip_i}+\frac{k_i}{z_i},$$where $k_i$ is an integer. Since $\tfrac{k_i}{z_i}$ doesn't depend on $p_i$, we find that $k_i$ must be bounded, since otherwise we can find roots outside $[-M,M]$. Therefore, by infinite pigeonhole again we can consider some $K$ which appears infinitely many times. In general, given our two polynomials $f,g$, as $t \to +\infty$ every root of $tf+g$ must approach the roots of $f$, since if there exists some absolute constant $c>0$ such that the absolute distance between some root $a$ of $tf+g$ and the closest root of $f$ is at least $c$, then we have a positive lower bound on $|f(a)|$, and sending $t \to \infty$ yields a contradiction, since $g(a)$ will always be bounded above (remember that $a \in [-M,M]$). On the other hand, picking the $i$ as described above, we can find some subsequence of roots all of the form $\tfrac{r}{z_ip_i}+\tfrac{K}{z_i}$, and as $i \to \infty$ this limit of this quantity is $\tfrac{K}{z_i}$, so $\tfrac{K}{z_i}$ must be a root of $f$. Since it's clearly rational, we are done. $\blacksquare$ Remark: The key steps in this solution are looking at the expression congruent $p^{\text{thing}}$ and considering the limit idea. The first is motivated once we get that we should have $y_i=p_iz_i$: in general, "most of the time", $p_i$ dividing the denominator will give a $\nu_{p_i}$ contradiction, so we should be able to get some (fairly strong) condition out of this. The limit idea can be motivated once we perform further manipulations, but in my case I actually arrived at it from a different direction before I did these manipulations and got to $\tfrac{r}{z_ip_i}+\tfrac{k_i}{z_i}$. Once I got the "we can fix $x_i$ modulo $p$" idea, I started thinking backwards, wondering how this would connect to the actual rational root of $f$. Instinctively one might suspect that some rational root of $f$ would pop up as a root of $pf+g$, but this is false: just take $f(x)=x$ and $g(x)=1$. But in this case, I actually realized that the root of $pf+g$ approached the root of $f$, and it became clear that this behavior generalized.

TheUltimate123 wrote: By Gauss' lemma $pf+g$ is the product of two polynomials $h_p$ and $j_p$, with the leading coefficient of $h_p$ dividing that of $f$, and $1\in\{\deg h_p,\deg j_p\}$. There are finitely many possible leading coefficients and degrees, so assume infinitely many $h_p$ have the same degree and leading coefficient. There are finitely many possible set of roots of $h_p$ by Rational Root theorem, so there are finitely many possible $h_p$. Thus for some $h$, we have $h=h_p$ infinitely often. squareman wrote: By Gauss's Lemma, each $h_i$ can be represented as the product of an integer polynomial with degree $1,$ and an integer polynomial with degree $\deg f - 1.$ One of these has a leading coefficient dividing the leading coefficient of $f,$ since $p$ is prime. Call this polynomial $j_i.$ By PHP, we can find infinitely many $j_i$ with equal degree and leading coefficient. These polynomials have equal degree, equal leading coefficient, and roots that are bounded in magnitude. By RRT, there are only finitely many numbers that can be the root of such a polynomial, and thus finitely many such polynomials that exist. So by PHP, we can find an integer polynomial $j$ of degree $1$ or $\deg f-1$ dividing at least two of the $h_i,$ and thus dividing $f$ as well. Either $j$ or $f/j$ yields a rational root of $f$. I'm wondering if someone can spell this out for me (post #19 had the same question). I think I'm missing something. I can see that for large prime $p$ in the problem statement, we should have $pf+g = h_p(x) j_p(x)$ for some $h_p$ and $j_p$ where $h_p$ has leading coefficient coprime to $p$ (using notation from #18; the notation from #23 uses $j_p$ instead), where one of the polynomials has degree $\deg f -1$ and the other has degree $1$. The problematic case seems to be where, say, $\deg h_p = \deg f - 1$ for all these primes $p$, and $h_p$ has leading coefficient coprime to $p$. In that case, there seems to be no promise that $h_p$ has rational roots at all, because the rational root is coming from the linear factor $j_p$. Therefore I don't see how the set of possible $h_p$ can be constrained to a finite set. (Meanwhile, the $j_p$ are all different because they have factors of $p$ in the leading coefficient.)

v_Enhance wrote: TheUltimate123 wrote: By Gauss' lemma $pf+g$ is the product of two polynomials $h_p$ and $j_p$, with the leading coefficient of $h_p$ dividing that of $f$, and $1\in\{\deg h_p,\deg j_p\}$. There are finitely many possible leading coefficients and degrees, so assume infinitely many $h_p$ have the same degree and leading coefficient. There are finitely many possible set of roots of $h_p$ by Rational Root theorem, so there are finitely many possible $h_p$. Thus for some $h$, we have $h=h_p$ infinitely often. squareman wrote: By Gauss's Lemma, each $h_i$ can be represented as the product of an integer polynomial with degree $1,$ and an integer polynomial with degree $\deg f - 1.$ One of these has a leading coefficient dividing the leading coefficient of $f,$ since $p$ is prime. Call this polynomial $j_i.$ By PHP, we can find infinitely many $j_i$ with equal degree and leading coefficient. These polynomials have equal degree, equal leading coefficient, and roots that are bounded in magnitude. By RRT, there are only finitely many numbers that can be the root of such a polynomial, and thus finitely many such polynomials that exist. So by PHP, we can find an integer polynomial $j$ of degree $1$ or $\deg f-1$ dividing at least two of the $h_i,$ and thus dividing $f$ as well. Either $j$ or $f/j$ yields a rational root of $f$. I'm wondering if someone can spell this out for me (post #19 had the same question). I think I'm missing something. I can see that for large prime $p$ in the problem statement, we should have $pf+g = h_p(x) j_p(x)$ for some $h_p$ and $j_p$ where $h_p$ has leading coefficient coprime to $p$ (using notation from #18; the notation from #23 uses $j_p$ instead), where one of the polynomials has degree $\deg f -1$ and the other has degree $1$. The problematic case seems to be where, say, $\deg h_p = \deg f - 1$ for all these primes $p$, and $h_p$ has leading coefficient coprime to $p$. In that case, there seems to be no promise that $h_p$ has rational roots at all, because the rational root is coming from the linear factor $j_p$. Therefore I don't see how the set of possible $h_p$ can be constrained to a finite set. (Meanwhile, the $j_p$ are all different because they have factors of $p$ in the leading coefficient.) I mentioned this to Evan a while ago but for the sake of posterity I will post it here. I also don't see how RRT is applicable here, but an alternate proof of the fact that finitely many polynomials exist is to invoke Vieta's. Each of the symmetric sums is bounded, since each possible root is bounded, and since the leading coefficients are all equal the coefficients are bounded too. Since they're integers, this implies the desired conclusion.

Let $h_p(x)=pf(x)+g(x)$ have root $r_p=\tfrac{s_p}{t_p}$ where $s_p$ and $t_p$ are relatively prime and $t_p$ is positive. Since $\deg f>\deg g$, there exists a value $N$ such that $|x|>N\implies |f(x)|>|g(x)|$. In this case, $|pf(x)|>|g(x)|$ which implies $pf(x)+g(x)\neq 0$. Therefore, $|r_p|\le N$. Let $f$ have leading coefficient $f_n$. By RRT, we have $t_p\mid pf_n$ for infinitely many $p$. If $p\nmid t_p$ for infinitely many $p$ then $t_p\mid f_n$. Since $t_p$ and $r_p$ are bounded, the set of all possible roots is finite. That means some specific root $r$ is the root of $pf(x)+g(x)$ for infinitely many $p$, and we have $f(r)=g(r)=0$, which finishes. $~$ Now consider the case where $p\nmid t_p$ only for finitely many $p$. Let $h_p(x)=(xt_p-s_p)i_p(n)$ where \[i_p(n)=\left(f_n \frac{p}{t_p} x^{\deg f-1}+\dots\right)\]Note that for infinitely many $p$, $p\mid t_p$ and in these cases, $i_p(n)$'s leading coefficient divides $f_n$. Also note that because the roots of $pf+g$ are bounded, so are the roots of $i_p$. This means that by Vieta's Formulas, each coefficient of $i_p$ is bounded, which means that only finitely many polynomials $i_p$ exist. However, since each $h_p$ corresponds to finitely many $i_p$, that's a contradiction.