Proving ${n \choose p} \equiv \Bigl[\frac{n}{p}\Bigr] \ (\text{mod} \ p)$

Question

This is an exercise from Apostol, which i have been struggling for a while.

Given a prime $p$, how does one show that $${n \choose p} \equiv \biggl[\frac{n}{p}\biggr] \ (\text{mod} \ p)$$ Note that $\Bigl[\frac{n}{p}\Bigr]$ denotes the integral part of $\frac{n}{p}$.

I would also like to know as to how does one try to solve this problem. Well, what we need is to show is whenever one divides ${n \choose p}$ by a prime $p$ the remainder is the integral part of $\frac{n}{p}$.

Now, $${ n \choose p} = \frac{n!}{p! \cdot (n-p)!}$$ Now $n!$ can be written as $$n!= n \cdot (n-1) \cdot (n-2) \cdots (n-p) \cdots 2 \cdot 1$$

But i am really struggling in getting the integral part.

Answer 1

It's easy: $\:$ if $\rm\ n\equiv j\ \: (mod\ p)\:\: $ and $\rm\: \bigl[\frac{n}{p}\bigr] = k\;, \: $ then pairing factors top $\equiv$ bottom $\rm\:(mod\ p)\:$ we have

$\rm\displaystyle\quad\quad {n \choose p}\ =\ \frac{n\:(n-1)\:\cdots\:(n-p+1)}{p\:(p-1)\:\cdots\: 1} $

$\rm\displaystyle\quad\quad \phantom{{n \choose p}}\ =\ \frac{n}{j}\ \frac{n-1}{j-1}\cdots\frac{kp+1}{1}\ \frac{kp}p\ \frac{kp-1}{p-1}\:\cdots\frac{n-p+2}{j+2}\ \frac{n-p+1}{j+1}$

Since $\rm\:n\equiv j\:,\: $ all of the above fractions are $\rm\: \equiv 1\:$ except the middle-shown one $\rm\: (kp)/p = k$

This is a very special case of much more general arithmetical results on binomial coefficients. For example, see Andrew Granville's very interesting survey The Arithmetic Properties of Binomial Coefficients

REMARK The above proof is a special case of a very simple purely arithmetical proof that I devised to show that binomial coefficients are integral. Namely, the same idea of exploiting the innate symmetry by aligning the numerators and denominators $\rm\:(mod\ p)\:$ extends to yield a simple algorithm that, given a binomial coefficient and a prime $\rm p$, rewrites the binomial coefficient as a product of fractions whose denominators are all coprime to $\rm p$. This implies that no prime divides the lowest-terms denominator, so that we may therefore conclude that the binomial coefficient is integral. For an example and further discussion see my prior post.

Answer 2

A useful result in such problems is Lucas's Theorem which states that

If $p$ is a prime and if $a = \sum_{i=0}^{k} a_{i} p^{i}, \ 0 \le a_i < p \ $ i.e. the $a_i$ are digits of $a$ in base $p$ and similarly $b = \sum_{i=0}^{k} b_{i}p^{i}$ (pad with zeroes if required) then

$${a \choose b} = \prod_{i=0}^{k} {a_i \choose b_i} \mod p$$

In our case $n=a$ and $b=p$. Since $b = p$ we have $b_1 = 1$ and rest of the $b_i = 0$.

Thus

$${a \choose p} = {a_1 \choose 1} = a_1 \mod p$$

It is easy to see that $a_1 = [\frac{a}{p}] \mod p$.

Answer 3

Here's another way to look at it. Suppose $n=kp+j,$ for $0 \le j \le p-1.$ Then

$$ (p-1)! {n \choose p} = \frac{n(n-1) \cdots (n-p+1)}{p} = \left( {n-j \over p} \right) \prod_{i=0,i\ne j }^{p-1} (n-i)$$ $$ \equiv k(p-1)! (\textrm{ mod } p). $$ Since the product runs through a complete set of non-zero residues mod p.

Answer 4

