amparvardi wrote: Let $p(x)$ be a polynomial with integer coefficients such that $p(0)=p(1)=1$. We define the sequence $a_0, a_1, a_2, \ldots, a_n, \ldots$ that starts with an arbitrary integer $a_0$ and satisfies $a_{n+1}=p(a_n)$ for all $n \in \mathbb N$. Prove that $\gcd(a_i,a_j)=1$ for all $i,j \in \mathbb N \cup \{0\}$. Formally, this is wrong : choose $P(x)=1$ and sequence $a_0,a_1,a_2,...=2,2,1,1,1,...$ as counter example. The problem needs two modifications : a) the relation $a_{n+1}=P(a_n)$ must be true $\forall n\in\mathbb N\cup\{0\}$ and not only $\forall n\in\mathbb N$ b) we must add the constraint $a_0\ne 0$ in order $\gcd(a_0,a_1)$ be defined. The fact that $P(0)=P(1)=1$ implies then that $P(x)\ne 0$ $\forall x\in\mathbb Z$ And if $p|x$ and $p|P(x)=P(0)+xQ(x)$, then $p|P(0)=1$ and so, $\forall x\ne 0$ : $\gcd(x,P(x))=1$ Hence the result.

I disagree, pco. If $a_0 = 0$, that clearly forces $a_n = 1$ for all $n\geq 1$ (the same as if we start with $a_0=1$). Why do you say $\gcd(a_0,a_1)$ would then be undefined? Only $\gcd(0,0)$ is undefined; for any positive integer $a \neq 0$ we have $\gcd(0,a) = a$, from definition. (Also, it is strange from a guy from France that you insist $\mathbb{N} = \{1,2,\ldots\}$. As far as I know, the Romanians adopted the French notation that $\mathbb{N} = \{0,1,2,\ldots\}$, and so denote $\mathbb{N}^* = \{1,2,\ldots\}$).

mavropnevma wrote: I disagree, pco. If $a_0 = 0$, that clearly forces $a_n = 1$ for all $n\geq 1$ (the same as if we start with $a_0=1$). Why do you say $\gcd(a_0,a_1)$ would then be undefined? Only $\gcd(0,0)$ is undefined; for any positive integer $a \neq 0$ we have $\gcd(0,a) = a$, from definition. 1) about "$a_0 = 0$ which clearly forces $a_n = 1$ for all $n\geq 1$" this was wrong in the first version of the problem since the equation $a_{n+1}=P(a_n)$ was only valid for $n\in\mathbb N$ and so $a_1$ was not deduced from $a_0$ 2) about gcd definition, I looked at http://en.wikipedia.org/wiki/Greatest_common_divisor in which gcd seems to be defined only for non zero integers (although I agree with the fact that $\gcd(n,0)=n$ for $n\ne 0$ has full sense (maybe better to write $\gcd(0,n)=|n|$)

I don't much care what wiki says The definition of the "meet" of two elements $a,b$ in a lattice, which yields the $\gcd$ for the divisibility relation, clearly provides $\gcd(0,a) = a$ for a positive integer $a$, since $a \mid a$ and $a \mid 0$.

I think we don't really need a "definition" of $gcd$. Greatest Common Divisor is clear enough.

mavropnevma wrote: I don't much care what wiki says The definition of the "meet" of two elements $a,b$ in a lattice, which yields the $\gcd$ for the divisibility relation, clearly provides $\gcd(0,a) = a$ for a positive integer $a$, since $a \mid a$ and $a \mid 0$. I understand and it's not a problem for me. But then I wonder what is then the interest of the statement $P(1)=1$ It seems to be that $P(0)=1$ is enough to prove that $\gcd(x,P(x))=1$ and I used $P(1)=1$ only to prove that $a_n\ne 0$ $\forall n\ge 1$ :

No, Patrick, all you did was prove that then $\gcd(a_n,a_{n+1}) = 1$ (you only work with consecutive terms). A simple counterexample is enough: take $P(x) = x+1$, so $P(0)=1$. Take $a_0=a\geq 0$. Then $a_n = a + n$, and clearly these values are not all pairwise coprime. A correct proof uses both conditions $P(0)=1$ and $P(1)=1$. It follows then $P(x) = (x-1)xQ(x) + 1$, so $P(x)-1 = (x-1)xQ(x)$. Then by simple iteration we have $a_{n+1} - 1= P(a_n) -1 = (a_n - 1)a_nQ(a_n) = \cdots = (a_0-1)\prod_{k=0}^n a_kQ(a_k)$. RHS is divisible by all $a_k$, $0\leq k\leq n$, so LHS is, but $a_{n+1}$ is coprime with LHS.

mavropnevma wrote: No, Patrick, all you did was prove that then $\gcd(a_n,a_{n+1}) = 1$ (you only work with consecutive terms). ... You're quite right ! Thanks