% German translation of [gcdanv.tex].

\documentclass[numbers=enddot,12pt,final,onecolumn,notitlepage]{scrartcl}%
\usepackage[headsepline,footsepline,manualmark]{scrlayer-scrpage}
\usepackage[all,cmtip]{xy}
\usepackage[german]{babel}
\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:17:18}
%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{ggTs rekursiver Folgen}
\ohead{page \thepage}
\cfoot{\today}
\begin{document}

\title{Elemente der Mathematik, Aufgabe 1414: ggTs rekursiver Folgen}
\author{Darij Grinberg\thanks{Drexel University, Korman Center, 15 S 33rd Street,
Philadelphia PA, 19104, USA}}
\date{9. Dezember 2020}
\maketitle

\section{Aufgabe}

Sei $n$ eine positive ganze Zahl. Sei $A$ eine $n\times n$-Matrix mit
ganzzahligen Eintr\"{a}gen. Sei $v$ ein Spaltenvektor der H\"{o}he $n$ mit
ganzzahligen Eintr\"{a}gen.

F\"{u}r jede ganze Zahl $m\geq0$ sei $g_{m}$ der gr\"{o}\ss te gemeinsame
Teiler der $n$ Eintr\"{a}ge des Vektors $A^{m}v$.

Man beweise folgendes: Wenn $g_{m}=1$ f\"{u}r mindestens eine ganze Zahl
$m\geq n$ gilt, dann gilt $g_{m}=1$ f\"{u}r jede ganze Zahl $m\geq0$.

\section{Anmerkungen}

Vor langer Zeit habe ich eine schw\"{a}chere Version eines Spezialfalls ($n=2$
und $A=\left(
\begin{array}
[c]{cc}%
p & q\\
q & p
\end{array}
\right)  $) der Aufgabe in einem Wettbewerb (5te QEDMO 2007, Aufgabe 1) gestellt.

Es mag nat\"{u}rlich erscheinen, die Aufgabe weiter zu verst\"{a}rken, indem
man vermutet, dass vielleicht $g_{kn}\mid g_{n}^{k}$ f\"{u}r jede ganze Zahl
$k\geq1$ gilt. Dies ist aber im Allgemeinen falsch, wie man unschwer einsieht.

