% ------------------------------------------------------------- % 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{} %TCIDATA{} %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