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


2 Answers 2


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.

  • $\begingroup$ 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. $\endgroup$ Sep 26, 2017 at 7:01
  • $\begingroup$ @darijgrinberg Ah good point, corrected. $\endgroup$
    – stewbasic
    Sep 26, 2017 at 21:49

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.