\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{needspace}
\usepackage{tabls}
%TCIDATA{OutputFilter=latex2.dll}
%TCIDATA{Version=5.50.0.2960}
%TCIDATA{LastRevised=Tuesday, March 03, 2020 13:36:29}
%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
\newcounter{exer}
\newcounter{exera}
\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{condition}[1][]
{\begin{conv}[#1]\begin{leftbar}}
{\end{leftbar}\end{conv}}
\newtheorem{quest}[theo]{Question}
\newenvironment{algorithm}[1][]
{\begin{quest}[#1]\begin{leftbar}}
{\end{leftbar}\end{quest}}
\newtheorem{warn}[theo]{Warning}
\newenvironment{conclusion}[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}}
\newtheorem{exetwo}[exera]{Additional exercise}
\newenvironment{addexercise}[1][]
{\begin{exetwo}[#1]\begin{leftbar}}
{\end{leftbar}\end{exetwo}}
\newenvironment{statement}{\begin{quote}}{\end{quote}}
\iffalse
\newenvironment{proof}[1][Proof]{\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=0cm
\setlength\textheight{22.5cm}
\setlength\textwidth{15.5cm}
\newenvironment{verlong}{}{}
\newenvironment{vershort}{}{}
\newenvironment{noncompile}{}{}
\excludecomment{verlong}
\includecomment{vershort}
\excludecomment{noncompile}
\newcommand{\id}{\operatorname{id}}
\ihead{On coprime characteristic polynomials over finite fields}
\ohead{page \thepage}
\cfoot{}
\begin{document}

\title{On coprime characteristic polynomials over finite fields\\{\large [Fragment of the paper \textquotedblleft Additive Cellular Automata
Over Finite Abelian Groups: Topological and Measure Theoretic
Properties\textquotedblright]}}
\author{Alberto Dennunzio
\and Enrico Formenti
\and Darij Grinberg
\and Luciano Margara}
\date{
%TCIMACRO{\TeXButton{today}{\today}}%
%BeginExpansion
\today
%EndExpansion
}
\maketitle
\tableofcontents

\section{On coprime characteristic polynomials over finite fields}

\begin{statement}
The following is a fragment of the paper {\normalsize \textquotedblleft%
}Additive Cellular Automata Over Finite Abelian Groups: Topological and
Measure Theoretic Properties\textquotedblright\ in which we prove some purely
algebraic properties of matrices and their characteristic polynomials. The
fragment has been somewhat rewritten to make it self-contained.
\end{statement}

\subsection*{Acknowledgments}

DG thanks the Mathematisches Forschungsinstitut Oberwolfach for its
hospitality during part of the writing process.

\subsection{The main theorem}

We shall use the following notations:

\begin{itemize}
\item The symbol $\mathbb{N}$ shall mean the set $\left\{  0,1,2,\ldots
\right\}  $.

\item If $n\in\mathbb{N}$, then the notation $I_{n}$ shall always stand for an
$n\times n$ identity matrix (over whatever ring we are using).

\item If $\mathbb{K}$ is a commutative ring, and if $n\in\mathbb{N}$, and if
$A\in\mathbb{K}^{n\times n}$ is an $n\times n$-matrix over $\mathbb{K}$, then
$\chi_{A}$ shall denote the characteristic polynomial $\det\left(
tI_{n}-A\right)  \in\mathbb{K}\left[  t\right]  $ of $A$.

\item If $f$ and $g$ are two univariate polynomials over a field $K$, then
\textquotedblleft$f\perp g$\textquotedblright\ will mean that the polynomials
$f$ and $g$ are coprime. (This makes sense, since the polynomial ring
$K\left[  t\right]  $ is a Euclidean domain.)
\end{itemize}

We are now ready to state the main result of this section:

\begin{theorem}
\label{thm.coprichar.main}We fix a prime power $q$ and consider the
corresponding finite field $\mathbb{F}_{q}$. Let $F$ be a field such that
$F/\mathbb{F}_{q}$ is a purely transcendental field extension. (For example,
$F$ can be the field of all rational functions in a single variable over
$\mathbb{F}_{q}$.)

Let $n\in\mathbb{N}$. Let $N\in F^{n\times n}$ be a matrix. Then, the
following three assertions are equivalent:

\begin{itemize}
\item \textit{Assertion }$\mathcal{X}$\textit{:} We have $\det\left(
N^{k}-I_{n}\right)  \neq0$ for all positive integers $k$.

\item \textit{Assertion }$\mathcal{Y}$\textit{:} We have $\chi_{N}\perp
t^{k}-1$ for all positive integers $k$.

\item \textit{Assertion }$\mathcal{Z}$\textit{:} We have $\chi_{N}\perp
t^{q^{i}-1}-1$ for all $i\in\left\{  1,2,\ldots,n\right\}  $.
\end{itemize}
\end{theorem}

\subsection{Proof of the main theorem}

Our proof of this theorem will rely on the following two lemmas:

\begin{lemma}
\label{lem.coprichar.fdiv}Let $q$, $\mathbb{F}_{q}$ and $F$ be as in Theorem
\ref{thm.coprichar.main}.

Let $n\in\mathbb{N}$. Let $f\in F\left[  t\right]  $ be a polynomial such that
$\deg f\leq n$. Assume that $f\perp t^{q^{i}-1}-1$ for all $i\in\left\{
1,2,\ldots,n\right\}  $. Then, $f\perp t^{k}-1$ for all positive integers $k$.
\end{lemma}

\begin{proof}
[Proof of Lemma \ref{lem.coprichar.fdiv}.]Let $k$ be a positive integer. We
must show that $f\perp t^{k}-1$.

Indeed, assume the contrary. Then, the polynomials $f$ and $t^{k}-1$ have a
non-constant common divisor $g\in F\left[  t\right]  $. Consider this $g$.
Then, $g\mid f$ and $g\mid t^{k}-1$.

Hence, the polynomial $g$ is a divisor of $t^{k}-1$; thus, its roots are
$k$-th roots of unity, and therefore are algebraic over the field
$\mathbb{F}_{q}$. Hence, the coefficients of $g$ are algebraic over the field
$\mathbb{F}_{q}$ as well (since these coefficients are symmetric polynomials
in these roots with integer coefficients). On the other hand, these
coefficients belong to $F$. But $F/\mathbb{F}_{q}$ is a purely transcendental
field extension. Thus, every element of $F$ that is algebraic over
$\mathbb{F}_{q}$ must belong to $\mathbb{F}_{q}$\ \ \ \ \footnote{Here we are
using one of the basic properties of purely transcendental field extensions:
If $L/K$ is a purely transcendental field extension, then every element of $L$
that is algebraic over $K$ must belong to $K$. (Equivalently: If $L/K$ is a
purely transcendental field extension, then every element $x\in L\setminus K$
is transcendental over $K$.) This is proven in \cite[\S 7.1, Remark
10]{Bosch18}, for example.}. Thus, the coefficients of $g$ must belong to
$\mathbb{F}_{q}$ (since they are elements of $F$ that are algebraic over
$\mathbb{F}_{q}$). In other words, $g\in\mathbb{F}_{q}\left[  t\right]  $.

Since this polynomial $g\in\mathbb{F}_{q}\left[  t\right]  $ is non-constant,
it must have a monic irreducible divisor in $\mathbb{F}_{q}\left[  t\right]
$. In other words, there exists a monic irreducible $\pi\in\mathbb{F}%
_{q}\left[  t\right]  $ such that $\pi\mid g$. Consider this $\pi$. Let
$j=\deg\pi$. Then, $j\geq1$ (since $\pi$ is irreducible) and
\begin{align*}
j  &  =\deg\pi\leq\deg f\ \ \ \ \ \ \ \ \ \ \left(  \text{since }\pi\mid g\mid
f\right) \\
&  \leq n.
\end{align*}
Hence, $j\in\left\{  1,2,\ldots,n\right\}  $. Thus, $f\perp t^{q^{j}-1}-1$
(since we assumed that $f\perp t^{q^{i}-1}-1$ for all $i\in\left\{
1,2,\ldots,n\right\}  $). Hence, every common divisor of $f$ and $t^{q^{j}%
-1}-1$ in $F\left[  t\right]  $ must be constant.

From $\pi\mid g\mid t^{k}-1$, we conclude that $t^{k}\equiv1\operatorname{mod}%
\pi$ in $F\left[  t\right]  $. If we had $\pi\mid t$ in $F\left[  t\right]  $,
then we would have $t\equiv0\operatorname{mod}\pi$ in $F\left[  t\right]  $,
which would entail $t^{k}\equiv0^{k}=0\operatorname{mod}\pi$ and thus $0\equiv
t^{k}\equiv1\operatorname{mod}\pi$, which would lead to $\pi\mid1$, which
would be absurd (since $\deg\pi=j\geq1$). Thus, we cannot have $\pi\mid t$ in
$F\left[  t\right]  $. Thus, we cannot have $\pi\mid t$ in $\mathbb{F}%
_{q}\left[  t\right]  $ either. Hence, $\pi\nmid t$ in $\mathbb{F}_{q}\left[
t\right]  $. Therefore, $\pi\mid t^{q^{j}-1}-1$%
\ \ \ \ \footnote{\textit{Proof.} This is a well-known fact about irreducible
polynomials in $\mathbb{F}_{q}\left[  t\right]  $ distinct from $t$, but for
the sake of completeness let us give a proof:
\par
For each $u\in\mathbb{F}_{q}\left[  t\right]  $, we let $\overline{u}$ denote
the projection of $u$ onto $\mathbb{F}_{q}\left[  t\right]  /\left(
\pi\right)  $.
\par
We have $\pi\nmid t$ in $\mathbb{F}_{q}\left[  t\right]  $. In other words,
$\overline{t}\neq0$ in $\mathbb{F}_{q}\left[  t\right]  /\left(  \pi\right)
$. In other words, the element $\overline{t}$ of $\mathbb{F}_{q}\left[
t\right]  /\left(  \pi\right)  $ is nonzero.
\par
The polynomial $\pi$ has degree $\deg\pi=j$. Hence, the quotient ring
$\mathbb{F}_{q}\left[  t\right]  /\left(  \pi\right)  $ is an $\mathbb{F}_{q}%
$-vector space of dimension $j$ (indeed, it has a basis consisting of
$\overline{t^{0}},\overline{t^{1}},\ldots,\overline{t^{j-1}}$). Hence, it has
size $\left\vert \mathbb{F}_{q}\left[  t\right]  /\left(  \pi\right)
\right\vert =\left\vert \mathbb{F}_{q}\right\vert ^{j}=q^{j}$ (since
$\left\vert \mathbb{F}_{q}\right\vert =q$). Moreover, this quotient ring
$\mathbb{F}_{q}\left[  t\right]  /\left(  \pi\right)  $ is a field (since
$\pi$ is irreducible). Thus, $\mathbb{F}_{q}\left[  t\right]  /\left(
\pi\right)  $ is a finite field of size $q^{j}$. As a consequence, its group
of units is a finite group of size $q^{j}-1$. Thus, Lagrange's theorem shows
that $u^{q^{j}-1}=1$ for every nonzero element $u\in\mathbb{F}_{q}\left[
t\right]  /\left(  \pi\right)  $. Applying this to $u=\overline{t}$, we
conclude that $\overline{t}^{q^{j}-1}=1$ (since the element $\overline{t}$ of
$\mathbb{F}_{q}\left[  t\right]  /\left(  \pi\right)  $ is nonzero). Hence,
$\overline{t^{q^{j}-1}}=\overline{t}^{q^{j}-1}=1=\overline{1}$, so that
$t^{q^{j}-1}\equiv1\operatorname{mod}\pi$ in $\mathbb{F}_{q}\left[  t\right]
$. In other words, $\pi\mid t^{q^{j}-1}-1$, qed.}.

Combining $\pi\mid g\mid f$ with $\pi\mid t^{q^{j}-1}-1$, we conclude that
$\pi$ is a common divisor of $f$ and $t^{q^{j}-1}-1$ in $F\left[  t\right]  $.
Hence, $\pi$ is constant (since every common divisor of $f$ and $t^{q^{j}%
-1}-1$ in $F\left[  t\right]  $ must be constant). This contradicts the
irreducibility of $\pi$. This contradiction shows that our assumption was
false. Hence, Lemma \ref{lem.coprichar.fdiv} is proven.
\end{proof}

\begin{lemma}
\label{lem.coprichar.f}Let $n\in\mathbb{N}$. Let $K$ be any field. Let $N\in
K^{n\times n}$ be a matrix. Let $f\in K\left[  t\right]  $ be any polynomial.
Then, $\det\left(  f\left(  N\right)  \right)  \neq0$ if and only if $\chi
_{N}\perp f$.
\end{lemma}

\begin{proof}
[First proof of Lemma \ref{lem.coprichar.f}.]Pick a splitting field $L$ of $f$
over $K$. Then, we can factor $f$ in the polynomial ring $L\left[  t\right]  $
as follows:
\[
f=\lambda\left(  t-a_{1}\right)  \left(  t-a_{2}\right)  \cdots\left(
t-a_{k}\right)  \ \ \ \ \ \ \ \ \ \ \text{for some }\lambda\in L\setminus
\left\{  0\right\}  \text{ and some }a_{1},a_{2},\ldots,a_{k}\in L.
\]
Consider these $\lambda$ and $a_{1},a_{2},\ldots,a_{k}$. Note that these $k$
elements $a_{1},a_{2},\ldots,a_{k}$ of $L$ are precisely the roots of $f$ in
$L$. Evaluating both sides of the equality $f=\lambda\left(  t-a_{1}\right)
\left(  t-a_{2}\right)  \cdots\left(  t-a_{k}\right)  $ at $N$, we obtain the
equality%
\[
f\left(  N\right)  =\lambda\left(  N-a_{1}I_{n}\right)  \left(  N-a_{2}%
I_{n}\right)  \cdots\left(  N-a_{k}I_{n}\right)
\]
in the matrix ring $L^{n\times n}$. Hence,
\begin{align*}
\det\left(  f\left(  N\right)  \right)   &  =\det\left(  \lambda\left(
N-a_{1}I_{n}\right)  \left(  N-a_{2}I_{n}\right)  \cdots\left(  N-a_{k}%
I_{n}\right)  \right) \\
&  =\lambda^{n}\cdot\det\left(  N-a_{1}I_{n}\right)  \cdot\det\left(
N-a_{2}I_{n}\right)  \cdot\cdots\cdot\det\left(  N-a_{k}I_{n}\right)  .
\end{align*}
Thus, we have the following chain of equivalences:%
\begin{align*}
&  \ \left(  \det\left(  f\left(  N\right)  \right)  \neq0\right) \\
&  \Longleftrightarrow\ \left(  \lambda^{n}\cdot\det\left(  N-a_{1}%
I_{n}\right)  \cdot\det\left(  N-a_{2}I_{n}\right)  \cdot\cdots\cdot
\det\left(  N-a_{k}I_{n}\right)  \neq0\right) \\
&  \Longleftrightarrow\ \left(  \det\left(  N-a_{1}I_{n}\right)  \cdot
\det\left(  N-a_{2}I_{n}\right)  \cdot\cdots\cdot\det\left(  N-a_{k}%
I_{n}\right)  \neq0\right) \\
&  \ \ \ \ \ \ \ \ \ \ \left(  \text{since }\lambda\neq0\right) \\
&  \Longleftrightarrow\ \left(  \det\left(  N-a_{i}I_{n}\right)  \neq0\text{
for each }i\in\left\{  1,2,\ldots,k\right\}  \right) \\
&  \Longleftrightarrow\ \left(  \left(  a_{i}\text{ is not an eigenvalue of
}N\right)  \text{ for each }i\in\left\{  1,2,\ldots,k\right\}  \right) \\
&  \ \ \ \ \ \ \ \ \ \ \left(
\begin{array}
[c]{c}%
\text{since the statement \textquotedblleft}\det\left(  N-a_{i}I_{n}\right)
\neq0\text{\textquotedblright\ for any given }i\in\left\{  1,2,\ldots
,k\right\} \\
\text{is equivalent to \textquotedblleft}a_{i}\text{ is not an eigenvalue of
}N\text{\textquotedblright}%
\end{array}
\right) \\
&  \Longleftrightarrow\ \left(  \left(  a_{i}\text{ is not a root of }\chi
_{N}\right)  \text{ for each }i\in\left\{  1,2,\ldots,k\right\}  \right) \\
&  \ \ \ \ \ \ \ \ \ \ \left(  \text{since the eigenvalues of }N\text{ are the
roots of }\chi_{N}\right) \\
&  \Longleftrightarrow\ \left(  \text{none of the }k\text{ elements }%
a_{1},a_{2},\ldots,a_{k}\text{ is a root of }\chi_{N}\right) \\
&  \Longleftrightarrow\ \left(  \text{none of the roots of }f\text{ in
}L\text{ is a root of }\chi_{N}\right) \\
&  \ \ \ \ \ \ \ \ \ \ \left(  \text{since the }k\text{ elements }a_{1}%
,a_{2},\ldots,a_{k}\text{ are precisely the roots of }f\text{ in }L\right) \\
&  \Longleftrightarrow\ \left(  f\perp\chi_{N}\right)  .
\end{align*}
Here, the last equivalence sign is due to a standard argument about
polynomials\footnote{Here is a detailed proof: We must show the equivalence%
\begin{equation}
\left(  \text{none of the roots of }f\text{ in }L\text{ is a root of }\chi
_{N}\right)  \ \Longleftrightarrow\ \left(  f\perp\chi_{N}\right)  .
\label{pf.lem.coprichar.f.fn1.2}%
\end{equation}
We shall show its \textquotedblleft$\Longrightarrow$\textquotedblright\ and
\textquotedblleft$\Longleftarrow$\textquotedblright\ directions separately:
\par
$\Longrightarrow:$ Assume that none of the roots of $f$ in $L$ is a root of
$\chi_{N}$. We must prove that $f\perp\chi_{N}$.
\par
Indeed, assume the contrary. Thus, the polynomials $f$ and $\chi_{N}$ have a
non-constant common divisor $g\in K\left[  t\right]  $. Consider this $g$.
Thus, $g\mid f$ and $g\mid\chi_{N}$ in $K\left[  t\right]  $. We WLOG assume
that $g$ is monic (since we can always achieve this by scaling $g$). We have
$g\mid f$ in $K\left[  t\right]  $, thus also in $L\left[  t\right]  $. Hence,
$g\mid f=\lambda\left(  t-a_{1}\right)  \left(  t-a_{2}\right)  \cdots\left(
t-a_{k}\right)  $ in $L\left[  t\right]  $. Hence, $g$ must be a product of
some of the linear polynomials $t-a_{1},t-a_{2},\ldots,t-a_{k}$ (since
$L\left[  t\right]  $ is a unique factorization domain, and $g$ is monic). In
other words, $g=\prod_{i\in I}\left(  t-a_{i}\right)  $ for some subset $I$ of
$\left\{  1,2,\ldots,k\right\}  $. Consider this $I$. If $I$ was empty, then
we would have
\begin{align*}
g  &  =\prod_{i\in I}\left(  t-a_{i}\right)  =\left(  \text{empty
product}\right)  \ \ \ \ \ \ \ \ \ \ \left(  \text{since }I\text{ is
empty}\right) \\
&  =1,
\end{align*}
which would contradict the fact that $g$ is non-constant. Hence, $I$ is
nonempty. Thus, there exists some $j\in I$. Consider this $j$. Now, $a_{j}$ is
a root of $f$ in $L$ (since $a_{1},a_{2},\ldots,a_{k}$ are the roots of $f$ in
$L$), and thus is not a root of $\chi_{N}$ (since none of the roots of $f$ in
$L$ is a root of $\chi_{N}$). Hence, $a_{j}$ is not a root of $g$ either
(since $g\mid\chi_{N}$). On the other hand, $g=\prod_{i\in I}\left(
t-a_{i}\right)  $ is a multiple of $t-a_{j}$ (since $j\in I$), and thus
$a_{j}$ is a root of $g$. This contradicts the fact that $a_{j}$ is not a root
of $g$. This contradiction shows that our assumption was false. Hence, the
\textquotedblleft$\Longrightarrow$\textquotedblright\ direction of
(\ref{pf.lem.coprichar.f.fn1.2}) is proven.
\par
$\Longleftarrow:$ Assume that $f\perp\chi_{N}$. We must prove that none of the
roots of $f$ in $L$ is a root of $\chi_{N}$.
\par
Indeed, assume the contrary. Thus, some root $\alpha$ of $f$ in $L$ is a root
of $\chi_{N}$. Consider this $\alpha$.
\par
But $f\perp\chi_{N}$. Hence, Bezout's theorem shows that there exist two
polynomials $a,b\in K\left[  t\right]  $ such that $af+b\chi_{N}=1$. Consider
these $a,b$. Now, evaluating both sides of the equality $af+b\chi_{N}=1$ at
$\alpha$, we obtain $a\left(  \alpha\right)  f\left(  \alpha\right)  +b\left(
\alpha\right)  \chi_{N}\left(  \alpha\right)  =1$. Hence,
\[
1=a\left(  \alpha\right)  \underbrace{f\left(  \alpha\right)  }%
_{\substack{=0\\\text{(since }\alpha\text{ is a root of }f\text{)}}}+b\left(
\alpha\right)  \underbrace{\chi_{N}\left(  \alpha\right)  }%
_{\substack{=0\\\text{(since }\alpha\text{ is a root of }\chi_{N}\text{)}%
}}=0+0=0.
\]
This is absurd. This contradiction shows that our assumption was false. Hence,
the \textquotedblleft$\Longleftarrow$\textquotedblright\ direction of
(\ref{pf.lem.coprichar.f.fn1.2}) is proven.
\par
Thus, the proof of (\ref{pf.lem.coprichar.f.fn1.2}) is complete.}.

This chain of equivalences entails $\left(  \det\left(  f\left(  N\right)
\right)  \neq0\right)  \ \Longleftrightarrow\ \left(  f\perp\chi_{N}\right)
$. Thus, Lemma \ref{lem.coprichar.f} is proven.
\end{proof}

We will soon give a second proof of Lemma \ref{lem.coprichar.f}, which
generalizes it to arbitrary commutative rings (see Lemma
\ref{lem.coprichar.f-ring} below).

\begin{proof}
[Proof of Theorem \ref{thm.coprichar.main}.]Let $k$ be a positive integer.
Then, Lemma \ref{lem.coprichar.f} (applied to $K=F$ and $f=t^{k}-1$) shows
that $\det\left(  N^{k}-I_{n}\right)  \neq0$ if and only if $\chi_{N}\perp
t^{k}-1$.

Now, forget that we fixed $k$. We thus have proven the equivalence
\newline$\left(  \det\left(  N^{k}-I_{n}\right)  \neq0\right)
\ \Longleftrightarrow\ \left(  \chi_{N}\perp t^{k}-1\right)  $ for each
positive integer $k$. Hence, Assertion $\mathcal{X}$ is equivalent to
Assertion $\mathcal{Y}$.

On the other hand, $\chi_{N}\in F\left[  t\right]  $ is a polynomial with
$\deg\left(  \chi_{N}\right)  =n$. Thus, Lemma \ref{lem.coprichar.fdiv}
(applied to $f=\chi_{N}$) shows that if we have $\chi_{N}\perp t^{q^{i}-1}-1$
for all $i\in\left\{  1,2,\ldots,n\right\}  $, then we have $\chi_{N}\perp
t^{k}-1$ for all positive integers $k$. In other words, Assertion
$\mathcal{Z}$ implies Assertion $\mathcal{Y}$. Conversely, Assertion
$\mathcal{Y}$ implies Assertion $\mathcal{Z}$ (since each $q^{i}-1$ with
$i\in\left\{  1,2,\ldots,n\right\}  $ is a positive integer). Combining these
two sentences, we conclude that Assertion $\mathcal{Y}$ is equivalent to
Assertion $\mathcal{Z}$. Since we have also shown that Assertion $\mathcal{X}$
is equivalent to Assertion $\mathcal{Y}$, we thus conclude that all three
Assertions $\mathcal{X}$, $\mathcal{Y}$ and $\mathcal{Z}$ are equivalent.
Theorem \ref{thm.coprichar.main} is thus proven.
\end{proof}

\subsection{Extending Lemma \ref{lem.coprichar.f} to rings}

As promised, we shall now extend Lemma \ref{lem.coprichar.f} to arbitrary
commutative rings and re-prove it in that generality. First, we need some more lemmas:

\begin{lemma}
\label{lem.coprichar.f(u)-f(v)}Let $\mathbb{K}$ be any commutative ring. Let
$f\in\mathbb{K}\left[  t\right]  $ be any polynomial. Let $\mathbb{L}$ be any
commutative $\mathbb{K}$-algebra. Let $u$ and $v$ be two elements of
$\mathbb{L}$. Then, $u-v\mid f\left(  u\right)  -f\left(  v\right)  $ in
$\mathbb{L}$.
\end{lemma}

\begin{proof}
[Proof of Lemma \ref{lem.coprichar.f(u)-f(v)}.]This is well-known in the case
when $\mathbb{K}=\mathbb{Z}$ and $\mathbb{L}=\mathbb{Z}$; but the same proof
applies in the general case.\footnote{Here is this proof:
\par
Write the polynomial $f\in\mathbb{K}\left[  t\right]  $ in the form
$f=\sum_{i=0}^{n}a_{i}t^{i}$ for some $n\in\mathbb{N}$ and some $a_{0}%
,a_{1},\ldots,a_{n}\in\mathbb{K}$. Then, $f\left(  u\right)  =\sum_{i=0}%
^{n}a_{i}u^{i}$ and $f\left(  v\right)  =\sum_{i=0}^{n}a_{i}v^{i}$.
Subtracting these two equalities from each other, we obtain%
\begin{align*}
f\left(  u\right)  -f\left(  v\right)   &  =\sum_{i=0}^{n}a_{i}u^{i}%
-\sum_{i=0}^{n}a_{i}v^{i}=\sum_{i=0}^{n}a_{i}\underbrace{\left(  u^{i}%
-v^{i}\right)  }_{=\left(  u-v\right)  \sum_{k=0}^{i-1}u^{k}v^{i-1-k}}\\
&  =\sum_{i=0}^{n}a_{i}\left(  u-v\right)  \sum_{k=0}^{i-1}u^{k}%
v^{i-1-k}=\left(  u-v\right)  \sum_{i=0}^{n}a_{i}\sum_{k=0}^{i-1}%
u^{k}v^{i-1-k}.
\end{align*}
The right hand side of this equality is clearly divisible by $u-v$. Thus, so
is the left hand side. In other words, we have $u-v\mid f\left(  u\right)
-f\left(  v\right)  $ in $\mathbb{L}$.} Note that commutativity of
$\mathbb{L}$ is crucial.
\end{proof}

\begin{lemma}
\label{lem.coprichar.det-error}Let $n\in\mathbb{N}$. Let $\mathbb{L}$ be any
commutative ring. Let $A\in\mathbb{L}^{n\times n}$ be any $n\times n$-matrix.
Let $\lambda\in\mathbb{L}$. Then,%
\[
\det\left(  \lambda I_{n}+A\right)  \equiv\det A\operatorname{mod}%
\lambda\mathbb{L}.
\]

\end{lemma}

\begin{proof}
[Proof of Lemma \ref{lem.coprichar.det-error}.]This can be proven using the
explicit formula for $\det\left(  \lambda I_{n}+A\right)  $ in terms of
principal minors of $A$, or using the fact that the characteristic polynomial
of $A$ has constant term $\left(  -1\right)  ^{n}\det A$. Here is another
argument: For each $u\in\mathbb{L}$, we let $\overline{u}$ be the projection
of $u$ onto the quotient ring $\mathbb{L}/\lambda\mathbb{L}$; furthermore, for
each matrix $B\in\mathbb{L}^{n\times n}$, we let $\overline{B}\in\left(
\mathbb{L}/\lambda\mathbb{L}\right)  ^{n\times n}$ be the result of projecting
each entry of the matrix $B$ onto the quotient ring $\mathbb{L}/\lambda
\mathbb{L}$. Then, $\lambda\in\lambda\mathbb{L}$ and thus $\overline{\lambda
}=0$. Hence, $\overline{\lambda I_{n}+A}=\underbrace{\overline{\lambda I_{n}}%
}_{\substack{=0\\\text{(since }\overline{\lambda}=0\text{)}}}+\overline
{A}=\overline{A}$. But the determinant of a matrix is a polynomial in the
entries of the matrix, and thus is respected by the canonical projection
$\mathbb{L}\rightarrow\mathbb{L}/\lambda\mathbb{L}$; hence,%
\[
\det\left(  \overline{\lambda I_{n}+A}\right)  =\overline{\det\left(  \lambda
I_{n}+A\right)  }\ \ \ \ \ \ \ \ \ \ \text{and}\ \ \ \ \ \ \ \ \ \ \det
\overline{A}=\overline{\det A}.
\]
The left hand sides of these two equalities are equal (since $\overline
{\lambda I_{n}+A}=\overline{A}$). Thus, the right hand sides are equal as
well. In other words, $\overline{\det\left(  \lambda I_{n}+A\right)
}=\overline{\det A}$. In other words, $\det\left(  \lambda I_{n}+A\right)
\equiv\det A\operatorname{mod}\lambda\mathbb{L}$. This proves Lemma
\ref{lem.coprichar.det-error}.
\end{proof}

\begin{lemma}
\label{lem.coprichar.detfN}Let $n\in\mathbb{N}$. Let $\mathbb{K}$ be any
commutative ring. Let $f\in\mathbb{K}\left[  t\right]  $ be any polynomial.
Let $N\in\mathbb{K}^{n\times n}$ be any $n\times n$-matrix. Then, there exist
two polynomials $a,b\in\mathbb{K}\left[  t\right]  $ such that%
\[
\det\left(  f\left(  N\right)  \right)  =fa+\chi_{N}%
b\ \ \ \ \ \ \ \ \ \ \text{in }\mathbb{K}\left[  t\right]  .
\]
(Note that the left hand side of this equality is a constant polynomial, since
$f\left(  N\right)  \in\mathbb{K}^{n\times n}$.)
\end{lemma}

\begin{proof}
[Proof of Lemma \ref{lem.coprichar.detfN}.]Consider $N$ as a matrix over the
polynomial ring $\mathbb{K}\left[  t\right]  $ (via the standard embedding
$\mathbb{K}^{n\times n}\rightarrow\left(  \mathbb{K}\left[  t\right]  \right)
^{n\times n}$). The $\mathbb{K}$-subalgebra $\left(  \mathbb{K}\left[
t\right]  \right)  \left[  N\right]  $ of $\left(  \mathbb{K}\left[  t\right]
\right)  ^{n\times n}$ is commutative (since it is generated by the single
element $N$ over the commutative ring $\mathbb{K}\left[  t\right]  $).

Hence, Lemma \ref{lem.coprichar.f(u)-f(v)} (applied to $\mathbb{L}=\left(
\mathbb{K}\left[  t\right]  \right)  \left[  N\right]  $ and $u=tI_{n}$ and
$v=N$) shows that $tI_{n}-N\mid f\left(  tI_{n}\right)  -f\left(  N\right)  $
in $\left(  \mathbb{K}\left[  t\right]  \right)  \left[  N\right]  $. In other
words, there exists some $U\in\left(  \mathbb{K}\left[  t\right]  \right)
\left[  N\right]  $ such that
\begin{equation}
f\left(  tI_{n}\right)  -f\left(  N\right)  =\left(  tI_{n}-N\right)  \cdot U.
\label{pf.lem.coprichar.detfN.1}%
\end{equation}
Consider this $U$. Taking determinants on both sides of the equality
(\ref{pf.lem.coprichar.detfN.1}), we find%
\begin{align*}
\det\left(  f\left(  tI_{n}\right)  -f\left(  N\right)  \right)   &
=\det\left(  \left(  tI_{n}-N\right)  \cdot U\right)  =\underbrace{\det\left(
tI_{n}-N\right)  }_{\substack{=\chi_{N}\\\text{(by the definition of }\chi
_{N}\text{)}}}\cdot\det U\\
&  =\chi_{N}\cdot\det U.
\end{align*}
In view of $f\left(  tI_{n}\right)  =f\left(  t\right)  \cdot I_{n}$, this
rewrites as%
\[
\det\left(  f\left(  t\right)  \cdot I_{n}-f\left(  N\right)  \right)
=\chi_{N}\cdot\det U.
\]
Hence,%
\begin{align*}
&  \chi_{N}\cdot\det U\\
&  =\det\underbrace{\left(  f\left(  t\right)  \cdot I_{n}-f\left(  N\right)
\right)  }_{=f\left(  t\right)  \cdot I_{n}+\left(  -f\left(  N\right)
\right)  }=\det\left(  f\left(  t\right)  \cdot I_{n}+\left(  -f\left(
N\right)  \right)  \right) \\
&  \equiv\det\left(  -f\left(  N\right)  \right)  \ \ \ \ \ \ \ \ \ \ \left(
\begin{array}
[c]{c}%
\text{by Lemma \ref{lem.coprichar.det-error}, applied to }\mathbb{L}%
=\mathbb{K}\left[  t\right]  \text{, }\lambda=f\left(  t\right) \\
\text{and }A=-f\left(  N\right)
\end{array}
\right) \\
&  =\left(  -1\right)  ^{n}\det\left(  f\left(  N\right)  \right)
\operatorname{mod}f\left(  t\right)  \mathbb{K}\left[  t\right]  .
\end{align*}
Multiplying this congruence by $\left(  -1\right)  ^{n}$, we obtain%
\[
\left(  -1\right)  ^{n}\chi_{N}\cdot\det U\equiv\underbrace{\left(  -1\right)
^{n}\left(  -1\right)  ^{n}}_{=1}\det\left(  f\left(  N\right)  \right)
=\det\left(  f\left(  N\right)  \right)  \operatorname{mod}f\left(  t\right)
\mathbb{K}\left[  t\right]  .
\]
In other words, $\left(  -1\right)  ^{n}\chi_{N}\cdot\det U-\det\left(
f\left(  N\right)  \right)  \in f\left(  t\right)  \mathbb{K}\left[  t\right]
$. In other words, there exists a polynomial $c\in\mathbb{K}\left[  t\right]
$ such that
\begin{equation}
\left(  -1\right)  ^{n}\chi_{N}\cdot\det U-\det\left(  f\left(  N\right)
\right)  =f\left(  t\right)  c. \label{pf.lem.coprichar.detfN.5}%
\end{equation}
Consider this $c$. Solving the equality (\ref{pf.lem.coprichar.detfN.5}) for
$\det\left(  f\left(  N\right)  \right)  $, we find%
\begin{align*}
\det\left(  f\left(  N\right)  \right)   &  =\left(  -1\right)  ^{n}\chi
_{N}\cdot\det U-\underbrace{f\left(  t\right)  }_{=f}c=\left(  -1\right)
^{n}\chi_{N}\cdot\det U-fc\\
&  =f\cdot\left(  -c\right)  +\chi_{N}\cdot\left(  -1\right)  ^{n}\det U.
\end{align*}
Hence, there exist two polynomials $a,b\in\mathbb{K}\left[  t\right]  $ such
that $\det\left(  f\left(  N\right)  \right)  =fa+\chi_{N}b$ in $\mathbb{K}%
\left[  t\right]  $ (namely, $a=-c$ and $b=\left(  -1\right)  ^{n}\det U$).
This proves Lemma \ref{lem.coprichar.detfN}.
\end{proof}

We can now generalize Lemma \ref{lem.coprichar.f} to arbitrary rings:

\begin{lemma}
\label{lem.coprichar.f-ring}Let $n\in\mathbb{N}$. Let $\mathbb{K}$ be any
commutative ring. Let $N\in\mathbb{K}^{n\times n}$ be a matrix. Let
$f\in\mathbb{K}\left[  t\right]  $ be any polynomial. Then, $\det\left(
f\left(  N\right)  \right)  \in\mathbb{K}$ is invertible if and only if there
exist polynomials $a,b\in\mathbb{K}\left[  t\right]  $ such that $fa+\chi
_{N}b=1$.
\end{lemma}

\begin{proof}
[Proof of Lemma \ref{lem.coprichar.f-ring}.]$\Longrightarrow:$ Assume that
$\det\left(  f\left(  N\right)  \right)  \in\mathbb{K}$ is invertible. Thus,
there exists some $c\in\mathbb{K}$ such that $\det\left(  f\left(  N\right)
\right)  \cdot c=1$. Consider this $c$.

Lemma \ref{lem.coprichar.detfN} shows that there exist two polynomials
$a,b\in\mathbb{K}\left[  t\right]  $ such that \newline$\det\left(  f\left(
N\right)  \right)  =fa+\chi_{N}b$ in $\mathbb{K}\left[  t\right]  $. Consider
these $a$ and $b$, and denote them by $a_{0}$ and $b_{0}$. Thus, $a_{0}$ and
$b_{0}$ are two polynomials in $\mathbb{K}\left[  t\right]  $ such that
$\det\left(  f\left(  N\right)  \right)  =fa_{0}+\chi_{N}b_{0}$. Now,
comparing $\det\left(  f\left(  N\right)  \right)  \cdot c=1$ with%
\[
\underbrace{\det\left(  f\left(  N\right)  \right)  }_{=fa_{0}+\chi_{N}b_{0}%
}\cdot c=\left(  fa_{0}+\chi_{N}b_{0}\right)  \cdot c=fa_{0}c+\chi_{N}b_{0}c,
\]
we obtain $fa_{0}c+\chi_{N}b_{0}c=1$. Thus, there exist polynomials
$a,b\in\mathbb{K}\left[  t\right]  $ such that $fa+\chi_{N}b=1$ (namely,
$a=a_{0}c$ and $b=b_{0}c$). This proves the \textquotedblleft$\Longrightarrow
$\textquotedblright\ direction of Lemma \ref{lem.coprichar.f-ring}.

$\Longleftarrow:$ Assume that there exist polynomials $a,b\in\mathbb{K}\left[
t\right]  $ such that $fa+\chi_{N}b=1$. Consider these $a$ and $b$. Now,
evaluating both sides of the equality $fa+\chi_{N}b=1$ at $N$, we obtain%
\[
f\left(  N\right)  a\left(  N\right)  +\chi_{N}\left(  N\right)  b\left(
N\right)  =I_{n}.
\]
Hence,%
\[
I_{n}=f\left(  N\right)  a\left(  N\right)  +\underbrace{\chi_{N}\left(
N\right)  }_{\substack{=0\\\text{(by the Cayley--Hamilton}\\\text{theorem)}%
}}b\left(  N\right)  =f\left(  N\right)  a\left(  N\right)  .
\]
Taking determinants on both sides of this equality, we find%
\[
\det\left(  I_{n}\right)  =\det\left(  f\left(  N\right)  a\left(  N\right)
\right)  =\det\left(  f\left(  N\right)  \right)  \cdot\det\left(  a\left(
N\right)  \right)  .
\]
Thus,%
\[
\det\left(  f\left(  N\right)  \right)  \cdot\det\left(  a\left(  N\right)
\right)  =\det\left(  I_{n}\right)  =1.
\]
Hence, $\det\left(  f\left(  N\right)  \right)  \in\mathbb{K}$ is invertible
(and its inverse is $\det\left(  a\left(  N\right)  \right)  $). This proves
the \textquotedblleft$\Longleftarrow$\textquotedblright\ direction of Lemma
\ref{lem.coprichar.f-ring}.
\end{proof}

\begin{proof}
[Second proof of Lemma \ref{lem.coprichar.f}.]Lemma \ref{lem.coprichar.f-ring}
(applied to $\mathbb{K}=K$) shows that $\det\left(  f\left(  N\right)
\right)  \in K$ is invertible if and only if there exist polynomials $a,b\in
K\left[  t\right]  $ such that $fa+\chi_{N}b=1$. But this is precisely the
statement of Lemma \ref{lem.coprichar.f}, because:

\begin{itemize}
\item the element $\det\left(  f\left(  N\right)  \right)  \in K$ is
invertible if and only if $\det\left(  f\left(  N\right)  \right)  \neq0$
(because $K$ is a field), and

\item there exist polynomials $a,b\in K\left[  t\right]  $ such that
$fa+\chi_{N}b=1$ if and only if $\chi_{N}\perp f$ (by Bezout's theorem).
\end{itemize}

Thus, Lemma \ref{lem.coprichar.f} is proven again.
\end{proof}

\begin{thebibliography}{9999999}                                                                                          %


\bibitem[Bosch18]{Bosch18}Siegfried Bosch, \textit{Algebra}, From the
Viewpoint of Galois Theory, Springer 2018.\newline\url{https://doi.org/10.1007/978-3-319-95177-5}
\end{thebibliography}


\end{document}