Switched P(X) with Q(X) Let $A(X)P(X)+Q(X)B(X)=c$ since the polynomials are coprime $deg Q =q$ let $A$=[set of primes $\le max,c, deg Q+2$} We can generate an infinite set of integers, $n$ with the exponent of any prime from $A$ in $Q(n)$, n from this set to be bounded (Chinese remeinder theorem etc) we have $gcd(3^a-1,3^b-1)= 3^{Gcd(a,b)}-1$ so we have $2^{p(n+yp(n)}-1/3^{q(n+yp(n))}-1$ so $2^{P(n)}-1/3^{Gcd(q(n),q(n+yp(n))} -1$ pick n from that infinite set and we have that the exponents of $gcd(q(n)....$ are bounded in the set A .Now if p prime not in $A$, $p/Gcd(Q(n),(q(n+p(n)y).$ for every $y$, p does not divide $p(n)$ $(p>c)$, $deg(Q)<p-1$ there exists y such that $q(n+yp(n))$ is not divisble by p ( Lagrage). So p(N) is a constant polynomial.

Here is a clearer solution. As $\gcd(P,Q) = 1$, there exist integer polynomials $A,B$ such that $P(x) A(x) + Q(x) B(x) = c$ for some integer $c$. This means that for all primes $p>c$ and positive integers $a$ such that $p|P(a)$, we have $p \nmid Q(a)$. Similarly if $p|Q(a)$ then $p \nmid P(a)$. Now, note that as we have for all integers $a,m,n$, $\gcd(a^m-1, a^n-1) = a^{\gcd(m,n)} - 1$, we have \[(2^{Q(n)}-1)|\gcd(2^{Q(n)} - 1, 2^{Q(n + zQ(n))}-1)\] \[ \implies (2^{Q(n)}-1)|(3^{\gcd(P(n), P(n + zQ(n))}-1)\] I claim that \[\gcd(P(n), P(n+Q(n)), P(n+2Q(n)), ...)\] is bounded by a value independent of $n$, which would imply $Q$ is constant. Now, consider all primes $q > \max(c, \deg P + \deg Q)$. It is clear that for such primes $P,Q$ cannot vanish modulo $q$. Suppose one of these primes divides all of the terms in above gcd. Then as it divides $P(n)$, it cannot divide $Q(n)$. But then it follows that $\gcd(Q(n), q) = 1$ so we have $P$ must vanish modulo $q$. This is a contradiction. Thus the above gcd only contains sufficiently small primes in its prime factorization. To show their exponents are bounded simply note that if $v_q(P(n)) = k > v_q(c)$ we have $v_q(Q(n))$ is bounded above by a number $L$ independent of $k$. But then it follows $P(n + q^Lx)$ is divisible by arbitrarily high powers of $q$ as $n$ varies. This is clearly absurd as then $P$ is $0$ on some positive integer between $1$ and $q^L$. Thus the gcd is bounded above for all $n$ implying $Q(n)$ is constant as desired.

dinoboy wrote: But then it follows $P(n + q^Lx)$ is divisible by arbitrarily high powers of $q$ as $n$ varies. This is clearly absurd as then $P$ is $0$ on some positive integer between $1$ and $q^L$. Can you explain this part please.

I have a solution that spams lifting exponent lemma but it's too long and not creative

From the proposition $P$ and $Q$ are coprime over rationals,then we will find integer polynomials $A$ and $B$ such that $P(x)A(x)-Q(x)B(x)= c$ for some integer $c$.Hence for any integer $n$,$gcd(P(n),Q(n))|c$ . Now if $Q$ is not constant we will indeed get an integer $n$ divisible by $c$ such that $2^{Q(n)}-1>3^{P(c)}-1$. Denote the order of $3$ modulo $2^{Q(n)}-1$ to be $h$.Hence $h \nmid P(c)$. Now clearly $Q(n)|Q(n+rQ(n))$ and hence $2^{Q(n)}-1|2^{Q(n+rQ(n))}-1$.So $ 2^{Q(n)}-1|3^{P(n+rQ(n))}-1$ for any $r$. Hence $h|P(n+rQ(n))$ for any $r$.If $gcd(h,Q(n))|c$ then congruence $xQ(n) \equiv c-n (mod h)$ has a solution $r$ as $n$ is divisible by $c$ as well. Hence $n+rQ(n) \equiv c(mod h)$ and hence $P(n+rQ(n)) \equiv P(c) (mod h)$ which gives $h|P(c)$,a contradiction. Hence $gcd(h,Q(n)) \nmid c$.But as $h|P(n)$,hence $gcd(h,Q(n))|gcd(P(n),Q(n))|c$.Thus once again a contradiction. Hence $Q$ must be constant.

Such a beautiful problem! Solution We firstly observe that $f(n) \mid f(n+zf(n))$ for all integer coefficient polynomials $f$ with $z$ an integer. Moreover, we have $\gcd(a^m-1,a^l-1)=a^{\gcd(m,l)}-1$ for all integers $a,m,l$. We now proceed to the main proof. Assume that $Q$ is non constant and so we have $P$ is also non constant. Next, we consider the fact that since $P,Q$ are coprime over $Q[X]$, there exists $A,B$ with integer coefficients such that $A(X)P(X)-B(X)Q(X)=c$ where $c$ is an integer by Euclid's division lemma. Now, we get \begin{align*} 2^{Q(n)}-1 \mid 2^{Q(n+zQ(n))}-1 \mid 3^{P(n+zQ(n))}-1 \end{align*}by our lemma on gcd of exponents and so, if we denote by \begin{align*} a_n := \gcd(P(n),P(n+Q(n)),P(n+2Q(n)), \dots) \end{align*}then $2^{Q(n)}-1 \mid 3^{a_n}-1$. We claim that $a_n$ is bounded above by a constant independent of $n$. This shall establish our requested result. Fix a sufficiently large integer $n$. Let $p$ be a prime and let $M$ denote the largest exponent of $p$ dividing $a_n$. We have $p^M \mid P(n)$ and $p^M \mid P(n+zQ(n))$ for all $z$. Let $t=v_p(Q(n))$ and suppose that $t \ge M$. In this case, by the equation of Euclid's algorithm, $p^M \mid c$ and so it is bounded. Suppose $t<M$. Notice that $\{ zQ(n) \bmod p^M \}=\{zp^t \bmod p^M \}$ and so we only consider $p^M \mid P(n+zp^t)$. Now, we can choose $z$ such that $n+zp^t$ lies in $\left[\frac{1}{2}\cdot p^t, \frac{3}{2}\cdot p^t\right]$ modulo $p^M$. Let this value be $r$. Then $P(r)=O(p^{dt})>p^M$ where $d$ is the degree of $P$ and so, $t>\frac{M}{d}-l$ for some constant $l$. We get that $M<(v_p(c)+l)\cdot d$ and so, $M$ is bounded. We now show that $p$ is bounded. Let $r_0$ be the smallest natural number for which $P(r_0)>0$. We set $p>\max(P(r_0),c)$. It is clear that $p \nmid \gcd(P(n),Q(n))$ and so, either $p \nmid P(n)$ or $p \nmid Q(n)$. In the former case, $p \nmid a_n$ whereas in the latter, we can see that $\{zQ(n) \bmod p\}=\{z \bmod p\}$ and we can select $z$ such that $n+zQ(n) \equiv r_0 \bmod p$. Thus, if $p \mid a_n$ then $p \mid P(r_0)$ which is false, by the definition of $p$. Thus, all prime factors of $a_n$ are bounded by a constant independent of $n$ and all exponents of primes dividing $a_n$ are bounded above by a constant independent of $n$. In any case, $a_n$ is a bounded sequence and the result follows.

Does this work? We will write $A \equiv B$ to denote the fact that $A$ and $B$ are equivalent as polynomials. Define $Y := \text{gcd}_{k=0}^{\infty}(P(n+kQ(n)))$. Let $a,b,c$ such that $aP + bQ \equiv c$. Let $Z(n) = \text{gcd}(P(n), Q(n))$; note that $Z(n)|c$ for all $n$. Let $fx^d$ be the leading term of $P(x)$. By the above solution, we only need to show that $Y$ is bounded from above by some constant independent of $n$. Note that taking the finite differences of the $P(n+kQ(n))$, we get that $Y|fQ(n)^d (d!)$. Also setting $k = 0$ yields $Y|P(n)$. Thus $Y|f Z(n)^d(d!)|f c^d (d!)$ which is independent of $n$. QED

From Bezout's it follows $Q(n) \mid Q(n+jQ(n))$ and hence $$2^{Q(n)}-1 \mid 2^{Q(n+jQ(n))}-1 \mid 3^{P(n+jQ(n))}-1$$Now if $a := \text{ord}_{2^{Q(n)}-1}(3)$ it follows that $a|P(n+jQ(n)), \forall j \in \mathbb N.$ Let $d := \text{deg P}$ and let $a_d$ be the leading coefficient of $P.$ Now we will interpolate polynomial $P$ in $d+1$ points, namely in $(n+jQ(n))_{j=0}^{d}=(x_i)_{i=0}^{d}.$ So, $$P(x)=\sum_{j=0}^{d}P(x_j) \prod_{i \neq j}\frac{(x-x_i)}{(x_j-x_i)}$$Notice now that $x_i - x_j=Q(n)\cdot (i-j)$ and hence $$P(x)\cdot Q(n)^{d}=\sum_{j=0}^{d} P(x_j) \prod_{i \neq j}\frac{(x-x_i)}{(j-i)}=\sum_{j=0}^{d} P(x_j) \prod_{i \neq j}(x-x_i) \cdot \frac{(-1)^{d-j}}{j! \cdot (d-j)!}$$Notice the $j! \cdot (d-j)!$ in the denominator. Intuitively we should multiply the whole thing with $d!$ in order to pack $\binom{d}{j}.$ So $$P(x)\cdot Q(n)^{d} \cdot d!=\sum_{j=0}^{d} P(x_j) \prod_{i \neq j}(x-x_i) \cdot (-1)^{d-j} \cdot \binom{d}{j}.$$Now considering the leading coefficient of both polynomials it follows that $$a_d \cdot Q(n)^{d} \cdot d!=\sum_{j=0}^{d} P(x_j) \cdot (-1)^{d-j} \cdot \binom{d}{j}$$So now $a|a_d \cdot Q(n+jQ(n))^{d} \cdot d!$ and also $a|P(n+jQ(n)).$ Suppose $Q$ is not constant $\implies$ it is unbounded $\implies$ $a$ is unbounded. So take advantage of this and let $a$ be very very large; since $a_d,d!$ are fixed it follows that $\text{gcd}(P(n),Q(n))_{n=1}^{\infty}$ is not bounded. But since $P,Q$ are coprime, $\exists u$ s.t $P(x)R(x)+Q(X)T(x)=u \in \mathbb Z.$ It follows that $u$ has infinitely many divisors which surely is a contradiction hence $a$ is bounded, hence $Q$ is bounded hence it is constant.

orl wrote: Let $P(x)$ and $Q(x)$ be two polynomials with integer coefficients, such that no nonconstant polynomial with rational coefficients divides both $P(x)$ and $Q(x).$ Suppose that for every positive integer $n$ the integers $P(n)$ and $Q(n)$ are positive, and $2^{Q(n)}-1$ divides $3^{P(n)}-1.$ Prove that $Q(x)$ is a constant polynomial. Since $P,Q$ are coprime, it follows that $P(x)U(x)+Q(x)V(x)=C$ for some $U,V\in\mathbb{Z}[x]$ and $C\in\mathbb{N}$, so $\text{gcd}(P(n),Q(n))$ is bounded. The set $S$ of all primes which divide some $2^{Q(n)}-1$ ($n=1,2,\dots$) is infinite by Zsigmondy's theorem if $Q$ is non-constant. For any prime $p$, let $(x_p,y_p)=(\text{ord}_p(2),\text{ord}_p(3))$; then $x_p|Q(n)$ implies $y_p|P(n)$. Note that $\text{gcd}(x_p,y_p)\le \text{gcd}(P(n),Q(n))\le C$. If $p\in S$, then $\exists n:x_p|Q(n)$, so $y_p|P(n+tx_p+t'y_p)$ ($t,t'\in\mathbb{Z}$) implies that $y_p$ divides one of \[ P(1),P(2),\dots,P(\text{gcd}(x_p,y_p)). \]Hence, all primes in $S$ divide $\prod_{n=1}^C (3^{P(n)}-1)$, a contradiction. This proves that $Q$ is a constant. $\blacksquare$

Take a constant $C$ such that there exist polynomials $A(x), B(x)\in \mathbb{Z}[X]$ with $A(x)P(x)+B(x)Q(x)=C$. Lemma: For a polynomial $f(x)=\sum_{i=0}^d a_i \binom{x}{i}$, we have $\gcd(f(0), f(1),\cdots, f(d)) = \gcd(a_0,a_1,\cdots, a_d)$. Proof: We prove the statement inductively on the degree of $f$. The statement is clearly true for $d=1$. Let $f_1(x)=f(x+1)-f(x)$ and $f_{n+1}(x)=f_n (x+1)-f_n(x)$. Inductively we have $f_n(x)=\sum_{i=n}^{d} a_i \binom{x}{i-n}$. Moreover, note that $f_d(0)$ is a linear combination of $f(0),f(1),\cdots, f(d)$. It thus follows that $\gcd(f(0),f(1),\cdots, f(d))\mid f_d(0)=a_d$. Write $g(x)=f(x)-a_d\binom{x}{d}$. Then note that $\gcd(g(0), g(1),\cdots, g(d-1))=\gcd(a_0,a_1,\cdots, a_{d-1})$. Since $g(i)=f(i)$ for $0\le i\le d-1$, we have $\gcd(f(0),f(1),\cdots, f(d))\mid \gcd(f(0), f(1),\cdots, f(d-1))=\gcd(a_0,a_1,\cdots, a_{d-1})$. Since this gcd also divides $a_d$, we have $\gcd(f(0),f(1),\cdots, f(d))\mid \gcd(a_0,a_1,\cdots, a_d)$. Clearly, the reverse divisibility must be true by the definition of $f$, so we are done. $\blacksquare$ Corollary: If $p$ is a prime, then $\gcd(f(a), f(a+p),\cdots, f(a+pd))$ is $c\cdot \gcd(a_0,a_1,\cdots, a_d)$ where $c\in\{1,p\}$. Proof: Note that the gcd of the coefficients of the Hilbert representation of $f(x+p)-f(x)$ is $p\cdot \gcd(a_0,a_1,\cdots, a_d)$. This proves the claim. Now, write $P(x)=\sum_{i=0}^d p_i \binom{x}{i}$ and $G=\gcd(p_0,p_1,\cdots, p_d)$. Moreover, suppose take a constant $C$ such that $A(x)P(x)+B(x)Q(x)=C>0$ where $A,B\in \mathbb{Z}[X]$. If $Q$ is nonconstant, then there are infinitely many primes that divide $Q(n)$ for some $n$, and thus take a prime $p$ that divides $Q(n)$ for some $n$ with $p>\text{max}(2G, C)$. We have $2^p-1\mid 2^{Q(n+kp)}-1\mid 3^{P(n+kp)}-1$. It thus follows that $2^p-1\mid 3^g-1$ where $g=\gcd(P(n), P(n+p),\cdots, P(n+pd))$. By the corollary above, $g=G$ or $g=Gp$. If $g=G$, then $2^p-1\le 3^G-1 < 4^G-1$, implying that $p<2G$, contradiction! Thus $g=Gp$. But then this means $p\mid P(n)$ and $p\mid G(n)$, implying that $p\mid C$, contradicting $p>C$! Thus we get our contradiction and $Q$ must be constant, as desired. $\square$

@above: What is Hilbert representation?

Yet another different solution. EDIT: oops, actually the same as in post 10.

Suppose that $Q$ is non-constant. Because $Q$ and $P$ are co-prime, by Bezout and Schur there is an arbitrarily big prime $p,$ such that $p\mid Q(n)$ and $p\nmid P(n)$ for some $n.$ Consider a prime divisor $t$ of $2^p-1,$ clearly $p\mid t-1 \implies t>p.$ By a well-known property we have that $p\mid Q(n+ap)$ for any integer $a \implies$ $$2^p-1\mid 2^{Q(n+ap)}-1 \mid 3^{P(n+ap)}-1 \implies d:=\text{ord}_t(3) \mid P(n+ap)$$Since $p\nmid P(n)$ we also have that $p \nmid P(n+ap),$ hence $\gcd(p,d)=1,$ thus as $a$ spans the integer axis, $n+ap$ spans the complete system of residues modulo $d,$ hence $d|P(1),$ but $d>\log_3(t)>\log_3(p),$ implying that $P(1)=0,$ a contradiction.

Here is a less high-powered solution. Fix $t$. Let $m = 2^{Q(t)}-1$ and let $a = \operatorname{ord}_m(2) = Q(t)$. We see then that \[ m \mid 2^{Q(t+ka)}-1 \mid 3^{P(t+ka)}-1. \]Say $P$ has leading coefficient $b$ and degree $d$. Then, we see that \[ \operatorname{ord}_m(3)\mid g = \gcd (P(t), P(t+ka), \ldots) \]Then, $g$ divides the $d+1$th finite difference of $P$ (where differences are taken by $a$ instead of $1$), which is precisely $a^dbd!$. Thus, \[ \operatorname{ord}_m(3)\mid a^dbd! \]On the other hand, \[ \gcd(\operatorname{ord}_m(2), \operatorname{ord}_m(3)) \mid \gcd(Q(t), P(t))\mid c, \]where $c$ is some fixed integer such that there exist $A,B\in \mathbb Z[x]$ such htat $AP + BQ = c$. Thus, $\gcd(a, \operatorname{ord}_m(3))\mid c$, so $\gcd(a^d, \operatorname{ord}_m(3))\mid c^d$. So, we get \[ \operatorname{ord}_m(3)\mid c^dbd!, \]which in particular implies that \[ m = 2^{Q(t)}-1 \mid 3^{c^dbd!}-1 \]is bounded, which thus forces $Q$ constant. $\blacksquare$

Bump. I have a question. Can this be solved without the condition "$P(x)$ and $Q(x)$ are coprime in $\mathbb{Q}[x]$ " ?

The sequence $(\gcd(P(n), Q(n)))_{n \ge 1}$ is bounded above. Proof: By Bezout there exist $A(x), B(x) \in \mathbb{Z}[x]$ and a $k \in \mathbb{N}$ such that $AP + BQ = k$, and so $\gcd(P(n), Q(n)) \mid k$ for all $n$. $\Box$ Suppose $Q$ is non-constant. Take $n$ very large and let $D$ be a large divisor of $2^{Q(n)}-1$. Let $s, t$ be the orders of $2, 3$, resp. mod $D$, where $s, t$ can be made arbitrarily large as we increase $n$ and $D$. By the lemma, $s \mid Q(n)$ and $t \mid P(n)$ imply $\gcd(s, t)$ is bounded above by some $k$ independent of $n$ and $p$. Substitute $n$ with $m=n + is$, where $i=1, 2, 3, \dots$. We preserve $Q(m) \equiv Q(n) \pmod{s}$, so we still have $D \mid 2^{Q(m)}-1 \mid 3^{P(m)}-1$ and thus $t \mid P(m)$ for all such $m$. But we also have the equality of sets \[\{P(m)\}_{i \ge 1} = \{P(n + j\gcd(s, t)) \}_{j \in \mathbb{Z}} \quad \pmod{t}.\]In particular, this means that we can find some $c, j$ such that $P(c) \equiv 0 \pmod{t}$ and $c = n + j\gcd(s, t) \in [1, \gcd(s, t)]$. But $P(c) > 0$ and $c$ is bounded above by $k$, so if $n$ is large enough so that $t > P(1), P(2), \dots, P(k)$ we get a contradiction.

Lemma: $\gcd(P(n),Q(n))|C$ for some fixed $C$. Proof: This is clear by Bezout's Lemma For all large $n$, consider the largest prime factor of $2^{Q(n)}-1$, $p$. Then, we must have $\text{ord}_p(3)|P(n)$. However, $p|Q(n+k\text{ord}_p(2))\implies p|P(n+k\text{ord}_p(2)\pmod{\text{ord}_p(3)})\forall k$. Hence, $P(n)$ has $\frac{\text{ord}_p(3)}{\gcd(\text{ord}_p(2),\text{ord}_p(3))}\ge \frac{\text{ord}_p(3)}{C}$ roots mod $\text{ord}_p(3)$. Now, we claim that we can force $\text{ord}_p(3)$ to have arbitrarily large prime divisors. Obviously, there exists a maximum $e_i$ for all primes $p_i$ such that $p_i^{e_i}\big|P(n)\forall n$. So, we can use CRT with $\pmod{p_i^{e_i+1}}$ to get large $n$ such that $\nu_{p_i}(P(n))$ is bounded for all small primes, such that there exists a big prime $q_0|P(n)$, and $n$ is sufficiently large such that $3^{\prod_{p_i<q_0}p_i^{e_i}}-1<p$. Then, we must have that a prime $q\ge q_0$ must divide $\text{ord}_p(3)$, as desired. Now, given this prime, we use Pigeonhole to show that if $P(n)$ has at least $\frac{\text{ord}}{C}$ roots mod $\text{ord}(3)$, then it has at least $\frac{q}{C}$ roots mod $q$. However, we can choose $q\gg\deg(n)$ which does not divide the leading coefficient of $P(n)$. Then, as $P(n)$ has at least $\frac{q}{C}$ roots mod $q$, we must have $\deg(n)\ge\frac{q}{C}$, which is a contradiction for big $q$. Thus, $p$ must be bounded and we must have $Q(n)$ is constant, as desired.

Since $\operatorname{gcd}(P,Q) =1 \implies \exists A,B \in \mathbb{Z}[X] \text{ such that } AP+BQ=c \text{ for some } c\in \mathbb Z $. In particular $\operatorname{gcd}(P(n),Q(n))$ is bounded and always divides $c$. Let $a \overset{\text{def}}{=} 2^{Q(n)}-1 \mid 3^{P(n)}-1$. Note that $\operatorname{ord}_{a}{2}=Q(n)$ . Also write $d \overset{\text{def}}{=} \operatorname{ord}_{a}{3}$ Now , note that $3^{P(n)}-1 \mid 3^{P(n+Q(n))}-1 \implies d \mid P(n+jQ(n)) \forall j\geq 0 \text{ and } j\in \mathbb{Z} $. Let $\operatorname{deg}P=r$ and let the coefficient of $x^r$ in $P(x)$ be $a_r$ . Hence , $d \mid \sum_{j=0}^{r}(-1)^r \binom{r}{j} P(n+jQ(n))= r! \cdot a_r \cdot {Q(n)}^r$. Note that $d | P(n)$ , so, we have : $$d \mid \operatorname{gcd}(P(n),r! \cdot a_r \cdot {Q(n)}^r)$$Since $\operatorname{gcd}(P(n),Q(n))$ is bounded , so is $d$. This implies $3^d-1$ is bounded . This in turn implies than $2^{Q(n)}-1$ is bounded , which contradicts Kobyashi (!) . Hence $Q(n)$ must be constant

Solved with moral support from Euclid31415. orl wrote: Let $P(x)$ and $Q(x)$ be two polynomials with integer coefficients, such that no nonconstant polynomial with rational coefficients divides both $P(x)$ and $Q(x).$ Suppose that for every positive integer $n$ the integers $P(n)$ and $Q(n)$ are positive, and $2^{Q(n)}-1$ divides $3^{P(n)}-1.$ Prove that $Q(x)$ is a constant polynomial. Proposed by Oleksiy Klurman, Ukraine Solution: Suppose that $Q$ is not a constant polynomial, then by ISL 2009 N3 we know that there exists infinitely many primes $p$ that divides $Q(n)$ for some $n$. We readily observe that $\gcd(P,Q)=c$ for some constant $c$. Thus there exists a $f,g\in \mathbb{Z}[x]$ such that $fP+gQ= c'$. Now observe that if a prime $p>c'$ divides both $P(n), Q(n)$ for some $n$ we must have $p\mid c'$, a contradiction. Now $$2^{Q(n)}-1 \mid 3^{P(n)}-1\implies \text{ord}_{p}(2)\mid Q(n)\implies \text{ord}_p(3)\mid Q(n)$$for all prime $p$. Now choose a prime $q>c'$ and set it equal to $\text{ord}_p(2)$. Thus we know that $\text{ord}_p(2)\mid Q(n+t\cdot\text{ord}_p(2))$ for any integer $t$. Thus we must have $\text{ord}_p(3)\mid P(n+ t \cdot \text{ord}_p(2)+s\cdot \text{ord}_p(3) )$ for all integer $s,t$. But we already know that $\gcd(\text{ord}_p(3), \text{ord}_p(2))=1$(by our choice of $\text{ord}_p(2)$). Thus $\text{ord}_p(3)\mid P(n)$ for all $n$. Thus $\text{ord}_p(3)\mid P(t)\ne 0$. Now take $\text{ord}_p(2)$ arbitrarily large while keeping it a prime. Thus $\text{ord}_p(3)$ will increase unboundedly too, thus we have arrived at a contradiction. $\blacksquare$

Suppose for the sake of contradiction that $Q$ is nonconstant. It is well known that $Q(n)$ has arbitrarily large prime factors. By Bezout's lemma on $P$ and $Q$, there exists some positive integer $g$ such that \[\gcd(P(n),Q(n))\mid g\]for all positive integers $n$. Now, pick $a$ such that $Q(a)$ has a prime factor $e>g$. Clearly by varying $a$, we can make $e$ arbitrarily large. Now, consider a prime factor $p$ of $2^e-1$. We see that \[p\mid 2^e-1\mid 2^{Q(a+ek)}-1\mid 3^{P(a+ek)}-1\]for all non-negative integers $k$. Thus, \[\mathrm{ord}_p(3)\mid P(a+ek)\]for all $k\ge 0$. Note that $\gcd(P(a+ek),Q(a+ek))\mid g$, and $e\mid Q(a+ek)$, $e>g$, so $e\nmid P(a+ek)$. Thus, by varying $k$, we can make $a+ek$ hit any residue mod $\mathrm{ord}_p(3)$, so in particular, \[\mathrm{ord}_p(3)\mid P(1),\]so $\mathrm{ord}_p(3)\le P(1)$. Thus, \[p\mid 3^{P(1)}-1,\]so $p$ is bounded above. However, \[e=\mathrm{ord}_p(2)\le p-1,\]so $e$ is bounded above, which is the desired contradiction. This completes the solution.

suppose $Q(X) $ is not constat choose a prime $q$ such that $\exists c :$ suc that $q|Q(c)$ $q>\phi(3^{p(1)}-1$ $q>gcd(P(X),Q(X))$ now by zsigmondi we have a prime $p$ $p|2^q-1$ and $p>3^{P(1)}-1$ $p|2^{Q(c)}-1$ $p|2^{Q(c+qk)}-1$ $p|3^{P(c+qk)}-1$ and $ord_3(p)|P(c+qk)$ since $q>gcd(P(c+qk),Q((c+qk))$ we have $gcd(q,ord_3(p))=1$ so choose $k$ such that $c+qk \equiv 1 \bmod ord_3(p)$ so $ord_3(p)|P(1)$ $p|3^{P(1)}-1$ contradiction so $Q(X)$ is constant

Suppose on the contrary that $Q$ is nonconstant. Now, suppose $(P(n),Q(n))=a$ for some $a\in\mathbb Q$. Then by Bezout's lemma there exists $A(n), B(n)\in\mathbb Q[x]$ such that $$A(n)P(n)+B(n)Q(n)=a$$let $b$ be a number such that for every coefficient of $A,B$, its denominator divides $b$ Therefore, $$bA(n)P(n)+bB(n)Q(n)=ab$$which implies $bA(n),bB(n)\in\mathbb Z$ and that $(P(bk),Q(bk))|ab$ for every $k$. Therefore replacing $ab$ by $a$ we may assume $(P(n),Q(n))|a$ for every $n$. Now by Zgismondy's theorem there exists infinitely many primes $p_1,p_2,...,$ such that there exists $a_i\in\mathbb N$ with $p_i|2^{Q(a_i)}-1$, hence $p_i|3^{P(a_i)}-1$. For each $1\leq i\leq n$ let $d_i$ be the order of $3$ mod $p_i$. CASE I: There exists infinitely many primes $q_1<q_2<...$ such that for every $j$, $q_j|d_k$ for some $k$. Obviously the sequence $\{d_n\}$ is unbounded. Therefore, for all sufficiently large $q's$, we have $(q,a)=1$. Now suppose $q|d_i$. For every $m\in\mathbb Z_{\geq 0}$, we have $Q(a_i)|Q(a_i+mQ(a_i))$. Therefore, $$p_i|2^{Q(a_i+mQ(a_i))}-1|3^{P(a_i+mQ(a_i)}-1$$Since $d_i$ is the order, we must have $$d_i|P(a_i+mQ(a_i))\hspace{20pt}(1)$$Notice that $q|d_i|P(a_i)$. Therefore, $(q,Q(a_i))|(P(a_i),Q(a_i))|a$. From $(q,a)=1$ we have $(q,Q(a_i))=1$. Therefore, the arithmetic progression $a_i+mQ(a_i)$ covers all residue class mod $q$, hence from $(1)$ we have $$q|P(x)$$for every $1\leq x\leq q$, for sufficiently large $q$ this implies $P$ is the zero polynomial in $\mathbb F_q$(using the well-known fact that a nonzero polynomial with degree $n$ in $\mathbb F_q$ has at most $n$ roots). This is obviously a contradiction. CASE II: There exists finitely many primes $q$ with $q|d_k$ for some $k$. Notice that $\{d_k\}$ is obviously unbounded, therefore, there exists some prime $q$ such that for all $\alpha\in\mathbb N$, $q^{\alpha}|d_k$ for some $k\in\mathbb N$. Similarly we have $$q^{\alpha}|P(a_k+mQ(a_k))$$and $$(q^{\alpha},Q(a_k))|(P(a_k),Q(a_k))|a$$. Let $c=(a,q^{\alpha})$. Pick $\alpha$ sufficiently large, by pigeonhole principle there exists $0\leq i\leq c-1$ such that $$a_k+mQ(a_k)\equiv i\pmod{q^{\alpha}}$$for some $m\mathbb N$ hence $$P(i)\equiv 1\pmod{q^{\alpha}}$$but this is clearly impossible for $$\alpha\geq \underset{1\leq j\leq q^{v_q(a)}}{\max}v_p(P(j))$$contradiction. This completes the proof.

FTSOC, assume $Q$ is nonconstant. Let $S$ be the set of primes such that there exists an $n$ where $p\in S$ divides $2^{Q(n)}-1$. By Kobayashi, the set $S$ is infinite. Since $\gcd(P,Q) = 1$, this means there exists a constant $c$ such that $\gcd(P(n), Q(n)) < c$ for all $n$. This is true by the Euclidean algorithm. Now, for some prime $p | 2^{Q(n)}-1$, we also have $p | 3^{P(n)}-1$. If $d = ord_{p}2, e = ord_{p}3$, then we must have $d | Q(n)$, $e | P(n)$. Now, consider $3^{P(n+kd)}-1$ for integer $k$. Since $d | Q(n), Q(n+kd)-Q(n)$, this means $d | Q(n+kd)$, so $p | 2^{Q(n+kd)}-1 | 3^{P(n+kd)}-1$. This also means $e | P(n+kd)$. Since we must also have $e | P(n+kd-me)$ for all integers $n$, this means $p | 3^{P(n+kd-me)} - 1$. By bezouts, this means $p | 3^{P(n+\gcd(d,e))} - 1$, so $e | P(n+\gcd(d,e))$. Since $d | Q(n), e | P(n)$, this means $\gcd(d,e) < c$. Now consider the smallest $m$ such that $e | P(m)$. Clearly $m < c$. This means, over all primes, there exists some $m < c$ such that $P(m)$ is divisible by the order of such prime. However, observe that for a prime $p$, $e = ord_{p} 3 > \log_{3}p$. Since there are infinite primes, this means there must be infinite values of $e$ as well, and the values of $e$ tend toward infinity. However, since only finite numbers divide $P(1), P(2), \ldots P(c-1)$, this gives a contradiction. We conclude that $Q$ is a constant polynomial.

Solved with Jeffrey Chen, who did not realize he's solved the problem before. Fix \(n\) for now, and note since \(Q(n)\mid \operatorname{ord}(2\bmod{2^{Q(n)}-1})\) that for all \(k\), \[2^{Q(n)}-1\mid2^{Q(n+kQ(n))}-1\mid3^{P(n+kQ(n))}-1.\]It follows that \[2^{Q(n)}-1\;\bigg\vert\;\gcd_k\left\{3^{P(n+kQ(n))}-1\right\}=3^{\gcd_k\left\{P(n+kQ(n))\right\}}-1.\] It will then suffice to show: Claim: As \(n\) varies, \[\gcd_k\left\{P(n+kQ(n))\right\}\]is bounded. Proof. Let \(p\) be a prime dividing the gcd. Then \(p\) divides \(P(n)\), so If \(p\mid Q(n)\), then \(p\mid\gcd(P(n),Q(n))\), which is bounded. If \(p\nmid Q(n)\), then \(n+kQ(n)\) is surjective modulo \(p\), so \(P(0)\equiv P(1)\equiv\cdots\equiv P(p-1)\equiv0\pmod p\), implying \(p\) divides the polynomial \(P\). It follows that only finitely many primes \(p\) can divide the gcd. Now I contend each exponent is bounded as well. Let \(M=\nu_p(\gcd(P(n),Q(n)))+1\), which is bounded, and let \[N=\max\left\{M,\nu_p(P(1)),\nu_p(P(2)),\ldots,\nu_p(P(p^M))\right\}+1,\]which is bounded. We will show \(p^N\) does not divide the gcd. If, for contradiction, \(p^N\mid P(n)\), then \(p^M\nmid Q(n)\), so \(kQ(n)\) will hit all multiples of \(p^M\) modulo \(p^N\). That is, if \(p^N\mid P(n+kQ(n))\) for all \(k\) then \[P(n)\equiv P(n+p^M)\equiv P(n+2p^M)\equiv\cdots\equiv0\pmod{p^N}.\]Some \(n+kp^M\) is one of 1, 2, \(\ldots\), \(p^M\) modulo \(p^N\), so \(P(n+kp^M)\) is not divisible by \(p^N\) by definition. \(\blacksquare\)

bumjoooon wrote: Bump. I have a question. Can this be solved without the condition "$P(x)$ and $Q(x)$ are coprime in $\mathbb{Q}[x]$ " ? Interesting question! While I cannot speak with certainty, I'd say that this problem is very difficult (but the statement should be true even without this assumption). Already disproving that one cannot have $2^n - 1 \mid 3^{P(n)} - 1$ for all (large enough) $n$ seems quite difficult, though one can settle this case. (However, the solution I have in mind requires the Chebotarev density theorem.) It should not be too difficult to show that in fact any linear $Q$ fails, but I have not checked the details. The problem for higher degree $Q$ seems out of reach to me. For concreteness, consider the case $Q(n) = n^2 + 1$. One is naturally led to consider the primes which divide $2^{n^2 + 1} - 1$ for some $n$ (and the order of $2$ modulo those primes). By Zsigmondy/Kobayashi/etc., one sees that there are infinitely many such primes, but at least I see no way to actually understanding the set of such primes, whereas in the case of linear $Q$ one can in particular show that the corresponding set has positive density in the set of primes (and one has further understanding as well, all via the Chebotarev density theorem). Namely, we would want to somehow prove that the implication $n^2 + 1 \equiv 0 \pmod{ord_p(2)} \implies P(n) \equiv 0 \pmod{ord_p(3)}$ is not true for some prime $p$. In the particular case $P(n) = n^2 + 1$, this would require disproving that "for any prime $p$ such that $ord_p(2)$ is composed only of primes $q \equiv 1 \pmod{4}$ and $2$, one has $ord_p(2) \neq ord_p(3)$". I do not see any way to do this, as one does not understand the primes $p$ for which $ord_p(2)$ satisfies this rather strange condition. And of course, this is still only a very tiny part of the whole problem... Note that here I have considered a very "local" tactic for solving the problem: take some suitable $p$ and show that $p \mid 2^{Q(n)} - 1$ and $p \nmid 3^{P(n)} - 1$ for some suitable $n$. There are "global" arguments one could use well - for an example, see Problems from the book, Chapter 17, Example 14, concerning the problem "If $a^n - 1 \mid b^n - 1$ for all $n$, then $b$ is a power of $a$". (I should mention that this problem could treated by a local tactic as well; once again the Chebotarev density theorem is an indispensable tool.) I am not an expert on this type of global arguments, so I cannot speak whether they could be adapted to the problem at hand. If yes, I would be very interested of reading such a proof.

Probably this paper which is an extension of a similar paper of its kind might help. It gives density estimates for prime divisors of sequence $a^{p(n)}-1.$ Particularly, in their concluding remarks, they take the case of $p(n)=n^2+1$ and remark that it can be proven unconditionally, that cardinality of set of prime divisors of the sequence $a^{n^2+1}-1$ is at least $c\cdot \frac{x}{(\log{x})^{3/2}}$ for some constant $c$ which, when combined with their theorem $1$ conditional on GRH, indicates that in fact it is the correct order. They also claim that it can be proven that the density of the prime divisors of the sequence the is zero unconditionally giving a precise upper bound.

Great catch! I am familiar with the paper and in fact based some of my thoughts about the difficulty of the problem on it, but apparently I had not read it carefully enough, as I didn't remember that there was any non-trivial lower bound for the count of prime divisors... One can settle the case $P(n) = Q(n) = n^2 + 1$ with these methods. As it is mentioned in the concluding remarks, one can find $\gg x/(\log x)^{3/2}$ primes $p$ such that $(p-1)/2$ is supported on primes $\equiv 1 \pmod{4}$ by the half-dimensional sieve. Though I am not familiar with this particular sieve, typically for sieves one can add sieving conditions for finitely many primes with no problems, and so surely one can tweak the sieve so that one has $\gg x/(\log x)^{3/2}$ primes $p \le x$ such that $p \equiv 23 \pmod{24}$ and $(p-1)/2$ is supported on primes $\equiv 1 \pmod{4}$. For any such prime $p$ one has $p \equiv 7 \pmod{8}$, and so the order of $2$ modulo $p$ is odd and hence divides $(p-1)/2$. By the assumption on prime divisors of $(p-1)/2$, the congruence $n^2 + 1 \equiv 0 \pmod{\text{ord}_p(2)}$ has a solution. Furthermore, the fact that $n$ satisfies this condition does not imply that $n$ also satisfies $n^2 + 1 \equiv 0 \pmod{\text{ord}_p(3)}$, as the order of $3$ modulo $p$ is even. Hence there are infinitely many primes $p$ such that for some $n$ one has $p \mid 2^{n^2 + 1} - 1$ but $p \nmid 3^{n^2 + 1} - 1$. This does not seem to generalize very well. Firstly, it is mentioned in the paper that the idea does not generalize very well even to any quadratic $f$. Secondly, it is very convenient that above we could get a contradiction just by controlling the parities of orders, as those are determined well enough on congruence conditions on $p$, and thus the sieving problem stays essentially intact. This is not the case already for the polynomial $2(n^2 + 1)$.

Solution with hint from islander7. We apply the method of attrition. Claim: $\gcd(P(n),Q(n))$ divides some fixed $k$. (Whoops this is just Bezout) Solution: We prove that for any polynomials $P$ and $Q$ with no common nonconstant polynomial factor, $\gcd(P(n),Q(n)$ divides a fixed positive integer $k$. The proof is by induction on $\min(\deg P,\deg Q)$. If $\min(\deg P,\deg Q)=0$, then WLOG $\deg Q = 0$. Then $k=Q$. Otherwise, let $\deg P\ge \deg Q$, let $a$ denote the first coefficient of $P$ and $b$ the first coefficient of $Q$ and let $d$ denote $\deg P - \deg Q$, and observe $\gcd(P(n),Q(n)) \mid \gcd(bP(n)-aQ(n)n^d,Q(n))$. This certainly reduces $\deg P$. If the degree of the first polynomial is still greater than the degree of the second, iterate, noting that $bP(x)-aQ(x)x^d$ is a new nonzero polynomial unless $Q(x)$ is constant in which case we were doing this unnecessarily. $\fbox{}$ Now, let positive integer $n$ and nonnegative integer $a$ be arbitrary and note that \[2^{Q(n)}-1\mid 2^{Q(n+aQ(n))}-1\mid 3^{P(n+aQ(n))}-1.\]Then modulo $2^{Q(n)}-1$, we see if $t$ is the greatest common divisor of $P(n),P(n+Q(n)),P(n+2Q(n)),\cdots$, then $3^t\equiv 1\pmod{2^{Q(n)}-1}$. We claim $t\mid k\displaystyle\prod_{i=1}^k P(i)$, which is enough. For each prime $p$, let $\nu_p(k)=s$ and observe that either $p^{s+1}\nmid P(n)$, or $p^{s+1}\mid P(n)$ meaning $p^{s+1}\nmid Q(n)$. In the former case, we are done. In the latter case, note that modulo $p^{\nu_p(P(n))}$, the expression is congruent to a divisor of $\gcd(P(n),P(n+k),P(n+2k),\cdots)$. One $P(n+ak)$ is congruent to a $P(m)$ with $1\le m\le k$, so the result follows: since $3^{k\prod_{i=1}^k P(i)}-1$ is finite, only finitely many distinct $2^{Q(n)}-1$ could divide it, meaning $Q(n)$ is bounded and thus constant.

I feel like this is a bit complicated but whatever... Firstly by Bezout,we have $A(x)P(x)+B(x)Q(x)=K$ for integer polynomials $A,B$ and a natural number $K$. Let $P$ be the set of prime powers such that they divide both $P(k),Q(k)$ for some positive $k$. By the above $P$ is finite.Consider the primes in $P$ to be $p_1...,p_k$. Then define $Q$ to be the set of prime powers which divide $P(a)$ for all natural $a$.Consider the primes in $Q$ to be $q_1,..q_c$ and assign each prime an index $e_1...,e_c$,such that the largest power of $q_i$ in $Q$ is $e_i$. Now, we can find a $M$ and an $l$ ,such that $v_{p_i}(P(l)) <M$. Infinitely many $l$ exist by the Chinese remainder theorem. Now form sets $N= [p_1,{p_1}^2....,{p_1}^M......p_k,{p_k}^2....{p_k}^M]$ and $L$ which is just the infinite set of numbers $l$ mentioned above. Now consider the set $S$ formed by taking the product of some elements of $N \cup Q$.Obviously $S$ is finite and so is the set of prime factors of the sequence $ ${$ 3^{[s \epsilon S]} -1 $}$ $. Now if $Q(x)$ is nonconstant ,so is $Q([L])$. Then,by Kobayashi,choose an $n \epsilon L$,such that there is a prime $p$ dividing $2^{Q(n)}-1$, and $p$ is not a prime factor of the sequence $ ${$ 3^{[s \epsilon S]} -1 $}$ $. Then we have that $p|2^{Q(n)}-1|2^{Q(n+kQ(n))}-1|3^{P(n+kQ(n))}-1$. Thus ,we have that $p|3^{gcd(P(n),P(n+kQ(n)))}-1$, Now consider any prime $r_i$ dividing $P(n)$ such that it does not belong to sets $P,Q$.Then there exists a $k_i$ such that $r_i$ does not divide $P(n+k_iQ(n))$.Also for any $q_i$ in set $Q$ but not in set $P$,if $v_{q_i}(P(n))>e_i$, then again we can find a $k_i$,such that $v_{q_i}(P(n+k_iQ(n))) <e_i+1$.Any other prime dividing $P(n)$,must be in set $P$,and we already know that $v_{p_i}(P(n)) <M$. So all in all, by the Chinese Remainder theorem,we can choose a $k$,such that $gcd(P(n),P(n+kQ(n))) \epsilon S$,which is a contradiction.

Does this work? If so it seems way simpler/shorter than everything else posted. Edit: seems like it does and it's also post #27 It is well-known by Bezout that the coprime condition implies $\gcd(P(n),Q(n)) \leq N$ for some $N>0$ and all $n \geq 1$. Now suppose that $Q$ is nonconstant, so by Kobayashi/Zsigmondy there exist infinitely many primes dividing $2^{Q(i)}-1$ for some $i$. Pick some arbitrarily large prime $p \mid 2^{Q(n)}-1$ for some $n$, so $p \mid 3^{P(n)}-1$ as well. Then $a:=\mathrm{ord}_p(2) \mid Q(n)$ and $b:=\mathrm{ord}_p(3) \mid P(n)$. As $\gcd(P(n),Q(n)) \leq N$, we must also have $d:=\gcd(a,b) \leq N$. The key claim is now the following: Claim: We have $3^{P(n+ax+by)} \equiv 1 \pmod{p}$ for all $x,y \in \mathbb{Z}$ such that $n+ax+by>0$. Proof: First, note that by replacing $(x,y)$ with $(x+b,y-a)$ we may assume WLOG that $n+ax>0$. Then, since $Q(n+ax) \equiv Q(n) \pmod{a}$, we have $p \mid 2^{Q(n+ax)}-1$ for all $a$, hence $p \mid 3^{P(n+ax)}-1$ as well. From this, because $P(n+ax+by) \equiv P(n+ax) \pmod{b}$, we also have $p \mid 3^{P(n+ax+by)}-1$, hence proved. By Bezout's (again!), this means that $3^{P(r)} \equiv 1 \pmod{p}$ for all $r \equiv n \pmod{d}$ and $r>0$. As $d \leq N$, it follows that we can pick some $0<r \leq d \leq N$ and this should hold. But then $$\prod_{i=1}^{N} (3^{P(i)}-1)$$has arbitrarily large prime divisors, yet is nonzero (else $P(i)$ isn't positive for some $i \geq 1$): absurd. Hence $Q$ must be constant, done. $\blacksquare$

Let $n\in\mathbb N$ and $k\in\mathbb Z_{\ge 0}$. Since $Q(n)\mid Q(n+kQ(n))$ we have $$2^{Q(n)}-1\mid 2^{Q(n+kQ(n))}-1\mid 3^{P(n+kQ(n))}-1.$$Hence if $d_n\doteqdot\gcd_{k\in\mathbb Z_{\ge 0}} P(n+kQ(n))$ then $$2^{Q(n)}-1\mid 3^{d_n}-1.$$We claim that the sequence $d_n$, $n\in\mathbb N$ is bounded above. Consider a fixed $n$. Then $d_n\mid P(n)$. Moreover for every $k\in\mathbb Z_{\ge 0}$ we have $d_n\mid P(n+kQ(n))$. Hence, since $P$ has integer coefficients, for every $k\in\mathbb Z_{\ge 0}$ and $l\in\mathbb Z$ we have $d_n\mid P(n+kQ(n)+lP(n))$. Since $\gcd(P(x),Q(x))=1$ in $\mathbb Q[x]$, there exist polynomials $A(x),B(x)\in\mathbb Z[x]$ and a positive integer $D$ such that $A(x)Q(x)+B(x)P(x)=D$. In particular, for every $r\in\mathbb Z$ there exist $k,l\in\mathbb Z$ such that $kQ(n)+lP(n)=rD$. By repeated replacements of $(k,l)$ by $(k+P(n),l-Q(n))$ we can assume that $k$ is positive. Therefore $d_n\mid P(n+rD)$ for every $r\in\mathbb Z$. So if $m$ is the unique integer in $1,\ldots,D$ which is equivalent to $n$ modulo $D$, then $d_n\mid P(m)$. Hence $d_n$ is bounded above by $C\doteqdot\max(P(1),\ldots,P(D))$ which is independent of $n$. As a result, we conclude that for each $n\in\mathbb N$ we have $$2^{Q(n)}-1\mid 3^{d_n}-1\le 3^C-1.$$Therefore the sequence $Q(n)$, $n\in\mathbb N$ is bounded so $Q$ is constant.

Here is a pretty short proof that \[\gcd_k\left\{P(n+kQ(n))\right\}\]is bounded for relatively prime polynomials $P(x), Q(x) \in \mathbb{Z}$ which I found when talking to DebayuRMO about my solution from 2021, realizing that I forgot the finish, I had to improvise leading me to this solution. Let $m = deg(P)$ and define for $i \in \{0, 1, \cdots, m\}$, $P_i(x) = P(x+iQ(x))$. $\textbf{Main Lemma:}$ There exists $A_i(x) \in \mathbb{Z}[x]$ for each $i \in \{0, \cdots, m\}$ such that $$\sum_{i=0}^{m} A_i(x) \cdot P_i(x) = C$$for some constant $C \in \mathbb{Z}$, $C \neq 0$. $\textbf{Proof)}$

Now, assume for the sake of contradiction that such an $\alpha$ exists, firstly, notice that $P(\alpha) = 0$ and hence $Q(\alpha) \neq 0$ as $P,Q$ are not both divisible by any polynomial with rational coefficients, in particular, $m_{\alpha}$, the minimal polynomial of $\alpha$ does not divide both of the polynomials. Then, notice that $\alpha+i \cdot Q(\alpha)$ are pairwise distinct for $i \in \{0, \cdots, m\}$, which means that $P$ has $m+1$ distinct roots, but $P$ is not the $0$ polynomial as $P(n) > 0$ for $n \in \mathbb{N}$ is given. This is a contradiction, implying the Lemma. $\blacksquare$ Now, notice that \[\gcd_k\left\{P(n+kQ(n))\right\}\]is bounded by $|C|$. Now, the remainder of the proof is as was done above. $\blacksquare$ $\blacksquare$

Firstly , since polynomials $P(x)$ and $Q(x)$ are coprime in $\mathbb{Q}[x]$ , by Bezout theorem there exist polynomials $A(x) , B(x) \in \mathbb{Z}[x]$ such that for a constant number $c \in \mathbb{Z}$ we have : $$P(x)A(x)+Q(x)B(x)=c$$So if we define $d_n$ for each $n \in \mathbb{N}$ such that $gcd(P(n) , Q(n))=d_n$ , we always have $d_n|c$ and $d_n$ is bounded while $n$ varies in $\mathbb{N}$. So suppose that $Q(x)$ is non-constant , then by Schor's lemma we know that there exist infinitely many prime numbers $p$ , such that for a natural $n$ , we have $p|Q(n)$. Now suppose that $c<p_1<p_2<...$ are prime factors of $Q(n)$ values , consider $q_i$ as a prime factor of number $2^{p_{i}}-1$ and for a natural $n$ , $p_i|Q(n_i)$ , then we have $q_i|2^{Q(n_i)}-1|3^{P(n_i)}-1$ and one can see that : $$ord_{q_i}3|P(n_i)$$Now notice that $p_i$ doesn't divide $ord_{q_i}3$ , because otherwise , $c<p_i|gcd(P(n_i),Q(n_i))$ , so for each natural number $j$ , by CRT there exist a number $m$ , such that we have : $$m \equiv n_i \pmod {p_i} , m \equiv j \pmod {ord_{q_i}3}$$So we have $p_i|Q(m)$ and $ord_{q_i}3|P(m)$ and since $m$ can varies in arbitrary values module $ord_{q_i}3$ , so this number divides all values of $P(n)$ for each proper prime number $q_i$. Now while polynomial $P(x)$ is non-zero , so the values of $ord_{q_i}3$ are bounded and as the result there exist finitely many proper primes $q_i$. ( because otherwise if $ord_{q_i}3 \le t$ , then by pigeonhole principle there exist a natural $r\le t$ , such that $3^r-1$ has infinitely many prime factors which is a contradiction. ) Now note that for each $i$ , $q_i|2^{p_i}-1$ , we have $q_{i} \equiv 1 \pmod{p_i}$ and $q_i>p_i$ which is a contradiction while the number of proper $q_i$ primes are finite. As the result , $Q(x)$ is constant and we're done.

Note that $Q(n) \mid Q(n+kQ(n)) - Q(n) \implies Q(n) \mid Q(n+kQ(n))$. Therefore, $2^{Q(n)} - 1 \mid 2^{Q(n+kQ(n))} - 1 \mid 3^{P(n+kQ(n))} - 1$ for all nonnegative $k$. But I claim that $\gcd(P(n), P(n+Q(n)), P(n+2Q(n)), \cdots)$ is bounded by a fixed number (independent of $n$) if $P$ and $Q$ are coprime. If this is true, since $\gcd(3^x - 1, 3^y - 1) = 3^{\gcd(x,y)} - 1$ then it implies that $2^{Q(n)} - 1$ is bounded, implying $Q(x)$ is the constant polynomial. Say $g$ is the $\gcd$ in question. By bezout, $\gcd(P(n),Q(n)) \leqslant C$ for some absolute constant $C$. Therefore, considering the values of $n+kQ(n) \pmod{g}$, since $\gcd(g,Q(n)) \leqslant C$, there must be a value of $k$ such that $n + kQ(n) \equiv r \pmod{g}$ with $1 \leqslant r \leqslant C$, if $n$ is taken to be coprime to $C$. But this would imply that $g$ must also divide this value. Therefore, $g$ must divide $\prod_{i=1}^{C} P(i)$, which is a finite value, so we're done.

Like #37, polynomials $P(x)$ and $Q(x)$ are coprime in $\mathbb{Q}[x]$ , so by Bezout theorem there exist polynomials $A(x) , B(x) \in \mathbb{Z}[x]$ such that for a constant number $C \in \mathbb{Z}$ we have : $$P(x)A(x)+Q(x)B(x)=C \text{ }\text{ }\text{ }\text{ }\text{ }\text{ } \gcd(P(x), Q(x)) \vert C \text{ }\forall x$$ Assume that $Q$ is non-constant and take any prime $p > 3^{\text{max}(Q(1), Q(2), ..., Q(C))}$ dividing $2^{Q(n)} -1$ for any $n$ (Which exists by zsigmondy if $Q$ is non-constant) then: $$ord_{p}{2} \vert Q(n) \text{ and } ord_{p}{3} \vert P(n) \implies \gcd(ord_{p}{2}, ord_{p}{3}) \vert C$$$$ord_{p}{2} \vert Q(n+k.ord_{p}{2}) \implies ord_{p}{3} \vert P(n+k.ord_{p}{2}) \implies ord_{p}{3} \vert P(n+l.\gcd(ord_{p}{2}, ord_{p}{3}))$$ So we can choose an $m \in \{1,2, \hdots , \gcd ( ord_{p}{2} , ord_{p}{3} )\} $ such that $ord_{p}{3} \vert P(m)$ but this is clearly false since $ord_{p}{3}>\text{max}(Q(1), Q(2), ..., Q(C))$.

Solved with rama1728 Replace $n$ with $n+kQ(n)$ and note that $2^{Q(n)}-1$ still divides the left hand side. So, we have that if $R(n) = \gcd(P(n+kQ(n))$ then $2^{Q(n)}-1$ divides $3^{R(n)}-1$. Now taking finite differences on $P$, we see that $R$ is dividing $kQ(n)^a$ for some constants $k, a$. But now $R$ divides $\gcd{P(n), kQ(n)}$ for all $n$, but then by applying Bezout's repeatedly we get that $Q$ is bounded and therefore so is $R$. Contradiction.

Assume the contrary. Then there exists a large prime $p$ and a positive integer $n$ such that $p \mid 2^{Q(n)} - 1$.(Kobayashi or Zsigmondy, whatever) Then we have $p \mid 3^{P(n)} - 1, 2^{Q(n)} - 1$, so $\text{ord}_p(2) \mid Q(n)$ and $\text{ord}_p(3) \mid P(n)$. Since $\gcd(P(x), Q(x))$ is a constant polynomial, so $\gcd(P(n), Q(n))$ is bounded above. Hence $\gcd(\text{ord}_p(2), \text{ord}_p(3))$ is bounded above. We'll prove that $p \mid 3^{P(r)} - 1$ for a small $r$, which yields a contradiction. Note that $p \mid 2^{Q(n + \text{ord}_p(2)k)} - 1 \mid 3^{P(n + \text{ord}_p(2)k)} - 1$ for all $k$ and $p \mid 3^{P(n + \text{ord}_p(3)l)} - 1$ for all $l$, so $p \mid 3^{P(n + \text{ord}_p(2)k + \text{ord}_p(3)l)} - 1$ for all $k, l$. Let $d = \gcd(\text{ord}_p(2), \text{ord}_p(3))$. Since $d$ is bounded above, so letting $r$ be the remainder of $n$ divided by $d$, we get $p \mid 3^{P(r)} - 1$ and $r < d$, so $p < 3^{P(d)} - 1$, which is an evident contradiction. $\blacksquare$

Suppose otherwise. There exist integer polynomials $A(x)$ and $B(x)$ with $A(x) P(x) + B(x) Q(x) = d$ for some nonnegative integer $d$. Clearly $\gcd(P(n), Q(n)) \le d$ for all integers $n$, implying that $\gcd(P(n), Q(n)) \mid d! = D$. Let $S$ be the set of all primes dividing $2^{Q(n)} - 1$ for some positive integer $n$. By Kobayashi, $S$ is an infinite set. Fix some prime $p\in S$ with $\log_3(p) > \max(P(1), \ldots, P(d-1), P(d)) + 1434$. Let $k$ be a positive integer satisfying $p\mid 2^{Q(k) } - 1$. Notice that $\mathrm{ord}_p(3) \mid P(k)$. Let $y = \mathrm{ord}_p(3)$. Claim: $y\mid P(k + n \cdot Q(k))$ for any integer $n$. Proof: We see that $Q(k)\mid Q(k + n Q(k))$ for any integer $n$, so $p\mid 2^{Q(k + n Q(k))} - 1 \mid 3^{P(k + n Q(k))} - 1$ for all integers $n$ satisfying $k + n Q(k) > 0$, implying that $y\mid P(k + n \cdot Q(k))$ whenever $k + n \cdot Q(k)$ is positive. To finish, note that for any positive integers $m,N$, \[y\mid P(k - m Q(k)) \iff y\mid P(k + N \cdot Q(k) \cdot y - m Q(k)) = P(k + (Ny - m)Q(k)),\]and taking $N$ with $Ny - m > 0$ gives that $y\mid P(k - mQ(k))$ also. $\square$ Claim: $y\mid P(k + n \cdot D)$ for any integer $n$. Proof: First notice that $\gcd(Q(k), y) \le \gcd(P(k), Q(k)) \le d$, so $\gcd(Q(k), y)\mid D$. Then there exist integers $a,b$ such that $a Q(k) + b y = D$. Since $y\mid P(k + ny)$ and $y\mid P(k + n Q(k))$ for any integer $n$, \[y\mid P(k + n(a Q(k) + by ) ) = P(k + n \cdot D)\]for any integer $n$. $\square$ Choose $n$ such that $0 < k + n\cdot D \le D$. Let $r = k + n \cdot D$. We have $y\mid P(r)$, so $y \le P(r)$. However, since $p\mid 3^y - 1$, $p \le 3^y - 1 < 3^{P(r)}$, contradiction to the fact that $\log_3(p) > P(r) + 1434$. Therefore, $Q$ must be constant.

Such a perfect problem, uses every important lemmas in Integer Polynomials and Advanced Modular Arithmetics Claim I: For any two polynomials $P(x), Q(x) \in \mathbb{Q}[x]$ $\exists R(x), S(x) \in \mathbb{Q}[x]$ such that $$P(x)R(x)+Q(x)S(x)=d \qquad \gcd({P(x), Q(x)}) \vert d$$Claim II: By Zsigmondy's Theorem $\exists$ infinitely many primes that divide $2^{Q(x)}-1\quad \forall x=1,2,\dots$ Claim III: $f(x)\mid f(x+k\cdot f(x)), f(x)\in \mathbb{Z}[x]$ Let that prime be $p$, such that $\text{ord}_{p}(3)>{\text{max}\{Q(1),Q(2),\dots, Q(d)\}}$ Since $\exists p$ such that \begin{align*} &p\mid 2^{Q(n)}-1\mid 3^{P(n)}-1\\ \implies& p \mid 2^{Q(n+\text{ord}_p{2}\cdot k)}-1\mid 3^{P(n+\text{ord}_p{2}\cdot k)}-1 \quad \text{and} \quad p\mid 3^{P(n+\text{ord}_{p}(3)\cdot l)}\qquad [\because\textbf{Claim 3}] \\ \implies& \text{ord}_{p}3\mid {P(n + \text{ord}_{p}(2)\cdot k + \text{ord}_{p}(3)\cdot l)} \end{align*}Note that ${P(n + \text{ord}_{p}(2)\cdot k + \text{ord}_{p}(3)\cdot l)}\in \{P(1),P(2), \dots,P(\gcd({\text{ord}_{p}(2),\text{ord}_{p}(3)}) \}.$ But $\text{ord}_{p}(3)>{max\{Q(1),Q(2),\dots, Q(d)\}}$, so we have a contradiction!!

By Bezout's there exist polynomials $A(x), B(x) \in \mathbb Z[x]$ and a constant $c$ such that $A(x)P(x)+B(x)Q(x)=c$ which means that for large enough primes $p$ we have that $p$ cannot divide both $P,Q$ (and the exponent is also bounded since $c$ is bounded), so in general we have that $\gcd(P(n), Q(n))$ is bounded, now by Schur select a large enough prime s.t. $p \mid Q(n)$ but then $p \not \; \mid P(n)$, now select using Zsigmondy some $q \mid 2^p-1$ (which then it holds that $q \equiv 1 \pmod p$), now from $a-b \mid f(a)-f(b)$ for a polynomial $f \in \mathbb Z[x]$ we have that $f(n) \mid f(n+kf(n))$ for any positive integer $k,n$ then we have that $$q \mid 2^p-1 \mid 2^{Q(n)}-1 \mid 2^{Q(n+kQ(n))}-1 \mid 3^{P(n+kQ(n))}-1$$Therefore we get that $\text{ord}_q(2) \mid Q(n)$ and $\text{ord}_q(3) \mid P(n+kQ(n))$ for all non-negative integers $k$. Now since $\gcd(P(n),Q(n))$ is bounded we have that $\gcd(\text{ord}_q(2), \text{ord}_q(3))$ is also bounded (suppose its at most $g$), then if for this prime $q$ it's $r$ then let $n \equiv n' \pmod r$ we get that $\text{ord}_q(3) \mid P(n')$ so $q \mid 3^{P(n')}-1$, therefore we can get that $p<q \le 3^{P(n')}-1 \le 3^{P(g)}-1$, but we can make $p$ as large as we want and repeat this proces while keeping this bound, this creates a size contradiction, coming from assuming that $Q$ is non-constant (at the moment of using Schur) therefore $Q$ is constant thus we are done .