Tuymaada 2024 Senior/P7 wrote: Given are two polynomial $f$ and $g$ of degree $100$ with real coefficients. For each positive integer $n$ there is an integer $k$ such that \[\frac{f(k)}{g(k)}=\frac{n+1}{n}.\]Prove that $f$ and $g$ have a common non-constant factor. Nice and instructive problem. The key idea of the problem is that to hit every positive integer, a polynomial can't grow too fast. Tedious writeup incoming. We will start the problem with the following claim. Claim 01. Suppose $p$ and $q$ are non-constant polynomials such that there exists $\alpha, \beta \in \mathbb{R}$ for which \[ \frac{p(x + \alpha)}{q(x + \alpha)} - \frac{p(x)}{q(x)} = \beta \]for infinitely many $x \in \mathbb{R}$. Then $p$ and $q$ has a common non-constant factor. Proof. Suppose otherwise, then we may WLOG $\gcd(p,q) = 1$. The equation can be rewritten as \[ p(x + \alpha)q(x) - p(x)q(x + \alpha) = \beta q(x) q(x + \alpha) \]holds for infinitely many $x \in \mathbb{R}$, which means that the above equation holds for all $x \in \mathbb{R}$ as $h(x) := p(x + \alpha)q(x) - p(x) q(x + \alpha) - \beta q(x) q(x + \alpha)$ is a polynomial which has infinitely many zeroes, which thus has to be null. Therefore, we must have $q(x) \mid p(x) q(x + \alpha)$ as polynomials. However, as $\gcd(p,q) = 1$, then $q(x) \mid q(x+\alpha)$ which forces $q$ to be constant, a contradiction. Therefore, $p$ and $q$ has a common non-constant factor, as desired. The condition of the problem can be restated as two polynomials $g,h \in \mathbb{R}[x]$ for which for any positive integer $n$, there is an integer $k$ such that $\frac{g(k)}{h(k)} = n$, by taking $h(k) := f(k) - g(k)$. Let us write $g(x) = p(x) \cdot h(x) + r(x)$, where $p,r \in \mathbb{R}[x]$ such that $\text{deg}(r) < \text{deg}(h)$. Claim 02. $p$ is linear. Proof. We note that the condition of the problem means that for all positive integer $n$, there exists $k \in \mathbb{Z}$ such that \[ n = \frac{g(k)}{h(k)} = p(k) + \frac{r(k)}{h(k)}. \]It's easy to see from here that $p$ is a nonconstant polynomial as it achieves arbitrarily large values. Let us now suppose otherwise that $p$ is not linear, i.e. that $p$ is of degree at least $2$. There exists $N$ for which $p$ is strictly monotone on $(-\infty, -N) \cup (N,\infty)$, $|p(x + 1) - p(x)| > 4$ and $\left| \frac{r(x)}{h(x)} \right| \le \frac{1}{2}$ for all $|x| \ge N$. Take a natural number $M > \max_{\substack{j \in \mathbb{Z}, h(j) \not= 0 \\ 1 \le |j| \le N }} \frac{g(j)}{h(j)}$ and consider some $k_M, k_{M + 1}, k_{M + 2}\in \mathbb{Z}$ to be integer solutions to \[ \frac{g(k_M)}{h(k_M)} = M, \frac{g(k_{M + 1})}{h(k_{M + 1})} = M + 1, \frac{g(k_{M + 2})}{h(k_{M + 2})} = M + 2 \]By choice of $M$, $|k_M|, |k_{M + 1}|, |k_{M + 2}| > N$ and two of them must be of the same sign by PHP. Take those two numbers, denote them as $x,y$ and note that $|y - x| \ge 1$ from which we have \[ 2 \ge \left| \frac{g(y)}{h(y)} - \frac{g(x)}{h(x)} \right| = \left| p(y) - p(x) + \frac{r(y)}{h(y)} - \frac{r(x)}{h(x)} \right| \ge |p(y) - p(x)| - 1 \]which gives us a contradiction. Therefore, $p$ has to be linear. As $p$ is linear, we may write $p(k) = ak + b$ for some $a,b \in \mathbb{R}$ where $a \not= 0$. This means that $ak + b + \frac{r(k)}{h(k)} = n$ has a solution in $k \in \mathbb{Z}$ for all $n \in \mathbb{N}$. Take $N$ large enough so that $\left| \frac{r(x)}{h(x)} \right| \le \frac{1}{4}$ for all $x \ge N$. Take a natural number $T > \max_{\substack{j \in \mathbb{Z}, h(j) \not= 0 \\ 1 \le |j| \le N }} \frac{g(j)}{h(j)}$ and for every natural number $M \ge T$, pick $k_M, k_{M + 1} \in \mathbb{Z}$ such that \[ ak_M + b + \frac{r(k_M)}{h(k_M)} = M \quad \text{and} \quad \ ak_{M + 1} + b + \frac{r(k_{M + 1})}{h(k_{M + 1})} = M + 1 \]Now I claim that $0 < |k_{M+ 1} - k_M| \le \left \lceil \frac{3}{2|a|} \right \rceil$. To see this, just note that \[ 1 = \left| a(k_{M + 1} - k_M) + \frac{r(k_{M + 1})}{h(k_{M + 1})} - \frac{r(k_M)}{h(k_M)} \right| \ge |a| \cdot |k_{M + 1} - k_M| - \frac{1}{2} \]which gives us the desired result. Now, consider the sequence $\{ k_i \}_{i \ge T}$ for which we have \[ ak_i + b + \frac{r(k_i)}{h(k_i)} = i \ \forall i \ge T \]By PHP, there exists $j \in \left \{ -\left \lceil \frac{3}{2|a|} \right \rceil, \dots, -2, -1, 1, 2, \dots, \left \lceil \frac{3}{2|a|} \right \rceil \right \}$ such that $k_{i + 1} - k_i = j$ happens infinitely often, for which we must have \[ ja + \frac{r(x + j)}{h(x + j)} - \frac{r(x)}{h(x)} = 1 \]for infinitely many $x \in \mathbb{R}$. By our first claim, this force $r$ and $h$ to have a common non-constant factor $s \in \mathbb{R}[x]$, but this forces $s$ to divide both $f$ and $g$ as well, and thus $f$ and $g$ has a common non-constant factor.

IndoMathXdZ wrote: Nice and instructive problem. Absolutely agree! In fact, $f-g|f,g$. Very nice problem!