\section{L\"{o}sung}

Wir werden zwei Lemmas gebrauchen:\footnote{Wir werden das Symbol $0$
freiz\"{u}gig f\"{u}r Nullmatrizen und f\"{u}r Nullvektoren verwenden.}

\begin{lemma}
\label{lem.sol.gcdAnv.nilmat}Sei $\mathbb{F}$ ein K\"{o}rper. Sei $A$ eine
$n\times n$-Matrix \"{u}ber $\mathbb{F}$. Sei $v$ ein Spaltenvektor der
H\"{o}he $n$ mit Eintr\"{a}gen in $\mathbb{F}$.

Sei $k\geq0$ eine ganze Zahl. Angenommen, es gilt $A^{k}v=0$. Dann ist
$A^{n}v=0$.
\end{lemma}

\begin{proof}
[Beweis von Lemma \ref{lem.sol.gcdAnv.nilmat}.]Dies ist eine Standard\"{u}bung
in linearer Algebra; der folgende Beweis ist einer der k\"{u}rzesten:

Sei $\chi_{A}=\det\left(  tI_{n}-A\right)  \in\mathbb{F}\left[  t\right]  $
das charakteristische Polynom der Matrix $A$ (wobei $I_{n}$ die $n\times
n$-Einheitsmatrix bezeichnet). Der Satz von Cayley--Hamilton ergibt dann
$\chi_{A}\left(  A\right)  =0$.

Bekanntlich ist der Polynomring $\mathbb{F}\left[  t\right]  $ ein
Hauptidealring. Folglich haben die Polynome $\chi_{A}$ und $t^{k}$ in
$\mathbb{F}\left[  t\right]  $ einen gr\"{o}\ss ten gemeinsamen Teiler. Ohne
Beschr\"{a}nkung der Allgemeinheit nehmen wir an, dass dieser gr\"{o}\ss te
gemeinsame Teiler monisch ist (denn sonst k\"{o}nnen wir ihn so skalieren,
dass er monisch wird). Dieser gr\"{o}\ss te gemeinsame Teiler ist dann ein
monischer Teiler des Polynoms $t^{k}$, und hat daher die Form $t^{j}$ f\"{u}r
ein $j\in\left\{  0,1,\ldots,k\right\}  $ (denn jeder monische Teiler des
Polynoms $t^{k}$ hat diese Form). Betrachten wir dieses $j$. Also ist $t^{j}$
der gr\"{o}\ss te gemeinsame Teiler der Polynome $\chi_{A}$ und $t^{k}$. Somit
ist $t^{j}$ ein Teiler von $\chi_{A}$; wir haben also $t^{j}\mid\chi_{A}$, und
damit $\deg\left(  t^{j}\right)  \leq\deg\left(  \chi_{A}\right)  =n$ (denn
das charakteristische Polynom einer $n\times n$-Matrix hat immer Grad $n$).
Mit anderen Worten: $n\geq\deg\left(  t^{j}\right)  =j$.

Laut dem Satz von Bezout l\"{a}\ss t sich der gr\"{o}\ss te gemeinsame Teiler
von zwei Polynomen $f,g\in\mathbb{F}\left[  t\right]  $ stets in der Form
$xf+yg$ f\"{u}r gewisse $x,y\in\mathbb{F}\left[  t\right]  $ ausdr\"{u}cken.
Wenden wir dies auf $f=\chi_{A}$ und $g=t^{k}$ an, so erhalten wir, dass sich
$t^{j}$ in der Form $x\chi_{A}+yt^{k}$ f\"{u}r gewisse $x,y\in\mathbb{F}%
\left[  t\right]  $ ausdr\"{u}cken l\"{a}\ss t (denn $t^{j}$ ist der
gr\"{o}\ss te gemeinsame Teiler von $\chi_{A}$ und $t^{k}$). Betrachte diese
$x,y$. Dann gilt also $t^{j}=x\chi_{A}+yt^{k}$. Setzen wir $A$ f\"{u}r $t$ auf
beiden Seiten dieser Gleichung ein, so erhalten wir%
\[
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}.
\]
Also ist%
\[
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.
\]
Aber wir haben $n\geq j$, daher $A^{n}=A^{n-j}A^{j}$ und somit $A^{n}%
v=A^{n-j}\underbrace{A^{j}v}_{=0}=A^{n-j}0=0$. Dies beweist Lemma
\ref{lem.sol.gcdAnv.nilmat}.
\end{proof}

\begin{lemma}
\label{lem.sol.gcdAnv.1}Sei $p$ eine Primzahl. Angenommen, $p\nmid g_{m}$ gilt
f\"{u}r mindestens eine ganze Zahl $m\geq n$. Dann gilt $p\nmid g_{k}$ f\"{u}r
jede ganze Zahl $k\geq0$.
\end{lemma}

\begin{proof}
[Beweis von Lemma \ref{lem.sol.gcdAnv.1}.]Betrachte den endlichen K\"{o}rper
$\mathbb{F}_{p}=\mathbb{Z}/p\mathbb{Z}$ mit $p$ Elementen. Ist $i$ eine ganze
Zahl, dann bezeichne $\left[  i\right]  $ die Projektion von $i\in\mathbb{Z}$
auf diesen endlichen K\"{o}rper $\mathbb{F}_{p}$ (das hei\ss t, die
Kongruenzklasse von $i$ modulo $p$). Ist $B$ eine Matrix mit ganzzahligen
Eintr\"{a}gen, dann bezeichne $\left[  B\right]  $ die Matrix, die entsteht,
wenn wir jeden Eintrag von $B$ auf $\mathbb{F}_{p}$ projizieren (das hei\ss t:
wenn $B=\left(  b_{i,j}\right)  _{1\leq i\leq k,\ 1\leq j\leq\ell}%
\in\mathbb{Z}^{k\times\ell}$, dann sei $\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}$). Wir betrachten Spaltenvektoren der H\"{o}he $n$ als
$n\times1$-Matrizen; daher ist $v$ eine $n\times1$-Matrix.

Die Projektion von $\mathbb{Z}$ nach $\mathbb{F}_{p}$ ist ein
Ringhomomorphismus. F\"{u}r jede ganze Zahl $m\geq0$ gilt also
\begin{equation}
\left[  A^{m}v\right]  =\left[  A\right]  ^{m}\left[  v\right]  .
\label{pf.lem.sol.gcdAnv.1.Amv}%
\end{equation}


Sei nun $k\geq0$ eine ganze Zahl. Wir werden zeigen, dass $p\nmid g_{k}$ gilt.

