True or false : $\gcd(a_m, a_n) = a_{\gcd(m, n)}$?

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.

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.