\documentclass[numbers=enddot,12pt,final,onecolumn,notitlepage]{scrartcl}%
\usepackage[headsepline,footsepline,manualmark]{scrlayer-scrpage}
\usepackage[all,cmtip]{xy}
\usepackage{amssymb}
\usepackage{amsmath}
\usepackage{amsthm}
\usepackage{framed}
\usepackage{comment}
\usepackage{color}
\usepackage{hyperref}
\usepackage[sc]{mathpazo}
\usepackage[T1]{fontenc}
\usepackage{tikz}
\usepackage{needspace}
\usepackage{tabls}
\usepackage{wasysym}
\usepackage{easytable}
\usepackage{pythonhighlight}
\usepackage[type={CC}, modifier={zero}, version={1.0},]{doclicense}
%TCIDATA{OutputFilter=latex2.dll}
%TCIDATA{Version=5.50.0.2960}
%TCIDATA{LastRevised=Thursday, July 14, 2022 14:18:06}
%TCIDATA{SuppressPackageManagement}
%TCIDATA{<META NAME="GraphicsSave" CONTENT="32">}
%TCIDATA{<META NAME="SaveForMode" CONTENT="1">}
%TCIDATA{BibliographyScheme=Manual}
%TCIDATA{Language=American English}
%BeginMSIPreambleData
\providecommand{\U}[1]{\protect\rule{.1in}{.1in}}
%EndMSIPreambleData
\usetikzlibrary{arrows.meta}
\usetikzlibrary{chains}
\newcounter{exer}
\newcounter{exera}
\numberwithin{exer}{subsection}
\theoremstyle{definition}
\newtheorem{theo}{Theorem}[section]
\newenvironment{theorem}[1][]
{\begin{theo}[#1]\begin{leftbar}}
{\end{leftbar}\end{theo}}
\newtheorem{lem}[theo]{Lemma}
\newenvironment{lemma}[1][]
{\begin{lem}[#1]\begin{leftbar}}
{\end{leftbar}\end{lem}}
\newtheorem{prop}[theo]{Proposition}
\newenvironment{proposition}[1][]
{\begin{prop}[#1]\begin{leftbar}}
{\end{leftbar}\end{prop}}
\newtheorem{defi}[theo]{Definition}
\newenvironment{definition}[1][]
{\begin{defi}[#1]\begin{leftbar}}
{\end{leftbar}\end{defi}}
\newtheorem{remk}[theo]{Remark}
\newenvironment{remark}[1][]
{\begin{remk}[#1]\begin{leftbar}}
{\end{leftbar}\end{remk}}
\newtheorem{coro}[theo]{Corollary}
\newenvironment{corollary}[1][]
{\begin{coro}[#1]\begin{leftbar}}
{\end{leftbar}\end{coro}}
\newtheorem{conv}[theo]{Convention}
\newenvironment{convention}[1][]
{\begin{conv}[#1]\begin{leftbar}}
{\end{leftbar}\end{conv}}
\newtheorem{quest}[theo]{Question}
\newenvironment{question}[1][]
{\begin{quest}[#1]\begin{leftbar}}
{\end{leftbar}\end{quest}}
\newtheorem{warn}[theo]{Warning}
\newenvironment{warning}[1][]
{\begin{warn}[#1]\begin{leftbar}}
{\end{leftbar}\end{warn}}
\newtheorem{conj}[theo]{Conjecture}
\newenvironment{conjecture}[1][]
{\begin{conj}[#1]\begin{leftbar}}
{\end{leftbar}\end{conj}}
\newtheorem{exam}[theo]{Example}
\newenvironment{example}[1][]
{\begin{exam}[#1]\begin{leftbar}}
{\end{leftbar}\end{exam}}
\newtheorem{exmp}[exer]{Exercise}
\newenvironment{exercise}[1][]
{\begin{exmp}[#1]\begin{leftbar}}
{\end{leftbar}\end{exmp}}
\newenvironment{statement}{\begin{quote}}{\end{quote}}
\newenvironment{fineprint}{\medskip \begin{small}}{\end{small} \medskip}
\iffalse
\newenvironment{proof}[1][Proof]{\noindent\textbf{#1.} }{\ \rule{0.5em}{0.5em}}
\newenvironment{question}[1][Question]{\noindent\textbf{#1.} }{\ \rule{0.5em}{0.5em}}
\newenvironment{warning}[1][Warning]{\noindent\textbf{#1.} }{\ \rule{0.5em}{0.5em}}
\newenvironment{teachingnote}[1][Teaching note]{\noindent\textbf{#1.} }{\ \rule{0.5em}{0.5em}}
\fi
\let\sumnonlimits\sum
\let\prodnonlimits\prod
\let\cupnonlimits\bigcup
\let\capnonlimits\bigcap
\renewcommand{\sum}{\sumnonlimits\limits}
\renewcommand{\prod}{\prodnonlimits\limits}
\renewcommand{\bigcup}{\cupnonlimits\limits}
\renewcommand{\bigcap}{\capnonlimits\limits}
\setlength\tablinesep{3pt}
\setlength\arraylinesep{3pt}
\setlength\extrarulesep{3pt}
\voffset=0cm
\hoffset=-0.7cm
\setlength\textheight{22.5cm}
\setlength\textwidth{15.5cm}
\newcommand\arxiv[1]{\href{http://www.arxiv.org/abs/#1}{\texttt{arXiv:#1}}}
\newenvironment{verlong}{}{}
\newenvironment{vershort}{}{}
\newenvironment{noncompile}{}{}
\newenvironment{teachingnote}{}{}
\excludecomment{verlong}
\includecomment{vershort}
\excludecomment{noncompile}
\excludecomment{teachingnote}
\newcommand{\CC}{\mathbb{C}}
\newcommand{\RR}{\mathbb{R}}
\newcommand{\QQ}{\mathbb{Q}}
\newcommand{\NN}{\mathbb{N}}
\newcommand{\ZZ}{\mathbb{Z}}
\newcommand{\KK}{\mathbb{K}}
\newcommand{\id}{\operatorname{id}}
\newcommand{\lcm}{\operatorname{lcm}}
\newcommand{\rev}{\operatorname{rev}}
\newcommand{\powset}[2][]{\ifthenelse{\equal{#2}{}}{\mathcal{P}\left(#1\right)}{\mathcal{P}_{#1}\left(#2\right)}}
\newcommand{\set}[1]{\left\{ #1 \right\}}
\newcommand{\abs}[1]{\left| #1 \right|}
\newcommand{\tup}[1]{\left( #1 \right)}
\newcommand{\ive}[1]{\left[ #1 \right]}
\newcommand{\floor}[1]{\left\lfloor #1 \right\rfloor}
\newcommand{\lf}[2]{#1^{\underline{#2}}}
\newcommand{\underbrack}[2]{\underbrace{#1}_{\substack{#2}}}
\newcommand{\horrule}[1]{\rule{\linewidth}{#1}}
\newcommand{\are}{\ar@{-}}
\newcommand{\nnn}{\nonumber\\}
\newcommand{\sslash}{\mathbin{/\mkern-6mu/}}
\newcommand{\numboxed}[2]{\underbrace{\boxed{#1}}_{\text{box } #2}}
\newcommand{\ig}[2]{\includegraphics[scale=#1]{#2.png}}
\newcommand{\UNFINISHED}{\begin{center} \Huge{\textbf{Unfinished material begins here.}} \end{center} }
\iffalse
\NOEXPAND{\today}{\today}
\NOEXPAND{\sslash}{\sslash}
\NOEXPAND{\numboxed}[2]{\numboxed}
\NOEXPAND{\UNFINISHED}{\UNFINISHED}
\fi
\ihead{gcds of recursive sequences}
\ohead{page \thepage}
\cfoot{\today}
\begin{document}

\title{Elemente der Mathematik, Problem 1414: gcds of recursively defined sequences}
\author{Darij Grinberg\thanks{Drexel University, Korman Center, 15 S 33rd Street,
Philadelphia PA, 19104, USA}}
\date{December 9, 2020}
\maketitle

\section{Problem}

Let $n$ be a positive integer. Let $A$ be an $n\times n$-matrix with integer
entries. Let $v$ be a column vector of size $n$ with integer entries.

For each integer $m\geq0$, define $g_{m}$ to be the greatest common divisor of
the $n$ entries of the vector $A^{m}v$.

Prove the following: If $g_{m}=1$ holds for at least one integer $m\geq n$,
then $g_{m}=1$ holds for every integer $m\geq0$.

\section{Remarks}

Long ago, I posed a weaker version of a particular case ($n=2$ and $A=\left(
\begin{array}
[c]{cc}%
p & q\\
q & p
\end{array}
\right)  $) as a contest problem (5th QEDMO 2007, problem 1).

It appears natural to try strengthening the problem further, conjecturing
perhaps that $g_{kn}\mid g_{n}^{k}$ for any integer $k\geq1$. However, this is
easily seen to be false in general.

\section{Solution}

We shall use two lemmas:\footnote{We shall liberally use the notation $0$ for
zero matrices and zero vectors.}

\begin{lemma}
\label{lem.sol.gcdAnv.nilmat}Let $\mathbb{F}$ be a field. Let $A$ be an
$n\times n$-matrix over $\mathbb{F}$. Let $v$ be a column vector of size $n$
with entries in $\mathbb{F}$.

Let $k\geq0$ be an integer. Assume that $A^{k}v=0$. Then, $A^{n}v=0$.
\end{lemma}

\begin{proof}
[Proof of Lemma \ref{lem.sol.gcdAnv.nilmat}.]This is a standard exercise in
linear algebra; here is one of the shortest proofs:

Let $\chi_{A}=\det\left(  tI_{n}-A\right)  \in\mathbb{F}\left[  t\right]  $ be
the characteristic polynomial of the matrix $A$ (where $I_{n}$ denotes the
$n\times n$ identity matrix). The Cayley--Hamilton theorem yields $\chi
_{A}\left(  A\right)  =0$.

Recall that the polynomial ring $\mathbb{F}\left[  t\right]  $ is a principal
ideal domain. Thus, the polynomials $\chi_{A}$ and $t^{k}$ in $\mathbb{F}%
\left[  t\right]  $ have a greatest common divisor. Without loss of
generality, we can assume that this greatest common divisor is monic
(otherwise, we can scale it so it becomes monic). This greatest common divisor
is then a monic divisor of $t^{k}$, and thus has the form $t^{j}$ for some
$j\in\left\{  0,1,\ldots,k\right\}  $ (since any monic divisor of $t^{k}$ has
this form). Consider this $j$. Thus, $t^{j}$ is the greatest common divisor of
the polynomials $\chi_{A}$ and $t^{k}$. Hence, $t^{j}$ is a divisor of
$\chi_{A}$; therefore, $t^{j}\mid\chi_{A}$, so that $\deg\left(  t^{j}\right)
\leq\deg\left(  \chi_{A}\right)  =n$ (since the characteristic polynomial of
an $n\times n$-matrix always has degree $n$). In other words, $n\geq
\deg\left(  t^{j}\right)  =j$.

Bezout's theorem shows that the greatest common divisor of any two polynomials
$f,g\in\mathbb{F}\left[  t\right]  $ can be written in the form $xf+yg$ for
some $x,y\in\mathbb{F}\left[  t\right]  $. Applying this to $f=\chi_{A}$ and
$g=t^{k}$, we thus conclude that $t^{j}$ can be written in the form $x\chi
_{A}+yt^{k}$ for some $x,y\in\mathbb{F}\left[  t\right]  $ (since $t^{j}$ is
the greatest common divisor of $\chi_{A}$ and $t^{k}$). Consider these $x,y$.
Thus, $t^{j}=x\chi_{A}+yt^{k}$. Substituting $A$ for $t$ on both sides of this
equality, we obtain%
\[
A^{j}=\left(  x\chi_{A}+yt^{k}\right)  \left(  A\right)  =x\left(  A\right)
\chi_{A}\left(  A\right)  +y\left(  A\right)  A^{k}.
\]
Thus,%
\[
A^{j}v=\left(  x\left(  A\right)  \chi_{A}\left(  A\right)  +y\left(
A\right)  A^{k}\right)  v=x\left(  A\right)  \underbrace{\chi_{A}\left(
A\right)  }_{=0}v+y\left(  A\right)  \underbrace{A^{k}v}_{=0}=0+0=0.
\]
However, $n\geq j$, so that $A^{n}=A^{n-j}A^{j}$ and thus $A^{n}%
v=A^{n-j}\underbrace{A^{j}v}_{=0}=A^{n-j}0=0$. This proves Lemma
\ref{lem.sol.gcdAnv.nilmat}.
\end{proof}

\begin{lemma}
\label{lem.sol.gcdAnv.1}Let $p$ be a prime number. Assume that $p\nmid g_{m}$
holds for at least one integer $m\geq n$. Then, $p\nmid g_{k}$ holds for every
integer $k\geq0$.
\end{lemma}

\begin{proof}
[Proof of Lemma \ref{lem.sol.gcdAnv.1}.]Consider the finite field
$\mathbb{F}_{p}=\mathbb{Z}/p\mathbb{Z}$ with $p$ elements. If $i$ is an
integer, then $\left[  i\right]  $ shall denote the projection of
$i\in\mathbb{Z}$ onto this finite field $\mathbb{F}_{p}$ (that is, the
congruence class of $i$ modulo $p$). Likewise, if $B$ is any matrix with
integer entries, then $\left[  B\right]  $ shall denote the matrix obtained by
projecting each entry of $B$ onto $\mathbb{F}_{p}$ (that is: if $B=\left(
b_{i,j}\right)  _{1\leq i\leq k,\ 1\leq j\leq\ell}\in\mathbb{Z}^{k\times\ell}%
$, then $\left[  B\right]  =\left(  \left[  b_{i,j}\right]  \right)  _{1\leq
i\leq k,\ 1\leq j\leq\ell}\in\mathbb{F}_{p}^{k\times\ell}$). We treat column
vectors of size $n$ as $n\times1$-matrices; thus, $v$ is an $n\times1$-matrix.

The projection from $\mathbb{Z}$ onto $\mathbb{F}_{p}$ is a ring homomorphism.
Thus, for each integer $m\geq0$, we have
\begin{equation}
\left[  A^{m}v\right]  =\left[  A\right]  ^{m}\left[  v\right]  .
\label{pf.lem.sol.gcdAnv.1.Amv}%
\end{equation}


Now, let $k\geq0$ be an integer. We shall show that $p\nmid g_{k}$.

Indeed, assume the contrary. Thus, $p\mid g_{k}$. Recall that $g_{k}$ was
defined as the greatest common divisor of the $n$ entries of the vector
$A^{k}v$. Hence, $p\mid g_{k}$ entails that all $n$ entries of the vector
$A^{k}v$ are divisible by $p$. Thus, the projections of these $n$ entries onto
$\mathbb{F}_{p}$ are all $0$. In other words, we have $\left[  A^{k}v\right]
=0$ (since the entries of the vector $\left[  A^{k}v\right]  $ are the
projections of the entries of $A^{k}v$ onto $\mathbb{F}_{p}$). But
(\ref{pf.lem.sol.gcdAnv.1.Amv}) shows that $\left[  A^{k}v\right]  =\left[
A\right]  ^{k}\left[  v\right]  $. Hence, $\left[  A\right]  ^{k}\left[
v\right]  =\left[  A^{k}v\right]  =0$. Thus, Lemma \ref{lem.sol.gcdAnv.nilmat}
(applied to $\mathbb{F}_{p}$, $\left[  A\right]  $ and $\left[  v\right]  $
instead of $\mathbb{F}$, $A$ and $v$) yields $\left[  A\right]  ^{n}\left[
v\right]  =0$.

We have assumed that $p\nmid g_{m}$ holds for at least one integer $m\geq n$.
Consider this $m$. From $m\geq n$, we obtain $\left[  A\right]  ^{m}=\left[
A\right]  ^{m-n}\left[  A\right]  ^{n}$, thus $\left[  A\right]  ^{m}\left[
v\right]  =\left[  A\right]  ^{m-n}\underbrace{\left[  A\right]  ^{n}\left[
v\right]  }_{=0}=\left[  A\right]  ^{m-n}0=0$.

Now, (\ref{pf.lem.sol.gcdAnv.1.Amv}) shows that $\left[  A^{m}v\right]
=\left[  A\right]  ^{m}\left[  v\right]  =0$. In other words, all $n$ entries
of the vector $\left[  A^{m}v\right]  $ are $0$. In other words, all $n$
entries of the vector $A^{m}v$ are divisible by $p$ (since the entries of the
vector $\left[  A^{m}v\right]  $ are the projections of the entries of the
vector $A^{m}v$ onto $\mathbb{F}_{p}$). Hence, the greatest common divisor of
these $n$ entries must also be divisible by $p$. Since we have denoted this
greatest common divisor by $g_{m}$, we thus conclude that $g_{m}$ is divisible
by $p$. In other words, $p\mid g_{m}$. This contradicts $p\nmid g_{m}$. This
contradiction shows that our assumption was false. Hence, $p\nmid g_{k}$ is
proved. Thus, we have proved Lemma \ref{lem.sol.gcdAnv.1}.
\end{proof}

Now, it is easy to solve the exercise: Assume that $g_{m}=1$ holds for at
least one integer $m\geq n$. Let $k\geq0$ be an integer. We shall show that
$g_{k}=1$.

Indeed, assume the contrary. Thus, $g_{k}\neq1$. Since $g_{k}$ is a
nonnegative integer (being defined as a greatest common divisor of $n$
integers), we thus conclude that $g_{k}\in\left\{  0\right\}  \cup\left\{
2,3,4,5,\ldots\right\}  $. Hence, there exists a prime $p$ such that $p\mid
g_{k}$. Consider this $p$. We have assumed that $g_{m}=1$ holds for at least
one integer $m\geq n$. Thus, $p\nmid g_{m}$ holds for at least one integer
$m\geq n$ (since $g_{m}=1$ clearly implies $p\nmid g_{m}$). Lemma
\ref{lem.sol.gcdAnv.1} thus shows that $p\nmid g_{k}$. This contradicts $p\mid
g_{k}$. This contradiction shows that our assumption was wrong. Hence,
$g_{k}=1$ is proved.

Forget that we fixed $k$. We thus have shown that $g_{k}=1$ holds for every
integer $k\geq0$. In other words, $g_{m}=1$ holds for every integer $m\geq0$.
This solves the exercise.
\end{document}