In der Tat nehmen wir das Gegenteil an. Dann ist also $p\mid g_{k}$. Doch
$g_{k}$ war definiert als der gr\"{o}\ss te gemeinsame Teiler der $n$
Eintr\"{a}ge des Vektors $A^{k}v$. Aus $p\mid g_{k}$ folgt somit, dass alle
$n$ Eintr\"{a}ge des Vektors $A^{k}v$ durch $p$ teilbar sind. Die Projektionen
dieser $n$ Eintr\"{a}ge auf $\mathbb{F}_{p}$ sind also alle $0$. Mit anderen
Worten: Wir haben $\left[  A^{k}v\right]  =0$ (denn die Eintr\"{a}ge des
Vektors $\left[  A^{k}v\right]  $ sind die Projektionen der Eintr\"{a}ge des
Vektors $A^{k}v$ auf $\mathbb{F}_{p}$). Doch laut
(\ref{pf.lem.sol.gcdAnv.1.Amv}) gilt $\left[  A^{k}v\right]  =\left[
A\right]  ^{k}\left[  v\right]  $. Somit ist $\left[  A\right]  ^{k}\left[
v\right]  =\left[  A^{k}v\right]  =0$. Lemma \ref{lem.sol.gcdAnv.nilmat}
(angewandt auf $\mathbb{F}_{p}$, $\left[  A\right]  $ und $\left[  v\right]  $
statt $\mathbb{F}$, $A$ und $v$) ergibt also $\left[  A\right]  ^{n}\left[
v\right]  =0$.

Wir haben angenommen, dass $p\nmid g_{m}$ f\"{u}r mindestens eine ganze Zahl
$m\geq n$ gilt. Betrachte diese Zahl $m$. Wegen $m\geq n$ ist $\left[
A\right]  ^{m}=\left[  A\right]  ^{m-n}\left[  A\right]  ^{n}$, und folglich
$\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$.

Nun folgt aus (\ref{pf.lem.sol.gcdAnv.1.Amv}) aber $\left[  A^{m}v\right]
=\left[  A\right]  ^{m}\left[  v\right]  =0$. Mit anderen Worten: Alle $n$
Eintr\"{a}ge des Vektors $\left[  A^{m}v\right]  $ sind $0$. Mit anderen
Worten: Alle $n$ Eintr\"{a}ge des Vektors $A^{m}v$ sind durch $p$ teilbar
(denn die Eintr\"{a}ge des Vektors $\left[  A^{m}v\right]  $ sind die
Projektionen der Eintr\"{a}ge des Vektors $A^{m}v$ auf $\mathbb{F}_{p}$).
Folglich muss der gr\"{o}\ss te gemeinsame Teiler dieser $n$ Eintr\"{a}ge auch
durch $p$ teilbar. Da wir diesen gr\"{o}\ss ten gemeinsamen Teiler mit $g_{m}$
bezeichnet haben, folgern wir also, dass $g_{m}$ durch $p$ teilbar ist. Das
hei\ss t, $p\mid g_{m}$. Dies widerspricht $p\nmid g_{m}$. Dieser Widerspruch
zeigt, dass unsere Annahme falsch war. Somit ist $p\nmid g_{k}$ bewiesen.
Damit ist Lemma \ref{lem.sol.gcdAnv.1} gezeigt.
\end{proof}

Nun l\"{a}\ss t sich die Aufgabe einfach l\"{o}sen: Nehmen wir an, dass
$g_{m}=1$ f\"{u}r mindestens eine ganze Zahl $m\geq n$ gilt. Sei $k\geq0$ eine
ganze Zahl. Wir werden zeigen, dass $g_{k}=1$ gilt.

In der Tat nehmen wir das Gegenteil an. Also gilt $g_{k}\neq1$. Da $g_{k}$
eine nichtnegative ganze Zahl ist (denn $g_{k}$ war definiert als
gr\"{o}\ss ter gemeinsamer Teiler von $n$ ganzen Zahlen), ist mithin $g_{k}%
\in\left\{  0\right\}  \cup\left\{  2,3,4,5,\ldots\right\}  $. Also existiert
eine Primzahl $p$ mit $p\mid g_{k}$. Betrachte diese Primzahl $p$. Wir haben
angenommen, dass $g_{m}=1$ f\"{u}r mindestens eine ganze Zahl $m\geq n$ gilt.
Daher gilt $p\nmid g_{m}$ f\"{u}r mindestens eine ganze Zahl $m\geq n$ (denn
aus $g_{m}=1$ folgt offensichtlich $p\nmid g_{m}$). Lemma
\ref{lem.sol.gcdAnv.1} zeigt daher, dass $p\nmid g_{k}$ ist. Dies widerspricht
aber $p\mid g_{k}$. Dieser Widerspruch zeigt, dass unsere Annahme falsch war.
Also ist $g_{k}=1$ bewiesen.

Vergessen wir, dass wir $k$ fixiert haben. Wir haben also gezeigt, dass
$g_{k}=1$ f\"{u}r jede ganze Zahl $k\geq0$ gilt. Mit anderen Worten: Wir haben
gezeigt, dass $g_{m}=1$ f\"{u}r jede ganze Zahl $m\geq0$ gilt. Die Aufgabe ist
damit gel\"{o}st.


\end{document}