The binomial theorem together with the identity $(x+y)^p = x^p + y^p \mod p$ is useful for this type of problem.

Here we want the the $x^p$ coefficient of $(1+x)^{Ap+B} = (1+x^p)^A (1+x)^B = (1 + Ax^p + \dots)(1+X)^B$ where $0 \leq B < p$. This coefficient comes only from multiplication of $(Ax^p)$ by $(1)$. So the result mod p is $A$.

Another solution is to use combinatorics. Partition the set of integers from 1 to $n$ into $A$ blocks of size $p$ and a (perhaps empty) remainder of size $B$, as above. Any subset is either a complete block or it contains a proper nonempty subset of at least one block. Rotating the elements in the first partially filled block organizes the $\binom{n}{p}$ p-subsets into collections of size $p$, plus a "remainder" consisting of complete $p$-blocks, and there are $A$ of the those.

Answer 5

Consider ${n \choose p}$ as $(n)(n-1)...(p+2)(p+1)/(n-p)!$. That can be written as $(n)/(n-p) \cdot (n-1)/(n-p-1) \cdot \cdots \cdot (p+1)/(1)$. Notice that these are all of the form $(x+p)/x$. Thus, terms where $x$ is not divisible by $p$ can be reduced modulo $p$ to $x/x=1$. The rest of the terms are going to be $(p [n/p])/((p [n/p]-1))) \cdot \cdots \cdot (3p)/(2p) \cdot (2p)/(p)$. This product telescopes to $(p [n/p])/p = [n/p]$.

Answer 6

Below is a sketch of the generating-function-based proof of Lucas's theorem - which is mentioned in passing in a number of other posts here. Below we will see that the original problem is just a special linear case.

$\rm\quad\quad\quad\quad\ (1 + X)^{\:a + b P + c P^2} \ \ \ (mod\ P)\quad\quad$ with $\rm\quad\quad 0 \le a,\: b,\: c < P$

$\rm\quad\quad =\ \ \: (1 + X)^a \ (1 + X^P)^b \ (1 + X^{P^2})^c \ \ \ (mod\ P)\quad\quad$

$\rm\quad\quad =\ \ \: (1 + \:\binom{\:a\:}1 \ X\ \ \ \:+ \ \:\binom{\:a\:}2\ X^2\ \ \ +\ \binom{a}3\ X^3 \ \ \ + \:\cdots\: + \ X^{a}\ )$
$\rm\quad\quad\ \ *\ (1 + \binom{b}1 \ X^P \ + \ \binom{b}2\: X^{2P} \ \: +\ \binom{b}3\ X^{3P} \ \:+\: \cdots\: + \ X^{bP}) $ $\rm\quad\quad\ \ * \ (1 +\: \binom{\:c\:}1 \ X^{P^2} + \ \binom{\:c\:}2\ X^{2P^2} +\ \binom{c}3\ X^{3P^2} +\: \cdots\: + \ X^{cP^2}) \quad\ \ (mod\ P)$

$\rm\quad\quad =\ \ \sum\ \binom{a}A \binom{b}B \binom{c}C\ X^{\: A + BP + CP^2}\quad\quad\quad\: (mod\ P)$

Therefore $\rm\quad \ \ \binom{a}A \binom{b}B \binom{c}C = \binom{a + bP + cP^2}{A + BP + CP^2}\ \ \ (mod\ P)$

$\rm\quad\ \Rightarrow\quad\ b\ \ =\ \ \binom{b}1 \quad\ \: =\quad\ \: \binom{a+bp}p\ \ \ $ for $\rm\ \ B = 1,\ A = C = c = 0,\ P = p$

which is the result sought with $\rm\ n = a+bp\ \Rightarrow\ [n/p] = b\:$.

For other proofs see Granville's delightful survey The Arithmetic Properties of Binomial Coefficients

Answer 7

You can see the solution for the case $p=7$ here: http://www.artofproblemsolving.com/Forum/viewtopic.php?p=1775313.