Prove that $\binom{k}{p} \equiv \left\lfloor \frac{k}{p} \right\rfloor \pmod p$ for all odd prime number $p$ and $k\ge 3$

Question

I don't really know how to start this exercise. Do I have to use p-adic valuation ?

If it's the case it will give $\nu_p(\binom{k}{p})= \sum \limits_{r=1}^{\infty}\left(\left\lfloor \frac{k}{p^r} \right\rfloor-\left\lfloor \frac{p}{p^r} \right\rfloor -\left\lfloor \frac{k-p}{p^r} \right\rfloor \right)$.

Thanks in advance !

Answer 1

Let $P(x)=x(x-1)\cdots (x-p+1)$. We know that $P(x)=x^p-x+pS(x)$, with $S\in \mathbb{Z}[x]$. Hence we get that $P^{\prime}(x)=px^{p-1}-1+pS^{\prime}(x)$, hence $P^{\prime}(x)=-1\mod{p}$. Now we have $P(x+p)=P(x)+pP^{\prime}(x)\mod{p^2}$, hence $P(x+p)=P(x)-p\mod{p^2}$. Let now be $Q(x)=P(x)/p!$. By the above, we get that for $x\in \mathbb{Z}$, we have $$Q(x+p)=Q(x)-\frac{p}{p!} \mod{p}$$

But $-\frac{p}{p!}=-\frac{1}{(p-1)!}=1\mod{p}$.

Hence we get that for $k\in \mathbb{N}$, we have $$\binom{k+p}{p}=\binom{k}{p}+1\mod{p}$$ And now an induction finish the job.

Answer 2

show that :

• ${k \choose p} = \frac{k}{k-p}{k-1 \choose p} = (1+\frac{p}{k-p}){k-1 \choose p}$ so if $k \not\equiv 0 \bmod p$ then $k-p \ | {k-1 \choose p}$ and ${k \choose p} \equiv {k-1 \choose p} \bmod p$.

• ${ap \choose p} \equiv a \bmod p$, since ${ap \choose p} = a {ap-1 \choose p-1}$ and ${ap-1 \choose p-1} = \prod_{m=1}^{p-1} \frac{ap-m}{m} \equiv \left(\prod_{m=1}^{p-1} (p-m) \right)\left(\prod_{m=1}^{p-1}m\right)^{-1}\equiv 1 \bmod p$

Answer 3

Let us define $jp$, with $j$ positive integer, the greatest multiple of $p$ lower than $k$. Now let us consider the definition of $\binom{k}{p}$ as $$\frac {k (k-1)(k-2)(k-3)...[k-(p-1)]}{p!}$$ The numerator is formed by $p$ consecutive numbers and can be expressed as a product of factors that are $\equiv i \pmod p$, where $i$ assumes all integer values between $0$ (this is the case of $jp$) and $p-1$. Because $1 \cdot 2 \cdot 3....\cdot (p-1) \equiv -1 \pmod p$, the whole numerator can be written as the product of $jp$ and a number $\equiv -1 \pmod p$. As a result, dividing the numerator by $p $ we get a number that is $\equiv -j \pmod p$.

On the other hand, the denominator $p!=p(p-1)!$ is the product of $p$ and a quantity $\equiv -1 \pmod p$, so that dividing it by $p$ we get a number that is $\equiv -1 \pmod p$.

Based on the considerations above, $\binom{k}{p}$ is given by a fraction where, simplifying both numerator and denominator by $p$, we are left with a ratio between a number that is $ \equiv -j \pmod p $ and another one that is $ \equiv -1 \pmod p $. It follows that the result of the fraction is $ \equiv j \pmod p $. Because $j=\lfloor k/p \rfloor $, we finally obtain

$$\binom{k}{p} \equiv \left\lfloor \frac{k}{p} \right\rfloor \pmod p$$

EDIT: since a comment asked to better explain the calculations for the numerator, I added an example below.

