Let $f(x),g(x)$ be two polynomials with integer coefficients. It is known that for infinitely many prime $p$, there exist integer $m_p$ such that $$f(a) \equiv g(a+m_p) \pmod p$$holds for all $a \in \mathbb{Z}.$ Prove that there exists a rational number $r$ such that $$f(x)=g(x+r).$$
Problem
Source: 2021 China TST, Test 1, Day 2 P4
Tags: algebra, polynomial, number theory, modular arithmetic
18.03.2021 14:23
20.03.2021 12:10
A good problem for P1 I think. <lemma> There exist $f(x) \in Z[x]$ and prime $p$ that satisfies $deg(f(x))=n$. If $f(x) \equiv 0$ $(mod\ p$) has more than $n$ roots, all of the coefficients of $f(x)$ can be divided by $p$.
Let $f(x)=a_nx^n+a_{n-1}x^{n-1}+\dots+a_1x+a_0$ and $g(x)=b_mx^m+b_{m-1}x^{m-1}+\dots+b_1x+b_0$ ($a_n\neq 0, b_m \neq 0$) WLOG) $n \ge m$ For infintly many $p>n$, the number of roots that satisfies $P_p(a)=f(a)-g(a+m_p) \equiv 0$ $(mod\ p)$ is $p$, which is bigger than $n$. since $deg(P_p(x))\leq n$, $p$ divides all coefficients of $P_p(x)$ because of the lemma. If $n>m$, infintly many $p| a_n \rightarrow a_n=0$ which is a contradiction. So, $n=m \rightarrow$ infinitly many $p|a_{n-1}-b_{n-1}-nb_nm_p \rightarrow$ $m_p=\frac{a_{n-1}-b_{n-1}}{nb_n}\pmod p$. This gives that $f(x)-g\left(x+\frac{a_{n-1}-b_{n-1}}{nb_n}\right)\equiv 0\pmod p$ for infintly many $p$. In conclution, $f(x)=g\left(x+\frac{a_{n-1}-b_{n-1}}{nb_n}\right)$ for all integers $x$.
20.03.2021 14:00
Definition 0: Say that pair \(\left(\pi_{0},\pi_{1}\right)\) of polynomials \(\pi_{0},\pi_{1}\in\mathbb{Q}\left[x\right]\) has the local twist property with respect to twisting \[s\colon\left(\left\{\text{primes of }\mathbb{Z}\right\}\to\mathbb{Q}\right)/\text{finite disagreement}\]if \[\text{For cofinitely many primes }\mathfrak{p}\text{, }\pi_{1}\left(x\right)=\pi_{0}\left(x+s\left(\mathfrak{p}\right)\right)\text{ identically over }\mathbb{Z}/\mathfrak{p}.\] Proposition 1: If \(\left(\pi_{0},\pi_{1}\right)\) has the local twist property, then \(\text{deg}\left(\pi_{1}\right)=\text{deg}\left(\pi_{0}\right)\). Proof of proposition 1: There are cofinitely many primes strictly greater than \(\text{max}\left(\text{deg}\left(\pi_{0}\right),\text{deg}\left(\pi_{1}\right)\right)\). \(\Box\) Definition 2: Say that pair \(\left(\pi_{0},\pi_{1}\right)\) as above has the global twist property if there exists some (cofinitelymanywhere) constant twisting \(s\) as above with respect to which \(\left(\pi_{0},\pi_{1}\right)\) has the local twist property. Proposition 3: If \(\left(\pi_{0},\pi_{1}\right)\) as above has the global twist property with respect to \(s\), then, denoting by \(\overline{s}\) the value attained cofinitelymanywhere by \(s\), \[\pi_{1}\left(x\right)=\pi_{0}\left(x+\overline{s}\right)\]for all \(x\in\mathbb{Q}\). Proof of proposition 3: It is classic that two polynomials in \(\mathbb{Q}\left[x\right]\) are equal as elements of \(\mathbb{Q}\left[x\right]\) if and only if they agree at cofinitely many primes of \(\mathbb{Z}\). \(\Box\) Proposition 4: If \(\pi_{0}\neq\pi_{1}\) identically over \(\mathbb{Q}\), i.e., the two disagree at at least one point in \(\mathbb{Q}\), then there is, for each \(\left(\pi_{0},\pi_{1}\right)\), at most one twisting \(s\) (modulo disagreement at finitely many places) relative to which \(\left(\pi_{0},\pi_{1}\right)\) has the local twist property (whence the global twisting property). Proof of proposition 4: Observe, recalling proposition 1, that \[s\left(\mathfrak{p}\right)=_{\mathbb{Z}/\mathfrak{p}}\text{deg}\left(\pi_{0}\right)^{-1}\cdot\text{leading coefficient}\left(\pi_{1}-\pi_{0}\right)\]for cofinitely many \(\mathfrak{p}\). Definition 5: Given polynomial \(\pi\in\mathbb{Q}\left[x\right]\), define \[\text{d}\pi\colon x\mapsto\pi\left(x+1\right)-\pi\left(x\right).\] Proposition 6: If \(\text{deg}\left(\pi\right)>0\), then \(\text{deg}\left(\text{d}\pi\right)=\text{deg}\left(\pi\right)-1\). Proof of proposition 6: Classical. \(\Box\) Proposition 7: For all primes \(\mathfrak{p}\) of \(\mathbb{Z}\), \[\text{d}\left(x\mapsto\rho\left(x+s\right)\right)=_{\mathbb{Z}/\mathfrak{p}}\text{d}\rho\left(x+s\right).\] Proof of proposition 7: Classical. \(\Box\) Proposition 8: If \(\left(\pi_{0},\pi_{1}\right)\) has the local twist property but not the global twist property, then \(\left(\text{d}\pi_{0},\text{d}\pi_{1}\right)\) has the local twist property but not the global twist property. Proof of proposition 8: That if \(\left(\pi_{0},\pi_{1}\right)\) has the local twist property with respect to some \(s\), then so, too, does \(\left(\text{d}\pi_{0},\text{d}\pi_{1}\right)\) is elementary from proposition 7. That if, if \(\pi_{0}\neq\pi_{1}\) as in proposition 3, and \(\left(\pi_{0},\pi_{1}\right)\) has the local twist property, then \(\left(\text{d}\pi_{0},\text{d}\pi_{1}\right)\) has the global twist property, then \(\left(\pi_{0},\pi_{1}\right)\) has the global twist property then follows from proposition 4. Theorem 9 (Problem): If \(\left(\pi_{0},\pi_{1}\right)\) has the local twist property, then \(\left(\pi_{0},\pi_{1}\right)\) has the global twist property. Proof of proposition 9: Suppose that there exists pair \(\left(\pi_{0},\pi_{1}\right)\) of minimal degree which has the local twist property but not the global twist property. Then from proposition 6 in conjunction with proposition 8, \(\text{deg}\left(\pi_{0}\right)=\text{deg}\left(\pi_{1}\right)=0\), whence an easy contradiction after which remains necessary only some quick workup via proposition 3. \(\blacksquare\)
27.04.2021 17:25
Let's consider the polynomial $g(x+y)-f(x)$. Now, let us write this as a polynomial in $x$ with coefficients as polynomials in $y$. Call this polynomial $P$ and let $n=\max(\deg f, \deg g)$. Now, pick $p>n$. Now, there exists a value of $y$ such that this polynomial becomes the $0$ polynomial mod $p$ as $n>p$ and this polynomial has $p$ roots. Now, if $\deg g\ne \deg f$ then the coefficient of $x^{n}$ is a non-zero constant and thus, it cannot have a root. Thus, $\deg f=\deg g$. Now, let us look at the coefficient of $x^{n-1}$. It is a linear polynomial in $y$ as there is a non-constant coefficient of $y$. Let the root of this polynomial be $r$. Now, $r$ is rational and thus the common root must always be congruent to $r\pmod{p}$ for all large enough primes. Thus, all large enough primes divide $f(x)-g(x+r)$ for all values of $x$. Thus, $f(x)-g(x+r)$ is the $0$ polynomial and we are done.
24.05.2021 18:35
Define \begin{align*} f(x)&=a_nx^{n-1}+a_{n-1}x^{n-1}+\cdots+a_1x+a_0\\ g(x)&=b_mx^{m-1}+b_{m-1}x^{m-1}+\cdots+b_1x+b_0. \end{align*}Restrict our attention to primes \(p>\max\{\deg f,\deg g\}\); for these primes \(f(x)-g(x+m_p)\) is the zero polynomial in \(\mathbb F_p[x]\). Claim: \(\deg f=\deg g\). Proof. If, for contradiction, \(\deg f>\deg g\), then by taking \(p>|a_n|\), the \(x^n\) coefficient of \(f(x)-g(x+m_p)\equiv0\) in \(\mathbb F_p[x]\) is nonzero, contradiction. \(\blacksquare\) Now observe that the \(x^{n-1}\) coefficient of \(g(x+m_p)\) is \(na_n\cdot m_p+b_{n-1}\). By taking \(p>|na_n|\), we find from analyzing the \(x^{n-1}\) coefficient of \(f(x)-g(x+m_p)\) in \(\mathbb F_p[x]\) that \[m_p\equiv\frac{a_{n-1}-b_{n-1}}{na_{n-1}}\pmod p.\] It follows that \[f(x)-f\left(x+\frac{a_{n-1}+b_{n-1}}{na_{n-1}}\right)\]is the zero polynomial modulo infinitely many \(p\), so it is the zero polynomial.
06.06.2021 05:45
We will consider the multivariate polynomial $P(a, b) = f(a) - g(a + b)$. We are given for infinitely primes $p$, that $P(a, b)$ in $a$ is equivalent to $0$ mod $p$ everywhere, and hence there exists $b$ for which its coefficients (which are polynomials in $b$) must all be $0 \pmod p$. First, note that $f, g$ have equal degree, else taking $p >> |f_{\text{leading}}|, |g_{\text{leading}}|$ yields that the $a$-leading coefficient of $P(a, b)$ for any $b$ has absolute value either $f_{\text{leading}}$ or $g_{\text{leading}}$, which is not divisible by $p$ and hence $P(a, b)$ cannot be $0$ mod $p$ everywhere if $\deg f \neq \deg g$. So now we write\begin{align*}f(x) &= f_nx^n + \ldots + f_1x + f_0\\g(x) &= g_nx^n + \ldots + g_1x + g_0\end{align*}for some integer coefficients $\{f_i\}_{i = 0}^n$ and $\{g_i\}_{i=0}^n$ with $f_n = g_n$. Now we individually analyze coefficients; the $x^{m-1}$ coefficient of $P(a, b)$ is\[(f_{m-1} - g_{m-1}) - mbg_m \equiv 0 \pmod p\]for all primes $p$. Let's consider sufficiently large primes $p > |n\max(f_i, g_j)|$. For each such $p$, choosing a\[b \equiv \tfrac{f_{m - 1} - g_{m-1}}{mg_m} \pmod p\]causes the coefficient of $x^{m-1}$ in $P(a, b)$ in terms of $a$ to vanish. Hence, by CRT, we may create a $b$ satisfying $b \equiv \tfrac{f_{m - 1} - g_{m-1}}{mg_m} \pmod p$ for all $m$, and then $f(x) - g(x + b)$ for that $b$ vanishes modulo $p$ for all $x$. We may do this for all sufficiently large $p$, so we are done. $\blacksquare$
25.01.2022 15:40
Consider sufficiently large such primes, which are greater than the degree of $f,g$ as well as their coefficients. We must have that in $\mathbb{F}_p$, $f(a) = g(a+m_p)$ holds as an identity. Clearly, this implies that both $f,g$ have the same degree (say $d$) as well as leading coefficient (say $k$). Let $z_1, z_2$ be the coefficients of $x^{d-1}$ in $f,g$. We must have(on comparing coefficients) that $z_1 \equiv dkm_p + z_2 \pmod p$, obviously, neither of $d,k$ are zero, so $m_p \equiv \frac{z_1 - z_2}{dk} \pmod p$ for infinitely many primes $p$, so we just can take $r = \frac{z_1 - z_2}{dk}$ for the problem, so we are done. $\blacksquare$
20.05.2022 08:21
A sketch, Just take large enough primes and conclude by lagrange that $f,g$ have equal deg,and equal leading coeff.Then,if the degree is $d$,then comparing by lagrange,the coeff of $d-1$,in $f,g(x+m_p)$ finishes
28.09.2023 16:11
Focus only on primes $p>\max(\deg f,\deg g)$, in which case we must have $f(x) \equiv g(x+m_p)$ as a polynomial identity in $\mathbb{F}_p[x]$. We immediately find that $f$ and $g$ have the same degree $d$ and leading coefficient $a$. Suppose that the coefficient of $x^{d-1}$ in $f$ is $b$ and the coefficient of $x^{d-1}$ in $g$ is $c$. By looking at primes greater than $\max(a,b,c,d)$ and equating the coefficients of $x^{d-1}$ we have $$b \equiv c+adm_p \pmod{p} \implies m_p \equiv \frac{b-c}{ad} \pmod{p},$$hence $f(x)=g(x+\tfrac{b-c}{ad})$ holds as a polynomial identity in $\mathbb{F}_p[x]$ for infinitely many $p$, hence holds in $\mathbb{Q}$. $\blacksquare$