2

I just want some hints on how to proceed. Please do not post entire solutions.

PROBLEM: Consider a polynomial $p(x)$ with integral coefficients such that $p(n) \gt n \forall n \in \mathbb N$.Now consider the sequence of integers ($x_i$) such that $x_1 = 1, x_i = p(x_{i-1}), \forall i \ge 2$. It is known that for every $n \in \mathbb N, n | x_j$ for some $j$. Show that $p(x) = x + 1$

I could'nt proceed at all except observing the trivial fact that $(x_i)$ is increasing. I can't find a suitable use for the second property. Any hints will be appreciated.

Lelouch
  • 724
  • I think the question is , there exist a polynomial $p$ such that $p(n) > n$ and $n | p(a)$ for some natural $n$ and $a$. Am I correct ? –  May 03 '17 at 13:06
  • Start with an example (test). Let $p(x)=x^2+1$. Then $p(n)>n$ and $x_1=0,x_2=1,x_3=2,x_4=5$ etc. Now use $n\mid x_j$ for all $n$. Can you obtain a contradiction? What about $n=7$ then? – Dietrich Burde May 03 '17 at 13:10
  • The question is absolutely correct. I re-checked it – Lelouch May 03 '17 at 13:12
  • @Dietrich it is given that x_1 = 1 and even if i assume p(x) = x^2 + 1 to be the generator, i see no harm directly. We may find the multiples of all natural nos. Here as well. – Lelouch May 03 '17 at 13:14
  • No, you wrote $x_1=0$ above. And again no, $x^2+1$ is never divisible by $7$. – Dietrich Burde May 03 '17 at 13:15
  • SOrry for the typo. Corrected it – Lelouch May 03 '17 at 13:15
  • @Dietrich. I agree that its not divisible by 7 but i can't possibly apply simple divisibility to all possible polynomials. What would a general method be?. – Lelouch May 03 '17 at 13:17
  • Simple divisibility and modulo considerations are the things you should apply, indeed. Why not? – Dietrich Burde May 03 '17 at 13:19
  • But for a general polynomial i should not be able to find a particular natural for contradiction. I would need a contradiction which can show that polynomial must be linear. – Lelouch May 03 '17 at 13:21

0 Answers0