% -------------------------------------------------------------
% NOTE ON THE DETAILED AND SHORT VERSIONS:
% -------------------------------------------------------------
% This paper comes in two versions, a detailed and a short one.
% The short version should be more than sufficient for any
% reasonable use; the detailed one was written purely to
% convince the author of its correctness.
% To switch between the two versions, find the line containing
% "\newenvironment{noncompile}{}{}" in this LaTeX file.
% Look at the two lines right beneath this line.
% To compile the detailed version, they should be as follows:
%   \includecomment{verlong}
%   \excludecomment{vershort}
% To compile the short version, they should be as follows:
%   \excludecomment{verlong}
%   \includecomment{vershort}
% As a rule, the line
%   \excludecomment{noncompile}
% should stay as it is.
% -------------------------------------------------------------
% NOTES ON SOME HACKS USED IN THIS FILE:
% -------------------------------------------------------------
% One of my pet peeves with amsthm is its use of italics in the theorem and
% proposition environments; this makes math and text indistinguishable in said
% enviroments. To avoid this, I redefine the enviroments to use the standard
% font and to use a hanging indent, along with a bold vertical bar to its
% left, to distinguish these environments from surrounding text. (Along with
% the advantage of distinguishing math from text, this also allows nesting
% several such environments inside each other, like a definition inside a
% remark. I'm not sure how good of an idea this is, though. There are also
% downsides related to the hanging indentation, such as footnotes out of it
% being painful to do right.) This is done starting from the line
%   \theoremstyle{definition}
% and until the line
%   {\end{leftbar}\end{exmp}}

