17
$\begingroup$

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.

  • 0
    I think that this is trivialized with Lucas's theorem.2013-10-17
  • 0
    Here's a cute proof for the case $p=2$: The sign of $\begin{pmatrix}n&\cdots&2&1\end{pmatrix}$ is, on the one hand, $\lfloor\frac n2\rfloor$: change $1$ with $n$, $2$ with $n-1$, ... On the other hand we can first bring the $1$ in front, step by step; then bring the $2$ to the 2nd place, ... This takes $1+\cdots+n-1=\binom n2$ transpositions, so $\lfloor\frac n2\rfloor\equiv\binom n2\pmod2$. I wonder if there's a way to generalise this to all $p$.2015-12-20

7 Answers 7

17

Hint $\ $ If $\rm\ n\equiv j\ \: (mod\ p)\: $ and $\rm\: \bigl[\frac{n}{p}\bigr] = k, \: $ then pairing factors so that top $\equiv$ bottom $\rm\:(mod\ p)\:$ in the binomial coefficient fractions below makes the result obvious. For example

$${17\choose 7}\ =\ \frac{17}3 \frac{16}2 \frac{15}1 \color{#c00}{\frac{14}7}\frac{13}6\frac{12}5\frac{11}4\,\equiv\, \color{#c00}2\, =\, \left\lfloor\frac{17}7\right\rfloor\pmod 7\qquad\qquad\ $$

since all of the fractions with bottom $\rm\ne p\,$ are $\,\rm\equiv 1\pmod p\,$ by top $\equiv$ bottom, and the red term with the bottom = $\rm \,p = 7\,$ is just $\rm\,\color{#c00}{kp/p = k}.\,$ Generally we have

$$\begin{eqnarray}\rm {n \choose p}\ &=&\rm\ \frac{n\:(n-1)\:\cdots\:(n-p+1)}{p\:(p-1)\:\cdots\: 1} \\ \\ &=&\ \rm \frac{n}{j}\ \frac{n-1}{j-1}\cdots\frac{kp+1}{1}\ \color{#c00}{\frac{kp}p}\ \frac{kp-1}{p-1}\:\cdots\frac{n-p+2}{j+2}\ \frac{n-p+1}{j+1}\end{eqnarray}$$

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 post here.

9

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$.

8

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.

  • 0
    @Moron Thanks, fixed.2010-10-01
  • 0
    That's equivalent to what I wrote.2010-10-01
  • 0
    @Bill Certainly similar, agreed, but I thought it was more snappy to start with my LHS.2010-10-01
  • 0
    @Derek Jennings: You've simply multiplied by (p-1)!, then cancelled it in the end. It's **precisely** the same proof except for that.2010-10-01
  • 0
    @Bill Maybe to you and me, yes. But the equivalence will not be immediate to all students, and for me that is the difference.2010-10-01
  • 7
    @Bill I did not copy your proof and I resent the suggestion.2010-10-01
  • 0
    @Derek Jennings: Ok, perhaps you didn't read my answer before posting yours. But it is clear that your proof is precisely the same as mine except for being scaled by (p-1)!.2010-10-01
  • 0
    @Derek Jennings: I added a remark to my proof to highlight why I prefer to present the proof in this fractional form (vs. your scaled form). Namely, it extends to a vivid elementary arithmetical proof of the integrality of binomial coefficients. Aligning the numerators and denominators (mod p) vividly highlights the innate symmetry of the problem.2010-10-01
  • 1
    @Bill. No problem. I used my approach as I recalled that my LHS was sometimes given as a hint. See for example problem 22 on page 51 of http://www.tar.hu/gergo73/nathanson.pdf . Anyway, I'm not into polemic, so I've just upvoted your answer.2010-10-01
  • 1
    @Derek: Thanks for the link. Initially I misunderstood and thought that you explicitly reformulated my proof because you thought there was some advantage to doing so (this happens occasionally here, usually due to my expository gaps, e.g. see http://math.stackexchange.com/questions/4150). Hopefully with my remark and the link you can see my motivation for presenting it in that form. Apologies for the misunderstanding.2010-10-01
5

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.

  • 0
    REMARK The above generating function approach is mentioned in section 6 of the Granville survey that I mentioned, where he credits its application to Lucas's theorem to Fine (1947). See my other posts here for a sketch of the simple proof (from one of my old sci.math posts).2010-10-02
1

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]$.

  • 6
    Please TeX it so that viewers can understand your answer clearly.2010-10-01
  • 8
    TeX is not a requirement for answers, but one way that users with high extraction rate (question to answer ratio) can contribute is to add TeX to answers that lack it. Questioners can also provide this courtesy to those who answer, and this is a reasonable division of labor. If somebody answers with correct mathematics *and* proper typography, that is purely a bonus.2010-10-01
  • 1
    @T: See, it was just a request, now don't make a big issue out of it.2010-10-01
  • 4
    Requesting, in the form of a command, further volunteering from a helper, is bad form. Anyone troubled by the lack of TeX can simply add it. If you wish to educate the helper about site operations, lead by example rather than demanding corrections.2010-10-01
1

Below is a sketch of a generating-function-based proof of Lucas's theorem (mentioned in passing in a number of other answers). The original problem is just a special linear case.

$\rm\quad\quad\quad\quad\! (1 + X)^{\large 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)^{\large a}\, (1 + X^P)^{\large b} \, (1 + X^{P^{\large 2}})^{\large 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\ \ (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$

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

1

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