Parsia-- wrote: 5. We call $(P_n)_{n\in \mathbb{N}}$ an arithmetic sequence with common difference $Q(x)$ if $\forall n: P_{n+1} = P_n + Q$ $\newline$ We have an arithmetic sequence with a common difference $Q(x)$ and the first term $P(x)$ such that $P,Q$ are monic polynomials with integer coefficients and don't share an integer root. Each term of the sequence has at least one integer root. Prove that: $\newline$ a) $P(x)$ is divisible by $Q(x)$ $\newline$ b) $\text{deg}(\frac{P(x)}{Q(x)}) = 1$ Let $G=\gcd(P,Q)$ then write $P=GA$ and $Q=GB$ where $A, B$ are monic integer coefficient polynomials (since $P, Q$ are monic). Next, let $U, V \in \mathbb{Z}[X]$ such that $AU+BV=1$. Since $P$ and $Q$ share no integer root, $G$ has no integer root. We have $P_n=G(A+(n-1)B)$ for all $n$, and there exists an integer sequence $(x_n)_n$ s.t. $P_n(x_n)=0$ for all $n$. Observe that $x_n$ are all distinct (otherwise, $P$ and $Q$ would share an integer root). Now, $P(x_n)=0 \implies A(x_n)+(n-1)B(x_n)=0 \implies B(x_n)(V(x_n)-(n-1)U(x_n))=1 \implies B(x_n)=1 \text{ or } -1$ for all $n$. So $B=1$ or $B=-1$ (because it is infinitely often $1$ or $-1$). But since $B$ is monic, we get $\boxed{B=1}$, so $Q=G$ which proves $a)$ $b)$ We have $A(x_n)=1-n$, so $\deg(A)$ is odd, therefore $(x_n)_n$ must be eventually decreasing. Let $n_0 \in \mathbb{N}$ such that $x_{n}>x_{n+1}$ for all $n \geq n_0$. We have $x_{n} - x_{n+1} \mid A(x_{n})-A(x_{n+1})=1$ $\implies$ $x_n-x_{n+1}=1$ for all $n \geq n_0$, so $x_{n+1}=x_{n_0}+n_0-1-n=c-n$ for all $n \geq n_0$, hence $A(c-n)=-n$ for all $n \geq n_0$, meaning the polynomial $A-X+c$ has infinitely many roots, so $A=X-c$

The proof of $a)$ is same as above. And for the proof of $b)$, Let $\frac{P}{Q}=R$ and $deg(R)=d$. Since $P_{n+1}=Q.(R+n)$, $R$ is surjective on negative integers which also means $d$ is odd as $R$ is monic. On the other hand, there exists an integer $N$ such that $(x+N)^d\leq R(x) <(x+N+1)^d$. But $R$ must be equal to $(-n)^d$ for all integer $n$ thus $R=(x+N)^d$ but we know $R$ is surjective $\implies d=1$.

for $b)$ can we prove that if there is a strictly monotonic sequence of integers $(x_n)_{n\in \mathbb{N}}$ such that $A(x_n) \sim n$ then $\deg(A)=1$

cazanova19921 wrote: Next, let $U, V \in \mathbb{Z}[X]$ such that $AU+BV=1$. $U$ and $V$ don't necessarily exist (take $A=x-1$ and $B=x+1$ as an example). What is true is that you can find $U$, $V$ such that $AU+BV=m$ for some non-zero integer $m$, and then the proof proceeds more or less the same way ($B(x_n) \mid m$ infinitely often so $B$ is constant and since it's monic it's equal to $1$).

MatteD wrote: cazanova19921 wrote: Next, let $U, V \in \mathbb{Z}[X]$ such that $AU+BV=1$. $U$ and $V$ don't necessarily exist (take $A=x-1$ and $B=x+1$ as an example). What is true is that you can find $U$, $V$ such that $AU+BV=m$ for some non-zero integer $m$, and then the proof proceeds more or less the same way ($B(x_n) \mid m$ infinitely often so $B$ is constant and since it's monic it's equal to $1$). Good catch, thanks!