# 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)}$.

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.

• This proves $\left|a_g\right| = h$, not $a_g = h$. This is probably why the OP wanted the coefficients of $P$ to be positive. Sep 26, 2017 at 7:01
• @darijgrinberg Ah good point, corrected. Sep 26, 2017 at 21:49