Let $P(x)$ be a nonzero polynomial with integer coefficients. Let $a_{0}=0$ and for $i \ge 0$ define $a_{i+1}=P(a_{i})$. Show that $\gcd ( a_{m}, a_{n})=a_{ \gcd (m, n)}$ for all $m, n \in \mathbb{N}$.
Problem
Source:
Tags: algebra, polynomial, induction, Recursive Sequences
Valentin Vornicu
26.03.2008 08:46
Induction after $ \max(m,n)$. In fact we can WLOG $ m>n$, and we will do induction after $ m$. Suppose $ m=1$. Then the result is obvious $ \gcd(a_1,a_0) = a_1 = a_{\gcd(1,0)}$. Suppose that we have proved for all pairs $ (m',n')$ such that $ m>m'>n'$. Then \[ \gcd(a_m,a_n) = \gcd(P^{(m-n)}(a_n),a_n) = \gcd(P^{(m-n)}(0),a_n)= \gcd(a_{m-n},a_n),\] which by induction is $ a_{\gcd(m-n,n)}$, which obviously equals $ a_{\gcd(m,n)}$.
rogueknight
28.02.2010 13:54
sorry, but who can explain for me why $ gcd(P^{(m - n)}(a_n);a_n) = gcd(P^{(m - n)}(0);a_n)$ (and I think that because $ a_0 = 0$ so $ P^{(m - n)}(0) = 0$) is it wrong thanks
pluristiq
27.03.2010 03:15
$ P^{m-n}(0)$ certainly need not equal 0. The reason is that $ a_n=a_n-0|P(a_n)-P(0)|P^{(2)}(a_n)-P^{(2)}(0)|\cdots|P^{(m-n)}(a_n)-P^{m-n}(0)$, so that if $ d|a_n$ and $ d|P^{(m-n)}(a_n)$ then $ d|P^{(m-n)}(0)$, and similarly, if $ d|a_n$ and $ d|P^{(m-n)}(0)$ then $ d|P^{(m-n)}(a_n)$.