Let $P$ and $Q$ be non-constant integer-coefficient monic polynomials, and let $a$ and $b$ be integers satisfying $| a | \geq 3$ and $ | b | \geq 3$. These satisfy the following conditions for all positive integers $n$: $$ P(n) \mid Q(n)^2 + aQ(n) + 1, \quad Q(n) \mid P(n)^2 + bP(n) + 1. $$Determine all possible ordered pairs $(a+b, \deg P)$.
HIDE: Original wording 상수다항식이 아닌 최고차항의 계수가 1인 정수계수다항식 $P$, $Q$와 정수 $a$, $b$($| a |, | b | \geq 3$)가 모든 양의 정수 $n$에 대해 $$P(n) \mid Q(n)^2 +aQ(n)+1, \quad Q(n) \mid P(n)^2+bP(n)+1$$을 만족한다. 이때 가능한 모든 $(a+b, \deg P)$ 순서쌍을 구하여라.Problem
Source: 2025 Korea winter program practice test P2
Tags:
Acorn-SJ
19.01.2025 08:59
bump this
kmh1
19.01.2025 12:18
The problem is trivial. Any integer pair $(k,l)$ such that $l\ge 1$ works. Let $a=-2$, $b=k+2$, $P(n)=n^l+c$ for a sufficiently large constant $c$, and let $Q(n)=P(n)^2+(k+2)P(n)+1$. If we choose $c$ large enough so that $P(n)Q(n)>0$ for all positive integers $n$ then the conditions are obviously satisfied.
Acorn-SJ
19.01.2025 17:16
kmh1 wrote: The problem is trivial. Any integer pair $(k,l)$ such that $l\ge 1$ works. Let $a=-2$, $b=k+2$, $P(n)=n^l+c$ for a sufficiently large constant $c$, and let $Q(n)=P(n)^2+(k+2)P(n)+1$. If we choose $c$ large enough so that $P(n)Q(n)>0$ for all positive integers $n$ then the conditions are obviously satisfied. Oops sorry I left out some conditions: namely $| a | \geq 3$ and $ | b | \geq 3$. I fixed the problem.
kmh1
19.01.2025 18:31
If we let $P(n)=n^{2k}+5mn^k+5$, $Q(n)=n^{2k}+6mn^k+6$, $a=5m^2-2$, $b=-6m^2+2$ these satisfy the conditions. We get $(a+b,deg P)=(-m^2,2k)$ for some positive integers $m,k$. Now we prove these are the only pairs that are possible. Easy to see $gcd(P(n),Q(n))=1$ so we have $P(n)Q(n) \mid P(n)^2+Q(n)^2+bP(n)+aQ(n)+1$. So for $x=Q(n)$, $y=P(n)$ we get $\frac{x^2+y^2+ax+by+1}{xy}\in\mathbb{Z}$. Now we prove the following lemma. The set of integers $k$ for which $\frac{x^2+y^2+ax+by+1}{xy}=k$ has a positive integer solution $(x,y)$ is finite.
For a fixed nonnegative integer $m$, if $|x-y|=m$ and $\frac{x^2+y^2+ax+by+1}{xy}\in\mathbb{Z}$, we need $x \mid m^2+bm+1$ or $y \mid m^2+am+1$. Because of $|a|, |b|\ge 3$ we have $m^2+bm+1, m^2+am+1\neq 0$. Therefore such $x,y$ are finite. Also, if $x=m$ and $\frac{x^2+y^2+ax+by+1}{xy}\in\mathbb{Z}$, we need $y \mid m^2+am+1$, which is also finite. If $y=m$ and $\frac{x^2+y^2+ax+by+1}{xy}\in\mathbb{Z}$, we need $x \mid m^2+bm+1$, which is also finite. We can conclude that the set of integer pairs $(x,y)$ such that $min(x,y,|x-y|)=m$ and $\frac{x^2+y^2+ax+by+1}{xy}\in\mathbb{Z}$ is finite.
Choose a large $M$. The set $\{(x,y) | min(x,y,|x-y|)\le M, \frac{x^2+y^2+ax+by+1}{xy}\in\mathbb{Z}\}$ is finite, so the set of integer values of $\frac{x^2+y^2+ax+by+1}{xy}$ for $min(x,y,|x-y|)\le M$ is finite. Now assume the lemma is not true. Then there must exist an integer $k$ such that $\frac{x^2+y^2+ax+by+1}{xy}=k$ has a positive integer solution $(x,y)$, and for all such solutions $min(x,y,|x-y|)>M$. Let $(x_0,y_0)$ be the solution such that $x+y$ is minimal. We have $x_0^2-(ky_0-a)x_0+y_0^2+by_0+1=0$. If $x_0>y_0$, then $(\frac{y_0^2+by_0+1}{x_0},y_0)$ is also a solution. However if we choose $M$ sufficiently large, then $y_0^2+by_0+1>0$ and $\frac{y_0^2+by_0+1}{x_0}<\frac{y_0^2+by_0+1}{y_0+M}<y_0<x_0$, contradicting the minimality of $x_0+y_0$. We similarly get contradiction for $x_0<y_0$, so the lemma is proven.
For all large enough $n$ we have $P(n),Q(n)>0$, so we get infinitely many positive integer pairs $(x,y)=(Q(n),P(n))$ such that $\frac{x^2+y^2+ax+by+1}{xy}\in\mathbb{Z}$. Because of the lemma, there exists an integer $k$ such that $\frac{Q(n)^2+P(n)^2+aQ(n)+bP(n)+1}{P(n)Q(n)}=k$ has infinitely many solutions. But then the polynomial $P(x)^2+Q(x)^2+bP(x)+aQ(x)+1-kP(x)Q(x)$ has infinitely many roots, so it must be the zero polynomial. If $deg P\neq deg Q$ we easily get contradiction. We get $deg P=deg Q$, and because $P,Q$ are monic, looking at the $x^{2deg P}$ coefficient we get $k=2$. We can then write $(Q(x)-P(x))^2+a(Q(x)-P(x))+1=-(a+b)P(x)$. The case when $a+b=0$ is trivially ruled out, and comparing the highest degree term here we get $-(a+b)$ is a positive perfect square and $deg P$ is even.