\documentclass[numbers=enddot,12pt,final,onecolumn,notitlepage]{scrartcl}%
\usepackage[headsepline,footsepline,manualmark]{scrlayer-scrpage}
\usepackage[all,cmtip]{xy}
\usepackage{amsfonts}
\usepackage{amssymb}
\usepackage{framed}
\usepackage{amsmath}
\usepackage{comment}
\usepackage{color}
\usepackage{hyperref}
\usepackage[sc]{mathpazo}
\usepackage[T1]{fontenc}
\usepackage{amsthm}
\usepackage{ytableau}
%TCIDATA{OutputFilter=latex2.dll}
%TCIDATA{Version=5.50.0.2960}
%TCIDATA{LastRevised=Monday, December 04, 2017 20:23:24}
%TCIDATA{SuppressPackageManagement}
%TCIDATA{<META NAME="GraphicsSave" CONTENT="32">}
%TCIDATA{<META NAME="SaveForMode" CONTENT="1">}
%TCIDATA{BibliographyScheme=Manual}
%BeginMSIPreambleData
\providecommand{\U}[1]{\protect\rule{.1in}{.1in}}
%EndMSIPreambleData
\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]{TODO}
\newenvironment{todo}[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{exmp}[theo]{Example}
\newenvironment{example}[1][]
{\begin{exmp}[#1]\begin{leftbar}}
{\end{leftbar}\end{exmp}}
\newenvironment{statement}{\begin{quote}}{\end{quote}}
\iffalse
\newenvironment{proof}[1][Proof]{\noindent\textbf{#1.} }{\ \rule{0.5em}{0.5em}}
\fi
\newenvironment{verlong}{}{}
\newenvironment{vershort}{}{}
\newenvironment{noncompile}{}{}
\excludecomment{verlong}
\includecomment{vershort}
\excludecomment{noncompile}
\newcommand{\id}{\operatorname{id}}
\newcommand{\NN}{\mathbb{N}}
\let\sumnonlimits\sum
\let\prodnonlimits\prod
\renewcommand{\sum}{\sumnonlimits\limits}
\renewcommand{\prod}{\prodnonlimits\limits}
\setlength\textheight{22.5cm}
\setlength\textwidth{15cm}
\ihead{Fleck's binomial congruence using circulant matrices}
\ohead{\today}
\begin{document}

\title{Fleck's binomial congruence using circulant matrices}
\author{Darij Grinberg}
\date{\today}
\maketitle
\tableofcontents

\section{Fleck's congruence}

\begin{definition}
Let $\mathbb{N}$ denote the set $\left\{  0,1,2,\ldots\right\}  $.
\end{definition}

The following elementary theorem appears, e.g., in \cite{SchWal12} and in
\cite[(12)]{Granvi05}:

\begin{theorem}
\label{thm.fleck}Let $p$ be a prime. Let $j\in\mathbb{Z}$, $n\in\mathbb{N}$
and $q\in\mathbb{N}$ be such that $q\leq\dfrac{n-1}{p-1}$. Then,%
\[
\sum\limits_{\substack{m\in\mathbb{N};\\m\equiv j\operatorname{mod}p}}\left(
-1\right)  ^{m}\dbinom{n}{m}\equiv0\operatorname{mod}p^{q}.
\]
(The sum on the left hand side of this congruence is well-defined, because
every $m>n$ satisfies $\dbinom{n}{m}=0$.)
\end{theorem}

Theorem \ref{thm.fleck} was found in A. Fleck in 1913. In \cite{Granvi05}, it
is proven using cyclotomic integers. Here, we shall instead give a proof using
nothing more advanced than polynomials and matrix multiplication. The tactic
used in the following proof is similar to that used in \cite{Grinbe15} (viz.,
proving congruences of integers by interpreting them as single-entry pieces of
matrix-valued congruences in commutative subrings of matrix rings), and is
probably helpful more often.

\section{Preliminaries: Iverson brackets and circulant matrices}

We now start preparing for the proof of Theorem \ref{thm.fleck}. Let us first
agree on some notations.

\begin{definition}
\label{def.iverson}We shall use the \textit{Iverson bracket notation}: If
$\mathcal{S}$ is a logical statement, then $\left[  \mathcal{S}\right]  $ will
mean the integer $%
\begin{cases}
1, & \text{if }\mathcal{S}\text{ is true};\\
0, & \text{if }\mathcal{S}\text{ is false}%
\end{cases}
$.
\end{definition}

The Iverson bracket can be used for counting (or, rather, for neatly writing
up counting arguments), via the following simple result:

\begin{proposition}
\label{prop.iverson.count}Let $\mathbf{K}$ be a set. For each $k\in\mathbf{K}%
$, let $\mathcal{A}\left(  k\right)  $ be some logical statement. Then,%
\[
\sum_{k\in\mathbf{K}}\left[  \mathcal{A}\left(  k\right)  \right]  =\left(
\text{the number of all }k\in\mathbf{K}\text{ satisfying }\mathcal{A}\left(
k\right)  \right)  .
\]

\end{proposition}

\begin{proof}
[Proof of Proposition \ref{prop.iverson.count}.]We have%
\begin{align*}
\sum_{k\in\mathbf{K}}\left[  \mathcal{A}\left(  k\right)  \right]   &
=\sum_{\substack{k\in\mathbf{K};\\\mathcal{A}\left(  k\right)  \text{ is
true}}}\underbrace{\left[  \mathcal{A}\left(  k\right)  \right]
}_{\substack{=1\\\text{(since }\mathcal{A}\left(  k\right)  \text{ is true)}%
}}+\sum_{\substack{k\in\mathbf{K};\\\mathcal{A}\left(  k\right)  \text{ is
false}}}\underbrace{\left[  \mathcal{A}\left(  k\right)  \right]
}_{\substack{=0\\\text{(since }\mathcal{A}\left(  k\right)  \text{ is false)}%
}}\\
&  =\sum_{\substack{k\in\mathbf{K};\\\mathcal{A}\left(  k\right)  \text{ is
true}}}1+\underbrace{\sum_{\substack{k\in\mathbf{K};\\\mathcal{A}\left(
k\right)  \text{ is false}}}0}_{=0}=\sum_{\substack{k\in\mathbf{K}%
;\\\mathcal{A}\left(  k\right)  \text{ is true}}}1\\
&  =\left(  \text{the number of all }k\in\mathbf{K}\text{ for which
}\mathcal{A}\left(  k\right)  \text{ is true}\right)  \cdot1\\
&  =\left(  \text{the number of all }k\in\mathbf{K}\text{ for which
}\mathcal{A}\left(  k\right)  \text{ is true}\right) \\
&  =\left(  \text{the number of all }k\in\mathbf{K}\text{ satisfying
}\mathcal{A}\left(  k\right)  \right)  .
\end{align*}
This proves Proposition \ref{prop.iverson.count}.
\end{proof}

\begin{definition}
In the following, all matrices are understood to have integer entries.
\end{definition}

\begin{definition}
\label{def.matrix.ij}Let $n\in\mathbb{N}$ and $m\in\mathbb{N}$.

\textbf{(a)} If $S$ is an $n\times m$-matrix, and if $\left(  i,j\right)
\in\left\{  1,2,\ldots,n\right\}  \times\left\{  1,2,\ldots,m\right\}  $, then
we will denote the $\left(  i,j\right)  $-th entry of $S$ by $S_{i,j}$.

\textbf{(b)} If $a_{i,j}$ is an integer for every $i\in\left\{  1,2,\ldots
,n\right\}  $ and $j\in\left\{  1,2,\ldots,m\right\}  $, then we let $\left(
a_{i,j}\right)  _{1\leq i\leq n,\ 1\leq j\leq m}$ denote the $n\times
m$-matrix whose $\left(  i,j\right)  $-th entry is $a_{i,j}$ for all $\left(
i,j\right)  \in\left\{  1,2,\ldots,n\right\}  \times\left\{  1,2,\ldots
,m\right\}  $.

Thus, any $n\times m$-matrix $S$ satisfies $S=\left(  S_{i,j}\right)  _{1\leq
i\leq n,\ 1\leq j\leq m}$. Moreover, the definition of the product of two
matrices can be stated as follows: For any $n\in\mathbb{N}$, any
$m\in\mathbb{N}$, any $\ell\in\mathbb{N}$, any $n\times m$-matrix $\left(
a_{i,j}\right)  _{1\leq i\leq n,\ 1\leq j\leq m}$ and any $m\times\ell$-matrix
$\left(  b_{i,j}\right)  _{1\leq i\leq m,\ 1\leq j\leq\ell}$, we have%
\begin{equation}
\left(  a_{i,j}\right)  _{1\leq i\leq n,\ 1\leq j\leq m}\left(  b_{i,j}%
\right)  _{1\leq i\leq m,\ 1\leq j\leq\ell}=\left(  \sum_{k=1}^{m}%
a_{i,k}b_{k,j}\right)  _{1\leq i\leq n,\ 1\leq j\leq\ell}.
\label{eq.def.matrix.ij.prod}%
\end{equation}

\end{definition}

\begin{definition}
\label{def.circ}Let $p$ be a positive integer. Let $S_{p}$ be the $p\times
p$-matrix $\left(  \left[  j\equiv i+1\operatorname{mod}p\right]  \right)
_{1\leq i\leq p,\ 1\leq j\leq p}$. Let $I_{p}$ denote the $p\times p$ identity matrix.
\end{definition}

For example, $I_{3}=\left(
\begin{array}
[c]{ccc}%
1 & 0 & 0\\
0 & 1 & 0\\
0 & 0 & 1
\end{array}
\right)  $ and $S_{3}=\left(
\begin{array}
[c]{ccc}%
0 & 1 & 0\\
0 & 0 & 1\\
1 & 0 & 0
\end{array}
\right)  $.

Roughly speaking, the $p\times p$-matrix $S_{p}$ can be viewed as the result
of \textquotedblleft moving $I_{p}$ one column to the right\textquotedblright%
\ in a cyclic way (i.e., each column apart from the last one moves one unit to
the right, whereas the last one moves to the front). More formally, $S_{p}$ is
the permutation matrix of a cyclic permutation. From this point of view, the
following proposition should be rather obvious:

\begin{proposition}
\label{prop.circ.pow}Let $p$ be a positive integer. Let $k\in\mathbb{N}$.
Then,%
\[
\left(  S_{p}\right)  ^{k}=\left(  \left[  j\equiv i+k\operatorname{mod}%
p\right]  \right)  _{1\leq i\leq p,\ 1\leq j\leq p}.
\]

\end{proposition}

For the sake of completeness, let me give a formal proof of this proposition:

\begin{proof}
[Proof of Proposition \ref{prop.circ.pow}.]We shall prove Proposition
\ref{prop.circ.pow} by induction over $k$:

\textit{Induction base:} The definition of the identity matrix $I_{p}$ yields
$I_{p}=\left(  \left[  i=j\right]  \right)  _{1\leq i\leq p,\ 1\leq j\leq p}$.
But if $i$ and $j$ are two elements of $\left\{  1,2,\ldots,p\right\}  $, then
$\left[  j\equiv i+0\operatorname{mod}p\right]  =\left[  i=j\right]
$\ \ \ \ \footnote{\textit{Proof.} Let $i$ and $j$ be two elements of
$\left\{  1,2,\ldots,p\right\}  $. Then, $i\equiv j\operatorname{mod}p$ holds
if and only if $i=j$ (because no two distinct elements of $\left\{
1,2,\ldots,p\right\}  $ are congruent to each other modulo $p$). Thus, we have
$\left[  i\equiv j\operatorname{mod}p\right]  =\left[  i=j\right]  $. Now,%
\[
\left[  j\equiv\underbrace{i+0}_{=i}\operatorname{mod}p\right]  =\left[
\underbrace{j\equiv i\operatorname{mod}p}_{\substack{\text{this is equivalent
to}\\\left(  i\equiv j\operatorname{mod}p\right)  }}\right]  =\left[  i\equiv
j\operatorname{mod}p\right]  =\left[  i=j\right]  .
\]
Qed.}. Hence, $\left(  \underbrace{\left[  j\equiv i+0\operatorname{mod}%
p\right]  }_{=\left[  i=j\right]  }\right)  _{1\leq i\leq p,\ 1\leq j\leq
p}=\left(  \left[  i=j\right]  \right)  _{1\leq i\leq p,\ 1\leq j\leq p}$.
Comparing this with $\left(  S_{p}\right)  ^{0}=I_{p}=\left(  \left[
i=j\right]  \right)  _{1\leq i\leq p,\ 1\leq j\leq p}$, we obtain $\left(
S_{p}\right)  ^{0}=\left(  \left[  j\equiv i+0\operatorname{mod}p\right]
\right)  _{1\leq i\leq p,\ 1\leq j\leq p}$. In other words, Proposition
\ref{prop.circ.pow} holds for $k=0$. This completes the induction base.

\textit{Induction step:} Let $K\in\mathbb{N}$. Assume that Proposition
\ref{prop.circ.pow} holds for $k=K$. We now must prove that Proposition
\ref{prop.circ.pow} holds for $k=K+1$.

We have assumed that Proposition \ref{prop.circ.pow} holds for $k=K$. In other
words, we have%
\begin{equation}
\left(  S_{p}\right)  ^{K}=\left(  \left[  j\equiv i+K\operatorname{mod}%
p\right]  \right)  _{1\leq i\leq p,\ 1\leq j\leq p}.
\label{pf.prop.circ.pow.indhyp}%
\end{equation}


For every $i\in\left\{  1,2,\ldots,p\right\}  $ and $j\in\left\{
1,2,\ldots,p\right\}  $, we have%
\begin{align}
&  \left[  k\equiv i+K\operatorname{mod}p\right]  \left[  j\equiv
k+1\operatorname{mod}p\right]  \nonumber\\
&  =\left[  k\equiv i+K\operatorname{mod}p\right]  \left[  j\equiv i+\left(
K+1\right)  \operatorname{mod}p\right]  .\label{pf.prop.circ.pow.prod}%
\end{align}


\begin{vershort}
[\textit{Proof of (\ref{pf.prop.circ.pow.prod}):} Let $i\in\left\{
1,2,\ldots,p\right\}  $ and $j\in\left\{  1,2,\ldots,p\right\}  $. We must
prove the equality (\ref{pf.prop.circ.pow.prod}). We are in one of the
following two cases:

\textit{Case 1:} We have $k\equiv i+K\operatorname{mod}p$.

\textit{Case 2:} We don't have $k\equiv i+K\operatorname{mod}p$.

Let us first consider Case 1. In this case, we have $k\equiv
i+K\operatorname{mod}p$. Thus, $\underbrace{k}_{\equiv i+K\operatorname{mod}%
p}+1\equiv i+K+1=i+\left(  K+1\right)  \operatorname{mod}p$. Therefore, we
have $j\equiv k+1\operatorname{mod}p$ if and only if $j\equiv i+\left(
K+1\right)  \operatorname{mod}p$. Therefore, $\left[  j\equiv
k+1\operatorname{mod}p\right]  =\left[  j\equiv i+\left(  K+1\right)
\operatorname{mod}p\right]  $. Now,%
\begin{align*}
&  \left[  k\equiv i+K\operatorname{mod}p\right]  \underbrace{\left[  j\equiv
k+1\operatorname{mod}p\right]  }_{=\left[  j\equiv i+\left(  K+1\right)
\operatorname{mod}p\right]  }\\
&  =\left[  k\equiv i+K\operatorname{mod}p\right]  \left[  j\equiv i+\left(
K+1\right)  \operatorname{mod}p\right]  .
\end{align*}
Hence, (\ref{pf.prop.circ.pow.prod}) is proven in Case 1.

Let us now consider Case 2. In this case, we don't have $k\equiv
i+K\operatorname{mod}p$. Thus, $\left[  k\equiv i+K\operatorname{mod}p\right]
=0$. Since $\left[  k\equiv i+K\operatorname{mod}p\right]  $ appears as a
factor on both sides of (\ref{pf.prop.circ.pow.prod}), this shows that both
sides of (\ref{pf.prop.circ.pow.prod}) are $0$. Thus,
(\ref{pf.prop.circ.pow.prod}) is proven in Case 2.

We now have proven (\ref{pf.prop.circ.pow.prod}) in each of the two Cases 1
and 2. Thus, (\ref{pf.prop.circ.pow.prod}) always holds. Qed.]
\end{vershort}

\begin{verlong}
[\textit{Proof of (\ref{pf.prop.circ.pow.prod}):} Let $i\in\left\{
1,2,\ldots,p\right\}  $ and $j\in\left\{  1,2,\ldots,p\right\}  $. We must
prove the equality (\ref{pf.prop.circ.pow.prod}). We are in one of the
following two cases:

\textit{Case 1:} We have $k\equiv i+K\operatorname{mod}p$.

\textit{Case 2:} We don't have $k\equiv i+K\operatorname{mod}p$.

Let us first consider Case 1. In this case, we have $k\equiv
i+K\operatorname{mod}p$. Thus, $\underbrace{k}_{\equiv i+K\operatorname{mod}%
p}+1\equiv i+K+1=i+\left(  K+1\right)  \operatorname{mod}p$. Therefore, we
have $j\equiv k+1\operatorname{mod}p$ if and only if $j\equiv i+\left(
K+1\right)  \operatorname{mod}p$. Therefore, $\left[  j\equiv
k+1\operatorname{mod}p\right]  =\left[  j\equiv i+\left(  K+1\right)
\operatorname{mod}p\right]  $. Now,%
\begin{align*}
&  \left[  k\equiv i+K\operatorname{mod}p\right]  \underbrace{\left[  j\equiv
k+1\operatorname{mod}p\right]  }_{=\left[  j\equiv i+\left(  K+1\right)
\operatorname{mod}p\right]  }\\
&  =\left[  k\equiv i+K\operatorname{mod}p\right]  \left[  j\equiv i+\left(
K+1\right)  \operatorname{mod}p\right]  .
\end{align*}
Hence, (\ref{pf.prop.circ.pow.prod}) is proven in Case 1.

Let us now consider Case 2. In this case, we don't have $k\equiv
i+K\operatorname{mod}p$. Thus, $\left[  k\equiv i+K\operatorname{mod}p\right]
=0$. Comparing%
\[
\underbrace{\left[  k\equiv i+K\operatorname{mod}p\right]  }_{=0}\left[
j\equiv k+1\operatorname{mod}p\right]  =0
\]
with%
\[
\underbrace{\left[  k\equiv i+K\operatorname{mod}p\right]  }_{=0}\left[
j\equiv i+\left(  K+1\right)  \operatorname{mod}p\right]  =0,
\]
we obtain%
\begin{align*}
&  \left[  k\equiv i+K\operatorname{mod}p\right]  \left[  j\equiv
k+1\operatorname{mod}p\right]  \\
&  =\left[  k\equiv i+K\operatorname{mod}p\right]  \left[  j\equiv i+\left(
K+1\right)  \operatorname{mod}p\right]  .
\end{align*}
Thus, (\ref{pf.prop.circ.pow.prod}) is proven in Case 2.

We now have proven (\ref{pf.prop.circ.pow.prod}) in each of the two Cases 1
and 2. Thus, (\ref{pf.prop.circ.pow.prod}) always holds. Qed.]
\end{verlong}

For every $i\in\left\{  1,2,\ldots,p\right\}  $ and $j\in\left\{
1,2,\ldots,p\right\}  $, we have
\begin{align}
&  \sum_{k=1}^{p}\left[  k\equiv i+K\operatorname{mod}p\right]  \left[
j\equiv k+1\operatorname{mod}p\right]  \nonumber\\
&  =\left[  j\equiv i+\left(  K+1\right)  \operatorname{mod}p\right]
\label{pf.prop.circ.pow.sum}%
\end{align}
\footnote{\textit{Proof of (\ref{pf.prop.circ.pow.sum}):} Let $i\in\left\{
1,2,\ldots,p\right\}  $ and $j\in\left\{  1,2,\ldots,p\right\}  $.
\par
The following fact is well-known: The integers $1,2,\ldots,p$ cover each of
the remainder classes modulo $p$ exactly once. In other words, for every
integer $N$, there is exactly one $k\in\left\{  1,2,\ldots,p\right\}  $
satisfying $k\equiv N\operatorname{mod}p$. In other words, for each integer
$N$, we have%
\begin{equation}
\left(  \text{the number of all }k\in\left\{  1,2,\ldots,p\right\}  \text{
satisfying }k\equiv N\operatorname{mod}p\right)
=1.\label{pf.prop.circ.pow.sum.pf.1}%
\end{equation}
\par
But%
\begin{align*}
&  \underbrace{\sum_{k=1}^{p}}_{=\sum_{k\in\left\{  1,2,\ldots,p\right\}  }%
}\underbrace{\left[  k\equiv i+K\operatorname{mod}p\right]  \left[  j\equiv
k+1\operatorname{mod}p\right]  }_{\substack{=\left[  k\equiv
i+K\operatorname{mod}p\right]  \left[  j\equiv i+\left(  K+1\right)
\operatorname{mod}p\right]  \\\text{(by (\ref{pf.prop.circ.pow.prod}))}}}\\
&  =\sum_{k\in\left\{  1,2,\ldots,p\right\}  }\left[  k\equiv
i+K\operatorname{mod}p\right]  \left[  j\equiv i+\left(  K+1\right)
\operatorname{mod}p\right]  \\
&  =\left[  j\equiv i+\left(  K+1\right)  \operatorname{mod}p\right]
\cdot\underbrace{\sum_{k\in\left\{  1,2,\ldots,p\right\}  }\left[  k\equiv
i+K\operatorname{mod}p\right]  }_{\substack{=\left(  \text{the number of all
}k\in\left\{  1,2,\ldots,p\right\}  \text{ satisfying }k\equiv
i+K\operatorname{mod}p\right)  \\\text{(by Proposition
\ref{prop.iverson.count} (applied to }\mathbf{K}=\left\{  1,2,\ldots
,p\right\}  \\\text{and }\mathcal{A}\left(  k\right)  =\left(
\text{\textquotedblleft}k\equiv i+K\operatorname{mod}p\text{\textquotedblright%
}\right)  \text{))}}}\\
&  =\left[  j\equiv i+\left(  K+1\right)  \operatorname{mod}p\right]
\cdot\underbrace{\left(  \text{the number of all }k\in\left\{  1,2,\ldots
,p\right\}  \text{ satisfying }k\equiv i+K\operatorname{mod}p\right)
}_{\substack{=1\\\text{(by (\ref{pf.prop.circ.pow.sum.pf.1}) (applied to
}N=i+K\text{))}}}\\
&  =\left[  j\equiv i+\left(  K+1\right)  \operatorname{mod}p\right]  .
\end{align*}
This proves (\ref{pf.prop.circ.pow.sum}).}.

Now,%
\begin{align*}
\left(  S_{p}\right)  ^{K+1} &  =\underbrace{\left(  S_{p}\right)  ^{K}%
}_{=\left(  \left[  j\equiv i+K\operatorname{mod}p\right]  \right)  _{1\leq
i\leq p,\ 1\leq j\leq p}}\underbrace{S_{p}}_{=\left(  \left[  j\equiv
i+1\operatorname{mod}p\right]  \right)  _{1\leq i\leq p,\ 1\leq j\leq p}}\\
&  =\left(  \left[  j\equiv i+K\operatorname{mod}p\right]  \right)  _{1\leq
i\leq p,\ 1\leq j\leq p}\left(  \left[  j\equiv i+1\operatorname{mod}p\right]
\right)  _{1\leq i\leq p,\ 1\leq j\leq p}\\
&  =\left(  \underbrace{\sum_{k=1}^{p}\left[  k\equiv i+K\operatorname{mod}%
p\right]  \left[  j\equiv k+1\operatorname{mod}p\right]  }_{\substack{=\left[
j\equiv i+\left(  K+1\right)  \operatorname{mod}p\right]  \\\text{(by
(\ref{pf.prop.circ.pow.sum}))}}}\right)  _{1\leq i\leq p,\ 1\leq j\leq p}\\
&  \ \ \ \ \ \ \ \ \ \ \left(
\begin{array}
[c]{c}%
\text{by (\ref{eq.def.matrix.ij.prod}), applied to }n=p\text{, }m=p\text{,
}\ell=p\text{,}\\
a_{i,j}=\left[  j\equiv i+K\operatorname{mod}p\right]  \text{ and }%
b_{i,j}=\left[  j\equiv i+1\operatorname{mod}p\right]
\end{array}
\right)  \\
&  =\left(  \left[  j\equiv i+\left(  K+1\right)  \operatorname{mod}p\right]
\right)  _{1\leq i\leq p,\ 1\leq j\leq p}.
\end{align*}
In other words, Proposition \ref{prop.circ.pow} holds for $k=K+1$. This
completes the induction step.

Thus, Proposition \ref{prop.circ.pow} is proven by induction.
\end{proof}

\begin{corollary}
\label{cor.circ.pow.entry}Let $p$ be a positive integer. Let $k\in\mathbb{N}$.
Let $u\in\left\{  1,2,\ldots,p\right\}  $ and $v\in\left\{  1,2,\ldots
,p\right\}  $. Then,
\[
\left(  \left(  S_{p}\right)  ^{k}\right)  _{u,v}=\left[  v\equiv
u+k\operatorname{mod}p\right]  .
\]

\end{corollary}

\begin{proof}
[Proof of Corollary \ref{cor.circ.pow.entry}.]Proposition \ref{prop.circ.pow}
yields $\left(  S_{p}\right)  ^{k}=\left(  \left[  j\equiv
i+k\operatorname{mod}p\right]  \right)  _{1\leq i\leq p,\ 1\leq j\leq p}$.
Hence, $\left(  \left(  S_{p}\right)  ^{k}\right)  _{u,v}=\left(  \left(
\left[  j\equiv i+k\operatorname{mod}p\right]  \right)  _{1\leq i\leq
p,\ 1\leq j\leq p}\right)  _{u,v}=\left[  v\equiv u+k\operatorname{mod}%
p\right]  $. This proves Corollary \ref{cor.circ.pow.entry}.
\end{proof}

\begin{corollary}
\label{cor.circ.pow.p=0}Let $p$ be a positive integer. Then, $\left(
S_{p}\right)  ^{p}=I_{p}$.
\end{corollary}

\begin{proof}
[Proof of Corollary \ref{cor.circ.pow.p=0}.]For every $i\in\left\{
1,2,\ldots,p\right\}  $ and $j\in\left\{  1,2,\ldots,p\right\}  $, we have%
\begin{equation}
\left[  \underbrace{j\equiv i+p\operatorname{mod}p}_{\substack{\text{this is
equivalent to}\\j\equiv i+0\operatorname{mod}p\\\text{(since }i+p\equiv
i=i+0\operatorname{mod}p\text{)}}}\right]  =\left[  j\equiv
i+0\operatorname{mod}p\right]  . \label{pf.cor.circ.pow.p=0.1}%
\end{equation}
Proposition \ref{prop.circ.pow} (applied to $k=0$) yields%
\begin{equation}
\left(  S_{p}\right)  ^{0}=\left(  \left[  j\equiv i+0\operatorname{mod}%
p\right]  \right)  _{1\leq i\leq p,\ 1\leq j\leq p}.
\label{pf.cor.circ.pow.p=0.2}%
\end{equation}
Proposition \ref{prop.circ.pow} (applied to $k=p$) yields%
\begin{align*}
\left(  S_{p}\right)  ^{p}  &  =\left(  \underbrace{\left[  j\equiv
i+p\operatorname{mod}p\right]  }_{\substack{=\left[  j\equiv
i+0\operatorname{mod}p\right]  \\\text{(by (\ref{pf.cor.circ.pow.p=0.1}))}%
}}\right)  _{1\leq i\leq p,\ 1\leq j\leq p}=\left(  \left[  j\equiv
i+0\operatorname{mod}p\right]  \right)  _{1\leq i\leq p,\ 1\leq j\leq p}\\
&  =\left(  S_{p}\right)  ^{0}\ \ \ \ \ \ \ \ \ \ \left(  \text{by
(\ref{pf.cor.circ.pow.p=0.2})}\right) \\
&  =I_{p}.
\end{align*}
This proves Corollary \ref{cor.circ.pow.p=0}.
\end{proof}

\begin{corollary}
\label{cor.circ.pow.binom}Let $p$ be a positive integer. Let $j\in\left\{
0,1,\ldots,p-1\right\}  $ and $n\in\mathbb{N}$. Then,%
\[
\sum\limits_{\substack{m\in\mathbb{N};\\m\equiv j\operatorname{mod}p}}\left(
-1\right)  ^{m}\dbinom{n}{m}=\left(  \left(  I_{p}-S_{p}\right)  ^{n}\right)
_{1,j+1}.
\]

\end{corollary}

To prove Corollary \ref{cor.circ.pow.binom}, we shall need the binomial
formula, in the following form:

\begin{proposition}
\label{prop.binom}Let $x\in\mathbb{N}$. Then,%
\[
\left(  1+X\right)  ^{x}=\sum_{k\in\mathbb{N}}\dbinom{x}{k}X^{k}%
\]
(an equality between polynomials in $\mathbb{Z}\left[  X\right]  $). (The sum
$\sum_{k\in\mathbb{N}}\dbinom{x}{k}X^{k}$ is an infinite sum, but only
finitely many of its addends are nonzero, so it is well-defined.)
\end{proposition}

\begin{proof}
[Proof of Corollary \ref{cor.circ.pow.binom}.]We have $1\in\left\{
1,2,\ldots,p\right\}  $ (since $p$ is positive) and $j+1\in\left\{
1,2,\ldots,p\right\}  $ (since $j\in\left\{  0,1,\ldots,p-1\right\}  $).
Hence, every $k\in\mathbb{N}$ satisfies%
\begin{align}
\left(  \left(  S_{p}\right)  ^{k}\right)  _{1,j+1}  &  =\left[
j+1\equiv\underbrace{1+k}_{=k+1}\operatorname{mod}p\right] \nonumber\\
&  \ \ \ \ \ \ \ \ \ \ \left(  \text{by Corollary \ref{cor.circ.pow.entry}
(applied to }u=1\text{ and }v=j+1\text{)}\right) \nonumber\\
&  =\left[  \underbrace{j+1\equiv k+1\operatorname{mod}p}%
_{\substack{\text{this is equivalent to}\\j\equiv k\operatorname{mod}%
p}}\right]  =\left[  \underbrace{j\equiv k\operatorname{mod}p}%
_{\substack{\text{this is equivalent to}\\k\equiv j\operatorname{mod}%
p}}\right] \nonumber\\
&  =\left[  k\equiv j\operatorname{mod}p\right]  .
\label{pf.cor.circ.pow.binom.1}%
\end{align}


\begin{vershort}
Proposition \ref{prop.binom} (applied to $x=n$) yields $\left(  1+X\right)
^{n}=\sum_{k\in\mathbb{N}}\dbinom{n}{k}X^{k}$ (an equality between polynomials
in $\mathbb{Z}\left[  X\right]  $). If we substitute $-S_{p}$ for $X$ in this
equality, then we obtain $\left(  I_{p}+\left(  -S_{p}\right)  \right)
^{n}=\sum_{k\in\mathbb{N}}\dbinom{n}{k}\left(  -S_{p}\right)  ^{k}$ (since the
unity of the ring of $p\times p$-matrices is $I_{p}$). Thus,%
\begin{align*}
\left(  \underbrace{I_{p}-S_{p}}_{=I_{p}+\left(  -S_{p}\right)  }\right)
^{n}  &  =\left(  I_{p}+\left(  -S_{p}\right)  \right)  ^{n}=\sum
_{k\in\mathbb{N}}\dbinom{n}{k}\underbrace{\left(  -S_{p}\right)  ^{k}%
}_{=\left(  -1\right)  ^{k}\left(  S_{p}\right)  ^{k}}\\
&  =\sum_{k\in\mathbb{N}}\dbinom{n}{k}\left(  -1\right)  ^{k}\left(
S_{p}\right)  ^{k}=\sum_{k\in\mathbb{N}}\left(  -1\right)  ^{k}\dbinom{n}%
{k}\left(  S_{p}\right)  ^{k}.
\end{align*}
Thus,%
\begin{align*}
&  \left(  \underbrace{\left(  I_{p}-S_{p}\right)  ^{n}}_{=\sum_{k\in
\mathbb{N}}\left(  -1\right)  ^{k}\dbinom{n}{k}\left(  S_{p}\right)  ^{k}%
}\right)  _{1,j+1}\\
&  =\left(  \sum_{k\in\mathbb{N}}\left(  -1\right)  ^{k}\dbinom{n}{k}\left(
S_{p}\right)  ^{k}\right)  _{1,j+1}=\sum_{k\in\mathbb{N}}\left(  -1\right)
^{k}\dbinom{n}{k}\underbrace{\left(  \left(  S_{p}\right)  ^{k}\right)
_{1,j+1}}_{\substack{=\left[  k\equiv j\operatorname{mod}p\right]  \\\text{(by
(\ref{pf.cor.circ.pow.binom.1}))}}}\\
&  =\sum_{k\in\mathbb{N}}\left(  -1\right)  ^{k}\dbinom{n}{k}\left[  k\equiv
j\operatorname{mod}p\right] \\
&  =\sum_{\substack{k\in\mathbb{N};\\k\equiv j\operatorname{mod}p}}\left(
-1\right)  ^{k}\dbinom{n}{k}\underbrace{\left[  k\equiv j\operatorname{mod}%
p\right]  }_{\substack{=1\\\text{(since }k\equiv j\operatorname{mod}p\text{)}%
}}+\sum_{\substack{k\in\mathbb{N};\\k\not \equiv j\operatorname{mod}p}}\left(
-1\right)  ^{k}\dbinom{n}{k}\underbrace{\left[  k\equiv j\operatorname{mod}%
p\right]  }_{\substack{=0\\\text{(since }k\not \equiv j\operatorname{mod}%
p\text{)}}}\\
&  =\sum_{\substack{k\in\mathbb{N};\\k\equiv j\operatorname{mod}p}}\left(
-1\right)  ^{k}\dbinom{n}{k}=\sum\limits_{\substack{m\in\mathbb{N};\\m\equiv
j\operatorname{mod}p}}\left(  -1\right)  ^{m}\dbinom{n}{m}%
\end{align*}
(here, we have renamed the summation index $k$ as $m$). This proves Corollary
\ref{cor.circ.pow.binom}.
\end{vershort}

\begin{verlong}
Proposition \ref{prop.binom} (applied to $x=n$) yields $\left(  1+X\right)
^{n}=\sum_{k\in\mathbb{N}}\dbinom{n}{k}X^{k}$ (an equality between polynomials
in $\mathbb{Z}\left[  X\right]  $). If we substitute $-S_{p}$ for $X$ in this
equality, then we obtain $\left(  I_{p}+\left(  -S_{p}\right)  \right)
^{n}=\sum_{k\in\mathbb{N}}\dbinom{n}{k}\left(  -S_{p}\right)  ^{k}$ (since the
unity of the ring of $p\times p$-matrices is $I_{p}$). Thus,%
\begin{align*}
\left(  \underbrace{I_{p}-S_{p}}_{=I_{p}+\left(  -S_{p}\right)  }\right)
^{n}  &  =\left(  I_{p}+\left(  -S_{p}\right)  \right)  ^{n}=\sum
_{k\in\mathbb{N}}\dbinom{n}{k}\underbrace{\left(  -S_{p}\right)  ^{k}%
}_{=\left(  -1\right)  ^{k}\left(  S_{p}\right)  ^{k}}\\
&  =\sum_{k\in\mathbb{N}}\underbrace{\dbinom{n}{k}\left(  -1\right)  ^{k}%
}_{=\left(  -1\right)  ^{k}\dbinom{n}{k}}\left(  S_{p}\right)  ^{k}=\sum
_{k\in\mathbb{N}}\left(  -1\right)  ^{k}\dbinom{n}{k}\left(  S_{p}\right)
^{k}.
\end{align*}
Thus,%
\begin{align*}
&  \left(  \underbrace{\left(  I_{p}-S_{p}\right)  ^{n}}_{=\sum_{k\in
\mathbb{N}}\left(  -1\right)  ^{k}\dbinom{n}{k}\left(  S_{p}\right)  ^{k}%
}\right)  _{1,j+1}\\
&  =\left(  \sum_{k\in\mathbb{N}}\left(  -1\right)  ^{k}\dbinom{n}{k}\left(
S_{p}\right)  ^{k}\right)  _{1,j+1}=\sum_{k\in\mathbb{N}}\left(  -1\right)
^{k}\dbinom{n}{k}\underbrace{\left(  \left(  S_{p}\right)  ^{k}\right)
_{1,j+1}}_{\substack{=\left[  k\equiv j\operatorname{mod}p\right]  \\\text{(by
(\ref{pf.cor.circ.pow.binom.1}))}}}\\
&  =\sum_{k\in\mathbb{N}}\left(  -1\right)  ^{k}\dbinom{n}{k}\left[  k\equiv
j\operatorname{mod}p\right] \\
&  =\underbrace{\sum_{\substack{k\in\mathbb{N};\\k\equiv j\operatorname{mod}%
p\text{ is true}}}}_{=\sum_{\substack{k\in\mathbb{N};\\k\equiv
j\operatorname{mod}p}}}\left(  -1\right)  ^{k}\dbinom{n}{k}\underbrace{\left[
k\equiv j\operatorname{mod}p\right]  }_{\substack{=1\\\text{(since }k\equiv
j\operatorname{mod}p\text{ is true)}}}\\
&  \ \ \ \ \ \ \ \ \ \ +\sum_{\substack{k\in\mathbb{N};\\k\equiv
j\operatorname{mod}p\text{ is false}}}\left(  -1\right)  ^{k}\dbinom{n}%
{k}\underbrace{\left[  k\equiv j\operatorname{mod}p\right]  }%
_{\substack{=0\\\text{(since }k\equiv j\operatorname{mod}p\text{ is false)}%
}}\\
&  =\sum_{\substack{k\in\mathbb{N};\\k\equiv j\operatorname{mod}p}}\left(
-1\right)  ^{k}\dbinom{n}{k}+\underbrace{\sum_{\substack{k\in\mathbb{N}%
;\\k\equiv j\operatorname{mod}p\text{ is false}}}\left(  -1\right)
^{k}\dbinom{n}{k}0}_{=0}\\
&  =\sum_{\substack{k\in\mathbb{N};\\k\equiv j\operatorname{mod}p}}\left(
-1\right)  ^{k}\dbinom{n}{k}=\sum\limits_{\substack{m\in\mathbb{N};\\m\equiv
j\operatorname{mod}p}}\left(  -1\right)  ^{m}\dbinom{n}{m}%
\end{align*}
(here, we have renamed the summation index $k$ as $m$). This proves Corollary
\ref{cor.circ.pow.binom}.
\end{verlong}
\end{proof}

\section{The polynomial $U$}

On the other hand, let us recall a standard property of primes:

\begin{proposition}
\label{prop.binom.p-1}Let $p$ be a prime. Let $k\in\left\{  0,1,\ldots
,p-1\right\}  $. Then,%
\[
\dbinom{p-1}{k}\equiv\left(  -1\right)  ^{k}\operatorname{mod}p.
\]

\end{proposition}

Proposition \ref{prop.binom.p-1} is well-known; we give its proof in the
appendix (Section \ref{sect.app1}) for the sake of completeness.

\begin{corollary}
\label{cor.binom.p-1.ak}Let $p$ be a prime. For every $k\in\left\{
0,1,\ldots,p-1\right\}  $, we have $\dfrac{\left(  -1\right)  ^{k}\dbinom
{p-1}{k}-1}{p}\in\mathbb{Z}$.
\end{corollary}

\begin{proof}
[Proof of Corollary \ref{cor.binom.p-1.ak}.]Let $k\in\left\{  0,1,\ldots
,p-1\right\}  $. Then, Proposition \ref{prop.binom.p-1} shows that
$\dbinom{p-1}{k}\equiv\left(  -1\right)  ^{k}\operatorname{mod}p$. Hence,
\[
\left(  -1\right)  ^{k}\underbrace{\dbinom{p-1}{k}}_{\equiv\left(  -1\right)
^{k}\operatorname{mod}p}\equiv\left(  -1\right)  ^{k}\left(  -1\right)
^{k}=\left(  \left(  -1\right)  ^{k}\right)  ^{2}=1\operatorname{mod}p
\]
(since $\left(  -1\right)  ^{k}\in\left\{  1,-1\right\}  $). In other words,
$p\mid\left(  -1\right)  ^{k}\dbinom{p-1}{k}-1$. In other words,
$\dfrac{\left(  -1\right)  ^{k}\dbinom{p-1}{k}-1}{p}\in\mathbb{Z}$. This
proves Corollary \ref{cor.binom.p-1.ak}.
\end{proof}

We recall that $\mathbb{Z}\left[  X\right]  $ denotes the ring of all
polynomials in one indeterminate $X$ with integer coefficients.

\begin{corollary}
\label{cor.poly.prime}Let $p$ be a prime. Then, there exists a polynomial
$U\in\mathbb{Z}\left[  X\right]  $ such that $\left(  1-X\right)  ^{p}=\left(
1-X^{p}\right)  +p\left(  1-X\right)  U$.
\end{corollary}

\begin{proof}
[Proof of Corollary \ref{cor.poly.prime}.]For every $k\in\left\{
0,1,\ldots,p-1\right\}  $, we have $\dfrac{\left(  -1\right)  ^{k}\dbinom
{p-1}{k}-1}{p}\in\mathbb{Z}$ (by Corollary \ref{cor.binom.p-1.ak}). Thus, for
every $k\in\left\{  0,1,\ldots,p-1\right\}  $, we can define an element
$a_{k}\in\mathbb{Z}$ by $a_{k}=\dfrac{\left(  -1\right)  ^{k}\dbinom{p-1}%
{k}-1}{p}$. Consider these elements $a_{k}$. Every $k\in\left\{
0,1,\ldots,p-1\right\}  $ satisfies%
\begin{equation}
pa_{k}=\left(  -1\right)  ^{k}\dbinom{p-1}{k}-1 \label{pf.cor.poly.prime.pak}%
\end{equation}
(since $a_{k}=\dfrac{\left(  -1\right)  ^{k}\dbinom{p-1}{k}-1}{p}$).

Define a polynomial $A\in\mathbb{Z}\left[  X\right]  $ by $A=\sum_{k=0}%
^{p-1}a_{k}X^{k}$.

The binomial formula says the following: If $a$ and $b$ are any two elements
of a commutative ring $\mathfrak{A}$, and if $g\in\mathbb{N}$, then%
\[
\left(  a+b\right)  ^{g}=\sum_{k=0}^{g}\dbinom{g}{k}a^{k}b^{g-k}.
\]
This formula (applied to $\mathfrak{A}=\mathbb{Z}\left[  X\right]  $, $a=-X$,
$b=1$ and $g=p-1$) yields%
\begin{align*}
\left(  \left(  -X\right)  +1\right)  ^{p-1}  &  =\sum_{k=0}^{p-1}\dbinom
{p-1}{k}\underbrace{\left(  -X\right)  ^{k}}_{=\left(  -1\right)  ^{k}X^{k}%
}\underbrace{1^{p-1-k}}_{=1}\\
&  =\sum_{k=0}^{p-1}\underbrace{\dbinom{p-1}{k}\left(  -1\right)  ^{k}%
}_{=\left(  -1\right)  ^{k}\dbinom{p-1}{k}}X^{k}=\sum_{k=0}^{p-1}\left(
-1\right)  ^{k}\dbinom{p-1}{k}X^{k}.
\end{align*}
Since $\left(  -X\right)  +1=1-X$, this rewrites as follows:%
\begin{equation}
\left(  1-X\right)  ^{p-1}=\sum_{k=0}^{p-1}\left(  -1\right)  ^{k}\dbinom
{p-1}{k}X^{k}. \label{pf.cor.poly.prime.3}%
\end{equation}


On the other hand, a well-known identity states the following: If $a$ and $b$
are any two elements of a commutative ring $\mathfrak{A}$, and if
$g\in\mathbb{N}$, then%
\[
a^{g}-b^{g}=\left(  a-b\right)  \sum_{k=0}^{g-1}a^{k}b^{g-1-k}.
\]
This formula (applied to $\mathfrak{A}=\mathbb{Z}\left[  X\right]  $, $a=1$,
$b=X$ and $g=p$) yields%
\begin{align}
1^{p}-X^{p}  &  =\left(  1-X\right)  \sum_{k=0}^{p-1}\underbrace{1^{k}}%
_{=1}X^{p-1-k}=\left(  1-X\right)  \sum_{k=0}^{p-1}X^{p-1-k}\nonumber\\
&  =\left(  1-X\right)  \sum_{k=0}^{p-1}X^{k} \label{pf.cor.poly.prime.2}%
\end{align}
(here, we have substituted $k$ for $p-1-k$ in the sum).

Now,%
\begin{align*}
&  \underbrace{\left(  1-X\right)  ^{p}}_{=\left(  1-X\right)  \left(
1-X\right)  ^{p-1}}-\left(  \underbrace{1}_{=1^{p}}-X^{p}\right) \\
&  =\left(  1-X\right)  \left(  1-X\right)  ^{p-1}-\underbrace{\left(
1^{p}-X^{p}\right)  }_{\substack{=\left(  1-X\right)  \sum_{k=0}^{p-1}%
X^{k}\\\text{(by (\ref{pf.cor.poly.prime.2}))}}}\\
&  =\left(  1-X\right)  \left(  1-X\right)  ^{p-1}-\left(  1-X\right)
\sum_{k=0}^{p-1}X^{k}=\left(  1-X\right)  \left(  \left(  1-X\right)
^{p-1}-\sum_{k=0}^{p-1}X^{k}\right)  .
\end{align*}
Since%
\begin{align*}
&  \underbrace{\left(  1-X\right)  ^{p-1}}_{\substack{=\sum_{k=0}^{p-1}\left(
-1\right)  ^{k}\dbinom{p-1}{k}X^{k}\\\text{(by (\ref{pf.cor.poly.prime.3}))}%
}}-\sum_{k=0}^{p-1}X^{k}\\
&  =\sum_{k=0}^{p-1}\left(  -1\right)  ^{k}\dbinom{p-1}{k}X^{k}-\sum
_{k=0}^{p-1}X^{k}=\sum_{k=0}^{p-1}\underbrace{\left(  \left(  -1\right)
^{k}\dbinom{p-1}{k}-1\right)  }_{\substack{=pa_{k}\\\text{(by
(\ref{pf.cor.poly.prime.pak}))}}}X^{k}\\
&  =\sum_{k=0}^{p-1}pa_{k}X^{k}=p\underbrace{\sum_{k=0}^{p-1}a_{k}X^{k}%
}_{\substack{=A\\\text{(since }A=\sum_{k=0}^{p-1}a_{k}X^{k}\text{)}}}=pA,
\end{align*}
this becomes%
\begin{align*}
\left(  1-X\right)  ^{p}-\left(  1-X\right)  ^{p}  &  =\left(  1-X\right)
\underbrace{\left(  \left(  1-X\right)  ^{p-1}-\sum_{k=0}^{p-1}X^{k}\right)
}_{=pA}\\
&  =\left(  1-X\right)  pA=p\left(  1-X\right)  A.
\end{align*}
In other words, $\left(  1-X\right)  ^{p}=\left(  1-X^{p}\right)  +p\left(
1-X\right)  A$. Hence, there exists a polynomial $U\in\mathbb{Z}\left[
X\right]  $ such that $\left(  1-X\right)  ^{p}=\left(  1-X^{p}\right)
+p\left(  1-X\right)  U$ (namely, $U=A$). This proves Corollary
\ref{cor.poly.prime}.
\end{proof}

\section{Back to the matrix}

We now shall use the polynomial $U$ from Corollary \ref{cor.poly.prime} to
factor out powers of $p$ from powers of $I_{p}-S_{p}$ when $p$ is a prime.

\begin{proposition}
\label{prop.matrix-poly.1}Let $p$ be a prime. Corollary \ref{cor.poly.prime}
shows that there exists a polynomial $U\in\mathbb{Z}\left[  X\right]  $ such
that $\left(  1-X\right)  ^{p}=\left(  1-X^{p}\right)  +p\left(  1-X\right)
U$. Consider this $U$.

Let $U_{p}=U\left(  S_{p}\right)  $. (This is the $p\times p$-matrix obtained
by substituting the matrix $S_{p}$ for $X$ in the polynomial $U$.)

\textbf{(a)} We have $\left(  I_{p}-S_{p}\right)  U_{p}=U_{p}\left(
I_{p}-S_{p}\right)  $.

\textbf{(b)} We have $\left(  I_{p}-S_{p}\right)  ^{p}=p\left(  I_{p}%
-S_{p}\right)  U_{p}$.

\textbf{(c)} For every $q\in\mathbb{N}$, we have%
\[
\left(  I_{p}-S_{p}\right)  ^{q\left(  p-1\right)  +1}=p^{q}\left(
I_{p}-S_{p}\right)  \left(  U_{p}\right)  ^{q}.
\]

\end{proposition}

We shall now prove this proposition. Our proof will use some very basic
abstract algebra (namely, the notion of a $\mathbb{Z}$-subalgebra generated by
some elements, and the fact that any $\mathbb{Z}$-algebra generated by a
single element is commutative). We shall show a way to avoid this proposition
in the appendix (Section \ref{sect.app2}).

\begin{proof}
[Proof of Proposition \ref{prop.matrix-poly.1}.]Corollary
\ref{cor.circ.pow.p=0} yields $\left(  S_{p}\right)  ^{p}=I_{p}$. Hence,
$I_{p}-\left(  S_{p}\right)  ^{p}=0$.

\begin{vershort}
Let $\mathbb{Z}^{p\times p}$ denote the $\mathbb{Z}$-algebra of all $p\times
p$-matrices. Let $\mathfrak{A}$ denote the $\mathbb{Z}$-subalgebra of
$\mathbb{Z}^{p\times p}$ generated by $S_{p}$. Hence, $\mathfrak{A}$ is a
$\mathbb{Z}$-algebra generated by a single element (namely, by $S_{p}$).
Recall that every $\mathbb{Z}$-algebra generated by a single element is
commutative. Thus, the $\mathbb{Z}$-algebra $\mathfrak{A}$ is commutative
(since $\mathfrak{A}$ is a $\mathbb{Z}$-algebra generated by a single
element). The matrix $S_{p}$ belongs to this commutative $\mathbb{Z}$-algebra
$\mathfrak{A}$ (since $\mathfrak{A}$ is generated by $S_{p}$). Hence, we can
substitute $S_{p}$ for $X$ on both sides of the equality%
\[
\left(  1-X\right)  ^{p}=\left(  1-X^{p}\right)  +p\left(  1-X\right)  U.
\]
We thus obtain%
\[
\left(  I_{p}-S_{p}\right)  ^{p}=\underbrace{\left(  I_{p}-\left(
S_{p}\right)  ^{p}\right)  }_{=0}+p\left(  I_{p}-S_{p}\right)
\underbrace{U\left(  S_{p}\right)  }_{=U_{p}}=p\left(  I_{p}-S_{p}\right)
U_{p}.
\]
This proves Proposition \ref{prop.matrix-poly.1} \textbf{(b)}.
\end{vershort}

\begin{verlong}
Let $\mathbb{Z}^{p\times p}$ denote the $\mathbb{Z}$-algebra of all $p\times
p$-matrices. Let $\mathfrak{A}$ denote the $\mathbb{Z}$-subalgebra of
$\mathbb{Z}^{p\times p}$ generated by $S_{p}$. Hence, $\mathfrak{A}$ is a
$\mathbb{Z}$-algebra generated by a single element (namely, by $S_{p}$).
Recall that every $\mathbb{Z}$-algebra generated by a single element is
commutative. Applying this to the $\mathbb{Z}$-algebra $\mathfrak{A}$, we see
that the $\mathbb{Z}$-algebra $\mathfrak{A}$ is commutative (since
$\mathfrak{A}$ is a $\mathbb{Z}$-algebra generated by a single element). The
matrix $S_{p}$ belongs to this commutative $\mathbb{Z}$-algebra $\mathfrak{A}$
(since $\mathfrak{A}$ is the $\mathbb{Z}$-subalgebra of $\mathbb{Z}^{p\times
p}$ generated by $S_{p}$). Hence, we can substitute $S_{p}$ for $X$ on both
sides of the equality%
\[
\left(  1-X\right)  ^{p}=\left(  1-X^{p}\right)  +p\left(  1-X\right)  U.
\]
We thus obtain%
\begin{align*}
\left(  I_{p}-S_{p}\right)  ^{p}  &  =\underbrace{\left(  I_{p}-\left(
S_{p}\right)  ^{p}\right)  }_{=0}+p\left(  I_{p}-S_{p}\right)  U\left(
S_{p}\right) \\
&  =p\left(  I_{p}-S_{p}\right)  \underbrace{U\left(  S_{p}\right)  }_{=U_{p}%
}=p\left(  I_{p}-S_{p}\right)  U_{p}.
\end{align*}
This proves Proposition \ref{prop.matrix-poly.1} \textbf{(b)}.
\end{verlong}

[Notice that the elements of $\mathfrak{A}$ are known as the \textit{circulant
matrices} of size $p$.]

\begin{vershort}
\textbf{(a)} Proposition \ref{prop.matrix-poly.1} \textbf{(a)} follows easily
from the commutativity of $\mathfrak{A}$. We leave the details to the reader,
since we will not actually use Proposition \ref{prop.matrix-poly.1}
\textbf{(a)}.
\end{vershort}

\begin{verlong}
\textbf{(a)} We have $S_{p}\in\mathfrak{A}$ (since we have shown that the
matrix $S_{p}$ belongs to this commutative $\mathbb{Z}$-algebra $\mathfrak{A}%
$). Therefore, $U\left(  S_{p}\right)  \in\mathfrak{A}$ (since $U$ is a
polynomial). Thus, $U_{p}=U\left(  S_{p}\right)  \in\mathfrak{A}$. Also,
$I_{p}\in\mathfrak{A}$ (since $\mathfrak{A}$ is a $\mathbb{Z}$-subalgebra of
$\mathbb{Z}^{p\times p}$), so that $I_{p}-S_{p}\in\mathfrak{A}$ (since
$I_{p}\in\mathfrak{A}$ and $S_{p}\in\mathfrak{A}$).

Now, $I_{p}-S_{p}$ and $U_{p}$ are two elements of $\mathfrak{A}$. Since the
$\mathbb{Z}$-algebra $\mathfrak{A}$ is commutative, this shows that the
elements $I_{p}-S_{p}$ and $U_{p}$ commute. In other words, $\left(
I_{p}-S_{p}\right)  U_{p}=U_{p}\left(  I_{p}-S_{p}\right)  $. This proves
Proposition \ref{prop.matrix-poly.1} \textbf{(a)}.
\end{verlong}

\textbf{(c)} We shall prove Proposition \ref{prop.matrix-poly.1} \textbf{(c)}
by induction over $q$:

\begin{vershort}
\textit{Induction base:} We have $\left(  I_{p}-S_{p}\right)  ^{0\left(
p-1\right)  +1}=p^{0}\left(  I_{p}-S_{p}\right)  \left(  U_{p}\right)  ^{0}$
(in fact, both sides of this equality equal $I_{p}-S_{p}$). In other words,
Proposition \ref{prop.matrix-poly.1} \textbf{(c)} holds for $q=0$. This
completes the induction base.
\end{vershort}

\begin{verlong}
\textit{Induction base:} We have $\underbrace{0\left(  p-1\right)  }_{=0}+1=1$
and thus $\left(  I_{p}-S_{p}\right)  ^{0\left(  p-1\right)  +1}=\left(
I_{p}-S_{p}\right)  ^{1}=I_{p}-S_{p}$. Comparing this with $\underbrace{p^{0}%
}_{=1}\left(  I_{p}-S_{p}\right)  \underbrace{\left(  U_{p}\right)  ^{0}%
}_{=I_{p}}=I_{p}-S_{p}$, we obtain%
\[
\left(  I_{p}-S_{p}\right)  ^{0\left(  p-1\right)  +1}=p^{0}\left(
I_{p}-S_{p}\right)  \left(  U_{p}\right)  ^{0}.
\]
In other words, Proposition \ref{prop.matrix-poly.1} \textbf{(c)} holds for
$q=0$. This completes the induction base.
\end{verlong}

\textit{Induction step:} Let $Q\in\mathbb{N}$. Assume that Proposition
\ref{prop.matrix-poly.1} \textbf{(c)} holds for $q=Q$. We must now prove that
Proposition \ref{prop.matrix-poly.1} \textbf{(c)} holds for $q=Q+1$.

We have assumed that Proposition \ref{prop.matrix-poly.1} \textbf{(c)} holds
for $q=Q$. In other words, we have
\begin{equation}
\left(  I_{p}-S_{p}\right)  ^{Q\left(  p-1\right)  +1}=p^{Q}\left(
I_{p}-S_{p}\right)  \left(  U_{p}\right)  ^{Q}.
\label{pf.prop.matrix-poly.1.c.indhyp}%
\end{equation}


Now,
\[
\underbrace{\left(  Q+1\right)  \left(  p-1\right)  }_{=Q\left(  p-1\right)
+\left(  p-1\right)  }+1=Q\left(  p-1\right)  +\underbrace{\left(  p-1\right)
+1}_{=p}=Q\left(  p-1\right)  +p,
\]
so that%
\begin{align*}
&  \left(  I_{p}-S_{p}\right)  ^{\left(  Q+1\right)  \left(  p-1\right)  +1}\\
&  =\left(  I_{p}-S_{p}\right)  ^{Q\left(  p-1\right)  +p}=\left(  I_{p}%
-S_{p}\right)  ^{Q\left(  p-1\right)  }\underbrace{\left(  I_{p}-S_{p}\right)
^{p}}_{\substack{=p\left(  I_{p}-S_{p}\right)  U_{p}\\\text{(by Proposition
\ref{prop.matrix-poly.1} \textbf{(b)})}}}\\
&  =\left(  I_{p}-S_{p}\right)  ^{Q\left(  p-1\right)  }p\left(  I_{p}%
-S_{p}\right)  U_{p}=p\underbrace{\left(  I_{p}-S_{p}\right)  ^{Q\left(
p-1\right)  }\left(  I_{p}-S_{p}\right)  }_{\substack{=\left(  I_{p}%
-S_{p}\right)  ^{Q\left(  p-1\right)  +1}\\=p^{Q}\left(  I_{p}-S_{p}\right)
\left(  U_{p}\right)  ^{Q}\\\text{(by (\ref{pf.prop.matrix-poly.1.c.indhyp}%
))}}}U_{p}\\
&  =\underbrace{pp^{Q}}_{=p^{Q+1}}\left(  I_{p}-S_{p}\right)
\underbrace{\left(  U_{p}\right)  ^{Q}U_{p}}_{=\left(  U_{p}\right)  ^{Q+1}%
}=p^{Q+1}\left(  I_{p}-S_{p}\right)  \left(  U_{p}\right)  ^{Q+1}.
\end{align*}
In other words, Proposition \ref{prop.matrix-poly.1} \textbf{(c)} holds for
$q=Q+1$. This completes the induction step. Thus, Proposition
\ref{prop.matrix-poly.1} \textbf{(c)} is proven by induction.
\end{proof}

\begin{corollary}
\label{cor.matrix-poly.2}Let $p$ be a prime. Let $u\in\left\{  1,2,\ldots
,n\right\}  $ and $v\in\left\{  1,2,\ldots,n\right\}  $. Let $j$, $n$ and $q$
be elements of $\mathbb{N}$ such that $q\leq\dfrac{n-1}{p-1}$. Then,
$p^{q}\mid\left(  \left(  I_{p}-S_{p}\right)  ^{n}\right)  _{u,v}$.
\end{corollary}

\begin{proof}
[Proof of Corollary \ref{cor.matrix-poly.2}.]Define $U$ and $U_{p}$ as in
Proposition \ref{prop.matrix-poly.1}.

Since $p$ is prime, we have $p>1$, so that $p-1>0$. Hence, we can multiply the
inequality $q\leq\dfrac{n-1}{p-1}$ by $p-1$. We thus obtain $q\left(
p-1\right)  \leq n-1$, so that $n-1\geq q\left(  p-1\right)  $.

\begin{vershort}
Let $h=n-1-q\left(  p-1\right)  $. Thus, $h\in\mathbb{N}$ (since $n-1\geq
q\left(  p-1\right)  $).
\end{vershort}

\begin{verlong}
Let $h=n-1-q\left(  p-1\right)  $. Thus, $h=\underbrace{n-1}_{\geq q\left(
p-1\right)  }-q\left(  p-1\right)  \geq q\left(  p-1\right)  -q\left(
p-1\right)  =0$, so that $h\in\mathbb{N}$.
\end{verlong}

Now,%
\[
n=\underbrace{\left(  n-1-q\left(  p-1\right)  \right)  }_{=h}+\left(
q\left(  p-1\right)  +1\right)  =h+\left(  q\left(  p-1\right)  +1\right)  .
\]
Hence,%
\begin{align*}
\left(  I_{p}-S_{p}\right)  ^{n}  &  =\left(  I_{p}-S_{p}\right)  ^{h+\left(
q\left(  p-1\right)  +1\right)  }=\left(  I_{p}-S_{p}\right)  ^{h}%
\underbrace{\left(  I_{p}-S_{p}\right)  ^{q\left(  p-1\right)  +1}%
}_{\substack{=p^{q}\left(  I_{p}-S_{p}\right)  \left(  U_{p}\right)
^{q}\\\text{(by Proposition \ref{prop.matrix-poly.1} \textbf{(c)})}}}\\
&  \ \ \ \ \ \ \ \ \ \ \left(  \text{since }h\in\mathbb{N}\text{ and }q\left(
p-1\right)  +1\in\mathbb{N}\right) \\
&  =\left(  I_{p}-S_{p}\right)  ^{h}p^{q}\left(  I_{p}-S_{p}\right)  \left(
U_{p}\right)  ^{q}=p^{q}\underbrace{\left(  I_{p}-S_{p}\right)  ^{h}\left(
I_{p}-S_{p}\right)  }_{=\left(  I_{p}-S_{p}\right)  ^{h+1}}\left(
U_{p}\right)  ^{q}\\
&  =p^{q}\left(  I_{p}-S_{p}\right)  ^{h+1}\left(  U_{p}\right)  ^{q}.
\end{align*}
Therefore,%
\[
\left(  \underbrace{\left(  I_{p}-S_{p}\right)  ^{n}}_{=p^{q}\left(
I_{p}-S_{p}\right)  ^{h+1}\left(  U_{p}\right)  ^{q}}\right)  _{u,v}=\left(
p^{q}\left(  I_{p}-S_{p}\right)  ^{h+1}\left(  U_{p}\right)  ^{q}\right)
_{u,v}=p^{q}\left(  \left(  I_{p}-S_{p}\right)  ^{h+1}\left(  U_{p}\right)
^{q}\right)  _{u,v}.
\]
This is clearly divisible by $p^{q}$ (since $\left(  \left(  I_{p}%
-S_{p}\right)  ^{h+1}\left(  U_{p}\right)  ^{q}\right)  _{u,v}\in\mathbb{Z}$).
In other words, $\left(  \left(  I_{p}-S_{p}\right)  ^{n}\right)  _{u,v}$ is
divisible by $p^{q}$. In other words, $p^{q}\mid\left(  \left(  I_{p}%
-S_{p}\right)  ^{n}\right)  _{u,v}$. This proves Corollary
\ref{cor.matrix-poly.2}.
\end{proof}

We can now finally prove Theorem \ref{thm.fleck}:

\begin{proof}
[Proof of Theorem \ref{thm.fleck}.]Let $s$ and $k$ be the quotient and the
remainder when $j$ is divided by $p$. Thus, $k\in\left\{  0,1,\ldots
,p-1\right\}  $ and $j=ps+k$. Now, $j=\underbrace{p}_{\equiv
0\operatorname{mod}p}s+k\equiv k\operatorname{mod}p$. Hence, for every
$m\in\mathbb{N}$, the condition $\left(  m\equiv j\operatorname{mod}p\right)
$ is equivalent to the condition $\left(  m\equiv k\operatorname{mod}p\right)
$. Hence, we can replace the summation sign $\sum\limits_{\substack{m\in
\mathbb{N};\\m\equiv j\operatorname{mod}p}}$ in the sum $\sum
\limits_{\substack{m\in\mathbb{N};\\m\equiv j\operatorname{mod}p}}\left(
-1\right)  ^{m}\dbinom{n}{m}$ by $\sum\limits_{\substack{m\in\mathbb{N}%
;\\m\equiv k\operatorname{mod}p}}$. Thus,%
\begin{equation}
\underbrace{\sum\limits_{\substack{m\in\mathbb{N};\\m\equiv
j\operatorname{mod}p}}}_{=\sum\limits_{\substack{m\in\mathbb{N};\\m\equiv
k\operatorname{mod}p}}}\left(  -1\right)  ^{m}\dbinom{n}{m}=\sum
\limits_{\substack{m\in\mathbb{N};\\m\equiv k\operatorname{mod}p}}\left(
-1\right)  ^{m}\dbinom{n}{m}=\left(  \left(  I_{p}-S_{p}\right)  ^{n}\right)
_{1,k+1} \label{pf.thm.fleck.1}%
\end{equation}
(by Corollary \ref{cor.circ.pow.binom}).

Notice that $k\in\left\{  0,1,\ldots,p-1\right\}  $, so that $k+1\in\left\{
1,2,\ldots,p\right\}  $. Also, $1\in\left\{  1,2,\ldots,p\right\}  $ (since
$p\geq1$).

But Corollary \ref{cor.matrix-poly.2} (applied to $u=1$ and $v=k+1$) yields
$p^{q}\mid\left(  \left(  I_{p}-S_{p}\right)  ^{n}\right)  _{1,k+1}$. In light
of (\ref{pf.thm.fleck.1}), this rewrites as $p^{q}\mid\sum
\limits_{\substack{m\in\mathbb{N};\\m\equiv j\operatorname{mod}p}}\left(
-1\right)  ^{m}\dbinom{n}{m}$. In other words, $\sum\limits_{\substack{m\in
\mathbb{N};\\m\equiv j\operatorname{mod}p}}\left(  -1\right)  ^{m}\dbinom
{n}{m}\equiv0\operatorname{mod}p^{q}$. This proves Theorem \ref{thm.fleck}.
\end{proof}

\section{\label{sect.app1}Appendix 1: Proof of Proposition
\ref{prop.binom.p-1}}

We are going to prove Proposition \ref{prop.binom.p-1}. Let us first recall a
really basic fact from number theory:

\begin{proposition}
\label{prop.nzm.1.10}Let $a$, $b$ and $c$ be three integers such that $b$ is
coprime to $c$. Assume that $c\mid ab$. Then, $c\mid a$.
\end{proposition}

Proposition \ref{prop.nzm.1.10} appears (for example) in \cite[Theorem
1.10]{NiZuMo91}.

Next, we observe the following:

\begin{lemma}
\label{lem.2.1.p44.lem1}Let $p$ be a prime. Let $k\in\left\{  0,1,\ldots
,p-1\right\}  $. Then, $k!$ is coprime to $p$.
\end{lemma}

\begin{proof}
[Proof of Lemma \ref{lem.2.1.p44.lem1}.]We shall prove Lemma
\ref{lem.2.1.p44.lem1} by induction over $k$:

\begin{vershort}
\textit{Induction base:} Clearly, $0!$ is coprime to any integer (since
$0!=1$), thus in particular to $p$. In other words, Lemma
\ref{lem.2.1.p44.lem1} holds for $k=0$. This completes the induction base.
\end{vershort}

\begin{verlong}
\textit{Induction base:} Clearly, $1$ is coprime to any integer. In
particular, $1$ is coprime to $p$. In other words, $0!$ is coprime to $p$
(since $0!=1$). In other words, Lemma \ref{lem.2.1.p44.lem1} holds for $k=0$.
This completes the induction base.
\end{verlong}

\textit{Induction step:} Let $K\in\left\{  0,1,\ldots,p-1\right\}  $ be
positive. Assume that Lemma \ref{lem.2.1.p44.lem1} holds for $k=K-1$. We must
prove that Lemma \ref{lem.2.1.p44.lem1} holds for $k=K$.

We have assumed that Lemma \ref{lem.2.1.p44.lem1} holds for $k=K-1$. In other
words, $\left(  K-1\right)  !$ is coprime to $p$.

Set $q=\gcd\left(  K!,p\right)  $. Then, $q=\gcd\left(  K!,p\right)  $ is a
positive integer (since $K!$ and $p$ are positive integers). Also,
$q=\gcd\left(  K!,p\right)  \mid K!$ and $q=\gcd\left(  K!,p\right)  \mid p$.

Assume (for the sake of contradiction) that $q\neq1$. Then, $q>1$ (since $q$
is a positive integer).

\begin{vershort}
The number $q$ is a positive divisor of $p$ (since $q$ is positive and $q\mid
p$). Therefore, $q$ is either $1$ or $p$ (since the only positive divisors of
$p$ are $1$ and $p$ (since $p$ is prime)). Since $q\neq1$, we thus conclude
that $q=p$. Hence, $p=q\mid K!=K\cdot\left(  K-1\right)  !$. Recall also that
$\left(  K-1\right)  !$ is coprime to $p$. Thus, Proposition
\ref{prop.nzm.1.10} (applied to $a=K$, $b=\left(  K-1\right)  !$ and $c=p$)
shows that $p\mid K$. Since $K$ and $p$ are positive, this entails that $K\geq
p$.
\end{vershort}

\begin{verlong}
Now, $q$ is a positive integer and divides $p$ (since $q\mid p$). Thus, $q$ is
a positive divisor of $p$. But the only positive divisors of $p$ are $1$ and
$p$ (since $p$ is a prime). Hence, every positive divisor of $p$ belongs to
the set $\left\{  1,p\right\}  $. In other words, if $r$ is a positive divisor
of $p$, then $r\in\left\{  1,p\right\}  $. Applying this to $r=q$, we obtain
$q\in\left\{  1,p\right\}  $ (since $q$ is a positive divisor of $p$).
Combining this with $q\neq1$, we obtain $q\in\left\{  1,p\right\}
\setminus\left\{  1\right\}  \subseteq\left\{  p\right\}  $. In other words,
$q=p$. Hence, $p=q\mid K!=K\cdot\left(  K-1\right)  !$. Recall also that
$\left(  K-1\right)  !$ is coprime to $p$. Thus, Proposition
\ref{prop.nzm.1.10} (applied to $a=K$, $b=\left(  K-1\right)  !$ and $c=p$)
shows that $p\mid K$. Since $K$ and $p$ are positive, this entails that $K\geq
p$.
\end{verlong}

But $K\in\left\{  0,1,\ldots,p-1\right\}  $, so that $K\leq p-1<p$. This
contradicts $K\geq p$. This contradiction proves that our assumption (that
$q\neq1$) was wrong. Hence, we cannot have $q\neq1$. Thus, we must have $q=1$.
In view of $q=\gcd\left(  K!,p\right)  $, this rewrites as $\gcd\left(
K!,p\right)  =1$. In other words, $K!$ is coprime to $p$. In other words,
Lemma \ref{lem.2.1.p44.lem1} holds for $k=K$. This completes the induction
step. Lemma \ref{lem.2.1.p44.lem1} is thus proven by induction.
\end{proof}

Here is another lemma, which shows how we can (sometimes) cancel factors from congruences:

\begin{lemma}
\label{lem.2.1.p44.lem2}Let $b$ and $c$ be integers such that $c$ is nonzero
and such that $b$ is coprime to $c$. Let $a$ and $a^{\prime}$ be integers such
that $ba\equiv ba^{\prime}\operatorname{mod}c$. Then, $a\equiv a^{\prime
}\operatorname{mod}c$.
\end{lemma}

\begin{proof}
[Proof of Lemma \ref{lem.2.1.p44.lem2}.]We have $ba\equiv ba^{\prime
}\operatorname{mod}c$. In other words, $c\mid ba-ba^{\prime}$. In other words,
$c\mid\left(  a-a^{\prime}\right)  b$ (since $ba-ba^{\prime}=b\left(
a-a^{\prime}\right)  =\left(  a-a^{\prime}\right)  b$). Thus, Proposition
\ref{prop.nzm.1.10} (applied to $a-a^{\prime}$ instead of $a$) yields $c\mid
a-a^{\prime}$. In other words, $a\equiv a^{\prime}\operatorname{mod}c$. This
proves Lemma \ref{lem.2.1.p44.lem2}.
\end{proof}

\begin{proof}
[First proof of Proposition \ref{prop.binom.p-1}.]The definition of
$\dbinom{p-1}{k}$ yields
\[
\dbinom{p-1}{k}=\dfrac{\left(  p-1\right)  \left(  p-2\right)  \cdots\left(
p-k\right)  }{k!}.
\]
Hence, $k!\dbinom{p-1}{k}=\left(  p-1\right)  \left(  p-2\right)
\cdots\left(  p-k\right)  $.

But $p-i\equiv-i\operatorname{mod}p$ for every $i\in\mathbb{Z}$. Multiplying
these congruences for all $i\in\left\{  1,2,\ldots,k\right\}  $, we obtain%
\begin{align*}
\left(  p-1\right)  \left(  p-2\right)  \cdots\left(  p-k\right)   &
\equiv\left(  -1\right)  \left(  -2\right)  \cdots\left(  -k\right) \\
&  =\left(  -1\right)  ^{k}\underbrace{\left(  1\cdot2\cdot\cdots\cdot
k\right)  }_{=k!}=\left(  -1\right)  ^{k}k!\operatorname{mod}p.
\end{align*}
Hence,%
\begin{equation}
k!\dbinom{p-1}{k}=\left(  p-1\right)  \left(  p-2\right)  \cdots\left(
p-k\right)  \equiv\left(  -1\right)  ^{k}k!=k!\left(  -1\right)
^{k}\operatorname{mod}p. \label{2.1.p44.1}%
\end{equation}
But Lemma \ref{lem.2.1.p44.lem1} shows that $k!$ is coprime to $p$. Hence,
from (\ref{2.1.p44.1}), we obtain $\dbinom{p-1}{k}\equiv\left(  -1\right)
^{k}\operatorname{mod}p$ (by Lemma \ref{lem.2.1.p44.lem2}, applied to $c=p$,
$a=\dbinom{p-1}{k}$, $a^{\prime}=\left(  -1\right)  ^{k}$ and $b=k!$). This
proves Proposition \ref{prop.binom.p-1}.
\end{proof}

We are now done proving Proposition \ref{prop.binom.p-1}; but let us explore
the surroundings a bit more and give a (slightly) different proof of
Proposition \ref{prop.binom.p-1}, which shows a generalization. But first,
here is a simple fact about binomial coefficients:

\begin{proposition}
\label{prop.2.1.p44.prop4}Let $k\in\mathbb{N}$. Then, $\dbinom{-1}{k}=\left(
-1\right)  ^{k}$.
\end{proposition}

In this proposition, we are using the fact that binomial coefficients
$\dbinom{n}{k}$ are defined for negative $n$ just as well as for
$n\in\mathbb{N}$. These binomial coefficients no longer count subsets (after
all, they can be negative), but nevertheless are integers\footnote{See
\cite[Proposition 3.20]{detnotes} for the proof of this fact.}.

\begin{proof}
[Proof of Proposition \ref{prop.2.1.p44.prop4}.]The definition of $\dbinom
{-1}{k}$ yields
\begin{align*}
\dbinom{-1}{k}  &  =\dfrac{\left(  -1\right)  \left(  -2\right)  \cdots\left(
-k\right)  }{k!}=\dfrac{1}{k!}\underbrace{\left(  -1\right)  \left(
-2\right)  \cdots\left(  -k\right)  }_{=\left(  -1\right)  ^{k}\left(
1\cdot2\cdot\cdots\cdot k\right)  }\\
&  =\dfrac{1}{k!}\left(  -1\right)  ^{k}\underbrace{\left(  1\cdot2\cdot
\cdots\cdot k\right)  }_{=k!}=\dfrac{1}{k!}\left(  -1\right)  ^{k}k!=\left(
-1\right)  ^{k}.
\end{align*}
Proposition \ref{prop.2.1.p44.prop4} is proven.
\end{proof}

We can now generalize Proposition \ref{prop.binom.p-1}:

\begin{proposition}
\label{prop.2.1.p44.prop5}Let $p$ be a prime. Let $u$ and $v$ be two integers
such that $u\equiv v\operatorname{mod}p$. Let $k\in\left\{  0,1,\ldots
,p-1\right\}  $. Then, $\dbinom{u}{k}\equiv\dbinom{v}{k}\operatorname{mod}p$.
\end{proposition}

Notice the condition $k\in\left\{  0,1,\ldots,p-1\right\}  $. Proposition
\ref{prop.2.1.p44.prop5} no longer holds when $k=p$ (indeed, $p\equiv
0\operatorname{mod}p$ but $\dbinom{p}{p}\not \equiv \dbinom{0}{p}%
\operatorname{mod}p$). When you work modulo $p$, you cannot blindly replace an
integer by a different integer congruent to it modulo $p$ when said integer
appears inside a binomial coefficient.

\begin{proof}
[Proof of Proposition \ref{prop.2.1.p44.prop5}.]The definition of $\dbinom
{u}{k}$ yields $\dbinom{u}{k}=\dfrac{u\left(  u-1\right)  \cdots\left(
u-k+1\right)  }{k!}$. Hence, $k!\dbinom{u}{k}=u\left(  u-1\right)
\cdots\left(  u-k+1\right)  $. The same argument (applied to $v$ instead of
$u$) shows that $k!\dbinom{v}{k}=v\left(  v-1\right)  \cdots\left(
v-k+1\right)  $.

But every $i\in\mathbb{Z}$ satisfies $u-i\equiv v-i\operatorname{mod}p$ (since
$u\equiv v\operatorname{mod}p$). Multiplying these congruences for all
$i\in\left\{  0,1,\ldots,k-1\right\}  $, we obtain%
\[
u\left(  u-1\right)  \cdots\left(  u-k+1\right)  \equiv v\left(  v-1\right)
\cdots\left(  v-k+1\right)  \operatorname{mod}p.
\]
Hence,%
\begin{align}
k!\dbinom{u}{k}  &  =u\left(  u-1\right)  \cdots\left(  u-k+1\right)
\nonumber\\
&  \equiv v\left(  v-1\right)  \cdots\left(  v-k+1\right)  =k!\dbinom{v}%
{k}\operatorname{mod}p. \label{2.1.p44.5}%
\end{align}
But Lemma \ref{lem.2.1.p44.lem1} shows that $k!$ is coprime to $p$. Hence,
from (\ref{2.1.p44.5}), we obtain $\dbinom{u}{k}\equiv\dbinom{v}%
{k}\operatorname{mod}p$ (by Lemma \ref{lem.2.1.p44.lem2}, applied to $c=p$,
$a=\dbinom{u}{k}$, $a^{\prime}=\dbinom{v}{k}$ and $b=k!$). Proposition
\ref{prop.2.1.p44.prop5} is proven.
\end{proof}

\begin{proof}
[Second proof of Proposition \ref{prop.binom.p-1}.]We have $p-1\equiv
-1\operatorname{mod}p$. Hence, Proposition \ref{prop.2.1.p44.prop5} (applied
to $u=p-1$ and $v=-1$) shows that%
\[
\dbinom{p-1}{k}\equiv\dbinom{-1}{k}=\left(  -1\right)  ^{k}\operatorname{mod}%
p\ \ \ \ \ \ \ \ \ \ \left(  \text{by Proposition \ref{prop.2.1.p44.prop4}%
}\right)  .
\]
This proves Proposition \ref{prop.binom.p-1} again.
\end{proof}

Let us record a simple (and really classical) fact that follows from
Proposition \ref{prop.binom.p-1}:

\begin{corollary}
\label{cor.binom.p}Let $p$ be a prime. Let $k\in\left\{  1,2,\ldots
,p-1\right\}  $. Then, $p\mid\dbinom{p}{k}$.
\end{corollary}

\begin{proof}
[Proof of Corollary \ref{cor.binom.p}.]We have $k\in\left\{  1,2,\ldots
,p-1\right\}  \subseteq\left\{  0,1,\ldots,p-1\right\}  $. Thus, Proposition
\ref{prop.binom.p-1} yields $\dbinom{p-1}{k}\equiv\left(  -1\right)
^{k}\operatorname{mod}p$.

But $k\in\left\{  1,2,\ldots,p-1\right\}  $, and thus $k-1\in\left\{
0,1,\ldots,\left(  p-1\right)  -1\right\}  \subseteq\left\{  0,1,\ldots
,p-1\right\}  $. Thus, Proposition \ref{prop.binom.p-1} (applied to $k-1$
instead of $k$) yields $\dbinom{p-1}{k-1}\equiv\left(  -1\right)
^{k-1}\operatorname{mod}p$.

But the recurrence relation of the binomial coefficients (see, e.g.,
\cite[Proposition 3.11]{detnotes}) shows that $\dbinom{m}%
{n}=\dbinom{m-1}{n-1}+\dbinom{m-1}{n}$ for every $m\in\mathbb{Q}$ and every
positive integer $n$. Applying this to $m=p$ and $n=k$, we obtain%
\begin{align*}
\dbinom{p}{k}  &  =\underbrace{\dbinom{p-1}{k-1}}_{\equiv\left(  -1\right)
^{k-1}\operatorname{mod}p}+\underbrace{\dbinom{p-1}{k}}_{\equiv\left(
-1\right)  ^{k}=-\left(  -1\right)  ^{k-1}\operatorname{mod}p}\\
&  \equiv\left(  -1\right)  ^{k-1}+\left(  -\left(  -1\right)  ^{k-1}\right)
=0\operatorname{mod}p.
\end{align*}
In other words, $p\mid\dbinom{p}{k}$. This proves Corollary \ref{cor.binom.p}.
\end{proof}

\section{\label{sect.app2}Appendix 2: avoiding subalgebras}

Above, we have derived Corollary \ref{cor.matrix-poly.2} from Proposition
\ref{prop.matrix-poly.1}, which was proven using a little bit of abstract
algebra. Let us now show how essentially the same argument could have been
rewritten in fully elementary terms. We shall derive Corollary
\ref{cor.matrix-poly.2} from the following fact:

\begin{proposition}
\label{prop.matrix-poly.app3}Let $p$ be a prime.

For every $k\in\left\{  0,1,\ldots,p-1\right\}  $, we have $\dfrac{\left(
-1\right)  ^{k}\dbinom{p-1}{k}-1}{p}\in\mathbb{Z}$ (by Corollary
\ref{cor.binom.p-1.ak}).

Thus, for every $k\in\left\{  0,1,\ldots,p-1\right\}  $, we can define an
element $a_{k}\in\mathbb{Z}$ by $a_{k}=\dfrac{\left(  -1\right)  ^{k}%
\dbinom{p-1}{k}-1}{p}$. Consider these elements $a_{k}$.

Define a $p\times p$-matrix $U_{p}$ by $U_{p}=\sum_{k=0}^{p-1}a_{k}\left(
S_{p}\right)  ^{k}$.

\textbf{(a)} We have $\left(  I_{p}-S_{p}\right)  ^{p}=p\left(  I_{p}%
-S_{p}\right)  U_{p}$.

\textbf{(b)} For every $q\in\mathbb{N}$, we have%
\[
\left(  I_{p}-S_{p}\right)  ^{q\left(  p-1\right)  +1}=p^{q}\left(
I_{p}-S_{p}\right)  \left(  U_{p}\right)  ^{q}.
\]

\end{proposition}

The proof of this proposition will mostly be a mix of our above proof of
Proposition \ref{prop.matrix-poly.1} and our proof of Corollary
\ref{cor.poly.prime}.

\begin{proof}
[Proof of Proposition \ref{prop.matrix-poly.app3}.]\textbf{(a)} Every
$k\in\left\{  0,1,\ldots,p-1\right\}  $ satisfies%
\begin{equation}
pa_{k}=\left(  -1\right)  ^{k}\dbinom{p-1}{k}-1
\label{pf.prop.matrix-poly.app3.a.pak}%
\end{equation}
(since $a_{k}=\dfrac{\left(  -1\right)  ^{k}\dbinom{p-1}{k}-1}{p}$).

Let $\mathbb{Z}^{p\times p}$ denote the ring of all $p\times p$-matrices. The
two matrices $-S_{p}$ and $I_{p}$ in $\mathbb{Z}^{p\times p}$ commute (since
$\left(  -S_{p}\right)  I_{p}=-S_{p}=I_{p}\left(  -S_{p}\right)  $). Thus,
$-S_{p}$ and $I_{p}$ are two commuting elements of the ring $\mathbb{Z}%
^{p\times p}$.

The binomial formula says the following: If $a$ and $b$ are any two commuting
elements of a ring $\mathfrak{A}$ (that is, any two elements of a ring
$\mathfrak{A}$ satisfying $ab=ba$), and if $g\in\mathbb{N}$, then%
\[
\left(  a+b\right)  ^{g}=\sum_{k=0}^{g}\dbinom{g}{k}a^{k}b^{g-k}.
\]
This formula (applied to $\mathfrak{A}=\mathbb{Z}^{p\times p}$, $a=-S_{p}$,
$b=I_{p}$ and $g=p-1$) yields%
\begin{align*}
\left(  \left(  -S_{p}\right)  +I_{p}\right)  ^{p-1}  &  =\sum_{k=0}%
^{p-1}\dbinom{p-1}{k}\underbrace{\left(  -S_{p}\right)  ^{k}}_{=\left(
-1\right)  ^{k}\left(  S_{p}\right)  ^{k}}\underbrace{\left(  I_{p}\right)
^{p-1-k}}_{=I_{p}}\\
&  =\sum_{k=0}^{p-1}\underbrace{\dbinom{p-1}{k}\left(  -1\right)  ^{k}%
}_{=\left(  -1\right)  ^{k}\dbinom{p-1}{k}}\left(  S_{p}\right)  ^{k}%
=\sum_{k=0}^{p-1}\left(  -1\right)  ^{k}\dbinom{p-1}{k}\left(  S_{p}\right)
^{k}.
\end{align*}
Since $\left(  -S_{p}\right)  +I_{p}=I_{p}-S_{p}$, this rewrites as follows:%
\begin{equation}
\left(  I_{p}-S_{p}\right)  ^{p-1}=\sum_{k=0}^{p-1}\left(  -1\right)
^{k}\dbinom{p-1}{k}\left(  S_{p}\right)  ^{k}.
\label{pf.prop.matrix-poly.app3.a.1}%
\end{equation}


On the other hand,%
\begin{align}
\left(  I_{p}-S_{p}\right)  \sum_{k=0}^{p-1}\left(  S_{p}\right)  ^{k}  &
=\sum_{k=0}^{p-1}\left(  S_{p}\right)  ^{k}-\underbrace{S_{p}\sum_{k=0}%
^{p-1}\left(  S_{p}\right)  ^{k}}_{=\sum_{k=0}^{p-1}S_{p}\left(  S_{p}\right)
^{k}}=\sum_{k=0}^{p-1}\left(  S_{p}\right)  ^{k}-\sum_{k=0}^{p-1}%
\underbrace{S_{p}\left(  S_{p}\right)  ^{k}}_{=\left(  S_{p}\right)  ^{k+1}%
}\nonumber\\
&  =\sum_{k=0}^{p-1}\left(  S_{p}\right)  ^{k}-\sum_{k=0}^{p-1}\left(
S_{p}\right)  ^{k+1}=\underbrace{\sum_{k=0}^{p-1}\left(  S_{p}\right)  ^{k}%
}_{=\left(  S_{p}\right)  ^{0}+\sum_{k=1}^{p-1}\left(  S_{p}\right)  ^{k}%
}-\underbrace{\sum_{k=1}^{p}\left(  S_{p}\right)  ^{k}}_{=\sum_{k=1}%
^{p-1}\left(  S_{p}\right)  ^{k}+\left(  S_{p}\right)  ^{p}}\nonumber\\
&  \ \ \ \ \ \ \ \ \ \ \left(  \text{here, we have substituted }k\text{ for
}k+1\text{ in the second sum}\right) \nonumber\\
&  =\left(  \left(  S_{p}\right)  ^{0}+\sum_{k=1}^{p-1}\left(  S_{p}\right)
^{k}\right)  -\left(  \sum_{k=1}^{p-1}\left(  S_{p}\right)  ^{k}+\left(
S_{p}\right)  ^{p}\right) \nonumber\\
&  =\underbrace{\left(  S_{p}\right)  ^{0}}_{=I_{p}}-\underbrace{\left(
S_{p}\right)  ^{p}}_{\substack{=I_{p}\\\text{(by Corollary
\ref{cor.circ.pow.p=0})}}}=I_{p}-I_{p}=0. \label{pf.prop.matrix-poly.app3.a.5}%
\end{align}
Now,%
\begin{align*}
&  \left(  I_{p}-S_{p}\right)  ^{p}\\
&  =\underbrace{\left(  I_{p}-S_{p}\right)  ^{p}}_{=\left(  I_{p}%
-S_{p}\right)  \left(  I_{p}-S_{p}\right)  ^{p-1}}-\underbrace{0}%
_{\substack{=\left(  I_{p}-S_{p}\right)  \sum_{k=0}^{p-1}\left(  S_{p}\right)
^{k}\\\text{(by (\ref{pf.prop.matrix-poly.app3.a.5}))}}}\\
&  =\left(  I_{p}-S_{p}\right)  \left(  I_{p}-S_{p}\right)  ^{p-1}-\left(
I_{p}-S_{p}\right)  \sum_{k=0}^{p-1}\left(  S_{p}\right)  ^{k}\\
&  =\left(  I_{p}-S_{p}\right)  \left(  \left(  I_{p}-S_{p}\right)
^{p-1}-\sum_{k=0}^{p-1}\left(  S_{p}\right)  ^{k}\right)  .
\end{align*}
Since%
\begin{align*}
&  \underbrace{\left(  I_{p}-S_{p}\right)  ^{p-1}}_{\substack{=\sum
_{k=0}^{p-1}\left(  -1\right)  ^{k}\dbinom{p-1}{k}\left(  S_{p}\right)
^{k}\\\text{(by (\ref{pf.prop.matrix-poly.app3.a.1}))}}}-\sum_{k=0}%
^{p-1}\left(  S_{p}\right)  ^{k}\\
&  =\sum_{k=0}^{p-1}\left(  -1\right)  ^{k}\dbinom{p-1}{k}\left(
S_{p}\right)  ^{k}-\sum_{k=0}^{p-1}\left(  S_{p}\right)  ^{k}=\sum_{k=0}%
^{p-1}\underbrace{\left(  \left(  -1\right)  ^{k}\dbinom{p-1}{k}-1\right)
}_{\substack{=pa_{k}\\\text{(by (\ref{pf.prop.matrix-poly.app3.a.pak}))}%
}}\left(  S_{p}\right)  ^{k}\\
&  =\sum_{k=0}^{p-1}pa_{k}\left(  S_{p}\right)  ^{k}=p\underbrace{\sum
_{k=0}^{p-1}a_{k}\left(  S_{p}\right)  ^{k}}_{\substack{=U_{p}\\\text{(since
}U_{p}=\sum_{k=0}^{p-1}a_{k}\left(  S_{p}\right)  ^{k}\text{)}}}=pU_{p},
\end{align*}
this becomes%
\begin{align*}
\left(  I_{p}-S_{p}\right)  ^{p}  &  =\left(  I_{p}-S_{p}\right)
\underbrace{\left(  \left(  I_{p}-S_{p}\right)  ^{p-1}-\sum_{k=0}^{p-1}\left(
S_{p}\right)  ^{k}\right)  }_{=pU_{p}}\\
&  =\left(  I_{p}-S_{p}\right)  pU_{p}=p\left(  I_{p}-S_{p}\right)  U_{p}.
\end{align*}
This proves Proposition \ref{prop.matrix-poly.app3} \textbf{(a)}.

\textbf{(b)} Proposition \ref{prop.matrix-poly.app3} \textbf{(b)} can be
derived from Proposition \ref{prop.matrix-poly.app3} \textbf{(a)} in the same
way as Proposition \ref{prop.matrix-poly.1} \textbf{(c)} was derived from
Proposition \ref{prop.matrix-poly.1} \textbf{(b)}.
\end{proof}

\begin{proof}
[Second proof of Corollary \ref{cor.matrix-poly.2}.]We can copy the above
proof of Corollary \ref{cor.matrix-poly.2} verbatim, with the only change that
we use Proposition \ref{prop.matrix-poly.app3} \textbf{(b)} instead of
Proposition \ref{prop.matrix-poly.1} \textbf{(c)}.
\end{proof}

\begin{thebibliography}{999999999}                                                                                        %


\bibitem[Granvi05]{Granvi05}Andrew Granville, \textit{Binomial coefficients
modulo prime powers}.\newline\url{http://www.dms.umontreal.ca/~andrew/PDF/BinCoeff.pdf}

\bibitem[Grinbe15]{Grinbe15}Darij Grinberg, \textit{An analogue of Hensel's
lifting for Fibonacci numbers}, math.stackexchange answer \#1441518,
Mathematics Stack Exchange.\newline\url{http://math.stackexchange.com/q/1441518}

\bibitem[Grinbe17]{detnotes}Darij Grinberg, \textit{Notes on the combinatorial
fundamentals of algebra}, 10 January 2019. \newline%
\url{https://github.com/darijgr/detnotes/releases/tag/2019-01-10} \newline See
also \url{http://www.cip.ifi.lmu.de/~grinberg/primes2015/sols.pdf} for a
version that is getting updates.

\bibitem[NiZuMo91]{NiZuMo91}Ivan Niven, Herbert S. Zuckerman, Hugh L.
Montgomery, \textit{An Introduction to the Theory of Numbers}, 5th edition,
Wiley 1991.

\bibitem[SchWal12]{SchWal12}Andrew Schultz, Robert Walker, \textit{A
generalization of the Gaussian formula and a q-analog of Fleck's congruence},
arXiv:1202.0199.\newline\url{http://arxiv.org/abs/1202.0199}
\end{thebibliography}


\end{document}