0$.
Also, $d\in\left\{ 0,1,\ldots,p-1\right\} $, so that $d\geq0$. Hence,
$\underbrace{b}_{>0}\underbrace{p}_{>0}+\underbrace{d}_{\geq0}>0$. Thus,
$bp+d$ is a positive integer (since $bp+d\in\mathbb{Z}$), so that
$bp+d\in\mathbb{N}$. Also, $c\in\left\{ 0,1,\ldots,p-1\right\}
\subseteq\mathbb{N}$. Moreover, $b>0$, so that $b\geq1$ (since $b$ is an
integer). Using $p>0$, we thus find $\underbrace{b}_{\geq1}p\geq p$. But
$c\in\left\{ 0,1,\ldots,p-1\right\} $, so that $c\leq p-1c$.
Now, $bp+\underbrace{d}_{\geq0}\geq bp\geq p>c$, so that $c0$. Hence, $00$.
Hence, $bp>0$ (since $p$ is positive). Thus, $bp$ is a positive integer (since
$bp\in\mathbb{Z}$), so that $bp\in\mathbb{N}$. Moreover, $00$). Hence, Proposition \ref{prop.binom.0} (applied to $m=0$ and $n=bp$)
yields $\dbinom{0}{bp}=0$.
Now, the definition of $A$ yields%
\begin{align*}
A\left( 0,b\right) & =\dbinom{0p}{bp}=\dbinom{0}{bp}%
\ \ \ \ \ \ \ \ \ \ \left( \text{since }0p=0\right) \\
& =0\equiv0\operatorname{mod}p^{2}.
\end{align*}
This proves Observation 4.]
We have now proven the four Observations 1, 2, 3 and 4. In other words, the
four conditions in Lemma \ref{lem.cong-lem} hold if we set $N=p^{2}$. Thus,
Lemma \ref{lem.cong-lem} (applied to $N=p^{2}$) yields that every
$a\in\mathbb{Z}$ and $b\in\mathbb{Z}$ satisfy%
\begin{equation}
A\left( a,b\right) \equiv u\dbinom{a}{b}\operatorname{mod}p^{2}.
\label{pf.thm.p2cong.at}%
\end{equation}
Now, let $a$ and $b$ be two integers. Thus, $a\in\mathbb{Z}$ and
$b\in\mathbb{Z}$. Hence, (\ref{pf.thm.p2cong.at}) yields%
\[
A\left( a,b\right) \equiv\underbrace{u}_{=1}\dbinom{a}{b}=\dbinom{a}%
{b}\operatorname{mod}p^{2}.
\]
In view of%
\[
A\left( a,b\right) =\dbinom{ap}{bp}\ \ \ \ \ \ \ \ \ \ \left( \text{by the
definition of }A\right) ,
\]
this rewrites as%
\[
\dbinom{ap}{bp}\equiv\dbinom{a}{b}\operatorname{mod}p^{2}.
\]
This proves Theorem \ref{thm.p2cong}.
\end{proof}
\section{The sums of the first $p$ powers}
\subsection{The congruence}
Next, we shall prove a well-known congruence concerning the sum $\sum
_{l=0}^{p-1}l^{k}=0^{k}+1^{k}+\cdots+\left( p-1\right) ^{k}$ for a prime $p$:
\begin{theorem}
\label{thm.powersums.p}Let $p$ be a prime. Let $k\in\mathbb{N}$. Assume that
$k$ is not a positive multiple of $p-1$. Then,%
\[
\sum_{l=0}^{p-1}l^{k}\equiv0\operatorname{mod}p.
\]
\end{theorem}
Theorem \ref{thm.powersums.p} has nothing to do with binomial coefficients.
Nevertheless, we shall prove it using binomial coefficients.
\subsection{Powers and power sums via Stirling numbers of the second kind}
We shall first introduce another family of integers: the so-called
\textit{Stirling numbers of the second kind}. They have various equivalent
definitions; we define them by recursion:
\begin{definition}
\label{def.stir2}For each $m\in\mathbb{N}$ and $n\in\mathbb{Z}$, we define an
integer $%
%TCIMACRO{\QDATOPD{\{}{\}}{m}{n}}%
%BeginExpansion
\genfrac{\{}{\}}{0pt}{0}{m}{n}%
%EndExpansion
$ as follows: We proceed by recursion on $m$:
\begin{itemize}
\item We set%
\begin{equation}%
%TCIMACRO{\QDATOPD{\{}{\}}{0}{n}}%
%BeginExpansion
\genfrac{\{}{\}}{0pt}{0}{0}{n}%
%EndExpansion
=%
\begin{cases}
1, & \text{if }n=0;\\
0, & \text{if }n\neq0
\end{cases}
\ \ \ \ \ \ \ \ \ \ \text{for all }n\in\mathbb{Z}. \label{eq.def.stir2.0}%
\end{equation}
This defines $%
%TCIMACRO{\QDATOPD{\{}{\}}{m}{n}}%
%BeginExpansion
\genfrac{\{}{\}}{0pt}{0}{m}{n}%
%EndExpansion
$ for $m=0$.
\item For each positive integer $m$ and each $n\in\mathbb{Z}$, we set%
\begin{equation}%
%TCIMACRO{\QDATOPD{\{}{\}}{m}{n}}%
%BeginExpansion
\genfrac{\{}{\}}{0pt}{0}{m}{n}%
%EndExpansion
=n%
%TCIMACRO{\QDATOPD{\{}{\}}{m-1}{n}}%
%BeginExpansion
\genfrac{\{}{\}}{0pt}{0}{m-1}{n}%
%EndExpansion
+%
%TCIMACRO{\QDATOPD{\{}{\}}{m-1}{n-1}}%
%BeginExpansion
\genfrac{\{}{\}}{0pt}{0}{m-1}{n-1}%
%EndExpansion
. \label{eq.def.stir2.m}%
\end{equation}
\end{itemize}
Thus, a family $\left(
%TCIMACRO{\QDATOPD{\{}{\}}{m}{n}}%
%BeginExpansion
\genfrac{\{}{\}}{0pt}{0}{m}{n}%
%EndExpansion
\right) _{\left( m,n\right) \in\mathbb{N}\times\mathbb{Z}}$ of integers is
defined. These integers $%
%TCIMACRO{\QDATOPD{\{}{\}}{m}{n}}%
%BeginExpansion
\genfrac{\{}{\}}{0pt}{0}{m}{n}%
%EndExpansion
$ are called the \textit{Stirling numbers of the second kind}.
\end{definition}
These Stirling numbers $%
%TCIMACRO{\QDATOPD{\{}{\}}{m}{n}}%
%BeginExpansion
\genfrac{\{}{\}}{0pt}{0}{m}{n}%
%EndExpansion
$ have a well-known combinatorial interpretation: Namely, if $m\in\mathbb{N}$
and $n\in\mathbb{N}$, then $%
%TCIMACRO{\QDATOPD{\{}{\}}{m}{n}}%
%BeginExpansion
\genfrac{\{}{\}}{0pt}{0}{m}{n}%
%EndExpansion
$ is the number of set partitions of the set $\left\{ 1,2,\ldots,m\right\} $
into $n$ nonempty subsets. This is actually not hard to prove by induction on
$m$ (for example, the proof is sketched in \cite[\S 1.9]{Stanley-EC1} and in
\cite[\S 6.1]{GKP}\footnote{To be more precise, both \cite[\S 1.9]%
{Stanley-EC1} and \cite[\S 6.1]{GKP} \textbf{define} $%
%TCIMACRO{\QDATOPD{\{}{\}}{m}{n}}%
%BeginExpansion
\genfrac{\{}{\}}{0pt}{0}{m}{n}%
%EndExpansion
$ as the number of set partitions of the set $\left\{ 1,2,\ldots,m\right\} $
into $n$ nonempty subsets, and then prove that (\ref{eq.def.stir2.0}) and
(\ref{eq.def.stir2.m}) hold with this definition. This is exactly the opposite
of what we are doing; but of course, it is equivalent.}); but we don't need
this. Instead, let us prove the following algebraic facts:
\begin{proposition}
\label{prop.stir2.0}For each $m\in\mathbb{N}$ and $n\in\mathbb{Z}$ satisfying
$n\notin\left\{ 0,1,\ldots,m\right\} $, we have $%
%TCIMACRO{\QDATOPD{\{}{\}}{m}{n}}%
%BeginExpansion
\genfrac{\{}{\}}{0pt}{0}{m}{n}%
%EndExpansion
=0$.
\end{proposition}
\begin{proof}
[Proof of Proposition \ref{prop.stir2.0}.]We shall prove Proposition
\ref{prop.stir2.0} by induction on $m$:
\begin{vershort}
\textit{Induction base:} Proposition \ref{prop.stir2.0} holds when $m=0$ (as
follows easily from (\ref{eq.def.stir2.0})). This completes the induction base.
\end{vershort}
\begin{verlong}
\textit{Induction base:} Proposition \ref{prop.stir2.0} holds when
$m=0$\ \ \ \ \footnote{\textit{Proof.} Let $n\in\mathbb{Z}$ be such that
$n\notin\left\{ 0,1,\ldots,0\right\} $. We have $n\notin\left\{
0,1,\ldots,0\right\} =\left\{ 0\right\} $. In other words, $n\neq0$. Now,
(\ref{eq.def.stir2.0}) yields $%
%TCIMACRO{\QDATOPD{\{}{\}}{0}{n}}%
%BeginExpansion
\genfrac{\{}{\}}{0pt}{0}{0}{n}%
%EndExpansion
=%
\begin{cases}
1, & \text{if }n=0;\\
0, & \text{if }n\neq0
\end{cases}
=0$ (since $n\neq0$).
\par
Now, forget that we fixed $n$. We thus have proven that for each
$n\in\mathbb{Z}$ satisfying $n\notin\left\{ 0,1,\ldots,0\right\} $, we have
$%
%TCIMACRO{\QDATOPD{\{}{\}}{0}{n}}%
%BeginExpansion
\genfrac{\{}{\}}{0pt}{0}{0}{n}%
%EndExpansion
=0$. In other words, Proposition \ref{prop.stir2.0} holds when $m=0$. Qed.}.
This completes the induction base.
\end{verlong}
\textit{Induction step:} Let $k$ be a positive integer. Assume that
Proposition \ref{prop.stir2.0} holds when $m=k-1$. We must now prove that
Proposition \ref{prop.stir2.0} holds when $m=k$.
We have assumed that Proposition \ref{prop.stir2.0} holds when $m=k-1$. In
other words, for each $n\in\mathbb{Z}$ satisfying $n\notin\left\{
0,1,\ldots,k-1\right\} $, we have
\begin{equation}%
%TCIMACRO{\QDATOPD{\{}{\}}{k-1}{n}}%
%BeginExpansion
\genfrac{\{}{\}}{0pt}{0}{k-1}{n}%
%EndExpansion
=0. \label{pf.prop.stir2.0.indhyp}%
\end{equation}
\begin{vershort}
Now, let $n\in\mathbb{Z}$ be such that $n\notin\left\{ 0,1,\ldots,k\right\}
$. Thus, $n-1\notin\left\{ 0,1,\ldots,k-1\right\} $. Hence,
(\ref{pf.prop.stir2.0.indhyp}) (applied to $n-1$ instead of $n$) yields $%
%TCIMACRO{\QDATOPD{\{}{\}}{k-1}{n-1}}%
%BeginExpansion
\genfrac{\{}{\}}{0pt}{0}{k-1}{n-1}%
%EndExpansion
=0$. Also, $n\notin\left\{ 0,1,\ldots,k-1\right\} $ (this again follows from
$n\notin\left\{ 0,1,\ldots,k\right\} $). Hence,
(\ref{pf.prop.stir2.0.indhyp}) yields $%
%TCIMACRO{\QDATOPD{\{}{\}}{k-1}{n}}%
%BeginExpansion
\genfrac{\{}{\}}{0pt}{0}{k-1}{n}%
%EndExpansion
=0$. Now, (\ref{eq.def.stir2.m}) (applied to $m=k$) yields%
\[%
%TCIMACRO{\QDATOPD{\{}{\}}{k}{n}}%
%BeginExpansion
\genfrac{\{}{\}}{0pt}{0}{k}{n}%
%EndExpansion
=n\underbrace{%
%TCIMACRO{\QDATOPD{\{}{\}}{k-1}{n}}%
%BeginExpansion
\genfrac{\{}{\}}{0pt}{0}{k-1}{n}%
%EndExpansion
}_{=0}+\underbrace{%
%TCIMACRO{\QDATOPD{\{}{\}}{k-1}{n-1}}%
%BeginExpansion
\genfrac{\{}{\}}{0pt}{0}{k-1}{n-1}%
%EndExpansion
}_{=0}=0.
\]
\end{vershort}
\begin{verlong}
Now, let $n\in\mathbb{Z}$ be such that $n\notin\left\{ 0,1,\ldots,k\right\}
$. Then, $n-1\notin\left\{ 0,1,\ldots,k-1\right\} $%
\ \ \ \ \footnote{\textit{Proof.} Assume the contrary. Thus, $n-1\in\left\{
0,1,\ldots,k-1\right\} $. Hence, $\left( n-1\right) +1\in\left\{
1,2,\ldots,k\right\} \subseteq\left\{ 0,1,\ldots,k\right\} $. This
contradicts $\left( n-1\right) +1=n\notin\left\{ 0,1,\ldots,k\right\} $.
This contradiction proves that our assumption was false. Qed.}. Hence,
(\ref{pf.prop.stir2.0.indhyp}) (applied to $n-1$ instead of $n$) yields $%
%TCIMACRO{\QDATOPD{\{}{\}}{k-1}{n-1}}%
%BeginExpansion
\genfrac{\{}{\}}{0pt}{0}{k-1}{n-1}%
%EndExpansion
=0$. Also, $n\notin\left\{ 0,1,\ldots,k-1\right\} $%
\ \ \ \ \footnote{\textit{Proof.} Assume the contrary. Thus, $n\in\left\{
0,1,\ldots,k-1\right\} $. Hence, $n\in\left\{ 0,1,\ldots,k-1\right\}
\subseteq\left\{ 0,1,\ldots,k\right\} $. This contradicts $n\notin\left\{
0,1,\ldots,k\right\} $. This contradiction proves that our assumption was
false. Qed.}. Hence, (\ref{pf.prop.stir2.0.indhyp}) yields $%
%TCIMACRO{\QDATOPD{\{}{\}}{k-1}{n}}%
%BeginExpansion
\genfrac{\{}{\}}{0pt}{0}{k-1}{n}%
%EndExpansion
=0$. Now, (\ref{eq.def.stir2.m}) (applied to $m=k$) yields%
\[%
%TCIMACRO{\QDATOPD{\{}{\}}{k}{n}}%
%BeginExpansion
\genfrac{\{}{\}}{0pt}{0}{k}{n}%
%EndExpansion
=n\underbrace{%
%TCIMACRO{\QDATOPD{\{}{\}}{k-1}{n}}%
%BeginExpansion
\genfrac{\{}{\}}{0pt}{0}{k-1}{n}%
%EndExpansion
}_{=0}+\underbrace{%
%TCIMACRO{\QDATOPD{\{}{\}}{k-1}{n-1}}%
%BeginExpansion
\genfrac{\{}{\}}{0pt}{0}{k-1}{n-1}%
%EndExpansion
}_{=0}=n0+0=0.
\]
\end{verlong}
Now, forget that we fixed $n$. We thus have shown that for each $n\in
\mathbb{Z}$ satisfying $n\notin\left\{ 0,1,\ldots,k\right\} $, we have $%
%TCIMACRO{\QDATOPD{\{}{\}}{k}{n}}%
%BeginExpansion
\genfrac{\{}{\}}{0pt}{0}{k}{n}%
%EndExpansion
=0$. In other words, Proposition \ref{prop.stir2.0} holds when $m=k$. This
completes the induction step. Thus, the proof of Proposition
\ref{prop.stir2.0} is complete.
\end{proof}
\begin{lemma}
\label{lem.j+1x}Let $j\in\mathbb{N}$ and $x\in\mathbb{Q}$. Then,
\[
j!\left( x-j\right) \dbinom{x}{j}=\left( j+1\right) !\dbinom{x}{j+1}.
\]
\end{lemma}
\begin{proof}
[Proof of Lemma \ref{lem.j+1x}.]We have $j\in\mathbb{N}$. Thus, the definition
of $\dbinom{x}{j}$ yields%
\[
\dbinom{x}{j}=\dfrac{x\left( x-1\right) \cdots\left( x-j+1\right) }{j!}.
\]
Hence,%
\begin{align}
j!\left( x-j\right) \underbrace{\dbinom{x}{j}}_{=\dfrac{x\left( x-1\right)
\cdots\left( x-j+1\right) }{j!}} & =j!\left( x-j\right) \cdot
\dfrac{x\left( x-1\right) \cdots\left( x-j+1\right) }{j!}\nonumber\\
& =\left( x-j\right) \cdot\left( x\left( x-1\right) \cdots\left(
x-j+1\right) \right) \nonumber\\
& =\left( x\left( x-1\right) \cdots\left( x-j+1\right) \right)
\cdot\left( x-j\right) \nonumber\\
& =x\left( x-1\right) \cdots\left( x-j\right) . \label{pf.lem.j+1x.1}%
\end{align}
On the other hand, $j+1\in\mathbb{N}$ (since $j\in\mathbb{N}$). Hence, the
definition of $\dbinom{x}{j+1}$ yields%
\[
\dbinom{x}{j+1}=\dfrac{x\left( x-1\right) \cdots\left( x-\left(
j+1\right) +1\right) }{\left( j+1\right) !}.
\]
Hence,%
\begin{align*}
\left( j+1\right) !\dbinom{x}{j+1} & =x\left( x-1\right) \cdots\left(
x-\left( j+1\right) +1\right) \\
& =x\left( x-1\right) \cdots\left( x-j\right) \ \ \ \ \ \ \ \ \ \ \left(
\text{since }x-\left( j+1\right) +1=x-j\right) \\
& =j!\left( x-j\right) \dbinom{x}{j}\ \ \ \ \ \ \ \ \ \ \left( \text{by
(\ref{pf.lem.j+1x.1})}\right) .
\end{align*}
This proves Lemma \ref{lem.j+1x}.
\end{proof}
\begin{proposition}
\label{prop.stir2.inter}Let $m\in\mathbb{N}$ and $x\in\mathbb{Q}$. Then,%
\[
x^{m}=\sum_{j=0}^{m}j!%
%TCIMACRO{\QDATOPD{\{}{\}}{m}{j}}%
%BeginExpansion
\genfrac{\{}{\}}{0pt}{0}{m}{j}%
%EndExpansion
\dbinom{x}{j}.
\]
\end{proposition}
\begin{proof}
[Proof of Proposition \ref{prop.stir2.inter}.]We shall prove Proposition
\ref{prop.stir2.inter} by induction on $m$:
\begin{vershort}
\textit{Induction base:} It is straightforward to see that Proposition
\ref{prop.stir2.inter} holds when $m=0$. This completes the induction base.
\end{vershort}
\begin{verlong}
\textit{Induction base:} Proposition \ref{prop.stir2.inter} holds when
$m=0$\ \ \ \ \footnote{\textit{Proof.} Applying (\ref{eq.def.stir2.0}) to
$n=0$, we obtain $%
%TCIMACRO{\QDATOPD{\{}{\}}{0}{0}}%
%BeginExpansion
\genfrac{\{}{\}}{0pt}{0}{0}{0}%
%EndExpansion
=%
\begin{cases}
1, & \text{if }0=0;\\
0, & \text{if }0\neq0
\end{cases}
=1$ (since $0=0$). Now,%
\[
\sum_{j=0}^{0}j!%
%TCIMACRO{\QDATOPD{\{}{\}}{0}{j}}%
%BeginExpansion
\genfrac{\{}{\}}{0pt}{0}{0}{j}%
%EndExpansion
\dbinom{x}{j}=\underbrace{0!}_{=1}\underbrace{%
%TCIMACRO{\QDATOPD{\{}{\}}{0}{0}}%
%BeginExpansion
\genfrac{\{}{\}}{0pt}{0}{0}{0}%
%EndExpansion
}_{=1}\dbinom{x}{0}=\dbinom{x}{0}=1
\]
(by Proposition \ref{prop.binom.00} (applied to $x$ instead of $m$)).
Comparing this with $x^{0}=1$, we obtain%
\[
x^{0}=\sum_{j=0}^{0}j!%
%TCIMACRO{\QDATOPD{\{}{\}}{0}{j}}%
%BeginExpansion
\genfrac{\{}{\}}{0pt}{0}{0}{j}%
%EndExpansion
\dbinom{x}{j}.
\]
In other words, Proposition \ref{prop.stir2.inter} holds when $m=0$. Qed.}.
This completes the induction base.
\end{verlong}
\textit{Induction step:} Let $k$ be a positive integer. Assume that
Proposition \ref{prop.stir2.inter} holds when $m=k-1$. We must now prove that
Proposition \ref{prop.stir2.inter} holds when $m=k$.
We have assumed that Proposition \ref{prop.stir2.inter} holds when $m=k-1$. In
other words, we have%
\[
x^{k-1}=\sum_{j=0}^{k-1}j!%
%TCIMACRO{\QDATOPD{\{}{\}}{k-1}{j}}%
%BeginExpansion
\genfrac{\{}{\}}{0pt}{0}{k-1}{j}%
%EndExpansion
\dbinom{x}{j}.
\]
Multiplying both sides of this equality by $x$, we obtain%
\begin{align}
x^{k-1}x & =\left( \sum_{j=0}^{k-1}j!%
%TCIMACRO{\QDATOPD{\{}{\}}{k-1}{j}}%
%BeginExpansion
\genfrac{\{}{\}}{0pt}{0}{k-1}{j}%
%EndExpansion
\dbinom{x}{j}\right) x=\sum_{j=0}^{k-1}j!%
%TCIMACRO{\QDATOPD{\{}{\}}{k-1}{j}}%
%BeginExpansion
\genfrac{\{}{\}}{0pt}{0}{k-1}{j}%
%EndExpansion
\dbinom{x}{j}\underbrace{x}_{=j+\left( x-j\right) }\nonumber\\
& =\sum_{j=0}^{k-1}\underbrace{j!%
%TCIMACRO{\QDATOPD{\{}{\}}{k-1}{j}}%
%BeginExpansion
\genfrac{\{}{\}}{0pt}{0}{k-1}{j}%
%EndExpansion
\dbinom{x}{j}\left( j+\left( x-j\right) \right) }_{=j!%
%TCIMACRO{\QDATOPD{\{}{\}}{k-1}{j}}%
%BeginExpansion
\genfrac{\{}{\}}{0pt}{0}{k-1}{j}%
%EndExpansion
\dbinom{x}{j}j+j!%
%TCIMACRO{\QDATOPD{\{}{\}}{k-1}{j}}%
%BeginExpansion
\genfrac{\{}{\}}{0pt}{0}{k-1}{j}%
%EndExpansion
\dbinom{x}{j}\left( x-j\right) }\nonumber\\
& =\sum_{j=0}^{k-1}\left( j!%
%TCIMACRO{\QDATOPD{\{}{\}}{k-1}{j}}%
%BeginExpansion
\genfrac{\{}{\}}{0pt}{0}{k-1}{j}%
%EndExpansion
\dbinom{x}{j}j+j!%
%TCIMACRO{\QDATOPD{\{}{\}}{k-1}{j}}%
%BeginExpansion
\genfrac{\{}{\}}{0pt}{0}{k-1}{j}%
%EndExpansion
\dbinom{x}{j}\left( x-j\right) \right) \nonumber\\
& =\sum_{j=0}^{k-1}j!%
%TCIMACRO{\QDATOPD{\{}{\}}{k-1}{j}}%
%BeginExpansion
\genfrac{\{}{\}}{0pt}{0}{k-1}{j}%
%EndExpansion
\dbinom{x}{j}j+\sum_{j=0}^{k-1}j!%
%TCIMACRO{\QDATOPD{\{}{\}}{k-1}{j}}%
%BeginExpansion
\genfrac{\{}{\}}{0pt}{0}{k-1}{j}%
%EndExpansion
\dbinom{x}{j}\left( x-j\right) . \label{pf.prop.stir2.inter.1}%
\end{align}
\begin{vershort}
But Proposition \ref{prop.stir2.0} (applied to $m=k-1$ and $n=k$) yields $%
%TCIMACRO{\QDATOPD{\{}{\}}{k-1}{k}}%
%BeginExpansion
\genfrac{\{}{\}}{0pt}{0}{k-1}{k}%
%EndExpansion
=0$, whereas Proposition \ref{prop.stir2.0} (applied to $m=k-1$ and $n=-1$)
yields $%
%TCIMACRO{\QDATOPD{\{}{\}}{k-1}{-1}}%
%BeginExpansion
\genfrac{\{}{\}}{0pt}{0}{k-1}{-1}%
%EndExpansion
=0$.
\end{vershort}
\begin{verlong}
But $k-1\in\mathbb{N}$ (since $k$ is a positive integer) and $k\notin\left\{
0,1,\ldots,k-1\right\} $\ \ \ \ \footnote{\textit{Proof.} Assume the
contrary. Thus, $k\in\left\{ 0,1,\ldots,k-1\right\} $. Hence, $k\leq k-1-1$, which is absurd. Thus, we have
found a contradiction. This contradiction shows that our assumption was wrong,
qed.}. Hence, Proposition \ref{prop.stir2.0} (applied to $m=k-1$ and $n=-1$)
yields $%
%TCIMACRO{\QDATOPD{\{}{\}}{k-1}{-1}}%
%BeginExpansion
\genfrac{\{}{\}}{0pt}{0}{k-1}{-1}%
%EndExpansion
=0$.
\end{verlong}
But (\ref{eq.def.stir2.m}) (applied to $m=k$ and $n=j$) yields%
\begin{equation}%
%TCIMACRO{\QDATOPD{\{}{\}}{k}{j}}%
%BeginExpansion
\genfrac{\{}{\}}{0pt}{0}{k}{j}%
%EndExpansion
=j%
%TCIMACRO{\QDATOPD{\{}{\}}{k-1}{j}}%
%BeginExpansion
\genfrac{\{}{\}}{0pt}{0}{k-1}{j}%
%EndExpansion
+%
%TCIMACRO{\QDATOPD{\{}{\}}{k-1}{j-1}}%
%BeginExpansion
\genfrac{\{}{\}}{0pt}{0}{k-1}{j-1}%
%EndExpansion
. \label{pf.prop.stir2.inter.2}%
\end{equation}
We have $k\in\mathbb{N}$ (since $k$ is a positive integer), so that
$k\in\left\{ 0,1,\ldots,k\right\} $. Now,%
\begin{align*}
& \sum_{j=0}^{k}j!%
%TCIMACRO{\QDATOPD{\{}{\}}{k-1}{j}}%
%BeginExpansion
\genfrac{\{}{\}}{0pt}{0}{k-1}{j}%
%EndExpansion
\dbinom{x}{j}j\\
& =\sum_{j=0}^{k-1}j!%
%TCIMACRO{\QDATOPD{\{}{\}}{k-1}{j}}%
%BeginExpansion
\genfrac{\{}{\}}{0pt}{0}{k-1}{j}%
%EndExpansion
\dbinom{x}{j}j+k!\underbrace{%
%TCIMACRO{\QDATOPD{\{}{\}}{k-1}{k}}%
%BeginExpansion
\genfrac{\{}{\}}{0pt}{0}{k-1}{k}%
%EndExpansion
}_{=0}\dbinom{x}{k}k\\
& \ \ \ \ \ \ \ \ \ \ \left(
\begin{array}
[c]{c}%
\text{here, we have split off the addend for }j=k\text{ from the sum}\\
\text{(since }k\in\left\{ 0,1,\ldots,k\right\} \text{)}%
\end{array}
\right) \\
& =\sum_{j=0}^{k-1}j!%
%TCIMACRO{\QDATOPD{\{}{\}}{k-1}{j}}%
%BeginExpansion
\genfrac{\{}{\}}{0pt}{0}{k-1}{j}%
%EndExpansion
\dbinom{x}{j}j+\underbrace{k!0\dbinom{x}{k}k}_{=0}=\sum_{j=0}^{k-1}j!%
%TCIMACRO{\QDATOPD{\{}{\}}{k-1}{j}}%
%BeginExpansion
\genfrac{\{}{\}}{0pt}{0}{k-1}{j}%
%EndExpansion
\dbinom{x}{j}j,
\end{align*}
so that%
\begin{equation}
\sum_{j=0}^{k-1}j!%
%TCIMACRO{\QDATOPD{\{}{\}}{k-1}{j}}%
%BeginExpansion
\genfrac{\{}{\}}{0pt}{0}{k-1}{j}%
%EndExpansion
\dbinom{x}{j}j=\sum_{j=0}^{k}j!%
%TCIMACRO{\QDATOPD{\{}{\}}{k-1}{j}}%
%BeginExpansion
\genfrac{\{}{\}}{0pt}{0}{k-1}{j}%
%EndExpansion
\dbinom{x}{j}j. \label{pf.prop.stir2.inter.3}%
\end{equation}
Also, $0\in\left\{ 0,1,\ldots,k\right\} $ (since $k\in\mathbb{N}$). Now,%
\begin{align*}
& \sum_{j=0}^{k-1}j!\underbrace{%
%TCIMACRO{\QDATOPD{\{}{\}}{k-1}{j}}%
%BeginExpansion
\genfrac{\{}{\}}{0pt}{0}{k-1}{j}%
%EndExpansion
\dbinom{x}{j}\left( x-j\right) }_{=\left( x-j\right) \dbinom{x}{j}%
%TCIMACRO{\QDATOPD{\{}{\}}{k-1}{j}}%
%BeginExpansion
\genfrac{\{}{\}}{0pt}{0}{k-1}{j}%
%EndExpansion
}\\
& =\sum_{j=0}^{k-1}\underbrace{j!\left( x-j\right) \dbinom{x}{j}%
}_{\substack{=\left( j+1\right) !\dbinom{x}{j+1}\\\text{(by Lemma
\ref{lem.j+1x})}}}\underbrace{%
%TCIMACRO{\QDATOPD{\{}{\}}{k-1}{j}}%
%BeginExpansion
\genfrac{\{}{\}}{0pt}{0}{k-1}{j}%
%EndExpansion
}_{\substack{=%
%TCIMACRO{\QDATOPD{\{}{\}}{k-1}{\left( j+1\right) -1}}%
%BeginExpansion
\genfrac{\{}{\}}{0pt}{0}{k-1}{\left( j+1\right) -1}%
%EndExpansion
\\\text{(since }j=\left( j+1\right) -1\text{)}}}\\
& =\sum_{j=0}^{k-1}\left( j+1\right) !\dbinom{x}{j+1}%
%TCIMACRO{\QDATOPD{\{}{\}}{k-1}{\left( j+1\right) -1}}%
%BeginExpansion
\genfrac{\{}{\}}{0pt}{0}{k-1}{\left( j+1\right) -1}%
%EndExpansion
\\
& =\sum_{j=1}^{k}j!\dbinom{x}{j}%
%TCIMACRO{\QDATOPD{\{}{\}}{k-1}{j-1}}%
%BeginExpansion
\genfrac{\{}{\}}{0pt}{0}{k-1}{j-1}%
%EndExpansion
\\
& \ \ \ \ \ \ \ \ \ \ \left( \text{here, we have substituted }j\text{ for
}j+1\text{ in the sum}\right) .
\end{align*}
Comparing this with%
\begin{align*}
& \sum_{j=0}^{k}j!\dbinom{x}{j}%
%TCIMACRO{\QDATOPD{\{}{\}}{k-1}{j-1}}%
%BeginExpansion
\genfrac{\{}{\}}{0pt}{0}{k-1}{j-1}%
%EndExpansion
\\
& =\sum_{j=1}^{k}j!\dbinom{x}{j}%
%TCIMACRO{\QDATOPD{\{}{\}}{k-1}{j-1}}%
%BeginExpansion
\genfrac{\{}{\}}{0pt}{0}{k-1}{j-1}%
%EndExpansion
+0!\dbinom{x}{0}\underbrace{%
%TCIMACRO{\QDATOPD{\{}{\}}{k-1}{0-1}}%
%BeginExpansion
\genfrac{\{}{\}}{0pt}{0}{k-1}{0-1}%
%EndExpansion
}_{=%
%TCIMACRO{\QDATOPD{\{}{\}}{k-1}{-1}}%
%BeginExpansion
\genfrac{\{}{\}}{0pt}{0}{k-1}{-1}%
%EndExpansion
=0}\\
& \ \ \ \ \ \ \ \ \ \ \left(
\begin{array}
[c]{c}%
\text{here, we have split off the addend for }j=0\text{ from the sum}\\
\text{(since }0\in\left\{ 0,1,\ldots,k\right\} \text{)}%
\end{array}
\right) \\
& =\sum_{j=1}^{k}j!\dbinom{x}{j}%
%TCIMACRO{\QDATOPD{\{}{\}}{k-1}{j-1}}%
%BeginExpansion
\genfrac{\{}{\}}{0pt}{0}{k-1}{j-1}%
%EndExpansion
+\underbrace{0!\dbinom{x}{0}0}_{=0}=\sum_{j=1}^{k}j!\dbinom{x}{j}%
%TCIMACRO{\QDATOPD{\{}{\}}{k-1}{j-1}}%
%BeginExpansion
\genfrac{\{}{\}}{0pt}{0}{k-1}{j-1}%
%EndExpansion
,
\end{align*}
we find%
\begin{equation}
\sum_{j=0}^{k-1}j!%
%TCIMACRO{\QDATOPD{\{}{\}}{k-1}{j}}%
%BeginExpansion
\genfrac{\{}{\}}{0pt}{0}{k-1}{j}%
%EndExpansion
\dbinom{x}{j}\left( x-j\right) =\sum_{j=0}^{k}j!\dbinom{x}{j}%
%TCIMACRO{\QDATOPD{\{}{\}}{k-1}{j-1}}%
%BeginExpansion
\genfrac{\{}{\}}{0pt}{0}{k-1}{j-1}%
%EndExpansion
. \label{pf.prop.stir2.inter.4}%
\end{equation}
Comparing the equality (\ref{pf.prop.stir2.inter.1}) with $x^{k-1}x=x^{k}$, we
find%
\begin{align*}
x^{k} & =\underbrace{\sum_{j=0}^{k-1}j!%
%TCIMACRO{\QDATOPD{\{}{\}}{k-1}{j}}%
%BeginExpansion
\genfrac{\{}{\}}{0pt}{0}{k-1}{j}%
%EndExpansion
\dbinom{x}{j}j}_{\substack{=\sum_{j=0}^{k}j!%
%TCIMACRO{\QDATOPD{\{}{\}}{k-1}{j}}%
%BeginExpansion
\genfrac{\{}{\}}{0pt}{0}{k-1}{j}%
%EndExpansion
\dbinom{x}{j}j\\\text{(by (\ref{pf.prop.stir2.inter.3}))}}}+\underbrace{\sum
_{j=0}^{k-1}j!%
%TCIMACRO{\QDATOPD{\{}{\}}{k-1}{j}}%
%BeginExpansion
\genfrac{\{}{\}}{0pt}{0}{k-1}{j}%
%EndExpansion
\dbinom{x}{j}\left( x-j\right) }_{\substack{=\sum_{j=0}^{k}j!\dbinom{x}{j}%
%TCIMACRO{\QDATOPD{\{}{\}}{k-1}{j-1}}%
%BeginExpansion
\genfrac{\{}{\}}{0pt}{0}{k-1}{j-1}%
%EndExpansion
\\\text{(by (\ref{pf.prop.stir2.inter.4}))}}}\\
& =\sum_{j=0}^{k}j!%
%TCIMACRO{\QDATOPD{\{}{\}}{k-1}{j}}%
%BeginExpansion
\genfrac{\{}{\}}{0pt}{0}{k-1}{j}%
%EndExpansion
\dbinom{x}{j}j+\sum_{j=0}^{k}j!\dbinom{x}{j}%
%TCIMACRO{\QDATOPD{\{}{\}}{k-1}{j-1}}%
%BeginExpansion
\genfrac{\{}{\}}{0pt}{0}{k-1}{j-1}%
%EndExpansion
\\
& =\sum_{j=0}^{k}\underbrace{\left( j!%
%TCIMACRO{\QDATOPD{\{}{\}}{k-1}{j}}%
%BeginExpansion
\genfrac{\{}{\}}{0pt}{0}{k-1}{j}%
%EndExpansion
\dbinom{x}{j}j+j!\dbinom{x}{j}%
%TCIMACRO{\QDATOPD{\{}{\}}{k-1}{j-1}}%
%BeginExpansion
\genfrac{\{}{\}}{0pt}{0}{k-1}{j-1}%
%EndExpansion
\right) }_{=j!\left( j%
%TCIMACRO{\QDATOPD{\{}{\}}{k-1}{j}}%
%BeginExpansion
\genfrac{\{}{\}}{0pt}{0}{k-1}{j}%
%EndExpansion
+%
%TCIMACRO{\QDATOPD{\{}{\}}{k-1}{j-1}}%
%BeginExpansion
\genfrac{\{}{\}}{0pt}{0}{k-1}{j-1}%
%EndExpansion
\right) \dbinom{x}{j}}\\
& =\sum_{j=0}^{k}j!\underbrace{\left( j%
%TCIMACRO{\QDATOPD{\{}{\}}{k-1}{j}}%
%BeginExpansion
\genfrac{\{}{\}}{0pt}{0}{k-1}{j}%
%EndExpansion
+%
%TCIMACRO{\QDATOPD{\{}{\}}{k-1}{j-1}}%
%BeginExpansion
\genfrac{\{}{\}}{0pt}{0}{k-1}{j-1}%
%EndExpansion
\right) }_{\substack{=%
%TCIMACRO{\QDATOPD{\{}{\}}{k}{j}}%
%BeginExpansion
\genfrac{\{}{\}}{0pt}{0}{k}{j}%
%EndExpansion
\\\text{(by (\ref{pf.prop.stir2.inter.2}))}}}\dbinom{x}{j}=\sum_{j=0}^{k}j!%
%TCIMACRO{\QDATOPD{\{}{\}}{k}{j}}%
%BeginExpansion
\genfrac{\{}{\}}{0pt}{0}{k}{j}%
%EndExpansion
\dbinom{x}{j}.
\end{align*}
In other words, Proposition \ref{prop.stir2.inter} holds when $m=k$. This
completes the induction step. Thus, Proposition \ref{prop.stir2.inter} is proven.
\end{proof}
Next, we shall prove another basic identity about binomial coefficients,
sometimes known as the \textit{hockey-stick identity} (in this or another
equivalent form):
\begin{proposition}
\label{prop.binom.downdiag}Let $j\in\mathbb{N}$ and $h\in\mathbb{N}$. Then,%
\[
\sum_{x=0}^{h}\dbinom{x}{j}=\dbinom{h+1}{j+1}.
\]
\end{proposition}
\begin{proof}
[Proof of Proposition \ref{prop.binom.downdiag}.]For each $x\in\mathbb{N}$, we
have%
\begin{equation}
\dbinom{x}{j}=\dbinom{x+1}{j+1}-\dbinom{x}{j+1}
\label{pf.prop.binom.downdiag.1}%
\end{equation}
\footnote{\textit{Proof of (\ref{pf.prop.binom.downdiag.1}):} Let
$x\in\mathbb{N}$. Then, Proposition \ref{prop.binom.rec.neg} (applied to
$m=x+1$ and $n=j+1$) yields%
\[
\dbinom{x+1}{j+1}=\dbinom{\left( x+1\right) -1}{\left( j+1\right)
-1}+\dbinom{\left( x+1\right) -1}{j+1}=\dbinom{x}{j}+\dbinom{x}{j+1}%
\]
(since $\left( x+1\right) -1=x$ and $\left( j+1\right) -1=j$). Solving
this equation for $\dbinom{x}{j}$, we obtain $\dbinom{x}{j}=\dbinom{x+1}%
{j+1}-\dbinom{x}{j+1}$. This proves (\ref{pf.prop.binom.downdiag.1}).}.
Proposition \ref{prop.binom.0} (applied to $m=0$ and $n=j+1$) yields
$\dbinom{0}{j+1}=0$ (since $0\leq j0$). In other words, $q\in\mathbb{N}$.
Proposition \ref{prop.fermat} yields $a^{p}\equiv a\operatorname{mod}p$.
Hence,
\begin{equation}
a^{\left( p-1\right) m}\equiv a\operatorname{mod}%
p\ \ \ \ \ \ \ \ \ \ \text{for each }m\in\mathbb{N}
\label{pf.cor.fermat.cong.short.m}%
\end{equation}
\footnote{\textit{Proof of (\ref{pf.cor.fermat.cong.short.m}):} We shall prove
(\ref{pf.cor.fermat.cong.short.m}) by induction on $m$:
\par
\textit{Induction base:} We have $a^{\left( p-1\right) 0+1}=a^{1}=a\equiv
a\operatorname{mod}p$. In other words, (\ref{pf.cor.fermat.cong.short.m})
holds for $m=0$. This completes the induction base.
\par
\textit{Induction step:} Let $n\in\mathbb{N}$. Assume that
(\ref{pf.cor.fermat.cong.short.m}) holds for $m=n$. We must prove that
(\ref{pf.cor.fermat.cong.short.m}) holds for $m=n+1$.
\par
We have assumed that (\ref{pf.cor.fermat.cong.short.m}) holds for $m=n$. In
other words, $a^{\left( p-1\right) n+1}\equiv a\operatorname{mod}p$. Now,
$\left( p-1\right) \left( n+1\right) +1=\left( \left( p-1\right)
n+1\right) +\left( p-1\right) $. Hence,%
\[
a^{\left( p-1\right) \left( n+1\right) +1}=a^{\left( \left( p-1\right)
n+1\right) +\left( p-1\right) }=\underbrace{a^{\left( p-1\right) n+1}%
}_{\equiv a\operatorname{mod}p}a^{p-1}\equiv aa^{p-1}=a^{p}\equiv
a\operatorname{mod}p.
\]
In other words, (\ref{pf.cor.fermat.cong.short.m}) holds for $m=n+1$. This
completes the induction step. Hence, (\ref{pf.cor.fermat.cong.short.m}) is
proven.}. Applying this to $m=q$, we obtain $a^{\left( p-1\right) q+1}\equiv
a\operatorname{mod}p$ (since $q\in\mathbb{N}$). Multiplying both sides of this
congruence with $a^{r-1}$, we find $a^{\left( p-1\right) q+1}a^{r-1}\equiv
aa^{r-1}=a^{r}\operatorname{mod}p$. Thus,%
\[
a^{r}\equiv a^{\left( p-1\right) q+1}a^{r-1}=a^{\left( p-1\right)
q+1+\left( r-1\right) }=a^{k}\operatorname{mod}p
\]
(since $\underbrace{\left( p-1\right) q}_{=k-r}+1+\left( r-1\right)
=k-r+1+\left( r-1\right) =k$). This proves Corollary \ref{cor.fermat.cong}.
\end{proof}
\end{vershort}
\begin{verlong}
\begin{proof}
[Proof of Corollary \ref{cor.fermat.cong}.]We have $r\equiv
k\operatorname{mod}p-1$ (since $r$ is the remainder of $k$ upon division by
$p-1$), but $k\not \equiv 0\operatorname{mod}p-1$ (since $k$ is not a multiple
of $p-1$). Hence, $r\equiv k\not \equiv 0\operatorname{mod}p-1$, so that
$r\neq0$.
Also, $r\in\left\{ 0,1,\ldots,\left( p-1\right) -1\right\} $ (since $r$ is
a remainder upon division by $p-1$). Hence, $r\in\left\{ 0,1,\ldots,\left(
p-1\right) -1\right\} \subseteq\mathbb{N}$, so that $r$ is a positive
integer (since $r\neq0$). Thus, $r-1\in\mathbb{N}$. Hence, the integer
$a^{r-1}$ is well-defined.
We have $r\equiv k\operatorname{mod}p-1$, so that $k\equiv r\operatorname{mod}%
p-1$. In other words, $p-1\mid k-r$. Hence, there exists a $q\in\mathbb{Z}$
such that $k-r=\left( p-1\right) q$. Consider this $q$. We have
$q\in\mathbb{N}$\ \ \ \ \footnote{\textit{Proof.} Assume the contrary. Thus,
$q\notin\mathbb{N}$. Combining $q\in\mathbb{Z}$ with $q\notin\mathbb{N}$, we
obtain $q\in\mathbb{Z}\setminus\mathbb{N}=\left\{ -1,-2,-3,\ldots\right\} $,
so that $q\leq-1$. But $p-1\geq0$ (since $p$ is a positive integer). Hence,
from $q\leq-1$, we obtain $\left( p-1\right) \underbrace{q}_{\leq-1}%
\leq\left( p-1\right) \left( -1\right) =1-p$. Now, $k-r=\left(
p-1\right) q\leq1-p$. But $r\in\left\{ 0,1,\ldots,\left( p-1\right)
-1\right\} $, so that $r\leq\left( p-1\right) -1$. Adding this inequality
to $k-r\leq1-p$, we find $\left( k-r\right) +r\leq\left( 1-p\right)
+\left( \left( p-1\right) -1\right) =-1<0$, so that $k=\left( k-r\right)
+r<0$. This contradicts the fact that $k$ is positive. This contradiction
shows that our assumption was false, qed.} and $\underbrace{\left(
p-1\right) q}_{=k-r}+1+\left( r-1\right) =k-r+1+\left( r-1\right) =k$.
Proposition \ref{prop.fermat} yields $a^{p}\equiv a\operatorname{mod}p$.
Hence,
\begin{equation}
a^{\left( p-1\right) m+1}\equiv a\operatorname{mod}%
p\ \ \ \ \ \ \ \ \ \ \text{for each }m\in\mathbb{N}
\label{pf.cor.fermat.cong.m}%
\end{equation}
\footnote{\textit{Proof of (\ref{pf.cor.fermat.cong.m}):} We shall prove
(\ref{pf.cor.fermat.cong.m}) by induction on $m$:
\par
\textit{Induction base:} We have $\left( p-1\right) 0+1=1$, so that
$a^{\left( p-1\right) 0+1}=a^{1}=a\equiv a\operatorname{mod}p$. In other
words, (\ref{pf.cor.fermat.cong.m}) holds for $m=0$. This completes the
induction base.
\par
\textit{Induction step:} Let $n\in\mathbb{N}$. Assume that
(\ref{pf.cor.fermat.cong.m}) holds for $m=n$. We must prove that
(\ref{pf.cor.fermat.cong.m}) holds for $m=n+1$.
\par
We have assumed that (\ref{pf.cor.fermat.cong.m}) holds for $m=n$. In other
words, $a^{\left( p-1\right) n+1}\equiv a\operatorname{mod}p$. Now, $\left(
p-1\right) \left( n+1\right) +1=\left( \left( p-1\right) n+1\right)
+\left( p-1\right) $. Hence,%
\[
a^{\left( p-1\right) \left( n+1\right) +1}=a^{\left( \left( p-1\right)
n+1\right) +\left( p-1\right) }=\underbrace{a^{\left( p-1\right) n+1}%
}_{\equiv a\operatorname{mod}p}a^{p-1}\equiv aa^{p-1}=a^{p}\equiv
a\operatorname{mod}p.
\]
In other words, (\ref{pf.cor.fermat.cong.m}) holds for $m=n+1$. This completes
the induction step. Hence, (\ref{pf.cor.fermat.cong.m}) is proven.}.
We can apply (\ref{pf.cor.fermat.cong.m}) to $m=q$ (since $q\in\mathbb{N}$).
Thus, we obtain $a^{\left( p-1\right) q+1}\equiv a\operatorname{mod}p$.
Multiplying both sides of this congruence with $a^{r-1}$, we find $a^{\left(
p-1\right) q+1}a^{r-1}\equiv aa^{r-1}=a^{r}\operatorname{mod}p$. Thus,%
\[
a^{r}\equiv a^{\left( p-1\right) q+1}a^{r-1}=a^{\left( p-1\right)
q+1+\left( r-1\right) }=a^{k}\operatorname{mod}p
\]
(since $\left( p-1\right) q+1+\left( r-1\right) =k$). In other words,
$a^{k}\equiv a^{r}\operatorname{mod}p$. This proves Corollary
\ref{cor.fermat.cong}.
\end{proof}
\end{verlong}
\begin{vershort}
\begin{proof}
[Proof of Theorem \ref{thm.powersums.p}.]If $k0$. Hence, $k$ is positive. Thus, $k$ is not a multiple of $p-1$
(because $k$ is not a positive multiple of $p-1$, but is positive).
Let $r$ be the remainder of $k$ upon division by $p-1$. Thus, $r\in\left\{
0,1,\ldots,\left( p-1\right) -1\right\} $, so that $r\in\mathbb{N}$ and
$r\leq\left( p-1\right) -11$ (since $p$ is a
prime) and thus $p-1>0$. Hence, $k\geq p-1>0$. In other words, $k$ is
positive. Hence, $k$ is not a multiple of $p-1$%
\ \ \ \ \footnote{\textit{Proof.} Assume the contrary. Thus, $k$ is a multiple
of $p-1$. Hence, $k$ is a positive multiple of $p-1$ (since $k$ is positive).
This contradicts the fact that $k$ is not a positive multiple of $p-1$. This
contradiction shows that our assumption was wrong. Qed.}.
Let $r$ be the remainder of $k$ upon division by $p-1$. Thus, $r\in\left\{
0,1,\ldots,\left( p-1\right) -1\right\} $, so that $r\in\mathbb{N}$ and
$r\leq\left( p-1\right) -1