%\documentclass[a4paper,12pt]{article}
\documentclass[10pt]{report}%
\usepackage{color}
\usepackage{amsthm, amssymb, amsmath}
\usepackage{amsmath}
\usepackage{amsfonts}
\usepackage{amssymb}%
\setcounter{MaxMatrixCols}{30}
%TCIDATA{OutputFilter=latex2.dll}
%TCIDATA{Version=5.00.0.2570}
%TCIDATA{LastRevised=Tuesday, April 21, 2009 00:38:33}
%TCIDATA{<META NAME="GraphicsSave" CONTENT="32">}
%TCIDATA{<META NAME="SaveForMode" CONTENT="1">}
\makeatletter
\newif\if@widepage \@widepagetrue
\newif\if@solin \@solintrue
\newif\if@english \@englishfalse
\newif\if@solwithprob \@solwithprobtrue
\DeclareOption{nowidepage}{\@widepagefalse}
\DeclareOption{widepage}{\@widepagetrue}
\DeclareOption{solwithprob}{\@solwithprobtrue}
\DeclareOption{onlysol}{\@solwithprobfalse}
\DeclareOption{solafter}{\@solinfalse}
\DeclareOption{solin}{\@solintrue}
\DeclareOption{english}{\@englishtrue}
\DeclareOption{hangul}{\@englishfalse} \ProcessOptions
\newtheorem{thm}{Theorem}[section]
\newtheorem{dfn}{Definition}[section]
\newtheorem{prp}{Proposition}[section]
\newtheorem{clm}{Claim}[section]
\newtheorem{fct}{Fact}[section]
\newtheorem{crl}{Corollary}[section]
\newtheorem{obs}{Observation}[section]
\newtheorem{lmm}{Lemma}[section]
\newtheorem{rmk}{\textsc{AFTERTHOUGHTS}}[section]
\newtheorem{rmrk}{Remark}[section]
\newtheorem{pr}{}[section]
\newtheorem{spr}{}[section]
\newtheorem{rfr}{References}[section]
\newtheorem{atr}{Problem}[section]
\newtheorem{prf}{Proof}[section]
\DeclareMathOperator{\lcm}{lcm}
\DeclareMathOperator{\ord}{ord}
\def\baselinestretch{1.3}
\if@widepage \input{a4wide.sty}\fi
\newlength{\Problen}
\newlength{\Probheadlen}
\newlength{\Probskip}
\Probheadlen 16mm \Probskip 3mm \Problen\textwidth
\addtolength\Problen{-\Probheadlen} \addtolength\Problen{-\Probskip}
\newcounter{Prob}
\newsavebox{\@syntest}
\newbox\@lastproblem
\if@english
\newenvironment{Prob}[1][]{\stepcounter{Prob}    \global\setbox\@lastproblem=\vbox\bgroup
\par\noindent\parbox[t]{\Probheadlen}{\raggedleft\fontsize{10}{10pt}\selectfont
{\bfseries\large \theProb}\\[-1.5mm]
\rule[1mm]{\Probheadlen}{.2mm}\\[-2mm]{\sffamily #1}}\hspace\Probskip    \begin{minipage}[t]{\Problen}}{\end{minipage}\par\vspace{3mm}\egroup    \unvcopy\@lastproblem}
\newenvironment{ProbK}{\begin{lrbox}{\@syntest}    \begin{minipage}\textwidth}{\end{minipage}\end{lrbox}}
\else
\newenvironment{ProbK}[1][]{\stepcounter{Prob}    \global\setbox\@lastproblem=\vbox\bgroup
\par\noindent\parbox[t]{\Probheadlen}{\raggedleft\fontsize{10}{10pt}\selectfont
{\bfseries\large \theProb}\\[-1.5mm]
\rule[1mm]{16mm}{.2mm}\\[-2mm]{\sffamily #1}}\hspace{\Probskip}    \begin{minipage}[t]{\Problen}}{\end{minipage}\par\vspace{3mm}\egroup    \unvcopy\@lastproblem}
\newenvironment{Prob}{\begin{lrbox}{\@syntest}    \begin{minipage}\textwidth}{\end{minipage}\end{lrbox}}
\fi
\newbox\@sol
\newbox\@temp
\newcommand{\makesolpage}{\if@solin\else\newpage\unvcopy\@sol\fi}
\def\lhead{\@ifnextchar[{\@xlhead}{\@ylhead}}
\def\@xlhead[#1]#2{\gdef\@elhead{#1}\gdef\@olhead{#2}}
\def\@ylhead#1{\gdef\@elhead{#1}\gdef\@olhead{#1}}
\def\chead{\@ifnextchar[{\@xchead}{\@ychead}}
\def\@xchead[#1]#2{\gdef\@echead{#1}\gdef\@ochead{#2}}
\def\@ychead#1{\gdef\@echead{#1}\gdef\@ochead{#1}}
\def\rhead{\@ifnextchar[{\@xrhead}{\@yrhead}}
\def\@xrhead[#1]#2{\gdef\@erhead{#1}\gdef\@orhead{#2}}
\def\@yrhead#1{\gdef\@erhead{#1}\gdef\@orhead{#1}}
\def\lfoot{\@ifnextchar[{\@xlfoot}{\@ylfoot}}
\def\@xlfoot[#1]#2{\gdef\@elfoot{#1}\gdef\@olfoot{#2}}
\def\@ylfoot#1{\gdef\@elfoot{#1}\gdef\@olfoot{#1}}
\def\cfoot{\@ifnextchar[{\@xcfoot}{\@ycfoot}}
\def\@xcfoot[#1]#2{\gdef\@ecfoot{#1}\gdef\@ocfoot{#2}}
\def\@ycfoot#1{\gdef\@ecfoot{#1}\gdef\@ocfoot{#1}}
\def\rfoot{\@ifnextchar[{\@xrfoot}{\@yrfoot}}
\def\@xrfoot[#1]#2{\gdef\@erfoot{#1}\gdef\@orfoot{#2}}
\def\@yrfoot#1{\gdef\@erfoot{#1}\gdef\@orfoot{#1}}
\newdimen\headrulewidth
\newdimen\footrulewidth
\newdimen\plainheadrulewidth
\newdimen\plainfootrulewidth
\newdimen\headwidth
\newif\if@fancyplain \@fancyplainfalse
\def\fancyplain#1#2{\if@fancyplain#1\else#2\fi}
\headrulewidth 0.4pt \footrulewidth\z@ \plainheadrulewidth\z@
\plainfootrulewidth\z@
\def\@fancyhead#1#2#3#4#5{#1\hbox to\headwidth{\vbox{\hbox
{\rlap{\parbox[b]{\headwidth}{\raggedright#2\strut}}\hfill
\parbox[b]{\headwidth}{\centering#3\strut}\hfill
\llap{\parbox[b]{\headwidth}{\raggedleft#4\strut}}}\headrule}}#5}
\def\@fancyfoot#1#2#3#4#5{#1\hbox to\headwidth{\vbox{\footrule
\hbox{\rlap{\parbox[t]{\headwidth}{\raggedright#2\strut}}\hfill
\parbox[t]{\headwidth}{\centering#3\strut}\hfill
\llap{\parbox[t]{\headwidth}{\raggedleft#4\strut}}}}}#5}
\def\headrule{{\if@fancyplain\headrulewidth\plainheadrulewidth\fi
\hrule\@height\headrulewidth\@width\headwidth
\vskip-\headrulewidth}}
\def\footrule{{\if@fancyplain\footrulewidth\plainfootrulewidth\fi
\vskip-0.3\normalbaselineskip\vskip-\footrulewidth
\hrule\@width\headwidth\@height\footrulewidth\vskip0.3\normalbaselineskip}}
\def\ps@orange{
\let\@mkboth\markboth
\@ifundefined{chapter}{\def\sectionmark##1{\markboth
{\uppercase{\ifnum \c@secnumdepth>\z@
\thesection\hskip 1em\relax \fi ##1}}{}}
\def\subsectionmark##1{\markright {\ifnum \c@secnumdepth >\@ne
\thesubsection\hskip 1em\relax \fi ##1}}}
{\def\chaptermark##1{\markboth {\uppercase{\ifnum
\c@secnumdepth>\m@ne
\@chapapp\ \thechapter. \ \fi ##1}}{}}
\def\sectionmark##1{\markright{\uppercase{\ifnum \c@secnumdepth >\z@
\thesection. \ \fi ##1}}}}
\lfoot{} \rfoot{\scriptsize \colorbox{white}{\textcolor{black}{\small{ \textsf{Problems in Elementary Number Theory \textbf{1}(2008) No. 1}}}}} \cfoot{}
\def\@oddhead{\@fancyhead\relax\@olhead\@ochead\@orhead\hss}
\def\@oddfoot{\@fancyfoot\relax\@olfoot\@ocfoot\@orfoot\hss}
\def\@evenhead{\@fancyhead\hss\@elhead\@echead\@erhead\relax}
\def\@evenfoot{\@fancyfoot\hss\@elfoot\@ecfoot\@erfoot\relax}
\headwidth\textwidth}
\newcommand{\ta}[4] {\lhead{ #1 #2}\chead{\bfseries\sffamily  #3}\rhead{\sffamily  \hspace{3.5cm} http://projectpen.wordpress.com  }\lfoot{\scriptsize #4}}
\makeatother
\ta{\textsc{Project PEN} }{\small }{}{}
\begin{document}
\pagenumbering{Roman}

\section{Binomial Sum Divisible by Primes}

\begin{ProbK}
[PEN E16]\textit{(MM, Problem 1392, George Andrews)}
Prove that for any positive integer $n$ and any prime $p$ in the interval
$\left]  n,\dfrac{4n}{3}\right]  $, $p$ divides
\[
\sum\limits_{j=0}^{n}{\dbinom{{n}}{{j}}}^{4}.
\]

\end{ProbK}

\textbf{Solution by Darij Grinberg.}

The problem can be vastly generalized:

\begin{quote}
\textbf{Theorem 1.} Let $\ell$ be a positive integer. If $n_{1},$ $n_{2},$
$...,$ $n_{\ell}$ are positive integers and $p$ is a prime such that $\left(
\ell-1\right)  \left(  p-1\right)  <\sum\limits_{i=1}^{\ell}n_{i}$ and
$n_{i}<p$ for every $i\in\left\{  1,2,...,\ell\right\}  $, then $p\mid
\sum\limits_{j=0}^{p-1}\left(  -1\right)  ^{\ell j}\prod\limits_{i=1}^{\ell
}\dbinom{n_{i}}{j}$.
\end{quote}

Before we prove this, we first show some basic facts about binomial
coefficients and remainders modulo primes. We recall how we define binomial coefficients:

\begin{quote}
\textbf{Definition.} The binomial coefficient $\dbinom{x}{u}$ is defined for
all reals $x$ and for all integers $u$ as follows: $\dbinom{x}{u}%
=\dfrac{x\cdot\left(  x-1\right)  \cdot...\cdot\left(  x-u+1\right)  }{u!}$ if
$u\geq0$, and $\dbinom{x}{u}=0$ if $u<0.$
\end{quote}

Note that the empty product evaluates to $1,$ and $0!=1,$ so this yields
\[
\dbinom{x}{0}=\dfrac{x\cdot\left(  x-1\right)  \cdot...\cdot\left(
x-0+1\right)  }{0!}=\dfrac{\text{empty product}}{0!}=\dfrac{1}{1}=1
\]
for every $x\in\mathbb{Z}.$

\begin{quote}
\textbf{Theorem 2, the upper negation identity.} If $n$ is a real, and $r$ is
an integer, then $\dbinom{-n}{r}=\left(  -1\right)  ^{r}\dbinom{n+r-1}{r}$.
\end{quote}

\textit{Proof of Theorem 2.} We distinguish two cases: the case $r<0$ and the
case $r\geq0$.

If $r<0,$ then $\dbinom{-n}{r}=0$ and $\dbinom{n+r-1}{r}=0,$ so that
$\dbinom{-n}{r}=\left(  -1\right)  ^{r}\dbinom{n+r-1}{r}$ ensues.

If $r\geq0,$ then, using the definition of binomial coefficients, we have%
\begin{align*}
\dbinom{-n}{r}  &  =\dfrac{\left(  -n\right)  \cdot\left(  -n-1\right)
\cdot...\cdot\left(  -n-r+1\right)  }{r!}=\left(  -1\right)  ^{r}\cdot
\dfrac{n\cdot\left(  n+1\right)  \cdot...\cdot\left(  n+r-1\right)  }{r!}\\
&  =\left(  -1\right)  ^{r}\cdot\dfrac{\left(  n+r-1\right)  \cdot
...\cdot\left(  n+1\right)  \cdot n}{r!}=\left(  -1\right)  ^{r}\cdot
\dbinom{n+r-1}{r}.
\end{align*}


Hence, in both cases $r<0$ and $r\geq0,$ we have established $\dbinom{-n}%
{r}=\left(  -1\right)  ^{r}\dbinom{n+r-1}{r}.$ Thus, $\dbinom{-n}{r}=\left(
-1\right)  ^{r}\dbinom{n+r-1}{r}$ always holds. This proves Theorem 2.

\begin{quote}
\textbf{Theorem 3.} If $p$ is a prime, if $u$ and $v$ are two integers such
that $u\equiv v\mod p$, and if $k$ is an integer such that $k<p$, then
$\dbinom{u}{k}\equiv\dbinom{v}{k}\mod p$.
\end{quote}

\textit{Proof of Theorem 3.} If $k<0$, then $\dbinom{u}{k}=\dbinom{v}{k}$
(because $\dbinom{u}{k}=0$ and $\dbinom{v}{k}=0$), so that Theorem 3 is
trivial. Thus, it remains to consider the case $k\geq0$ only. In this case,
$k!$ is coprime with $p$ (since $k!=1\cdot2\cdot...\cdot k$, and all numbers
$1$, $2$, ..., $k$ are coprime with $p$, since $p$ is a prime and $k<p$).

Now, $u\equiv v\mod p$ yields%
\begin{align*}
k!\cdot\dbinom{u}{k}  &  =k!\cdot\dfrac{u\cdot\left(  u-1\right)
\cdot...\cdot\left(  u-k+1\right)  }{k!}=u\cdot\left(  u-1\right)
\cdot...\cdot\left(  u-k+1\right) \\
&  \equiv v\cdot\left(  v-1\right)  \cdot...\cdot\left(  v-k+1\right)
=k!\cdot\dfrac{v\cdot\left(  v-1\right)  \cdot...\cdot\left(  v-k+1\right)
}{k!}=k!\cdot\dbinom{v}{k}\mod p.
\end{align*}


Since $k!$ is coprime with $p$, we can divide this congruence by $k!$, and
thus we get $\dbinom{u}{k}\equiv\dbinom{v}{k}\mod p$. Hence, Theorem 3 is proven.

Finally, a basic property of binomial coefficients:

\begin{quote}
\textbf{Theorem 4.} For every nonnegative integer $n$ and any integer $k$, we
have $\dbinom{n}{k}=\dbinom{n}{n-k}$.
\end{quote}

This is known, but it is important not to forget the condition that $n$ is
nonnegative (Theorem 4 would not hold without it!).

Now we will reprove an important fact:

\begin{quote}
\textbf{Theorem 5.} If $p$ is a prime, and $f\in\mathbb{Q}\left[  X\right]  $
is a polynomial of degree $<p-1$ such that $f\left(  j\right)  \in\mathbb{Z}$
for all $j\in\left\{  0,1,...,p-1\right\}  ,$ then $\sum\limits_{j=0}%
^{p-1}f\left(  j\right)  \equiv0\mod p$.
\end{quote}

Before we prove Theorem 5, we recall two lemmata:

\begin{quote}
\textbf{Theorem 6.} If $p$ is a prime and $i$ is an integer satisfying $0\leq
i\leq p-1$, then $\dbinom{p-1}{i}\equiv\left(  -1\right)  ^{i}\mod p$.

\textbf{Theorem 7.} If $N$ is a positive integer, and $f$ is a polynomial of
degree $<N,$ then $\sum\limits_{j=0}^{N}\left(  -1\right)  ^{j}\dbinom{N}%
{j}f\left(  j\right)  =0$.
\end{quote}

Theorem 6 appeared as Lemma 1 in [2], post \#2. Theorem 7 is a standard result
from finite differences theory.

\textit{Proof of Theorem 5.} Let $N=p-1.$ Then, $f$ is a polynomial of degree
$<N$ (since $f$ is a polynomial of degree $<p-1$). Thus, Theorem 7 yields
$\sum\limits_{j=0}^{N}\left(  -1\right)  ^{j}\dbinom{N}{j}f\left(  j\right)
=0$. Hence,%
\begin{align*}
0
&=\sum\limits_{j=0}^{N}\left(  -1\right)  ^{j}\dbinom{N}{j}f\left(  j\right)
=\sum\limits_{j=0}^{p-1}\left(  -1\right)  ^{j}\underbrace{\dbinom{p-1}{j}%
}_{\substack{\equiv\left(  -1\right)  ^{j}\mod p\\\text{by Theorem 6}%
}}f\left(  j\right) \\
& \equiv\sum\limits_{j=0}^{p-1}\underbrace{\left(
-1\right)  ^{j}\left(  -1\right)  ^{j}}_{\substack{=\left(  \left(  -1\right)
^{j}\right)  ^{2}=\left(  \left(  -1\right)  ^{2}\right)  ^{j}\\=1^{j}%
=1}}f\left(  j\right)
=\sum\limits_{j=0}^{p-1}f\left(  j\right)  \mod p.
\end{align*}
This proves Theorem 5.

\textit{Proof of Theorem 1.} The condition $\left(  \ell-1\right)  \left(
p-1\right)  <\sum\limits_{i=1}^{\ell}n_{i}$ rewrites as $\ell\left(
p-1\right)  -\left(  p-1\right)  <\sum\limits_{i=1}^{\ell}n_{i}.$
Equivalently, $\ell\left(  p-1\right)  -\sum\limits_{i=1}^{\ell}n_{i}<p-1.$

For every $i\in\left\{  1,2,...,\ell\right\}  ,$ we have $p-n_{i}-1\geq0$,
since $n_{i}<p$ yields $n_{i}+1\leq p$.

For every $i\in\left\{  1,2,...,\ell\right\}  $ and every integer $j$ with
$0\leq j<p$, we have%

\begin{align*}
\dbinom{n_{i}}{j}  &  =\dbinom{-\left(  -n_{i}\right)  }{j}=\left(  -1\right)
^{j}\dbinom{\left(  -n_{i}\right)  +j-1}{j}\ \ \ \ \ \ \ \ \ \ \left(
\text{after Theorem 2}\right) \\
&  \equiv\left(  -1\right)  ^{j}\dbinom{p-n_{i}+j-1}{j}\\
& \ \ \ \ \ \ \ \ \ \ \left(  \text{by Theorem 3, since }\left(  -n_{i}\right)
+j-1\equiv p-n_{i}+j-1\mod p\text{ and }j<p\right) \\
&  =\left(  -1\right)  ^{j}\dbinom{p-n_{i}+j-1}{\left(  p-n_{i}+j-1\right)
-j}\\
&  \ \ \ \ \ \ \ \ \ \ \left(  \text{by Theorem 4, since }p-n_{i}+j-1\text{ is
nonnegative, since }p-n_{i}-1\geq0\text{ and }j\geq0\right) \\
&  =\left(  -1\right)  ^{j}\dbinom{p-n_{i}+j-1}{p-n_{i}-1}=\left(  -1\right)
^{j}\dfrac{\prod\limits_{u=0}^{\left(  p-n_{i}-1\right)  -1}\left(  \left(
p-n_{i}+j-1\right)  -u\right)  }{\left(  p-n_{i}-1\right)  !}\mod p.
\end{align*}
Hence, for every integer $j$ with $0\leq j<p$, we have%
\begin{align*}
\prod\limits_{i=1}^{\ell}\dbinom{n_{i}}{j}  &  \equiv\prod\limits_{i=1}^{\ell
}\left(  -1\right)  ^{j}\dfrac{\prod\limits_{u=0}^{\left(  p-n_{i}-1\right)
-1}\left(  \left(  p-n_{i}+j-1\right)  -u\right)  }{\left(  p-n_{i}-1\right)
!}=\left(  \left(  -1\right)  ^{j}\right)  ^{\ell}\prod\limits_{i=1}^{\ell
}\dfrac{\prod\limits_{u=0}^{\left(  p-n_{i}-1\right)  -1}\left(  \left(
p-n_{i}+j-1\right)  -u\right)  }{\left(  p-n_{i}-1\right)  !}\\
&  =\left(  \left(  -1\right)  ^{j}\right)  ^{\ell}\dfrac{\prod\limits_{i=1}%
^{\ell}\prod\limits_{u=0}^{\left(  p-n_{i}-1\right)  -1}\left(  \left(
p-n_{i}+j-1\right)  -u\right)  }{\prod\limits_{i=1}^{\ell}\left(
p-n_{i}-1\right)  !}\mod p,
\end{align*}
so that%
\begin{align}
&  \prod\limits_{i=1}^{\ell}\left(  p-n_{i}-1\right)  !\cdot\left(  -1\right)
^{\ell j}\prod\limits_{i=1}^{\ell}\dbinom{n_{i}}{j}\nonumber\\
&  \equiv\prod\limits_{i=1}^{\ell}\left(  p-n_{i}-1\right)  !\cdot
\underbrace{\left(  -1\right)  ^{\ell j}\cdot\left(  \left(  -1\right)
^{j}\right)  ^{\ell}}_{\substack{=\left(  -1\right)  ^{\ell j}\cdot\left(
-1\right)  ^{\ell j}\\=\left(  -1\right)  ^{2\ell j}=1,\text{ since}\\2\ell
j\text{ is even}}}\dfrac{\prod\limits_{i=1}^{\ell}\prod\limits_{u=0}^{\left(
p-n_{i}-1\right)  -1}\left(  \left(  p-n_{i}+j-1\right)  -u\right)  }%
{\prod\limits_{i=1}^{\ell}\left(  p-n_{i}-1\right)  !}\nonumber\\
&  =\prod\limits_{i=1}^{\ell}\left(  p-n_{i}-1\right)  !\cdot\dfrac
{\prod\limits_{i=1}^{\ell}\prod\limits_{u=0}^{\left(  p-n_{i}-1\right)
-1}\left(  \left(  p-n_{i}+j-1\right)  -u\right)  }{\prod\limits_{i=1}^{\ell
}\left(  p-n_{i}-1\right)  !}\nonumber\\
&  =\prod\limits_{i=1}^{\ell}\prod\limits_{u=0}^{\left(  p-n_{i}-1\right)
-1}\left(  \left(  p-n_{i}+j-1\right)  -u\right)  \mod p. \label{1}%
\end{align}
Now, define a polynomial $f$ in one variable $X$ by%
\begin{equation}
f\left(  X\right)  =\prod\limits_{i=1}^{\ell}\prod\limits_{u=0}^{\left(
p-n_{i}-1\right)  -1}\left(  \left(  p-n_{i}+X-1\right)  -u\right)  .
\label{2}%
\end{equation}
Then,%
\begin{align*}
\deg f  &  =\deg\left(  \prod\limits_{i=1}^{\ell}\prod\limits_{u=0}^{\left(
p-n_{i}-1\right)  -1}\left(  \left(  p-n_{i}+X-1\right)  -u\right)  \right)
=\sum_{i=1}^{\ell}\sum_{u=0}^{\left(  p-n_{i}-1\right)  -1}\underbrace
{\deg\left(  \left(  p-n_{i}+X-1\right)  -u\right)  }_{=1}\\
&  \ \ \ \ \ \ \ \ \ \ \left(  \text{since the degree of a product of some
polynomials is the sum of the degrees of these polynomials}\right) \\
&  =\sum_{i=1}^{\ell}\underbrace{\sum_{u=0}^{\left(  p-n_{i}-1\right)  -1}%
1}_{\substack{=\left(  p-n_{i}-1\right)  \cdot1\\=p-n_{i}-1\\=p-1-n_{i}}%
}=\sum_{i=1}^{\ell}\left(  p-1-n_{i}\right)  =\underbrace{\sum_{i=1}^{\ell
}\left(  p-1\right)  }_{=\ell\left(  p-1\right)  }-\sum_{i=1}^{\ell}n_{i}%
=\ell\left(  p-1\right)  -\sum\limits_{i=1}^{\ell}n_{i}<p-1.
\end{align*}
In other words, $f$ is a polynomial of degree $<p-1.$ Besides, obviously,
$f\in\mathbb{Q}\left[  X\right]  ,$ and we have $f\left(  j\right)
\in\mathbb{Z}$ for all $j\in\left\{  0,1,...,p-1\right\}  $ (since
$f\in\mathbb{Z}\left[  X\right]  $). Thus, Theorem 5 yields $\sum
\limits_{j=0}^{p-1}f\left(  j\right)  \equiv0\mod p.$ Thus,%
\begin{align*}
0  &  \equiv\sum\limits_{j=0}^{p-1}f\left(  j\right)  =\sum\limits_{j=0}%
^{p-1}\prod\limits_{i=1}^{\ell}\prod\limits_{u=0}^{\left(  p-n_{i}-1\right)
-1}\left(  \left(  p-n_{i}+j-1\right)  -u\right)  \ \ \ \ \ \ \ \ \ \ \left(
\text{by (2)}\right) \\
&  \equiv\sum\limits_{j=0}^{p-1}\prod\limits_{i=1}^{\ell}\left(  p-n_{i}-1\right)
!\cdot\left(  -1\right)  ^{\ell j}\prod\limits_{i=1}^{\ell}\dbinom{n_{i}}{j}\\
&  \ \ \ \ \ \ \ \ \ \ \left(  \text{since }\prod\limits_{i=1}^{\ell}%
\prod\limits_{u=0}^{\left(  p-n_{i}-1\right)  -1}\left(  \left(
p-n_{i}+j-1\right)  -u\right)  \equiv \prod\limits_{i=1}^{\ell}\left(
p-n_{i}-1\right)  !\cdot\left(  -1\right)  ^{\ell j}\prod\limits_{i=1}^{\ell
}\dbinom{n_{i}}{j}\text{ by (1)}\right) \\
&  =\prod\limits_{i=1}^{\ell}\left(  p-n_{i}-1\right)  !\cdot\sum
\limits_{j=0}^{p-1}\left(  -1\right)  ^{\ell j}\prod\limits_{i=1}^{\ell
}\dbinom{n_{i}}{j}\mod p.
\end{align*}
In other words,%
\begin{equation}
p\mid\prod\limits_{i=1}^{\ell}\left(  p-n_{i}-1\right)  !\cdot\sum
\limits_{j=0}^{p-1}\left(  -1\right)  ^{\ell j}\prod\limits_{i=1}^{\ell
}\dbinom{n_{i}}{j}. \label{3}%
\end{equation}


For every $i\in\left\{  1,2,...,\ell\right\}  ,$ the integer $\left(
p-n_{i}-1\right)  !$ is coprime with $p$ (since $\left(  p-n_{i}-1\right)
!=1\cdot2\cdot...\cdot\left(  p-n_{i}-1\right)  $, and all numbers $1$, $2$,
..., $p-n_{i}-1$ are coprime with $p$ because $p$ is a prime and $p-n_{i}%
-1<p$). Hence, the product $\prod\limits_{i=1}^{\ell}\left(  p-n_{i}-1\right)
!$ is also coprime with $p.$ Thus, (3) yields%
\[
p\mid\sum\limits_{j=0}^{p-1}\left(  -1\right)  ^{\ell j}\prod\limits_{i=1}%
^{\ell}\dbinom{n_{i}}{j}.
\]
Thus, Theorem 1 is proven.

Theorem 1 is a rather general result; we can repeatedly specialize it and
still get substantial assertions. Here is a quite strong particular case of
Theorem 1:

\begin{quote}
\textbf{Theorem 8.} Let $\ell$ be an even positive integer. If $n_{1},$
$n_{2},$ $...,$ $n_{\ell}$ are positive integers and $p$ is a prime such that
$\left(  \ell-1\right)  \left(  p-1\right)  <\sum\limits_{i=1}^{\ell}n_{i}$
and $n_{i}<p$ for every $i\in\left\{  1,2,...,\ell\right\}  $, then $p\mid
\sum\limits_{j=0}^{p-1}\prod\limits_{i=1}^{\ell}\dbinom{n_{i}}{j}$.
\end{quote}

\textit{Proof of Theorem 8.} Theorem 1 yields $p\mid\sum\limits_{j=0}%
^{p-1}\left(  -1\right)  ^{\ell j}\prod\limits_{i=1}^{\ell}\dbinom{n_{i}}{j}.$
But $\ell$ is even, so that $\ell j$ is even for any $j\in\mathbb{Z},$ and
thus%
\[
\sum\limits_{j=0}^{p-1}\underbrace{\left(  -1\right)  ^{\ell j}}%
_{\substack{=1,\text{ since}\\\ell j\text{ is even}}}\prod\limits_{i=1}^{\ell
}\dbinom{n_{i}}{j}=\sum\limits_{j=0}^{p-1}1\prod\limits_{i=1}^{\ell}%
\dbinom{n_{i}}{j}=\sum\limits_{j=0}^{p-1}\prod\limits_{i=1}^{\ell}%
\dbinom{n_{i}}{j}.
\]
Hence, $p\mid\sum\limits_{j=0}^{p-1}\left(  -1\right)  ^{\ell j}%
\prod\limits_{i=1}^{\ell}\dbinom{n_{i}}{j}$ becomes $p\mid\sum\limits_{j=0}%
^{p-1}\prod\limits_{i=1}^{\ell}\dbinom{n_{i}}{j}.$ Therefore, Theorem 8 is proven.

Specializing further, we arrive at the following result (which I proved in
[1], post \#2):

\begin{quote}
\textbf{Theorem 9.} If $n$ and $k$ are positive integers and $p$ is a prime
such that $\dfrac{2k-1}{2k}\left(  p-1\right)  <n<p$, then $p\mid
\sum\limits_{j=0}^{n}\dbinom{n}{j}^{2k}$.
\end{quote}

\textit{Proof of Theorem 9.} Let $\ell=2k.$ Define positive integers $n_{1},$
$n_{2},$ $...,$ $n_{\ell}$ by $n_{i}=n$ for every $i\in\left\{  1,2,...,\ell
\right\}  .$ Then, $n_{i}<p$ for every $i\in\left\{  1,2,...,\ell\right\}  $
(since $n_{i}=n<p$) and%
\[
\left(  \ell-1\right)  \left(  p-1\right)  =\left(  2k-1\right)  \left(
p-1\right)  =2k\cdot\underbrace{\dfrac{2k-1}{2k}\left(  p-1\right)  }%
_{<n}<2kn=\ell n=\sum\limits_{i=1}^{\ell}n=\sum\limits_{i=1}^{\ell}n_{i}.
\]
Hence, Theorem 8 yields $p\mid\sum\limits_{j=0}^{p-1}\prod\limits_{i=1}^{\ell
}\dbinom{n_{i}}{j}.$ But $\prod\limits_{i=1}^{\ell}\dbinom{n_{i}}{j}%
=\prod\limits_{i=1}^{\ell}\dbinom{n}{j}=\dbinom{n}{j}^{\ell}=\dbinom{n}%
{j}^{2k},$ and thus%
\begin{align*}
\sum\limits_{j=0}^{p-1}\prod\limits_{i=1}^{\ell}\dbinom{n_{i}}{j} &
=\sum\limits_{j=0}^{p-1}\dbinom{n}{j}^{2k}=\sum\limits_{j=0}^{n}\dbinom{n}%
{j}^{2k}+\sum\limits_{j=n+1}^{p-1}\underbrace{\dbinom{n}{j}^{2k}%
}_{\substack{=0,\text{ since }n\geq0\text{ and}\\j>n\text{ yield }\dbinom
{n}{j}=0}}\ \ \ \ \ \ \ \ \ \ \left(  \text{since }n<p\right)  \\
&  =\sum\limits_{j=0}^{n}\dbinom{n}{j}^{2k}+\underbrace{\sum\limits_{j=n+1}%
^{p-1}0}_{=0}=\sum\limits_{j=0}^{n}\dbinom{n}{j}^{2k}.
\end{align*}
Therefore, $p\mid\sum\limits_{j=0}^{p-1}\prod\limits_{i=1}^{\ell}\dbinom
{n_{i}}{j}$ becomes $p\mid\sum\limits_{j=0}^{n}\dbinom{n}{j}^{2k}.$ Hence,
Theorem 9 is proven.

The problem quickly follows from Theorem 9 in the particular case $k=2.$

%\end{proof}

\medskip


\textsc{References}

\begin{itemize}
\item[1] \textit{PEN Problem E16}, http://www.mathlinks.ro/viewtopic.php?t=150539

\item[2] \textit{PEN Problem A24}, http://www.mathlinks.ro/viewtopic.php?t=150392
\end{itemize}


\end{document}