Let us set, for example, $k=7$ and $p=3$. So we have $jp=6$ and $j=2$. The binomial coefficient is given by the ratio

$$\frac {7 (7-1)(7-2)}{3!} $$

The numerator is formed by $3$ consecutive numbers and can be expressed as a product of factors that are $\equiv i \pmod 3$, where $i$ assumes all integer values between $0$ and $p-1=2$. In fact, the numerator can be written as $6(6+1)(3+2) $. The product of these factors, not considering $jp=6$, is $$(p-1)! \mod p = (3-1)! \pmod 3=2 \pmod 3$$ (note that we can also consider this last number as $-1 \pmod p $, although it is not necessary). Then, the numerator can be written as the product of $jp=6$ and a number $\equiv 2 \pmod 3$, i.e. it is $\equiv jp (p-1)! \pmod p=\equiv (6 \cdot 2) \pmod 3$.

The denominator is $3! $ and then can be written as the product of $p=3$ and $(p-1)!=2$, where this last number is $\equiv (p-1)! \pmod p = \equiv 2 \pmod 3$.

Then the initial binomial coefficient is the ratio of a quantity $ \equiv (6 \cdot 2) \pmod 3$ and another quantity that is $ \equiv (3 \cdot 2) \pmod 3$. Their ratio is then a number $\equiv 2 \pmod 3$, where the number $2$ simply reflects the initial value of $j$, which in turn is equal to $ \left\lfloor \frac{7}{3} \right\rfloor$. We then conclude that

$$\binom{7}{3} \equiv \left\lfloor \frac{7}{3} \right\rfloor \pmod 3$$

Answer 4

I try to explain better my previous comment on induction's argument:

let's suppose $\binom{k}{p}=n$, so that $np\leq k <np+p$;

it's easy to prove $\binom{k+1}{p}=\frac{k+1}{k+1-p}\binom{k}{p}\equiv 1\left\lfloor \frac{k}{p} \right\rfloor\pmod{p}$, if $k+1\not\equiv 0\pmod p$, and in this case we are done since $k+1<pn+p$ and so $\left\lfloor \frac{k+1}{p} \right\rfloor=\left\lfloor \frac{k}{p} \right\rfloor$.

If otherwise $k+1=p^{r}a,a\not\equiv 0\pmod p$ then $\left\lfloor \frac{k+1}{p} \right\rfloor=p^{r-1}a$ and $\binom{k+1}{p}=\frac{p^{r-1}a}{p^{r-1}a-1}\binom{k}{p}$;

Now if $r\geq 2$ then $\binom{k+1}{p}\equiv 0\pmod p$ and similarly for $\left\lfloor \frac{k+1}{p} \right\rfloor=p^{r-1}a$;

if $r=1$ then $\binom{k+1}{p}=\frac{a}{a-1}\binom{k}{p}$ and its easy to see that $a=n+1$ so that $\binom{k+1}{p}=\frac{n+1}{n}\binom{k}{p}$;

But now if $n\not \equiv 0 \pmod p$ since $n=\left\lfloor \frac{k}{p} \right\rfloor$ and $n+1=\left\lfloor \frac{k+1}{p} \right\rfloor$ we get $\binom{k+1}{p}=\frac{n+1}{n}\binom{k}{p}\equiv \left\lfloor \frac{k+1}{p} \right\rfloor\pmod p$.

Finally if $n=p^{c}m$ with $m\not\equiv 0\pmod p$ then $\left\lfloor \frac{k+1}{p} \right\rfloor\equiv 1\pmod p$ and $\binom{k}{p}=\binom{p^{c+1}m+p-1}{p}=\frac{(p^{c+1}m+p-1)...(p^{c+1}m)}{p(p-1)!}=p^{c}mw$, with $w\equiv 1\pmod p$

and we get the desired equivalence, since $\binom{k+1}{p}=\frac{p^{c}m+1}{p^{c}m}\binom{k}{p}=(p^{c}m+1)w\equiv 1\pmod p$.