True or false : $\gcd(a_m, a_n) = a_{\gcd(m, n)}$? Define a sequence $\left(a_0, a_1, a_2, \ldots\right)$ of integers by $a_0= 0, a_{n+1}=P(a_n)$, where $P$ is a polynomial with POSITIVE integer coefficients.
I guess that $\gcd(a_m, a_n) = a_{\gcd(m, n)} $.
 A: Hint $ $ Mimic the $\overbrace{\text{(subtractive) Euclidean algorithm}}^{\rm \Large\qquad\!  (n,m)\ =\ (n,\,m-n)}\,$ with inductive step being
$$\rm \begin{align}\rm (\overbrace{P^n(0),\,P^m(0)}^{\Large (a(n),\,\ a(m))\ })\, &=\,\rm (\color{#0a0}{P^n(0)},\,P^{m-n}(\color{#c00}{P^n(0)})\\
\rm  &=\, \rm (\underbrace{P^n(0),\,P^{m-n}(\color{#c00}0))}_{\Large (a(n),\,\ a(m-n))}\end{align}\qquad\qquad\qquad $$
via Polynomial Congruence Rule: $\ \ \ \rm\begin{align}\rm\bmod\, \color{#0a0}{P^n(0)}\!:\,\  &\rm\color{#c00}{P^n(0)\,\equiv\, 0}\\\,\rm\Rightarrow\ \ \ P^{m-n}(&\rm\color{#c00}{P^n(0)})\equiv P^{m-n}(\color{#c00}0)\end{align}$ 
As does the Congruence Rule, the proof works for any polynomial  with integer coefficients.
A: This is true (and if we allow nonpositive integer coefficients, it's true up to sign). Let $P^{(k)}$ denote the composition of $P$ with itself $k$ times, so $a_n=P^{(n)}(0)$. Note that $P^{(n)}$ is again an integer polynomial. Recall that if $R$ is an integer polynomial and $s\equiv t\pmod m$ then $R(s)\equiv R(t)\pmod m$.
Let $g=\gcd(n,m)$ and $h=\gcd(a_n,a_m)$. Let $Q=P^{(g)}$, so $a_g=Q(0)$. Thus $Q(0)\equiv 0\pmod{a_g}$. It follows inductively that $Q^{(k)}(0)\equiv 0\pmod{a_g}$ for all positive integers $k$. Thus
$$
  a_n=Q^{(n/g)}(0)\equiv 0\pmod{a_g}
$$
and similarly for $a_m$. Hence $a_g|h$.
Now let $b_k$ be the image of $a_{gk}$ in $\mathbb Z_h$, where $\mathbb Z_h$ is the ring of integers modulo $h$. Then $b_{k+1}=\bar Q(b_k)$ where $\bar Q$ is the map on $\mathbb Z_h$ induced by $Q$. We have $b_0=b_{n/g}=b_{m/g}=0$. Pick $p>0$ minimal such that $b_p=0$. By the usual argument we have $p|n/g,m/g$. But $\gcd(n/g,m/g)=1$, so $p=1$. Hence $b_1=0$, so $h|a_g$ as required.
